Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography

1.1 Overview of results

• Cutwidth and tree-cutwidth bound the bond-dimension overhead for transforming general tensor networks into MPSs or TTNs, with tree-cutwidth also bounding grouped subsystem dimensions.The transformations use entanglement rerouting; the corresponding decompositions can be computed with graph-parameter-dependent runtimes.Source: §1.1 · p. 5
• Known-topology TTNs admit tomography with sample and runtime complexity polynomial in n, (dχ)^max{2,∆}, 1/ε, and log(1/δ).For constant d and χ, the method is sample- and computationally efficient when the tree has maximum degree O(log n); for paths it recovers known MPS bounds.Source: §1.1 · pp. 5–6
• For general known graphs, black-box tomography uses cutwidth or tree-cutwidth to obtain a structured representation, while direct tomography optimises a learning sequence without choosing an MPS or TTN target.The direct method’s learning complexity is bounded in terms of degree and treewidth, and its exponent can be sharper than the black-box approach on some graph families.Source: §1.1 · pp. 6–7
• For arbitrary input states, agnostic tomography outputs a pure state with fidelity within additive ε of the optimum over states in the specified graph-and-bond-dimension class.Its copy and computational complexity are polynomial in the learning-sequence length, 1/ϑ, 1/min{ε,ϑ}, and log(1/δ), and exponential only in the largest active register.Source: §1.1 · p. 7

1.2 Technical overview

• The tomography methods extend sequential disentangling from paths to trees and general graphs by learning active subsystems whose reduced-state rank is bounded by the separating cut.On trees, degree affects active-subsystem size; for general graphs, learning complexity minimises the largest combined active subsystem and retained register over learning sequences.Source: §1.2 · p. 8

1.3 Related work

• Earlier work established efficient MPS tomography, but the paper presents explicit tomography guarantees for TTNs beyond the MPS case and extends agnostic tomography to trees and general graphs.Prior structure-learning heuristics for tensor-network topologies lacked provable sample or computational guarantees; this work assumes the graph is known.Source: §1.3 · p. 9, §1.4 · p. 10

1.4 Discussion and outlook

• The work leaves open learning tensor-network structure and whether learnability and classical simulability are generally connected; contraction complexity bounds the direct learner’s exponent, but optimal graph-dependent bounds remain unknown.The results assume a known graph, and the paper calls for lower bounds for learning and graph families that separate efficient learning from efficient simulation.Source: §1.4 · p. 10
• For complete graphs, contraction complexity is Θ(n^2), while learning sequences can introduce a dense region at once and avoid the costs of pairwise contractions.Contraction sequences provide a general construction of learning sequences, but may not be optimal because they can pay for many edges between partially assembled parts.Source: §1.4 · p. 11
• The optimal graph-dependent copy complexity of TNS tomography remains open, including whether d^lcd,χ(G) is necessary or adaptive learning can beat it.The discussion also asks how large the gap can be between optimal learning complexity and its contraction-based upper bound.Source: §1.4 · p. 11
• Extending tensor-network testing to general graphs remains open: TTN testers accept target states, but their soundness applies only to a larger class because bags hide internal edges.The discussion asks whether membership testers can achieve two-sided error with copy complexity polynomial in n and χtcw(G), or in n and χcw(G), and raises testing graph parameters and fixed-graph TNS classes.Source: §1.4 · p. 12
• Theorem 1.2 bounds MPS bond-dimension overhead by cutwidth, giving a rigorous basis for interpreting orbital-ordering heuristics as approximate cutwidth minimisers.Parameterised cutwidth algorithms are an alternative to greedy methods on graphs with small cutwidth.Source: §1.4 · p. 12
• For TTN methods, Theorem 1.3 identifies tree-cutwidth as a relevant parameter and approximate tree-cut decompositions as a starting point for choosing tree topologies.Source: §1.4 · p. 12
• Graph parameters also govern representation transformations and learning, suggesting shared decompositions for simulation, compression, and tomography, while truncation remains important in practice.Integrating parameterised algorithms for cutwidth, treewidth, and tree-cutwidth into TN optimisation may improve current methods and suggest practical improvements.Source: §1.4 · pp. 12–13

2.1 Graph theory and graph parameters

• Treewidth is defined by minimum-width tree decompositions, contraction complexity by minimum maximum degree during contractions, and cutwidth and tree-cutwidth by linear and tree-structured cuts.Tree-cutwidth uses adhesion and torso size in a tree-cut decomposition.Source: §2.1 · pp. 14–16

2.2 Tensor network notation

