Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography
Abstract
Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state? We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In the TTN case, tree-cutwidth also bounds the local dimension of the grouped subsystems. The proofs are based on entanglement rerouting, a tensor-network analogue of rerouting information in a classical network. Second, we derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth. We obtain these results by extending the disentangling MPS learner of (Cramer et al., 2010), as analysed further in (Bakshi et al., 2025; Lin et al., 2025), to TTNs and to tensor networks on arbitrary known graphs. Finally, we extend the framework beyond the realisable setting. For an arbitrary input state, our agnostic learner outputs a pure state whose fidelity is within additive error ε of the optimum over tensor-network states on the given graph with a given bond dimension, with explicit graph-dependent bounds on sample and computational complexity.
Related
- Sample-Efficient Tomography of a Class of Mixed States with Extensive Entanglement and Magic
- Tight Lower Bounds for State Tomography with Limited Entanglement
- Accessing electronic entanglement via photo-assisted two-electron tomography
- Simplification Rules for Continuous-Time Quantum Walks on Dynamic Graphs
- Compile-Time Simplification of Classically Controlled Operations in Dynamic Circuits
BibTeX
@misc{caro2026parameterised,
title = {{Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography}},
author = {Matthias C. Caro and Natalie McHugh and Sergii Strelchuk},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04165},
eprint = {2609.04165},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04165},
}
RIS
TY - UNPB
TI - Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography
AU - Matthias C. Caro
AU - Natalie McHugh
AU - Sergii Strelchuk
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.04165
UR - https://arxiv.org/abs/2609.04165
AB - Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state? We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In the TTN case, tree-cutwidth also bounds the local dimension of the grouped subsystems. The proofs are based on entanglement rerouting, a tensor-network analogue of rerouting information in a classical network. Second, we derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth. We obtain these results by extending the disentangling MPS learner of (Cramer et al., 2010), as analysed further in (Bakshi et al., 2025; Lin et al., 2025), to TTNs and to tensor networks on arbitrary known graphs. Finally, we extend the framework beyond the realisable setting. For an arbitrary input state, our agnostic learner outputs a pure state whose fidelity is within additive error ε of the optimum over tensor-network states on the given graph with a given bond dimension, with explicit graph-dependent bounds on sample and computational complexity.
ER -