• A weighted tensor network assigns a shared virtual index of range w(e) to each edge, contracts vertex tensors over those indices, and defines state classes by fixed edge dimensions or an upper bond-dimension bound.Removing weight-one edges does not change a fixed representation’s state class; paths, trees, and grids give MPS, TTN, and PEPS classes, respectively.Source: §2.2 · pp. 17–18
• With bond dimension d, a star or clique on at least two vertices can represent every pure n-qudit state by storing its amplitudes at a central vertex.The other vertices pass their physical indices to the centre, while unused clique edges are fixed to one virtual value.Source: §2.2 · p. 18
• Across any bipartition, a tensor-network state’s Schmidt rank is at most the product of the weights on edges crossing the cut.When every edge dimension is at most χ, this gives a bound in terms of the number of crossing edges.Source: §2.2 · p. 19
• The rank of the reduced state on S equals its Schmidt rank, and the second claim follows from w(e) ≤ χ.Source: §2.2 · p. 19

3 Entanglement rerouting for TN representations

• Repeated local rerouting moves virtual indices onto a target path or tree, preserving the state while increasing dimensions on edges that carry the rerouted indices.The single-edge move removes edge {x, y} of dimension q and multiplies the dimensions of {x, z} and {y, z} by q.Source: §3 · p. 20, §3.1 · pp. 20, 22

3.1 Rerouting single edges in a TN

• Rerouting an edge through a third vertex preserves the represented state and multiplies the dimensions of the two carrying edges by the rerouted edge’s dimension.The theorem uses total rerouting; partial rerouting is not needed in the subsequent constructions.Source: §3.1 · pp. 20–21

3.2 Rerouting to an MPS

• Rerouting each edge along a vertex ordering’s path yields an MPS whose bond dimensions are controlled by cutwidth; for an m × m grid, the bound is χ^(m+1).The grid construction retains all m² physical subsystems and their local dimension d, rather than blocking rows into supersites.Source: §3.2 · pp. 23–25

3.3 Rerouting to a TTN

• Rerouting across a tree-cut decomposition gives a TTN whose tree-cutwidth bounds both grouped local dimensions and bond dimensions.Empty bags can be removed while preserving bounds on bag sizes and induced cuts; with width k, the resulting representation has local dimension d^k and bond dimension χ^k.Source: §3.3 · pp. 25–27
• If no decomposition is supplied, one can compute a tree-cut decomposition of width at most 2 Tree-Cut-Width(G).The passage gives running time 2^O(Tree-Cut-Width(G)^2 log Tree-Cut-Width(G)) n^2; the algorithmic statement uses a standard approximation algorithm for tree-cut decompositions.Source: §3.3 · pp. 27–28
• The rerouted TTN has bond dimension at most χ^k, where χ bounds original edge dimensions and k bounds the tree decomposition width.Inter-bag virtual indices are routed along paths in the tree; each rerouting preserves the represented state, and each tree-edge cut has size at most k.Source: §3.3 · p. 28
• Grouping each bag yields at most n physical subsystems, each padded to dimension d^k; the resulting tree degree is relevant when using the representation for tomography.The bag size is at most k, and grouping and padding preserve the represented state under the canonical Hilbert-space identification.Source: §3.3 · p. 28

• Tomography seeks a classical state description within trace-norm error ε and confidence 1−δ; requiring the estimate to remain in the target class makes the task proper tomography.Source: §4 · p. 30
• The analysis aims to minimise the number of input copies while also considering computational efficiency, sometimes separating statistical from computational costs.Source: §4 · p. 30
• The algorithms iteratively learn small reduced states, approximately disentangle part of the system, project it onto |0⟩, and continue using fresh copies after each step.Source: §4 · p. 30
• The section extends tomography from MPS learners to TTNs and arbitrary known graphs, then develops a direct learner and an agnostic extension.Source: §4 · p. 31

• Subnormalised tomography estimates a positive operator of trace at most one produced by a known postselection procedure, rather than only its normalised conditional state.Source: §4.1 · p. 31
• When the success probability is at most ε, the zero operator is an ε-accurate estimate; otherwise, successful postselected copies feed a rank-r tomography routine.Source: §4.1 · pp. 32–33
• When the success probability is unknown but bounded, the procedure uses the bounds; if the upper bound is at most ε, the zero operator suffices.Source: §4.1 · p. 33
• Sub-Tomography takes a postselection operator, subsystem, rank, accuracy, confidence, and success-probability interval; a singleton interval gives the known-probability case.Source: §4.1 · pp. 32, 34
• Normalising a subnormalised estimate introduces an error factor proportional to the inverse success probability, so the algorithms defer normalisation until the final step.Source: §4.1 · p. 35

4.2 MPS tomography via iterated disentangling

• A unitary on S disentangles qudits when the post-unitary state factors as a fixed state on those qudits and a remaining state on their complement.The definition permits the states to be subnormalised.Source: §4.2 · p. 35
• For an MPS, each active block has reduced-state rank at most χ, so a supported unitary can map its relevant support to a subspace with the next qudit fixed to |0⟩.The block is S_i = {i, …, i + κ}, with κ = max{1, ⌈log_d χ⌉}; the procedure repeats from left to right and learns the residual system directly.Source: §4.2 · pp. 35, 40
• The exact rank-bound claim supplies a disentangler, and the TN-cut corollary applies that principle to states represented on a graph.The corollary states that a unitary supported on S can disentangle a specified number of qudits in S; the bound itself is not reproduced in the supplied passage.Source: §4.2 · p. 37

Then the subnormalised reduced state

• Approximate disentangling loses at most 2η in squared branch norm per step, while η = ε²/(128n) suffices for final trace-norm error at most ε.The analysis tracks the subnormalised branch through successive projections before bounding the final reconstruction error.Source: §4.2 · p. 40, Then the subnormalised reduced state · pp. 41, 43
• Theorem 4.12 guarantees trace-norm-ε learning with success probability at least 1−δ and polynomial runtime in n, d^(κ+1), χ, 1/ε, and log(1/δ), assuming efficient tomography and eigendecompositions.Here κ = max{1, ⌈log_d χ⌉}.Source: §4.2 · p. 35, Then the subnormalised reduced state · p. 42
• The sequential learner has linear circuit depth in n; the logarithmic-depth learner of [LCH25] has a different tradeoff, and neither guarantee uniformly dominates the other.The sequential analysis has better dependence on χ and target accuracy, while the [LCH25] learner achieves depth O(log n).Source: Then the subnormalised reduced state · p. 43

4.3 TTN state tomography via iterated disentangling

• Algorithm 4 processes vertices from leaves to root, keeping a residual subsystem at each subtree and acting on each parent together with its children’s residual subsystems.At most n−1 nontrivial disentangling steps are needed.Source: §4.3 · pp. 44, 46
• The rooting bounds the maximum child count b by 1 for n ≤ 2 and by Δ(T)−1 for n ≥ 3.For n ≥ 3, the algorithm roots at a degree-one vertex.Source: §4.3 · pp. 44–46
• Immediately before processing a vertex, its active subsystem has reduced-state rank at most χ because its subtree is separated from the rest by at most one tree edge.Earlier operations are local to either side of that cut, and removing already projected product-state factors cannot increase rank.Source: §4.3 · p. 46
• Choosing η = ε²/(128n) makes the TTN learner’s final trace-norm error at most ε, with each disentangling step losing at most 2η in branch weight.The correctness proof combines the rank bound with the approximate-disentangling guarantee.Source: §4.3 · pp. 46–48
• Theorem 4.17 gives a sample guarantee for trace-norm-ε TTN learning and polynomial runtime in n, d^(1+bκ), χ, 1/ε, and log(1/δ), assuming efficient tomography and eigendecompositions.Here κ = max{1, ⌈log_d χ⌉} and b is the maximum number of children in the chosen rooting.Source: §4.3 · p. 48
• For a path with endpoint rooting, b = 1, and the TTN learner’s copy bound matches the sequential MPS bound.The path traversal from leaves to root plays the role of the MPS path order.Source: §4.3 · p. 49

4.4 TNS tomography of general graphs via entanglement rerouting

• The black-box reductions learn from graph structure and the promise of a representation; they do not require an explicit tensor-network description of the unknown state.The method reroutes to a simpler representation and then applies its corresponding learner.Source: §4.4 · pp. 50, 52
• The MPS reduction uses an ordering π and its cutwidth to obtain a trace-norm learning guarantee; an optimal cutwidth ordering can be computed when none is supplied.The stated preprocessing time is 2^O(cw(G)^2)n.Source: §4.4 · p. 50
• The tree-cut reduction groups qudits into bags and applies the TTN learner, yielding a graph-dependent learning guarantee from the supplied decomposition.The grouped TTN has local dimension at most d^k and bond dimension at most χ^k; a computed approximate decomposition is also covered.Source: §4.4 · p. 51
• When both reductions are available, the paper recommends using the cheaper guarantee; the tree-cut bound retains the chosen decomposition tree’s maximum degree.For trees with at least three vertices, the second term can use (dχ)^k Δ( T̂ ).Source: §4.4 · p. 52

4.5 Direct TNS tomography for graphs

• The direct learner chooses active subsystems from the original graph, avoiding the information loss possible when black-box procedures first replace it by a path or tree.At each step it combines fresh vertices with child residual subsystems and retains a small residual register.Source: §4.5 · p. 53

4.5.1 Learning sequences

• Learning sequences specify assembled subsets, their earlier child subsets, and fresh vertices, organizing which residual subsystems are combined at each tomography step.Their rooted dependency structure and disjoint fresh sets make the assembled subsets laminar, so earlier postselection maps are local to each current cut.Source: §4.5.1 · pp. 53–54

4.5.2 Tomography using a learning sequence

• The rank of the active reduced state at each step is bounded by the cut of its assembled subset in the original graph.Laminarity makes earlier postselections local across that cut, and removing already projected product-state qudits cannot increase rank.Source: §4.5.2 · pp. 57–58
• Algorithm 5 learns a TNS from any learning sequence to trace-norm error ϵ with success probability at least 1 − δ, using sample bounds in terms of sequence parameters.When only a uniform bond-dimension bound χ is known, the theorem substitutes cut-based parameter bounds.Source: §4.5.2 · p. 59

4.5.3 Constructing learning sequences from contraction sequences

• A contraction sequence of complexity C induces a polynomial-time learning sequence of length n−1 whose sets have cut size at most C.Each contraction creates a learning step; the current vertex degree counts edges crossing the corresponding set’s cut.Source: §4.5.3 · pp. 61–62
• The learning-sequence framework applies to arbitrary graphs, including disconnected graphs by combining sequences for their components, while the stated contraction-complexity corollaries assume connected graphs.Isolated vertices can be introduced as fresh systems before the component sequences are combined.Source: §4.5.3 · pp. 61–62
• lcd,χ(G) ≤ min{n, 3 max{1, ⌈C log_d χ⌉}} ≤ 3Δ(G)(tw(G)+1) max{1, ⌈log_d χ⌉}.For connected graphs with n ≥ 2 and contraction complexity C, the learning-complexity bound follows from the contraction-sequence conversion and the degree/treewidth bound on contraction complexity.Source: §4.5.3 · pp. 61–62
• The induced learning sequence gives direct TNS tomography bounds from contraction complexity, and degree and treewidth yield further sample-complexity bounds.For a connected graph with bond dimension bound χ, the learner achieves trace-norm error at most ϵ with success probability at least 1−δ; the stated sample-count formulas are not present in the supplied passages.Source: §4.5.3 · pp. 62–63
• Learning sequences reproduce the path- and tree-based black-box estimates and can improve them with other choices, while the separate TTN theorem gives a sharper tree bound with explicit degree dependence.For a tree, a rooted-subtree learning sequence recovers the residual-subsystem formulation of the TTN learner.Source: §4.5.3 · pp. 63–64

4.6 Agnostic TNS tomography

• The agnostic setting allows an arbitrary density operator and seeks a pure state with overlap nearly matching the best tensor-network state, paralleling closest-product-state and closest-MPS learning [Bak+25] [LCH25].Source: §4.6 · p. 64

4.6.1 Projection estimates for agnostic learning

• The agnostic projection estimate improves the rank dependence from r to √r by applying Cauchy–Schwarz to the positive-semidefinite form induced by ρ.Source: §4.6.1 · p. 64

4.6.2 The agnostic sequence learner

• The agnostic sequence learner retains a larger residual subsystem and maintains a Schmidt-rank bound for each reference TNS through local postselections and removal of fixed product factors.Source: §4.6.2 · pp. 67, 69

4.6.3 Correctness

• Given a learning sequence for G and known ϑ ∈ (0, 1], Theorem 4.45 says Algorithm 6 outputs a pure state; encountered postselections succeed with probability in [ϑ/2, 1].Source: §4.6.3 · pp. 70–71

4.6.4 Applications

• Corollary 4.47 specializes agnostic tomography to a contraction sequence of complexity C for a connected graph when the arbitrary input state has optimum overlap at least ϑ.Source: §4.6.4 · p. 72
• For a tree, the learner processes rooted subtrees from leaves to root; its retained dimension is bounded using Λ_i ≤ 2048 χ n^2 / min{ε, ϑ}^2.Each non-final subtree is separated from its complement by one edge, so r_i ≤ χ; the final set has empty cut and r_L = 1.Source: §4.6.4 · p. 73
• Theorem 4.45 covers arbitrary known graphs, extending agnostic tomography beyond the edgeless-graph and path families to trees and general known graphs.Agnostic TTN tomography follows as the tree case, using the learning sequence of rooted subtrees.Source: §4.6.4 · pp. 73–74
• On paths, the specialization has linear reconstruction depth, whereas [LCH25] has logarithmic depth; neither bound uniformly dominates the other.The passage attributes the tradeoff to the retained dimension, sequential schedule, and full-rank tomography-call rate.Source: §4.6.4 · p. 74
• The projection estimate improves 2r√η to 2√rη over [Bak+25, Lemma B.12], saving a factor of r_i in general-graph retained dimensions.The estimates agree for product states, where r = 1; the weaker estimate would double the exponent of χ in each residual register.Source: §4.6.4 · p. 74