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

Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography Matthias C. Caro∗1 , Natalie McHugh†1 , and Sergii Strelchuk‡2

arXiv:2609.04165v1 [quant-ph] 3 Sep 2026

1

Department of Computer Science, University of Warwick, Coventry, UK 2 Department of Computer Science, University of Oxford, Oxford, UK

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 [MS08]. Its implications for tensornetwork 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 [Cra+10], as analysed further in [Bak+25, LCH25], 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.

∗

matthias.caro@warwick.ac.uk natalie.mchugh@warwick.ac.uk ‡ sergii.strelchuk@cs.ox.ac.uk †

1

Contents 1 Introduction 1.1 Overview of results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Discussion and outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4 7 9 10

2 Definitions and notation 2.1 Graph theory and graph parameters . . . . . . . . . . . . . . . . . . . . 2.2 Tensor network notation . . . . . . . . . . . . . . . . . . . . . . . . . . .

13 13 17

3 Entanglement rerouting for TN representations 3.1 Rerouting single edges in a TN . . . . . . . . . . . . . . . . . . . . . . . 3.2 Rerouting to an MPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Rerouting to a TTN . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20 20 23 25

4 Tensor network state tomography 4.1 Auxiliary lemmas on subnormalised tomography . . . . . . . . . . . . . 4.2 MPS tomography via iterated disentangling . . . . . . . . . . . . . . . . 4.3 TTN state tomography via iterated disentangling . . . . . . . . . . . . . 4.4 TNS tomography of general graphs via entanglement rerouting . . . . . 4.5 Direct TNS tomography for graphs . . . . . . . . . . . . . . . . . . . . . 4.5.1 Learning sequences . . . . . . . . . . . . . . . . . . . . . . . . . . 4.5.2 Tomography using a learning sequence . . . . . . . . . . . . . . . 4.5.3 Constructing learning sequences from contraction sequences . . . 4.6 Agnostic TNS tomography . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6.1 Projection estimates for agnostic learning . . . . . . . . . . . . . 4.6.2 The agnostic sequence learner . . . . . . . . . . . . . . . . . . . . 4.6.3 Correctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30 31 35 44 50 53 53 55 61 64 64 67 69 72

References

76

2

1

Introduction

Tensor networks (TNs) provide a unifying language for quantum computation and quantum information by expressing large linear maps and quantum states as compositions of small tensors wired according to an underlying graph. In this framework, vertices represent individual tensors containing local physical degrees of freedom, while edges correspond to shared indices that are contracted to form the composite object. The topology of this graph encodes the entanglement structure of the physical state, effectively mapping quantum correlations to geometric connectivity. This representation is useful for two closely related reasons. First, a wide range of objects arising in quantum computation, such as quantum circuits, measurement patterns, or decoders for quantum error correcting codes, can be written as TNs whose contraction yields an output amplitude or probability [BSV14, Vid03, SDV06, GE07, PCR24]. Second, a TN representation often exposes which structural aspects of a quantum computation are responsible for classical hardness (e.g., entanglement growth), thereby suggesting tractable subclasses and principled approximation schemes. One of the first results in this direction was obtained by Markov and Shi [MS08], showing that quantum circuits with small underlying graph treewidth can be simulated efficiently by contracting the associated TN. Currently, TN contraction methods are among the most competitive approaches to the classical simulation and benchmarking of quantum computations, and they underpin large simulation efforts for random circuit sampling for quantum advantage [ZSW20, GK21, Ayr+23]. Conversely, tensor-network contraction can encode general quantum computation: additive approximation of a tensor-network contraction is complete for BQP [AL10]. Whereas TN representations with bounded bond dimension and controlled graph parameters admit efficient algorithms for contraction [OGo19], optimization [Sch11], and verification [HM13, SW22], TN representations that require large bond dimension or induce large intermediate tensors lead to exponential computational overhead [SDV06, Orú14]. Therefore, characterizing states that admit tractable TN representations as well as transforming between different TN representations become essential for determining the algorithmic feasibility of problems in quantum computation and quantum information. In addition to efficient contractions and simulability, understanding the learnability of tensor networks is equally important, since it determines when quantum states or processes can be efficiently reconstructed or verified from limited data. The learnability of TN states (TNSs) has been studied primarily under strong structural assumptions. For matrix product states (MPSs) [RÖ07, Wei+09], efficient learning and tomography are possible due to the existence of small separators: cutting a single internal edge separates the system, allowing the global state to be reconstructed from local reduced density matrices with polynomial sample and computational complexity [LLP10, Cra+10, Bak+25, LCH25]. As we show, these ideas extend to tree tensor networks (TTNs) [SDV06] when the tree structure is known, although additional challenges arise in learning the network topology itself [Has+21]. In contrast, for higher-dimensional TNs and for TNs with loops, such as PEPS [VC04], separators grow with system size, leading to both information-theoretic and computational obstacles to efficient learning, and no general efficient learning algorithms are known in this setting [Sch+07, WS23].

3

(a)

(b)

C reroute via C A

message

B

C message A

B

Figure 1: Rerouting classical information. A message from A to B can be sent over a direct link, panel (a), or mediated by C, panel (b). Entanglement rerouting, Theorem 1.1, is the tensor network analogue of this operation.

1.1

Overview of results

In this work, we use parameterised graph theory to study properties of TN representations beyond simulability. We show how to transform a TN representation of a general graph to an MPS or TTN representation with bond dimension bounded in terms of suitable graph parameters. We also give upper bounds on the sample complexity of TNS learning for general graphs in terms of graph parameters. To formulate our results, let G = ([n], E) denote the unweighted tensor-network topology. For a weight function w : E → N, we write Sd (G, w) for the pure n-qudit states admitting a TN representation with virtual dimension w(e) on each edge e. We write Sd (G, χ) for the class in which only a common upper bound χ on the virtual dimensions is specified. Equivalently, [ Sd (G, χ) = Sd (G, w). (1.1) w:E→[χ]

See Section 2.2 for the formal definition. The convention w(f ) = 1 for f ∈ / E does not add f to the edge set. For a fixed weight function w, removing an edge e ∈ E with w(e) = 1 does not change the represented state class. Graph parameters for Sd (G, χ) are evaluated on the given graph G. We use three standard graph parameters: cutwidth (cw), tree-cutwidth (tcw), and treewidth (tw). This overview gives only their intuitive meaning. Precise definitions and the properties used below appear in Section 2.1. Entanglement rerouting. Our first result is a local rerouting rule suggested by classical communication. A direct link from Alice to Bob can be replaced by a route through Charlie when both Alice and Bob are linked to Charlie, without changing the transmitted message. See Figure 1 for an illustration. We prove an analogous operation for virtual indices, which we call entanglement rerouting: Theorem 1.1 (Entanglement rerouting). Let G = ([n], E) be a graph, let w : E → N, and let |ψ⟩ ∈ Sd (G, w). Choose an edge e = {x, y} ∈ E and a vertex z ∈ [n] \ {x, y}. Let E ′ = (E \ {e}) ∪ {{x, z}, {y, z}}, and extend w by the convention w(f ) = 1 for f ∈ / E. Define w′ : E ′ → N by ( w(f )w(e), f ∈ {{x, z}, {y, z}}, w′ (f ) = w(f ), otherwise.

(1.2)

(1.3)

Then, for G′ = ([n], E ′ ), |ψ⟩ ∈ Sd (G′ , w′ ). 4

(1.4)

Since G′ and w′ depend only on G, w, e, and z, the same construction applies to every state in Sd (G, w); thus, Sd (G, w) ⊆ Sd (G′ , w′ ). In particular, if every original edge dimension is at most χ, then the rerouted representation has maximum bond dimension at most χ2 . Theorem 1.1 (proved formally as Theorem 3.1 below) shows that a virtual index can be routed through an intermediate vertex by enlarging the two edges on the new route. Tensor network representations from graph parameters. Repeated applications of entanglement rerouting transform a TN on a general graph into one on a chosen target graph. This may increase the bond dimension. Our next two results bound this increase for paths and trees using cutwidth and tree-cutwidth. Theorem 1.2 (Transforming to MPS (informal)). A tensor network state on n qudits with graph G, physical dimension d, and maximum bond dimension χ can be represented as an MPS on n qudits with physical dimension d and maximum bond dimension χcw(G) . Here, the cutwidth cw(G) is the smallest number c such that the vertices of G can be arranged on a line with at most c edges crossing between any prefix of the arrangement 2 and the rest. An ordering achieving the cutwidth can be computed in time 2O(cw(G) ) n. Theorem 1.3 (Transforming to TTN (informal)). A tensor network state on n qudits with graph G, physical dimension d, and maximum bond dimension χ can be represented as a TTN on at most n grouped subsystems with physical dimension at most d2 tcw(G) and maximum bond dimension at most χ2 tcw(G) . Here, the tree-cutwidth tcw(G) is the analogue of cutwidth in which the vertices are organised into a tree of small groups rather than along a line. A tree-cut decomposition certifying these bounds can be computed in 2 time 2O(tcw(G) log tcw(G)) n2 . Every quantum state admits an MPS or TTN representation at sufficiently large bond dimension. Theorems 1.2 and 1.3, proved as Theorems 3.3 and 3.6, give explicit bounds on the bond dimension required when the starting point is a TN on a general weighted graph. Learning tensor network states. We next use these representation results to study TNS tomography. Throughout, “learning a state” means performing tomography of that state, and we use the two terms interchangeably. Given a TNS on a complicated graph, we may first obtain a representation on a simpler graph and then apply a learner tailored to that representation. We begin by proving efficient tomography of TTNs with known topology. Theorem 1.4 (TTN state tomography (informal)). We can perform tomography of an unknown n-qudit TTN state with bond dimension χ (and with a known tree structure) from  3  n max{2,∆} O (dχ) + log(n/δ) (1.5) ε4 many copies, where ∆ = ∆(T ) is the maximum degree of the underlying tree T , ε is the desired accuracy in trace norm, and 1 − δ is the desired success probability. The runtime of the tomography procedure is polynomial in n, (dχ)max{2,∆} , 1/ε, and log(1/δ).

5

Theorem 1.4, proved as Theorem 4.17, extends efficient MPS tomography [Cra+10, LLP10] to TTNs. For constant d and χ, the algorithm is both sample efficient and computationally efficient for TTNs of maximum degree O(log n). For paths, it recovers the known MPS bounds. This gives two tractable target representations for learning, namely MPSs and TTNs. Combining the representation transformations with the corresponding tomography algorithms yields the following result for general TNSs: Theorem 1.5 (Parameterised complexity of black-box TNS tomography (informal)). We can perform tomography of an unknown TN state on n qudits with (known) graph G, physical dimension d, and maximum bond dimension χ from  3 n o  n 2 2 cw(G) 2 tcw(G) max{2,∆(T̂ )} O (1.6) min d χ , (dχ) + log(n/δ) ε4 many copies, where ∆(T̂ ) is the maximum degree of the decomposition tree obtained from the computed tree-cut decomposition, ε is the desired accuracy in trace norm, and 1 − δ is the desired success probability. The learner runs in time polynomial in n, the quantity inside the minimum, 1/ε, and log(1/δ), after computing an optimal 2 cutwidth ordering in time 2O(cw(G) ) n or an approximate tree-cut decomposition in time 2 2O(tcw(G) log tcw(G)) n2 . The proof of Theorem 1.5, given in Theorems 4.20 and 4.22, first uses cutwidth or tree-cutwidth to obtain a structured representation and then applies the corresponding tomography algorithm. The graph parameters bound the increase in bond dimension and thereby the overall learning complexity. The approach to general-graph TNS tomography in Theorem 1.5 uses the transformations of Theorems 1.2 and 1.3 as black boxes (see also the discussion in Section 1.2 below). The preceding construction is modular, but treating the representation transformations as black boxes can yield weaker bounds. Our next result works directly with cuts of the original graph along a chosen sequence of subsets, and its cost is described by a finer graph parameter. Theorem 1.6 (Parameterised complexity of direct TNS tomography (informal)). We can perform tomography of an unknown TNS on n qudits with (known) graph G, physical dimension d, and maximum bond dimension χ from  3  n lcd,χ (G) O d + log(n/δ) (1.7) ε4 many copies, where ε is the desired accuracy in trace norm, and 1−δ is the desired success probability. Here, lcd,χ (G) is a graph parameter that we call learning complexity. It is the minimum over learning sequences of the largest combined size of an active subsystem and its retained residual register. We show that lcd,χ (G) ≤ min {n, 3 max{1, ⌈cc(G) logd χ⌉}} .

(1.8)

In particular, lcd,χ (G) = O (∆ tw(G) max{1, ⌈logd χ⌉}) when G is connected and has at least two vertices. Here, cc(G) is the contraction complexity of Markov and Shi [MS08], ∆ = ∆(G) is the maximum degree of G, and the treewidth tw(G) measures how well the vertices of G can be organised into a tree of small overlapping bags. The learner runs in time polynomial in n, d lcd,χ (G) , 1/ε, and log(1/δ) once a learning sequence achieving the bound is supplied. A learning sequence attaining the upper bound can be constructed 2 from an optimal contraction sequence in time 2O(cc(G) ) poly(n). 6

The formal version of Theorem 1.6 is Theorem 4.32, while Corollary 4.35 gives the displayed estimate in terms of contraction complexity. The direct approach does not choose an MPS or TTN target in advance. Its exponent depends on the cuts encountered along the chosen learning sequence. The precise learning-sequence bound contains the path and tree schedules used by the black-box algorithms as special cases. Optimising over learning sequences can only improve on these choices. The contraction-complexity estimate is a more general bound obtained from a particular learning sequence and can be less sharp on some graph families. Finally, we extend the direct approach to agnostic tomography. The input may lie outside Sd (G, χ), and the algorithm outputs a pure state whose fidelity is within additive error ϵ of the optimum over that class. The output is represented by the circuit produced by the algorithm and need not lie in Sd (G, χ). That is, it need not admit a representation on G with bond dimension at most χ. Theorem 1.7 (Agnostic TNS tomography (informal)). Let ρ be an arbitrary n-qudit state, and let a graph G, a bond dimension bound χ, and a learning sequence for G be known. Suppose further that OPTG,χ (ρ) :=

sup

⟨ϕ|ρ|ϕ⟩ ≥ ϑ

(1.9)

|ϕ⟩∈Sd (G,χ)

for a known ϑ > 0. There is an algorithm that outputs a pure state |ψ̂⟩ such that ⟨ψ̂|ρ|ψ̂⟩ ≥ OPTG,χ (ρ) − ϵ

(1.10)

with probability at least 1 − δ. Its copy and computational complexity are polynomial in the length of the learning sequence, 1/ϑ, 1/ min{ϵ, ϑ}, and log(1/δ), and exponential only in the largest active register induced by the sequence. The formal statement of Theorem 1.7 and its specialisations to contraction sequences and TTNs are given in Theorem 4.45 and Corollaries 4.47 and 4.48.

1.2

Technical overview

Entanglement rerouting. Suppose that an edge e = {x, y} in a TNS with weighted graph (G, w) is to be rerouted through a vertex z ̸= x, y, as shown in Figure 2. Multiply the dimensions of {x, z} and {y, z} by w(e) and delete e. View the two enlarged indices as pairs (i, j) and (k, ℓ), where j, ℓ ∈ [w(e)]. The new tensor at z retains the old tensor entries when j = ℓ and is zero otherwise. This enforces equality of the two components carrying the rerouted index, so summing over the enlarged indices reproduces the original contraction. Tensor network representations from graph parameters. We describe the MPS construction first. The TTN construction is analogous, with a tree-cut decomposition replacing the linear ordering. Fix an ordering v1 , . . . , vn and take v1 − v2 − · · · − vn as the target path. Every original edge {va , vb } with a < b − 1 is routed along the segment from va to vb . Its weight is multiplied into every path edge on that segment. The final bond dimension on {vi , vi+1 } is the product of the weights of the original edges crossing the corresponding prefix cut. If at most c edges cross any prefix cut and every original

7

(a)

(b)

z

w({x, z})

w({y, z})

x

y

z

w({x, z}) w(e) reroute e via z

x

w({y, z}) w(e) y

w(e) new tensor at z: read each enlarged index as a pair, keep the old value when the two components carrying the e-index agree, and set it to 0 otherwise

Figure 2: Entanglement rerouting. The edge e = {x, y} of a weighted tensor network graph, panel (a), is deleted and its virtual dimension is routed through z by multiplying the weights of the two rerouting edges by w(e), panel (b). The tensor at z is updated so that the overall contraction is unchanged, see Theorem 1.1. weight is at most χ, this bond dimension is at most χc . The maximum prefix-cut size is the cutwidth of the ordering, and minimising over orderings gives cw(G). For the TTN construction, the bags of a tree-cut decomposition become grouped physical subsystems. Each original edge is routed along the unique path between the bags containing its endpoints. Adhesion sizes bound the resulting bond dimensions, while torso sizes bound the dimensions of the grouped physical systems. Learning tree tensor network states. Our starting point is the MPS tomography algorithm of [Cra+10], which proceeds from left to right along the known path, unitarily disentangling one qudit at a time. At each step, a single virtual edge separates the active block from the unprocessed suffix, so its reduced state has rank at most χ. This rank bound allows the disentangling unitary to be learned from few copies. We extend the same strategy to trees by processing vertices from the leaves towards the root. At a vertex u, the active subsystem consists of u and the residual registers retained by its child subtrees. A single tree edge separates this subsystem from the remainder of the tree, so its reduced-state rank is again at most χ. The degree ∆ enters through the active-subsystem size rather than the cut size: there is one fresh qudit and at most ∆ − 1 residual registers, each containing approximately logd χ qudits. Learning general tensor network states. One approach to learning a general TNS is first to use entanglement rerouting to obtain an MPS or TTN representation, then apply the corresponding learner. This construction gives Theorem 1.5. The direct approach behind Theorem 1.6 does not choose a fixed target representation. It processes the graph according to a learning sequence, a rooted schedule in which subsets of vertices are assembled into the full vertex set. At step i, the learner acts on the fresh vertices introduced at that step and the residual registers retained by its children. It then compresses this active subsystem to a residual register of approximately | cutG (Si )| logd χ qudits. The standard rank bound across a TN cut gives reduced-state rank at most χ| cutG (Si )| . The analysis uses only this rank bound and imposes no further structure on either side of the cut. The learning complexity lcd,χ (G) records the largest combined size of an active subsystem and its retained residual register, minimised over learning sequences. Lemma 4.33 shows that every contraction sequence induces a learning sequence, yielding the upper bound in Theorem 1.6.

8

1.3

Related work

Parameterised complexity for tensor networks. Markov and Shi initiated the parameterised analysis of TN contraction by relating classical simulation costs to the treewidth of the associated graph [MS08]. Arad and Landau showed that additive TN evaluation is BQP-complete [AL10]. Together, these results motivate the study of structural restrictions that make TN problems tractable. O’Gorman [OGo19] formulated TN contraction explicitly within parameterised complexity and analysed alternative width parameters. Jakes-Schauer, Anekstein, and Wocjan [JAW19] gave empirical evidence that carving-width is a useful measure of the memory required to contract planar tensor networks. Dudek, Dueñas-Osorio, and Vardi [DDV20] related optimal contraction orders to carving decompositions and used tree-decomposition heuristics to apply TN methods to weighted model counting. Graph parameters have also been used extensively in practical contraction-ordering methods, including benchmarks of treewidth-based strategies [Dum+18] and the exact and approximate contraction methods of Gray and collaborators [GK21, GC24]. Cheng et al. [Che+25] showed that decision-diagram representations can outperform purely treewidth-based contraction on some circuit families, suggesting that parameters beyond treewidth may describe simulability more accurately. Learning simple tensor network states. The earliest results on efficient tomography for structured TN states are due to Landon-Cardinal, Liu, and Poulin [LLP10] and Cramer et al. [Cra+10]. They use local reduced states and local disentangling operations to reconstruct an MPS with constant bond dimension and known ordering from polynomially many copies. Cramer et al. give both a scheme based on local unitaries and a scheme based only on local measurements with more involved classical postprocessing. These results rely on the path topology of the underlying graph: cutting a single virtual edge separates the system into two parts, allowing the global state to be reconstructed from local information. Fewer results are known beyond MPS: For higher-dimensional TNs and TNs with loops, separators grow with system size, and no efficient learning algorithm is known. Existing computational hardness results suggest that none exists in general [Sch+07, WS23]. Recent work has extended these results for MPS. Bakshi et al. [Bak+25] give a proper closest-product-state learner and an improper closest-MPS learner (in Appendix B). Their analysis also gives bounds for propagating subspace errors, of which we use a sharper version in our agnostic analysis (see Lemma 4.40). Lin, Chia, and Hung [LCH25] improve the system-size dependence of MPS tomography from quintic to cubic via a clever parallelisation of the iterative disentangling. Our reduction to MPS learning invokes our sequential learner by default and their parallel learner when circuit depth matters (see Theorem 4.20 and the accompanying remark). In the agnostic setting, where the input state need not lie in the promised class, guarantees were known for the closest product state [Bak+25] and for the closest MPS [Bak+25, LCH25]. Our results extend agnostic tomography to tensor network states on trees and on general graphs (see Remark 4.49). Regarding structure learning, Hashemizadeh et al. [Has+21] propose an adaptive heuristic for learning TN topologies from data, but without provable guarantees on sample or computational complexity. To our knowledge, no prior work exhibited an efficient tomography algorithm with explicit guarantees for TTN states beyond the MPS special case. Also, the dependence of learning complexity on graph parameters of the underlying entanglement graph had not been previously investigated.

9

1.4

Discussion and outlook

Our work develops the interface between graph theory and tensor networks beyond classical simulation. Prior work [MS08, Che+25] showed that parameterised complexity can provide useful structural descriptions of TN simulation. We show that the same perspective also gives a systematic way to analyse the efficiency of TN representations and the sample and computational complexity of learning them. We next describe several open questions within this setting. TNS structure learning. All our TNS learning results assume that the underlying graph is known. This assumption already appears for MPS: the learners of [LLP10, Cra+10] require a known ordering of the subsystems and use that ordering in the iterative-disentangling procedure. Recent work has studied structure learning for classical graphical models, quantum channels, and quantum Hamiltonians [Bre15, Vuf+16, KM17, RF23, BCO26, Bak+24, Zha25, Hu+25, LTW26]. This motivates the corresponding problem for TNSs: given only that an unknown state admits a representation on some graph with tractable structure, recover a suitable graph from copies of the state. Learning versus simulation. Efficient quantum learnability often seems to coincide with efficient classical simulability, such as for TNS classes with tractable structure as discussed in this work [Vid03, MS08, Cra+10], for Clifford circuits [Got98, AG04, Low09] and stabilizer states [AG08, Mon17, Roc18], for Clifford+T circuits with few T -gates [BG16, LC22] and their output states [Gre+25, LOH24], for non-interactingfermion states [Val01, TD02, AG23, Bit+25a], for Gaussian bosonic unitaries [Fan+25] and states [Bit+25c, Mel+25, Bit+25b], and for bosonic or fermionic operations with few non-Gaussian gates [ROK24, DK24a, DK24b, CS24, CS25, Iye25] and their output states [MH25]. While these separate results can be viewed as evidence for a connection between learnability and simulability, whether such a connection can be established in general remains an important open question in quantum learning theory [Yog19] and quantum machine learning [Cer+25]. Our results strongly hint at the potential of parameterised complexity in investigating such a connection for TNSs by considering which graph parameters govern the complexities of learning and simulations of TNs, respectively. Our results relate the two upper bounds through contraction complexity. This parameter determines the cost of classical simulation through the treewidth relation of [MS08] and, by Corollary 4.35, bounds the exponent of our direct learner. It remains open to determine the optimal graph-dependent exponents for both tasks, to prove corresponding lower bounds for learning, and to identify graph families that are efficiently learnable but hard to simulate, or vice versa. Learning and contraction complexity. Lemma 4.33 shows that every contraction sequence induces a learning sequence, and thus lcd,χ (G) ≤ 3 max {1, ⌈cc(G) logd χ⌉} .

(1.11)

A learning sequence consisting of a single step with S1 = F1 = V and I1 = ∅ gives lcd,χ (G) ≤ n.

(1.12)

lcd,χ (G) ≤ min {n, 3 max {1, ⌈cc(G) logd χ⌉}} .

(1.13)

Combining these bounds yields

10

The contraction-complexity bound is not always tight. Consider G = Kn with d = χ = 2. The one-step learning sequence gives lc2,2 (Kn ) ≤ n. Conversely, let i be a leaf of the dependency tree of an arbitrary learning sequence, and write s = |Si |. Then Ii = ∅, and we have Si = Fi . Moreover, | cutKn (Si )| = s(n − s), so this step contributes s + s(n − s) = n + (s − 1)(n − s) ≥ n

(1.14)

to the learning complexity of the sequence. It follows that lc2,2 (Kn ) = n.

(1.15)

On the other hand, cc(Kn ) = Θ(n2 ). Indeed, a current vertex corresponding to a set S ⊆ V has degree |S|(n − |S|). For n ≥ 4, consider the first set of size at least n/3 created by a contraction. Its two constituent sets have size less than n/3, so its size is less than 2n/3. The corresponding current vertex therefore has degree Ω(n2 ), while |S|(n − |S|) ≤ n2 /4 for every S ⊆ V . Hence cc(Kn ) = Θ(n2 ). This separation reflects the different operations allowed by the two notions. A contraction sequence uses pairwise contractions and may pay for many edges between partially assembled parts of a dense region. A learning sequence may introduce the entire region in one step, paying instead for the fresh vertices and the cuts connecting the assembled sets to the rest of the graph. Contraction sequences provide a general construction of learning sequences, but not always an optimal one. Given this, we ask: Question 1.8 (Tightness of the contraction-complexity bound). For which graph families and parameter regimes do we have lcd,χ (G) = Θ (max {1, ⌈cc(G) logd χ⌉})?

(1.16)

More generally, how large can the gap be between optimal learning complexity and the upper bound based on contraction, and which graph properties determine it? The exact relation between learning complexity and the optimal copy complexity beyond the bound in Theorem 1.6 also remains open. Question 1.9 (Optimal graph-dependent complexity of TNS tomography). What is the optimal copy complexity of TNS tomography as a function of the underlying graph? In particular: 1. Is there a family of graphs Gn and states in Sd (Gn , χ) for which every tomography algorithm requires dΩ(lcd,χ (Gn )) copies? 2. Can an adaptive learner, which re-optimises the remaining learning sequence after each step using the information obtained so far, achieve copy complexity below dlcd,χ (G) for some graph family or some inputs? TNS testing. There has been a recent surge in interest in property testing of quantum states (e.g., [OW15b, MW16, BOW19, GNW21, Gre+24, HH25, AD25, BDH25, IL25, Bec+25, Gir+25, FO24, Ali+25, CNS25]), unitaries (e.g., [Low09, CNY]), Hamiltonians (e.g., [ACQ22, LW22, BCO26, KL25, Gao+25, ST25, Blu+25, LS25]), and channels (e.g., [BY25]). In particular, MPS and TTN testers have recently been developed that extend the product testing algorithm of Harrow and Montanaro [HM13, SW22, LL24].

11

Can these testing algorithms be extended to achieve testing for more general TN graph structures, with complexities governed by suitable graph parameters? We note that, while our results (Theorems 1.2 and 1.3) on transforming to MPS or TTN representations are immediately useful to learning, they unfortunately cannot be straightforwardly applied to lift MPS or TTN testers to general graphs, since one cannot in general reduce testing a property P to testing a “super-”property Q with P ⊆ Q. They do, however, transfer in a relaxed form. By Theorem 3.6, any tester for a TTN class accepts every state of Sd (G, χ), with certainty for testers of perfect completeness such as that of [LL24], while its soundness guarantee refers only to the larger class Sd2 tcw(G) (T̂ , χ2 tcw(G) ). The obstruction to full soundness comes from the underlying structure: grouping the vertices in a bag hides the internal edge structure that a tester for Sd (G, χ) would need to verify. Question 1.10 (Testing tensor network structure). Is there a tester for membership in Sd (G, χ), with two-sided error and copy complexity polynomial in n and χtcw(G) , or in n and χcw(G) ? Further questions arise from this parameterised perspective. Can one test graph parameters such as cutwidth, treewidth, or tree-cutwidth of a general-graph TNS under a bond-dimension promise? For a fixed graph, or a fixed graph class, and a fixed bond dimension, what is the complexity of testing whether a state belongs to the corresponding TNS class? Graph-theoretic insights for TN heuristics. Graph-theoretic ideas already appear, often implicitly, in numerical TN heuristics. In DMRG for quantum chemistry [Sch11], for example, the optimisation cost depends strongly on the orbital ordering. Existing heuristics use the Fiedler vector of a mutual-information or exchange matrix [Wou+15], matrix bandwidth [RNW06], or block entropies [LS03] to keep strongly correlated orbitals close. Theorem 1.2 gives a rigorous explanation for this practice: the MPS bond-dimension overhead is bounded by the cutwidth of the graph in the chosen ordering. Existing orbital-ordering heuristics can be interpreted as approximate cutwidth minimisers. Parameterised cutwidth algorithms [TSB05a, TSB05b] provide an alternative to greedy methods on graphs of small cutwidth. A similar opportunity arises for TTN methods such as T3 NS [Gun+18] and hierarchical Tucker decompositions [Gra10]. Tree topologies are currently chosen largely through physical intuition or clustering heuristics. Theorem 1.3 identifies tree-cutwidth as a relevant parameter and approximate tree-cut decompositions [Kim+18] as a natural starting point. Modern TN contraction methods [Dum+18, ZSW20, GK21, Ayr+23, GC24] use heuristic searches for contraction orderings that approximate treewidth or contraction complexity. Our results show that related graph parameters also control representation transformations and learning. This opens the possibility of a unified approach in which a single decomposition, guided by graph parameters, is reused across simulation, compression to a simpler representation (by Theorem 1.1), and tomographic reconstruction. While our exact theorems do not by themselves replace numerical heuristics (we think truncation will remain essential in practice), they identify the structural quantities that those heuristics implicitly optimise. We expect that integrating parameterised algorithms for cutwidth, treewidth,

12

and tree-cutwidth into existing TN optimisation approaches will both improve the analysis of current methods and suggest concrete pathways for further practical improvements.

2

Definitions and notation

2.1

Graph theory and graph parameters

We recall the graph-theoretic notions and parameters used throughout the paper. For more details on graph theory and parameterised complexity, we refer the reader to textbooks such as [Jun08, Cyg+15]. Graph theory  basics. A graph G = (V, E) consists of a finite vertex set V and an edge set E ⊆ {u, v} | u, v ∈ V, u ̸= v . We usually take V = [n], and we write V (G) and E(G) when the graph in question needs to be named explicitly. In figures, we draw each vertex as a circle, or as a filled dot when vertex names are irrelevant, and each edge as a line joining its two endpoints, as in Figure 3 below. The degree of a vertex v ∈ V is deg(v) = {u | {u, v} ∈ E} , and ∆(G) = maxv∈V deg(v) is the maximum degree of G. We suppress the argument and simply write ∆ whenever the graph is clear from context. We will also work with weighted graphs, in which every edge carries a positive integer weight. Definition 2.1. A weighted graph is a pair (G, w), where G = (V, E) is a graph and w : E → [M ] is a positive integer weight function for some M ∈ N. When G is clear from context, we refer simply to the weight function w. For convenience, we extend w to all unordered pairs of vertices by setting w({u, v}) = 1

(2.1)

whenever {u, v} ∈ / E. Edges of weight one may also be present explicitly. We ignore edges of weight 1 for calculating parameters, even when explicitly present, as they are equivalent to non-existent edges for our purposes. Unless stated otherwise, we will work with simple graphs. Parallel edges can be combined as described in Remark 2.16. A path from u to v consists of distinct vertices x1 = u, x2 , . . . , xk = v

(2.2)

and edges {xi , xi+1 } for i ∈ [k − 1]. We denote it by P , or by Pu,v when the endpoints matter. Adding the edge {u, v} to a path on at least three vertices produces a cycle, and a graph is acyclic if it contains no cycle. We allow disconnected graphs and isolated vertices. Statements involving contraction sequences assume connectedness explicitly and apply separately to the nontrivial connected components. A tree is a connected acyclic graph. Equivalently, a tree is a graph in which any two vertices are joined by a unique path, and a tree on k vertices has exactly k − 1 edges. We usually denote trees by T , and we note that every path is a tree. Designating one vertex r ∈ V as the root turns T into a rooted tree. When no root is specified, we choose one as convenient. For a vertex u other than the root, the parent of u is the unique neighbour of u on the path Pu,r , and u is a child of its parent. The root has no parent. We write ch(u) for the set of children of u, and a vertex without children

13

is called a leaf. The depth of a vertex v, denoted depth(v), is the number of edges on the path Pr,v , with depth(r) = 0, and the height of T is h = maxv∈V depth(v) + 1. Finally, the subtree rooted at u, denoted Tu , is the induced subgraph on the vertex set V (Tu ) = {v ∈ V (T ) | u ∈ V (Pv,r )}, that is, on all vertices whose path to the root passes through u. Next, we recall the notion of a cut. Definition 2.2. Let G = (V, E) be a graph and let A, B ⊆ V be disjoint. We define  cutG (A, B) = {x, y} ∈ E | x ∈ A, y ∈ B , cutG (A) = cutG (A, V \ A). (2.3) When the graph is clear from context, we write cut(A, B) and cut(A). Deleting the edge between a vertex v ̸= r and its parent separates V (Tv ) from the rest of the tree, so | cut(V (Tv ))| = 1 for every v ̸= r, while cut(V (Tr )) = ∅. We next introduce treewidth, contraction complexity, cutwidth, and tree-cutwidth, using the graphs in Figure 3 as recurring examples.

star

grid

tree

clique

2-tree

Figure 3: Recurring example graphs. From left to right: a star, a tree, a square grid, a clique, and a 2-tree (in fact, the example graph shown is a 2-path). These families reappear throughout the paper to illustrate graph parameters (Table 1) and tensor network classes.

Treewidth and contraction complexity. Treewidth measures how closely a graph resembles a tree. Its definition uses a tree decomposition, which partitions the vertices into overlapping bags indexed by a tree. We use T for a decomposition tree whose vertices index bags, and T for a tree that is itself used as a tensor-network graph. Definition 2.3 (Tree decomposition [RS86]). A tree decomposition of a graph G = (V, E) is a tree T , together with a mapping t 7→ Bt from vertices t ∈ V (T ) to subsets Bt ⊆ V (G), called bags, such that the following conditions hold: S • t∈V (T ) Bt = V (G), that is, each vertex appears in at least one bag. • For every edge {u, v} ∈ E(G), there is a vertex t ∈ V (T ) such that {u, v} ⊆ Bt , that is, at least one bag contains both endpoints of every edge. • For every u ∈ V (G), the set {t ∈ V (T ) | u ∈ Bt } forms a connected subtree of T . The width of a tree decomposition is maxt∈V (T ) |Bt | − 1. The treewidth of G is the minimum width over all tree decompositions,   tw(G) = min max |Bt | − 1 . (2.4) T

t∈V (T )

14

2

Finding an optimal tree decomposition of G can be done in time 2O(tw ) nO(1) , as shown in [KL23]. Example 2.4. We now illustrate this definition with some simple examples (see Figure 3): 1. The treewidth of a tree with at least two vertices is equal to 1, independently of its size. In particular, the treewidth of the star is 1. 2. The treewidth of the clique Kn is n − 1. 3. The treewidth of a square lattice with n2 vertices is n. Note that such a graph is the entanglement graph of a Projected Entangled Pair State (PEPS). We next introduce contraction complexity, a graph parameter used to analyse the cost of tensor network contraction [MS08]. It is closely related to treewidth. Definition 2.5 (Contraction complexity [MS08, Definition 4.1]). A contraction sequence starts from G and repeatedly chooses a non-loop edge of the current multigraph and identifies its endpoints, until every connected component of G has been contracted to a single vertex. Parallel edges are retained and counted with multiplicity, while loops created by an identification are deleted. The complexity of the sequence is the maximum degree, counted with multiplicity, of any vertex created by a contraction. Thus the degrees of the initial vertices are not included unless a vertex later appears as the result of a contraction. The contraction complexity of G, denoted by cc(G), is the minimum of this quantity over all contraction sequences. If no contraction is required, we set cc(G) = 0. We can bound cc(G) using maximum degree and treewidth. Theorem 2.6 (Bounds on contraction complexity [MS08, Theorem 4.5]). For any graph G with maximum degree ∆ = ∆(G), we have (tw(G) − 1)/2 ≤ cc(G) ≤ ∆(tw(G) + 1) − 1 .

(2.5)

Markov and Shi also prove the exact identity cc(G) = tw(L(G)) and show how to construct a contraction sequence of the same width from a tree decomposition of L(G) [MS08]. Combined with the exact treewidth algorithm of [KL23], this gives an 2 optimal contraction sequence in time 2O(cc(G) ) |E|O(1) . Cutwidth and tree-cutwidth. Cutwidth [Chu85] is the minimum, over linear orderings of the vertices, of the largest edge cut between a prefix and the remaining vertices. Definition 2.7 (Cutwidth). The cutwidth of a bijection π : V → [n] is defined as cw(π) = max | cut({v ∈ V | π(v) ≤ i})|.

(2.6)

i∈[n]

The cutwidth of G = (V, E) is defined as cw(G) = minπ cw(π). We often call π a linear ordering. Finding an optimal ordering can be done in time 2 2O(cw ) n, as shown in [TSB05a, TSB05b].

Tree-cutwidth [Wol15] is a tree-structured analogue of cutwidth. Its definition uses a near partition.

15

Definition 2.8. A near partition of X is a pairwise disjoint family X1 , . . . , Xk ⊆ X whose union is X, allowing for the possibility of Xi to be empty. We next define a tree-cut decomposition of a graph G. Definition 2.9 (Tree-cut decomposition). A tree-cut decomposition of G is a pair (T , X ) where T is a rooted tree, with root r, and X = {Xt ⊆ V (G) : t ∈ V (T )} is a near partition of V (G). The sets Xt are called bags. Tree-cutwidth is now defined using two terms, adhesion and torso size. These in turn are defined with respect to a tree-cut decomposition (T , X ). Definition 2.10 (Adhesion). Let (T , X ) be a tree-cut decomposition of G. Let t ̸= r have parent u, and let e = {u, t}. Deleting e separates T into components Tu and Tt containing u and t, respectively. The adhesion adh(t) is the number of edges of G joining vertices in bags on opposite sides of this separation:   [ [ adh(t) = cut  Xb , Xb  . (2.7) b∈V (Tu )

b∈V (Tt )

For the root r, which has no parent, we set adh(r) = 0. Definition 2.11 (Torso size). Let (T , X ) be a tree-cut decomposition of a graph G, where X = {Xt : t ∈ V (T )}. Fix t ∈ V (T ), and let T1 , . . . , Tℓ be the connected components of T − t. The torso of (T , X ) at t, denoted Ht , is the multigraph obtained from G as follows: For every i ∈ [ℓ], contract the vertex set [ Xs (2.8) s∈V (Ti )

to a single vertex zi , preserving parallel edges and deleting loops. The vertices in Xt are called the core vertices of Ht , and the vertices z1 , . . . , zℓ are called the peripheral vertices of Ht . e t , is obtained from Ht by repeatedly suppressing periphThe 3-centre of Ht , denoted H eral vertices of degree at most 2, while never suppressing core vertices. More precisely, while there exists a peripheral vertex z ∈ / Xt with deg(z) ≤ 2, perform one of the following operations: • If deg(z) = 0 or deg(z) = 1, delete z and all edges incident to z. • If deg(z) = 2, with incident neighbours a and b, delete z and its incident edges and, if a ̸= b, add an edge {a, b}, preserving multiplicity. The torso size of t is e t )|. tor(t) = |V (H

(2.9)

The tree-cutwidth is then defined as follows: Definition 2.12 (Tree-cutwidth). Let (T , X ) be a tree-cut decomposition of G. The width of such a tree-cut decomposition is maxt∈V (T ) {adh(t), tor(t)}. The tree-cutwidth of G, denoted tcw(G), is the minimum width of all tree-cut decompositions of G.

16

A tree-cut decomposition of G of width at most 2 tcw(G) can be computed in time 2 2O(tcw log tcw) n2 , as shown in [Kim+18]. Remark 2.13. The vertices in the central bag Xt are never suppressed when forming e t , so|Xt | ≤ tor(t) for every t ∈ V (T ). In particular, every bag in a width-k the 3-centre H tree-cut decomposition has size at most k. Table 1 summarises the scaling of these parameters on the recurring graph families. Parameter maximum degree treewidth cutwidth tree-cutwidth

Small examples paths, grids, binary trees paths, trees, cycles, k-trees (k constant) paths, cycles, bounded-degree trees paths, trees, cycles

Large examples stars, cliques grids, cliques stars, cliques, grids grids, cliques

Table 1: Scaling of graph parameters on example families. A family is listed as small if the parameter is constant or logarithmic in the number of vertices, and as large otherwise. The families are drawn in Figure 3.

2.2

Tensor network notation

A pure n-qudit state |ψ⟩ ∈ (Cd )⊗n can be described by a tensor (ψi1 ,...,in )di1 ,...,in =1 of Pd complex computational basis amplitudes via |ψ⟩ = i1 ,...,in =1 ψi1 ,...,in |i1 , . . . , in ⟩. As this representation uses a tensor with dn complex numbers, constrained only by the normalisation condition ⟨ψ|ψ⟩ = 1, its size is exponential in the system size n. However, for many physically relevant states, the tensor (ψi1 ,...,in )di1 ,...,in =1 admits a more efficient representation. We will consider tensor networks [Cir+21] as follows. Let G = ([n], E) be a graph and let w : E → N be a positive integer weight function. We say that a tensor (ψi1 ,...,in )di1 ,...,in =1 is compatible with (G, w) if, for every vertex v ∈ [n] with neighbourhood N (v) = {u ∈ [n] | {u, v} ∈ E} = {u1 , . . . , udeg(v) }, there exists a tensor  [v] [v]  j1 ,...,jdeg(v) [v] [v] φ = φiv with indices jk ∈ [w({uk , v})] and iv ∈ [d], such that the following holds. If E = {e1 , . . . , em }, where m = |E|, then for all i1 , . . . , in ∈ [d], w(e1 )

ψi1 ,...,in =

X j[e1 ] =1

w(em )

...

X

[1] [n] φi1 ← j[e1 ] , . . . , j[em ] . . . φin ← j[e1 ] , . . . , j[em ] .

(2.10)

j[em ] =1

Here, we use the notation φ[v] ← j[e1 ] , . . . , j[em ] for the version of φ[v] in which every [v]

index jk is set to j[e] for e = {uk , v}. To express Equation (2.10) in words, we say that our amplitude tensor is obtained by contracting the tensor network: every edge carries one shared summation index of range equal to its weight, every vertex tensor is evaluated with its virtual slots set to the indices of its incident edges, and the amplitude is the sum over all virtual indices. Figure 4 illustrates the contraction for the smallest nontrivial example. A pure n-qudit state |ψ⟩ admits a TN representation on (G, w) if its amplitude tensor in the computational basis is compatible with (G, w). We define the bond dimension of this representation by χ(w) := max ({1} ∪ {w(e) : e ∈ E}) , 17

(2.11)

w(e1 ) 1

w(e2 ) 2

φ[1]

3

weighted graph (G, w)

ψi1 ,i2 ,i3 =

i1

w(e1 )

w(e2 )

X

X

j[e1 ]

φ[2]

j[e2 ]

i2

φ[3] i3

[2]
[3]
[1] φi1 ← j[e1 ] φi2 ← j[e1 ] , j[e2 ] φi3 ← j[e2 ]

j[e1 ] =1 j[e2 ] =1

Figure 4: Contracting a tensor network. Left: a weighted path graph G on three vertices with edges e1 = {1, 2} and e2 = {2, 3}. Right: compatible tensors φ[v] , one per vertex, with a shared virtual index j[e] of range w(e) for each edge e and one physical index iv per vertex. The amplitude ψi1 ,i2 ,i3 is obtained by summing over all virtual indices, as in the displayed instance of Equation (2.10). so an edgeless representation has bond dimension 1. Definition 2.14 (Tensor-network state classes). Let G = ([n], E) be a graph and let w : E → N be a positive integer weight function. We define Sd (G, w) to be the class of pure n-qudit states that admit a TN representation whose virtual index on each edge e has dimension w(e). For χ ∈ N, we define the class of TNSs on G with bond dimension at most χ by [ Sd (G, χ) := Sd (G, w). (2.12) w:E→[χ]

For E = ∅, the union contains the unique empty weight function. For a fixed weight function w, removing an edge e ∈ E with w(e) = 1 does not change the represented state class. When graph parameters are associated with a fixed weighted representation (G, w), we evaluate them after removing all edges of weight one. For the class Sd (G, χ), the graph G remains fixed, since the edge dimensions vary over the weight functions in (2.12). For the class Sd (G, χ), the graph G remains part of the class definition because the edge dimensions are not fixed. The notation Sd (G, w) specifies the individual edge dimensions, while Sd (G, χ) specifies only an upper bound. A state in Sd (G, w) may use a smaller effective dimension on some edges, since unused virtual levels can be padded with zero tensor entries. Example 2.15. For the recurring graphs of Figure 3, if G is a path, then Sd (G, χ) is the class of matrix product states with physical dimension d and bond dimension at most χ. If G is a tree, then Sd (G, χ) is the corresponding class of tree tensor network states. If G is the square grid, then Sd (G, χ) is the class of PEPS with open boundary conditions and bond dimension at most χ. For the clique Kn with n ≥ 2, already χ = d suffices to represent every pure n-qudit state. To see this, choose vertex 1 as a centre. The edge {1, k} carries the physical index of qudit k to the centre, the tensor at vertex k > 1 enforces equality between its physical index and this virtual index, and the tensor at vertex 1 stores the full amplitude tensor ψi1 ,...,in . All clique edges not incident to vertex 1 are fixed to one distinguished virtual value. The resulting contraction equals ψi1 ,...,in and uses edge dimension at most d. The same construction works for a star on n ≥ 2 vertices.

18

Remark 2.16 (Multi-edges and grouping). One could allow parallel virtual edges between the same pair of vertices. Any family of parallel edges can be grouped into a single edge whose weight is the product of their weights, without changing the represented class of states, since a tuple of virtual indices can be encoded as one index of the product range [BC17]. We work with simple weighted graphs throughout. Grouping is used implicitly whenever rerouting creates an edge parallel to an existing one (Section 3) and when parallel edges are counted during contractions (Section 4.5.3). We will repeatedly use the following standard rank bound across a TN cut. Claim 2.17 (Rank bound across a TN cut). Let G = ([n], E) be a graph, let w : E → N, and let |ψ⟩ ∈ Sd (G, w). For every subset S ⊆ [n], we have Y
w(e). (2.13) rank tr[n]\S [|ψ⟩⟨ψ|] ≤ e∈cutG (S)

Here and throughout, the empty product is 1. In particular, if w(e) ≤ χ for every edge, then
rank tr[n]\S [|ψ⟩⟨ψ|] ≤ χ| cutG (S)| . (2.14) Proof. Let cutG (S) = {e1 , . . . , em }.

(2.15)

Contract all tensors whose physical legs lie in S, leaving open the virtual indices corresponding to edges in cutG (S). This gives vectors |Φα1 ,...,αm ⟩S

(2.16)

αj ∈ [w(ej )]

(2.17)

on the Hilbert space of S, where for every j ∈ [m]. Similarly, contracting all tensors whose physical legs lie in [n] \ S gives vectors |Γα1 ,...,αm ⟩[n]\S (2.18) on the complementary Hilbert space. Thus the global state can be written as w(e1 )

|ψ⟩ =

X

w(em )

···

X

|Φα1 ,...,αm ⟩S ⊗ |Γα1 ,...,αm ⟩[n]\S .

(2.19)

The Schmidt rank of |ψ⟩ across the bipartition S | [n] \ S is at most Y w(e).

(2.20)

α1 =1

αm =1

e∈cutG (S)

The rank of the reduced state on S is equal to this Schmidt rank, which proves the first claim. The second claim follows immediately from w(e) ≤ χ.

19

3

Entanglement rerouting for TN representations

We now show how the underlying graph of a TN representation can be modified while preserving the class of states that can be represented. The basic operation is local: an edge {x, y} can be removed and its virtual index can be routed through a third vertex z, at the cost of increasing the virtual dimensions of the two edges {x, z} and {y, z}. We call this operation entanglement rerouting. We first prove the rerouting move for a single edge in Theorem 3.1. The rest of the section then applies this move iteratively. In Section 3.2, we reroute all edges of a general graph onto a path, obtaining an MPS representation whose bond dimension is controlled by cutwidth. In Section 3.3, we reroute all edges onto a tree, obtaining TTN representations with bounds in terms of tree-cutwidth. Thus, the local operation in Theorem 3.1 is the basic mechanism behind all representation transformations in this section. Throughout this section, we use the convention from Section 2.2 that an absent edge is equivalent to an edge of virtual dimension 1. Thus, when we write w({u, v}) = 1 for a pair {u, v} ∈ / E, this simply means that we may add a formal virtual leg of dimension one without changing the represented state.

3.1

Rerouting single edges in a TN

We begin with the basic local move. Suppose a TN representation contains an edge {x, y} of virtual dimension q. If z is any other vertex, enlarge the virtual legs connecting x to z and y to z so that each also carries the value of the virtual index on {x, y}. The tensor at z is then defined to enforce equality between these two components. This removes the direct edge {x, y}, and multiplies the virtual dimensions of {x, z} and {y, z} by q. In this way, the represented physical state is unchanged. The following theorem states this precisely. We call it a total rerouting statement: the entire virtual index on {x, y} is moved through z. We do not need partial rerouting (where only some of the virtual dimension q of the edge {x, y} is rerouted through a third vertex z) in the sequel, so we formulate only the total version. Theorem 3.1 (Total entanglement rerouting: Formal statement of Theorem 1.1). Let G = ([n], E) be a graph, let w : E → N, and extend w to all unordered pairs of distinct vertices by setting w(f ) = 1 whenever f ∈ / E. Let |ψ⟩ ∈ Sd (G, w) and let e = {x, y} ∈ E. Assume that there is a vertex z ∈ [n] \ {x, y}, and set q := w(e).

(3.1)

E ′ := (E \ {{x, y}}) ∪ {{x, z}, {y, z}},

(3.2)

Define and a weight function w′ : E ′ → N by   q w({x, z}), ′ w (f ) = q w({y, z}),   w(f ),

if f = {x, z}, if f = {y, z}, otherwise.

(3.3)

Let G′ = ([n], E ′ ). Then |ψ⟩ ∈ Sd (G′ , w′ ).

20

(3.4)

Moreover, the dimension of the largest edge in the new representation is
χ′ := max {1} ∪ {w′ (f ) : f ∈ E ′ } .

(3.5)

Equivalently, the edge {x, y} can be removed and its virtual index routed through z by multiplying the dimensions of {x, z} and {y, z} by w({x, y}). Proof. Fix a tensor network representation of |ψ⟩ with underlying weighted graph (G, w). Let q = w({x, y}), a = w({x, z}), b = w({y, z}), (3.6) where a = 1 or b = 1 if the corresponding edge is absent from G. We write the tensors i at x, y, z as Airxx ,α,γ , Bryy ,β,γ , Mrizz ,α,β , where α ∈ [a], β ∈ [b], γ ∈ [q]. Here, γ is the virtual index on the edge {x, y}, α is the virtual index on {x, z}, β is the virtual index on {y, z}, and the multi-indices rx , ry , rz collect all other virtual legs incident to x, y, z, respectively. If {x, z} or {y, z} is absent, the corresponding index has dimension 1. e B, e M f. The new edge {x, z} has dimension aq, and we We now define new tensors A, write its index as a pair (α, γx ) ∈ [a] × [q]. Similarly, the new edge {y, z} has dimension bq, and we write its index as a pair (β, γy ) ∈ [b] × [q]. Define ix eix A rx ,(α,γx ) := Arx ,α,γx , iy e iy B ry ,(β,γy ) := Bry ,β,γy , iz fiz M rz ,(α,γx ),(β,γy ) := 1γx =γy Mrz ,α,β .

All other tensors in the network are unchanged. It remains to check that the overall contraction (and thus the state) is unchanged. Contract all tensors other than those at x, y, z, and denote the resulting tensor by Rrirest . The original tensor amplitudes can be written as x ,ry ,rz ψi =

q a X b X X X

i

. Airxx ,α,γ Bryy ,β,γ Mrizz ,α,β Rrirest x ,ry ,rz

rx ,ry ,rz α=1 β=1 γ=1

The amplitudes of the modified network are ψei =

q q X a X b X X X

irest fiz eix e iy A rx ,(α,γx ) Bry ,(β,γy ) Mrz ,(α,γx ),(β,γy ) Rrx ,ry ,rz .

rx ,ry ,rz α=1 γx =1 β=1 γy =1

Substituting the definitions of the modified tensors gives ψei =

q X q a X b X X X

i

Airxx ,α,γx Bryy ,β,γy 1γx =γy Mrizz ,α,β Rrirest x ,ry ,rz

rx ,ry ,rz α=1 γx =1 β=1 γy =1

=

q a X b X X X

i

= ψi , Airxx ,α,γ Bryy ,β,γ Mrizz ,α,β Rrirest x ,ry ,rz

rx ,ry ,rz α=1 β=1 γ=1

The indicator 1γx =γy enforces γx = γy , so ψei = ψi . Thus the modified tensor network represents the same state and has weighted graph (G′ , w′ ). The expression for χ′ follows from the definition of the maximum bond dimension.

21

q edge {u, x} of weight q = w({u, x})

(a) v1

u

v2

v3

x

q reroute {u, x} through v1

(b) u

×q

v1

v2

v3

x

iterate: reroute {v1 , x} through v2 , . . .

(c) u

×q

v1

×q

v2

×q

v3

×q

x

Figure 5: Rerouting along a path. An edge {u, x} can be rerouted through successive intermediate vertices. The example shows three such vertices. Each step removes the current long edge and multiplies the weights of the two carrying edges by q. Although Theorem 3.1 reroutes an edge through a single intermediate vertex, it can be applied repeatedly to reroute an edge along a path, as illustrated in Figure 5. For example, suppose we want to remove an edge {u, x} and route it along the path u − v1 − v2 − · · · − vj − x. We first reroute {u, x} through v1 . This removes {u, x} and creates, or increases the weights of, {u, v1 } and {v1 , x}. We then reroute {v1 , x} through v2 , and continue in this way until the virtual index has been routed along the whole path. Thus, a direct virtual edge can be replaced by a chain of virtual edges, with the original virtual dimension multiplied into every edge of the chosen route. This path-rerouting perspective is what we use in the next subsections. To transform a general TN graph into a target graph, such as a path or a tree, we route each edge that is not present in the target graph along an appropriate path in the target graph. The resulting bond dimension is controlled by the maximum number of original edges whose indices are routed through any one target edge. We use the following direct consequence of Theorem 3.1. Corollary 3.2. Let G = ([n], E) be a graph, let w : E → N, let e = {x, y} ∈ E, and let z ∈ [n] \ {x, y}. Let (G′ , w′ ) be obtained by totally rerouting e through z as in Theorem 3.1. Then Sd (G, w) ⊆ Sd (G′ , w′ ). (3.7) If only the uniform bound w(f ) ≤ χ is known, then every new edge weight is at most χ2 , and hence Sd (G, χ) ⊆ Sd (G′ , χ2 ). (3.8) Since a single rerouting step gives an inclusion of TNS classes, any finite sequence of rerouting steps gives an inclusion from the original TNS class into the TNS class associated with the final weighted graph. In particular, if we can reroute a general graph onto a path, we obtain an MPS representation. If we can reroute it onto a tree, we obtain a TTN representation. The price paid for simplifying the graph is an increase in the virtual dimensions of the edges that carry rerouted indices.

22

3.2

Rerouting to an MPS

We now iteratively apply the single-edge rerouting move from Theorem 3.1 to transform an arbitrary TN graph into a path, and hence into an MPS representation. The only choice involved is a linear ordering of the vertices. Once an ordering π : V → [n] has been fixed, we write vi = π −1 (i) and use the path v1 − v2 − · · · − vn as the target MPS graph. The construction is conceptually simple. If an original edge {va , vb } has a < b − 1, we reroute its virtual index along the path va − va+1 − · · · − vb . This edge contributes a multiplicative factor w({va , vb }) to each path edge {vi , vi+1 } with a ≤ i < i + 1 ≤ b. Thus, the bond dimension on the path edge {vi , vi+1 } is controlled by the number of original edges crossing the cut {v1 , . . . , vi } | {vi+1 , . . . , vn }. We call these cuts the prefix cuts of the ordering. The maximum size of a prefix cut is the cutwidth of the ordering. Minimising this maximum over all orderings gives cw(G). Theorem 3.3 (Rerouting to an MPS). Let G = (V, E) be a graph with V = [n], let w : E → N, and let π : V → [n] be a linear ordering. Write vi = π −1 (i) for i ∈ [n], and let Pnπ be the labelled path on vertices v1 , . . . , vn . Define its edge weights by Y wP ({vi , vi+1 }) = w(e), i ∈ [n − 1], (3.9) e∈cutG ({v1 ,...,vi })

where the empty product is 1. Then Sd (G, w) ⊆ Sd (Pnπ , wP ).

(3.10)

Consequently, if only the uniform bound w(e) ≤ χ is specified, then Sd (G, χ) ⊆ Sd (Pnπ , χCut-Width(π) ).

(3.11)

In particular, for an ordering π ⋆ of minimum cutwidth, ⋆

Sd (G, χ) ⊆ Sd (Pnπ , χCut-Width(G) ).

(3.12)

Moreover, for a fixed ordering π, this transformation can be implemented using at most n−1 X |cutG ({v1 , . . . , vi })| ≤ (n − 1) Cut-Width(π) (3.13) i=1

single-edge rerouting steps. If no ordering is given, we can first compute an optimal 2 cutwidth ordering in time 2O(Cut-Width(G) ) n. Proof. Fix a linear ordering π and write vi = π −1 (i). We first describe the rerouting procedure. Consider an original edge e = {va , vb } ∈ E with a < b. If b = a + 1, then e is already an edge of the target path and no rerouting is needed. If b > a + 1, we reroute e through va+1 . This removes {va , vb } and creates, or increases the weights of, the two edges {va , va+1 } and {va+1 , vb }. We then reroute {va+1 , vb } through va+2 , and continue in this way until the virtual index has been routed along the full path va − va+1 − · · · − vb .

(3.14)

Thus the original edge e contributes its weight w(e) to every path edge {vi , vi+1 } with a ≤ i < b. 23

After all original edges have been processed, every nontrivial virtual edge lies on the target path. Each rerouting preserves the represented state by Theorem 3.1, so every state in Sd (G, w) is represented on (Pnπ , wP ). It remains to bound the final path weights. Fix i ∈ [n − 1]. By the construction above, an original edge e = {va , vb } with a < b contributes to the final edge {vi , vi+1 } if and only if a ≤ i < b. This is precisely the condition that e crosses the cut {v1 , . . . , vi } | {vi+1 , . . . , vn } in the original graph. Hence Y w(e). (3.15) wP ({vi , vi+1 }) = e∈cutG ({v1 ,...,vi })

Equation (3.10) now follows from the expression for wP . Suppose next that |ψ⟩ ∈ Sd (G, χ). By definition, there exists a weight function wψ : E → [χ] such that |ψ⟩ ∈ Sd (G, wψ ). Hence wP ({vi , vi+1 }) ≤ χ| cutG ({v1 ,...,vi })| ≤ χCut-Width(π) .

(3.16) (3.17)

This proves   Sd (G, χ) ⊆ Sd Pnπ , χCut-Width(π) .

(3.18)

Optimising over π gives the bound in terms of Cut-Width(G). Finally, we bound the number of rerouting steps. An original edge e = {va , vb } with a < b requires at most b − a − 1 ≤ b − a rerouting steps. The total number of rerouting steps is at most X

(b − a) =

{va ,vb }∈E, a<b

n−1 X

|cutG ({v1 , . . . , vi })|

(3.19)

≤ (n − 1) Cut-Width(π).

(3.20)

i=1

If π is not supplied, we first compute an optimal cutwidth ordering using the standard 2 algorithm. This takes time 2O(Cut-Width(G) ) n (see Section 2.1), after which the above rerouting procedure is applied. Algorithm 1 describes the corresponding transformation of the weighted graph. Given a tensor network representation, each rerouting step is implemented by the tensor update in Theorem 3.1. The algorithm may group several virtual indices into a single weighted edge whenever they have the same endpoints. This is equivalent to keeping parallel virtual legs and then combining their dimensions by multiplication. Example 3.4 (Square-grid PEPS to MPS rerouting). Let Gm,m be the open-boundary m × m square grid, which has m2 vertices. Consider a PEPS-like tensor network state with underlying graph Gm,m , physical dimension d, and bond dimension χ. Order the vertices row by row as illustrated in Figure 6, i.e., label the vertex in row r and column c by (r, c) and set π(r, c) = (r − 1)m + c.

(3.21)

For every prefix cut in this ordering, at most m vertical grid edges cross the cut, and at most one horizontal grid edge crosses the cut. Hence, Cut-Width(π) ≤ m + 1. 24

(3.22)

Algorithm 1 Reroute to an MPS Input: A graph G = (V, E) with V = [n], an edge-dimension function w : E → N, and optionally a linear ordering π : V → [n]. Output: A weighted labelled path Pnπ and a sequence of rerouting steps transforming G into Pnπ . 1: if π is not provided then 2: Compute an optimal cutwidth ordering π of G. 3: end if 4: Let vi ← π −1 (i) for every i ∈ [n]. 5: G′ ← G. 6: for i = 1 to n − 2 do 7: for j = i + 2 to n do 8: if {vi , vj } ∈ E(G′ ) then 9: Reroute the edge {vi , vj } through vi+1 using Theorem 3.1, and update G′ . 10: end if 11: end for 12: end for 13: Retain every target path edge formally, assigning weight 1 to a trivial virtual leg. 14: return the weighted path Pnπ and the recorded rerouting sequence. By Theorem 3.3, we obtain π m+1 Sd (Gm,m , χ) ⊆ Sd (Pm ). 2, χ

(3.23)

Thus an m × m PEPS with physical dimension d and bond dimension χ can be represented as an MPS on the same m2 qudits, with the same physical dimension d, and with MPS bond dimension at most χm+1 . This should be distinguished from blocking each row into a single supersite. Row blocking would produce an MPS on only m sites, but with physical dimension dm . The rerouting construction above does not block physical systems. It preserves the original m2 local physical subsystems, and the local physical dimension remains d. The change in representation affects only the bond dimension of the MPS.

3.3

Rerouting to a TTN

We next construct a TTN representation. Unlike the MPS construction of Theorem 3.3, this construction groups physical systems according to the bags of a tree-cut decomposition. Let (T , X ) be a tree-cut decomposition of G, whereX = {Xt : t ∈ V (T )}. We group the qudits in each bag Xt into one physical subsystem, whose local dimension is d|Xt | , and use T as the target TTN graph. Each original edge whose endpoints lie in different bags is routed along the unique path between those bags in T . A tree edge then carries the virtual indices of the original edges crossing the associated cut. Tree-cutwidth bounds two quantities. The torso sizes bound the bag sizes and hence the local dimensions of the grouped subsystems. The adhesions bound the number of virtual indices routed through each tree edge and hence the resulting bond dimensions. Since tree-cut decompositions are defined using near partitions, some bags may be empty. Empty bags do not correspond to physical subsystems. Before constructing the

25

(a) 1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

row-major ordering π(r, c) = (r − 1)m + c shaded: prefix {v1 , . . . , v6 } thick: cut({v1 , . . . , v6 }), at most m vertical edges and one horizontal edge

reroute along the ordering (b) 1

2

3

4

5

6

7

···

16

≤ χ m+1

Figure 6: Rerouting a square grid to a path, shown for m = 4. Panel (a): the row-major ordering π(r, c) = (r − 1)m + c of the m × m grid, with the prefix {v1 , . . . , v6 } shaded and its prefix cut highlighted, consisting of m vertical edges and one horizontal edge. Panel (b): the resulting path on m2 vertices. Each MPS bond carries the product of the virtual dimensions of the grid edges crossing the corresponding prefix cut, here at most χm+1 on the bond {v6 , v7 }. TTN, we remove them by contracting them into neighbouring bags, as formalised in the next lemma. Lemma 3.5 (Removing empty bags). Let (T , X ) be a tree-cut decomposition of a graph G of width k, where X = {Xt : t ∈ V (T )} is a near partition of V (G). Then one can obtain a tree T̂ and a partition X̂ = {X̂t : t ∈ V (T̂ )} of V (G) into nonempty bags such that: 1. Every bag X̂t is one of the nonempty bags of the original decomposition. 2. For every edge f ∈ E(T̂ ), the cut of V (G) induced by T̂ − f is equal to the cut induced by some edge of T . 3. Every bag has size at most k, and every cut induced as in 2. has size at most k. Removing empty bags can increase torso sizes and hence the width of the resulting decomposition. The lemma shows, however, that it preserves the original bounds on bag sizes and on cuts induced by decomposition-tree edges. Proof. Starting from (T , X ), repeatedly choose a vertex t ∈ V (T ) with Xt = ∅ and contract a tree edge incident to t. If the chosen edge is {s, t}, the new bag assigned to the contracted vertex is Xs ∪ Xt = Xs . Thus, contracting an empty bag does not change any nonempty bag. We claim that this operation does not increase any relevant adhesion. Indeed, every tree edge that remains after the contraction corresponds to an edge of the previous tree. The two connected components obtained by deleting that edge may have changed by the presence or absence of the empty bag, but the union of the original graph vertices on each side is unchanged because Xt = ∅. Hence the induced cut in G is the same as 26

before. Iterating this argument proves that every edge of the final tree T̂ induces a cut that already appeared as an adhesion cut in the original tree-cut decomposition. After all empty bags have been removed, the remaining bags form a partition of V (G) into nonempty sets. Since the original decomposition has width k, all adhesion cuts have size at most k. Moreover, using the standard convention for tree-cut torsos that the vertices of the central bag are retained in the torso, we have |Xt | ≤ tor(t) ≤ k

(3.24)

for every original nonempty bag Xt . Every final bag also has size at most k. The proof of Theorem 3.1 does not require equal local physical dimensions, so it applies after grouping the systems in each bag. Parallel virtual legs between grouped tensors are combined as in Remark 2.16. Theorem 3.6 (Rerouting to a TTN). Let G = ([n], E) be a graph, let w : E → N, and let |ψ⟩ ∈ Sd (G, w). Let (T , X ) be a tree-cut decomposition of G of width k ≥ 1. Let (T̂ , X̂ ) be the tree-indexed partition obtained from (T , X ) by removing empty bags as in Lemma 3.5. Write m = |V (T̂ )|. Then, after grouping all qudits in the same bag of X̂ into one physical subsystem, |ψ⟩ has a TTN representation on the weighted tree (T̂ , wT̂ ). More explicitly, for every edge f ∈ E(T̂ ), let Af ⊆ [n] be the union of the bags on one side of the cut T̂ − f and define Y wT̂ (f ) = w(e), (3.25) e∈cutG (Af )

where the empty product is 1. Under the canonical identification O O Cd ∼ (Cd )⊗|X̂t | , = v∈[n]

(3.26)

t∈V (T̂ )

and after padding the grouped local Hilbert spaces to dimension dk if needed, we obtain |ψ⟩X̂ ∈ Sdk (T̂ , wT̂ ).

(3.27)

If w(e) ≤ χ for every original edge, then wT̂ (f ) ≤ χk

(3.28)

for every f ∈ E(T̂ ). Hence, after the same grouping and padding, every state in Sd (G, χ) has a representation in Sdk (T̂ , χk ). Moreover, lnm ≤ m ≤ n. (3.29) k In particular, if (T , X ) is an optimal tree-cut decomposition, then one may take k = Tree-Cut-Width(G). If no decomposition is supplied, one may first compute a tree-cut decomposition of 2 width at most 2 Tree-Cut-Width(G) in time 2O(Tree-Cut-Width(G) log Tree-Cut-Width(G)) n2 , and the same statement holds with k = 2 Tree-Cut-Width(G).

27

Proof. Let (T̂ , X̂ ) be obtained from (T , X ) by Lemma 3.5. By that lemma, the bags of X̂ form a partition of [n] into nonempty sets, each of size at most k, and every cut of G induced by an edge of T̂ has size at most k. We first group the physical systems according to the bags. For each t ∈ V (T̂ ), we contract the subnetwork induced by X̂t , including every virtual edge whose endpoints both lie in X̂t . The resulting tensor has one physical index of dimension d|X̂t | and one virtual leg for each original edge leaving the bag. Since |X̂t | ≤ k, we embed every grouped physical space into a space of dimension dk . We combine parallel virtual legs as in Remark 2.16 and then apply Theorem 3.1. Grouping and padding preserve the represented state under the canonical Hilbert-space identification above. It remains to transform the virtual graph between the grouped tensors into the tree T̂ . Consider an original edge e = {u, v} ∈ E. Let s, t ∈ V (T̂ ) be the unique bag labels such that u ∈ X̂s and v ∈ X̂t . If s = t, then e was already absorbed into the local tensor at s. If s ̸= t, let x1 = s, x2 , . . . , xℓ = t (3.30) be the unique path from s to t in T̂ . If ℓ = 2, the edge already lies on T̂ and no rerouting is required. If ℓ ≥ 3, we route the virtual index of e along this path by repeated applications of Theorem 3.1. First reroute the edge from x1 to xℓ through x2 , then reroute the remaining edge from x2 to xℓ through x3 , and continue through the intermediate vertices x2 , . . . , xℓ−1 . Each step preserves the represented state. After performing this procedure for every original inter-bag edge, all nontrivial virtual legs lie on edges of T̂ . The formal tree edges are retained even when their final virtual dimension is one. Fix a tree edge f ∈ E(T̂ ), and let Af be the union of the bags on one side of T̂ − f . An original edge contributes its virtual dimension to f exactly when its endpoints lie on opposite sides of this cut. The final weight of f is Y wT̂ (f ) = w(e). (3.31) e∈cutG (Af )

By Lemma 3.5, the cut cutG (Af ) has size at most k. Since every original edge weight is at most χ, we obtain wT̂ (f ) ≤ χ| cutG (Af )| ≤ χk . (3.32) Thus the resulting TTN has bond dimension at most χk . Finally, since the bags form a partition of [n] into nonempty sets and every bag has size at most k, the number m of bags satisfies lnm ≤ m ≤ n. (3.33) k This proves the required representation. The algorithmic statement follows by using the standard approximation algorithm for tree-cut decompositions, see Section 2.1. Algorithm 2 computes the final tree weights without updating the tensors after each rerouting step. An original edge contributes exactly to the tree edges on the path between the bags containing its endpoints. Parallel virtual legs are combined as in Remark 2.16. Remark 3.7 (Using the representation in tomography). The resulting TTN has m = |V (T̂ )| ≤ n grouped physical subsystems. After padding, each local physical space has dimension dk , and the bond dimension is at most χk . When this representation is used for tomography, the relevant tree degree is ∆(T̂ ). 28

Algorithm 2 Reroute to a TTN Input: A graph G = ([n], E), an edge-dimension function w : E → N, and optionally a tree-cut decomposition (T , X ) of G. Output: A tree T̂ , a partition X̂ = {X̂t : t ∈ V (T̂ )} of [n], edge weights wT̂ on T̂ , and a sequence of rerouting steps realising the corresponding TTN representation. 1: if (T , X ) is not provided then 2: Compute a tree-cut decomposition (T , X ) of width ≤ 2 Tree-Cut-Width(G). 3: end if 4: while there exists t ∈ V (T ) with Xt = ∅ do 5: Choose a neighbour s of t in T . 6: Contract the tree edge {s, t} in T . 7: Assign the bag Xs ∪ Xt to the new contracted vertex. 8: end while 9: Let (T̂ , X̂ ) be the resulting tree-indexed partition. 10: Set wT̂ (f ) ← 1 for every f ∈ E(T̂ ). 11: for all t ∈ V (T̂ ) do 12: Group all physical systems in X̂t into one physical subsystem. 13: Absorb all original edges with both endpoints in X̂t into the local tensor at t. 14: end for 15: for all e = {u, v} ∈ E(G) do 16: Let s, t ∈ V (T̂ ) be the unique vertices such that u ∈ X̂s and v ∈ X̂t . 17: if s ̸= t then 18: Let x1 = s, x2 , . . . , xk = t be the unique path from s to t in T̂ . 19: for j = 1 to k − 1 do 20: wT̂ ({xj , xj+1 }) ← wT̂ ({xj , xj+1 })w(e). 21: end for 22: if k ≥ 3 then 23: Record the rerouting sequence through x2 , . . . , xk−1 using Theorem 3.1. 24: end if 25: end if 26: end for 27: Retain every edge of T̂ formally, including edges of weight one. 28: return (T̂ , X̂ , wT̂ ) and the recorded rerouting sequence.

29

4

Tensor network state tomography

We now turn from representation questions to tomography. Throughout this section, learning a state means producing a classical description ρ̂ of an unknown state ρ such that ∥ρ − ρ̂∥1 is small. We call this quantity the trace norm error. An ϵ-accurate reconstruction satisfies ∥ρ − ρ̂∥1 ≤ ϵ. The corresponding trace distance is D(ρ, ρ̂) := 1 2 ∥ρ − ρ̂∥1 . The tensor network states considered in this paper are pure states. However, the tomography procedures below repeatedly learn reduced states of subsystems, and these reduced states are generally mixed. We now formulate the basic tomography task for arbitrary density operators. Definition 4.1 (State tomography). Let S be a known set of n-qudit states. The state tomography problem for S with accuracy parameter ϵ and confidence parameter δ is the following task: given i.i.d. copies of an unknown state ρ ∈ S, output a classical description of a state ρ̂ such that ∥ρ − ρ̂∥1 ≤ ϵ

(4.1)

with probability at least 1 − δ. If we additionally require ρ̂ ∈ S, then we call the task proper state tomography for S. We aim to minimise the number of copies of ρ used by a tomography procedure. We also aim for computational efficiency, although in several places we separate the statistical and computational aspects of the analysis. When S is the set of all states of rank at most r on a Hilbert space of dimension D, we call the task rank-r state tomography. If D = dm is the dimension of an m-qudit subsystem, then sample-optimal rank-r tomography in trace norm has copy complexity  m  rd + log(1/δ) O , (4.2) ϵ2 and this scaling is optimal up to constants [OW15a, Haa+17, SSW25, PSW25, Pel+25]. Remark 4.2 (Choice of tomography routine). Sample-optimal tomography generally requires collective measurements across many copies [Che+23, CLL24]. When such measurements are unavailable, one may instead use a single-copy tomography procedure, at the cost of a larger copy complexity. Every subsequent call to subnormalised tomography may be replaced by another routine with the same input-output guarantee. The resulting copy bounds are obtained by substituting the copy complexity of the chosen routine into Lemma 4.4. The algorithms below use iterative disentangling. At each stage, they learn a small reduced state, apply a unitary that approximately disentangles part of the system, project that subsystem onto |0⟩, and continue with the successful branch. Each subsequent tomography call uses fresh copies after applying the unitaries and projections learned in the preceding steps. The next subsection develops tomography for the subnormalised states produced by known postselection maps. The map changes from one step to the next but is known once the preceding tomography outcomes have been fixed. The rest of this section is organised as follows. In Section 4.1, we show how ordinary tomography implies tomography for subnormalised postselected states. In Section 4.2, 30

we recall the iterated-disentangling learner for MPS. In Section 4.3, we extend this strategy to TTN states. In Section 4.4, we combine these learners with the rerouting results of Section 3 to obtain black-box tomography for general-graph TNSs. In Section 4.5, we give a direct learner whose cost depends on the cuts of the original graph. In Section 4.6, we extend the direct learner to the agnostic setting.

4.1

Auxiliary lemmas on subnormalised tomography

A subnormalised state is a positive semidefinite operator with trace at most one. The subnormalised states that arise in our algorithms are produced by postselection. We use the following notation to describe them. A known postselection procedure is a two-outcome physical operation whose successful branch is represented by a known linear map K : H → H satisfying K † K ≤ I.

(4.3)

On success, the input state is mapped to ρ 7→ KρK † .

(4.4)

In our applications, K is a composition of known unitaries and computational-basis projections. Let ρ be a state on H = (Cd )⊗n . For a known postselection operation with measured Kraus operator K and for a subsystem L ⊆ [n], we define the subnormalised postselected reduced state i h (4.5) σK,L (ρ) := tr[n]\L KρK † . The success probability of the postselection operation is i h µK (ρ) := tr KρK † .

(4.6)

When µK (ρ) > 0, the corresponding normalised postselected reduced state is ρK,L :=

σK,L (ρ) . µK (ρ)

(4.7)

With this notation established, we can now introduced the task of subnormalised tomography. Definition 4.3 (Subnormalised tomography). Let S be a known set of n-qudit states. Let K describe the success branch of a known postselection procedure, and let L ⊆ [n] be a subsystem. The subnormalised tomography problem for S, K, and L, with accuracy parameter ϵ and confidence parameter δ, is the following task: given i.i.d. copies of an unknown state ρ ∈ S, output a classical description of a subnormalised state σ̂L on L such that ∥σK,L (ρ) − σ̂L ∥1 ≤ ϵ (4.8) with probability at least 1 − δ. The simplest instance of a known postselection procedure is a computational-basis projection, for example ⊗(n−i) K = |0i ⟩⟨0i | ⊗ Id . (4.9) 31

This describes the postselection in the original MPS learner of [Cra+10] after each disentangling unitary has been absorbed into a change of basis. In our formulation the unitaries are kept explicit: after i steps of Algorithm 3, the relevant operator is Ki = Pi Ui · · · P1 U1 , a composition of computational-basis projections with previously learned disentangling unitaries. This is the general form allowed by the definition above. We first consider the case in which the success probability µK (ρ) is known. Lemma 4.4 (Subnormalised tomography with known success probability). Let S be a known set of n-qudit states, let K be the measured Kraus operator of a known postselection operation, and let L ⊆ [n]. Suppose that, for every ρ ∈ S with µK (ρ) > 0, the normalised postselected reduced state ρK,L has rank at most r. Let DL = d|L| ,

(4.10)

and let A be a tomography algorithm for rank-r states on L which, when run with accuracy parameter α ∈ (0, 1] and confidence parameter β ∈ (0, 1), uses mA (r, DL , α, β)

(4.11)

µ = µK (ρ)

(4.12)

copies. Assume that is known. Then there is a subnormalised tomography algorithm for σK,L (ρ) with the following sample complexity: If µ ≤ ϵ, the algorithm uses no samples and outputs the zero operator. If µ > ϵ, it suffices to use    2mA (r, DL , ϵ/µ, δ/2) 8 2 mB = + log (4.13) µ µ δ copies of ρ. In particular, if A is a sample-optimal rank-r tomography procedure, then for µ > ϵ the sample complexity is   µ(rDL + log(1/δ)) log(1/δ) + . (4.14) O ϵ2 µ Proof. If µ ≤ ϵ, then ∥σK,L (ρ)∥1 = tr [σK,L (ρ)] = µ ≤ ϵ,

(4.15)

and we already have an ϵ-accurate estimate. It remains to consider µ > ϵ. Apply the postselection operation independently to m copies of ρ, and let M be the number of successful outcomes. Then M ∼ Binomial(m, µ).

(4.16)

N = mA (r, DL , ϵ/µ, δ/2).

(4.17)

Let The choice of m = mB ensures that   2 mµ ≥ 2N + 8 log . δ

(4.18)

In particular, N ≤ mµ/2. By the multiplicative Chernoff bound, Pr[M < N ] ≤ Pr[M < mµ/2] ≤ exp(−mµ/8) ≤ δ/2. 32

(4.19)

Thus, with probability at least 1 − δ/2, we obtain at least N successful postselected copies. Conditioned on success, the reduced state on L is ρK,L . Therefore, on the event M ≥ N , we run A on N successful postselected copies and obtain an estimate ρ̂K,L satisfying ∥ρK,L − ρ̂K,L ∥1 ≤ ϵ/µ (4.20) with probability at least 1 − δ/2. The algorithm outputs σ̂L = µρ̂K,L .

(4.21)

A union bound over the postselection and tomography events gives an overall success probability of at least 1 − δ, and on this event ∥σK,L (ρ) − σ̂L ∥1 = ∥µρK,L − µρ̂K,L ∥1

(4.22)

= µ ∥ρK,L − ρ̂K,L ∥1

(4.23)

≤ ϵ.

(4.24)

This proves the claim. In the algorithms below, the exact success probability is usually not known. Instead, the analysis provides upper and lower bounds on it. We thus provide a suitable version of subnormalised tomography for when only bounds on the success probability of the postselection are known. Corollary 4.5 (Subnormalised tomography from bounds on success probability). Let S, K, L, r, DL , and A be as in Lemma 4.4. Suppose that the success probability µ = µK (ρ)

(4.25)

0 < µℓ ≤ µ ≤ µu ≤ 1

(4.26)

is unknown, but that known bounds

are available. If µu ≤ ϵ, then the zero operator is an ϵ-accurate estimate. Otherwise, there is a subnormalised tomography algorithm with sample complexity      2mA (r, DL , ϵ/(2µu ), δ/3) 8 3 2 6 mB = + log + 2 log . (4.27) µℓ µℓ δ ϵ δ If A is a sample-optimal rank-r tomography procedure, this becomes  2  µu (rDL + log(1/δ)) log(1/δ) log(1/δ) O + + . µℓ ϵ2 µℓ ϵ2

(4.28)

Proof. If µu ≤ ϵ, then ∥σK,L (ρ)∥1 = µ ≤ µu ≤ ϵ,

(4.29)

so the zero operator suffices as an ϵ-accurate estimate. Assume now that µu > ϵ. Apply the postselection operation independently to m copies of ρ, let M be the number of successful outcomes, and set µ̂ =

M . m

33

(4.30)

Let N = mA (r, DL , ϵ/(2µu ), δ/3).

(4.31)

The first two terms in the definition of mB imply   3 . mµ ≥ mµℓ ≥ 2N + 8 log δ

(4.32)

As in the proof of Lemma 4.4, a Chernoff bound gives Pr[M < N ] ≤ δ/3. The final term in the definition of mB gives, by Hoeffding’s inequality,
Pr [|µ̂ − µ| > ϵ/2] ≤ 2 exp −mϵ2 /2 ≤ δ/3.

(4.33)

(4.34)

On the event M ≥ N , we run A on N successful postselected copies. With probability at least 1 − δ/3, it outputs ρ̂K,L satisfying ∥ρK,L − ρ̂K,L ∥1 ≤

ϵ . 2µu

(4.35)

The algorithm outputs σ̂L = µ̂ρ̂K,L .

(4.36)

By a union bound, all three good events occur with probability at least 1 − δ. On this event, ∥σK,L (ρ) − σ̂L ∥1 = ∥µρK,L − µ̂ρ̂K,L ∥1 ≤ µ ∥ρK,L − ρ̂K,L ∥1 + |µ − µ̂| ∥ρ̂K,L ∥1 ϵ ≤ µu + ϵ/2 2µu = ϵ.

(4.37) (4.38) (4.39) (4.40)

This proves the claim. In the remainder of the paper, we write Sub-Tomography(K, L, r, ϵ, δ, [µℓ , µu ]) for the procedure of Corollary 4.5 run with postselection operator K, subsystem L, rank parameter r, accuracy ϵ, confidence δ, and success probability bounds µℓ ≤ µK (ρ) ≤ µu . This is the calling convention used by all algorithms below. The singleton interval [µ, µ] recovers the setting of Lemma 4.4, and the rank parameter may be set to the full dimension DL when no rank promise is available, as in Algorithm 6. Renormalisation. The procedure returns a subnormalised estimate. At several points we require the corresponding normalised state. The following estimate bounds the error introduced by normalisation. Let σ be a subnormalised state with tr(σ) = µ ≥ µℓ > 0,

(4.41)

and suppose that σ̂ is a positive semidefinite estimate satisfying ∥σ − σ̂∥1 ≤ η < µℓ . 34

(4.42)

Let µ̂ = tr(σ̂).

(4.43)

2η σ σ̂ ≤ − . µ µ̂ 1 µℓ

(4.44)

Then |µ̂ − µ| ≤ η, µ̂ > 0, and

Indeed, ∥σ − σ̂∥1 1 σ σ̂ 1 − ≤ + − tr(σ̂) µ µ̂ 1 µ µ µ̂ ∥σ − σ̂∥1 |µ − µ̂| = + µ µ 2η ≤ . µℓ

(4.45) (4.46) (4.47)

Normalising a subnormalised estimate introduces an error factor proportional to the inverse success probability. The algorithms below work with subnormalised branches and normalise only in the final step.

4.2

MPS tomography via iterated disentangling

We now recall the iterated-disentangling approach to MPS tomography, originally due to [Cra+10]. We present the original, sequential version because it is the conceptual starting point for the TTN and general TNS algorithms we develop later. The more recent parallel learner of [LCH25] achieves logarithmic circuit depth and improves the systemsize dependence of the original analysis of [Cra+10]. We compare the two guarantees at the end of this subsection. Let S ⊆ [n], and let A ⊆ S. For a positive semidefinite operator ρ on n qudits, we say that a unitary U supported on S disentangles the subsystem A for ρ if U ρU † = |0|A| ⟩⟨0|A| |A ⊗ σ[n]\A

(4.48)

for some positive semidefinite operator σ[n]\A . We allow ρ and σ[n]\A to be subnormalised. When |A| = 1, we also say that U disentangles the corresponding qudit. For an MPS on the path 1 − 2 − · · · − n, the basic observation is that, after the first i − 1 qudits have been disentangled and projected onto |0⟩, the next active block Si = {i, i + 1, . . . , i + κ},

κ = max{1, ⌈logd χ⌉},

(4.49)

has reduced-state rank at most χ. Since dκ ≥ χ, a unitary supported on Si can map the relevant χ-dimensional support into the subspace in which qudit i is fixed to |0⟩. Repeating this from left to right reduces the state to a state on the final κ qudits, which can then be learned directly. The following algorithm is written making use of the subnormalised tomography primitive from Section 4.1. At each stage, the cumulative postselection operation is described by a known linear map Ki . Operationally, a call to Sub-Tomography with input Ki means that we apply the known postselection procedure described by Ki to fresh copies of the original state and keep the successful branch (as in Lemma 4.4 and Corollary 4.5). The required unitary exists because dim(Wi ) ≤ χ ≤ dκ , while the target subspace has dimension dκ . Choose an orthonormal basis of Wi , map it isometrically into the target subspace, and extend the isometry to a unitary on Si . 35

Algorithm 3 LearnMPS Input: Path Pn , bond dimension χ, physical dimension d, copies of |ψ⟩ ∈ Sd (Pn , χ), accuracy parameter ϵ, confidence parameter δ. Output: A classical description of a pure state |ψ̂⟩. 1: κ ← max{1, ⌈logd χ⌉}. 2: m ← max{n − κ, 0}. 3: η ← ϵ2 /(128n). 4: K0 ← I and µ e0 ← 1. 5: for i = 1 to m do 6: Si ← {i, i + 1, . . . , i + κ}. ▷ Active block. 7: σ̂i ← Sub-Tomography (Ki−1 , Si , χ, η, δ/(2n), [e µi−1 , 1]) . 8: Let Wi be the span of the eigenvectors associated with the χ largest eigenvalues of σ̂i . ei supported on Si such that 9: Compute a unitary U  ⊗κ ei Wi ⊆ |0⟩i ⊗ Cd U . (4.50) 10: 11:

ei ⊗ I[n]\S . Let Ui = U i Let Pi = |0⟩⟨0|i ⊗ I[n]\{i} .

Ki ← Pi Ui Ki−1 . 13: µ ei ← µ ei−1 − 2η. 14: end for 15: R ← {m + 1, m + 2, . . . , n}. 16: τ̂ ← Sub-Tomography (Km , R, 1, η, δ/(2n), [e µm , 1]) . 17: Let |φ̂⟩ be a top eigenvector of τ̂ . 18: return † |ψ̂⟩ = U1† U2† · · · Um (|0m ⟩ ⊗ |φ̂⟩) .

(4.51)

12:

36

(4.52)

We next establish the results used to analyse Algorithm 3. The first gives an exact disentangler from a rank bound. Claim 4.6 (Exact disentangling from a rank bound). Let ρ = |ψ⟩⟨ψ| be a pure n-qudit state, let S ⊆ [n], and suppose that rank(ρS ) = R.

(4.53)

0 ≤ a ≤ |S| − ⌈logd R⌉,

(4.54)

Then, for every integer there exists a unitary supported on S that disentangles some chosen a qudits in S for ρ. In particular, one can disentangle max{|S| − ⌈logd R⌉, 0}

(4.55)

qudits in S. Proof. Let a ≤ |S| − ⌈logd R⌉. After relabelling the qudits in S, we may assume that the a qudits to be disentangled are the first a qudits of S. Since d|S|−a ≥ R,

(4.56)

there is an isometry from the support of ρS into the subspace  ⊗(|S|−a) . |0a ⟩ ⊗ Cd

(4.57)

Extend this isometry to a unitary U on the Hilbert space of the qudits in S. Taking a Schmidt decomposition of |ψ⟩ across the bipartition S | [n] \ S, the Schmidt vectors on S span the support of ρS . Hence, applying U maps all Schmidt vectors on S into the subspace in which the first a qudits are fixed to |0a ⟩. Therefore, (U ⊗ I[n]\S )|ψ⟩ = |0a ⟩ ⊗ |ν⟩

(4.58)

for some state |ν⟩ on the remaining n − a qudits. This proves the claim. Combining this claim with the rank bound from Claim 2.17 gives the following disentangling corollary for tensor network states. Corollary 4.7 (Disentangling from a TN cut). Let G = ([n], E), let w : E → N, let |ψ⟩ ∈ Sd (G, w), and let S ⊆ [n]. Then one can construct a unitary supported on S that disentangles at least       X  (4.59) log w(e) , 0 max |S| −  d      e∈cutG (S) qudits in S for |ψ⟩. In particular, for every state in Sd (G, χ), one can disentangle at least max {|S| − ⌈| cutG (S)| logd χ⌉ , 0} (4.60) qudits in S.

37

Proof. By Claim 2.17, Y

rank(ρS ) ≤

w(e).

(4.61)

e∈cutG (S)

Therefore, 

 X

⌈logd rank(ρS )⌉ ≤  logd w(e)  . e∈cut(S) 

(4.62)

The result follows from Claim 4.6. The next lemma is the perturbation statement that we use for approximate disentanglers. It is a subnormalised version of the top-eigenspace argument used in [LCH25, Lemma B.1]. Lemma 4.8 (Approximate top-eigenspace overlap). Let τ and τ̂ be positive semidefinite operators on a finite-dimensional Hilbert space. Suppose that rank(τ ) ≤ r

and

∥τ − τ̂ ∥1 ≤ η.

(4.63)

Let W be the span of the eigenvectors associated with the r largest eigenvalues of τ̂ , and let ΠW be the orthogonal projector onto W . Then tr [(I − ΠW )τ ] ≤ 2η.

(4.64)

Proof. If r is at least the Hilbert-space dimension, the claim is trivial. Otherwise, let τ̂(r) be the truncation of τ̂ to the eigenspaces associated with its r largest eigenvalues, i.e., τ̂(r) = ΠW τ̂ ΠW . (4.65) Since ΠW is a spectral projector of τ̂ , we have τ̂ − τ̂(r) = (I − ΠW )τ̂ (I − ΠW ) ⪰ 0 and hence tr[(I − ΠW )τ̂ ] = ∥τ̂ − τ̂(r) ∥1 . By the Eckart–Young–Mirsky theorem, τ̂(r) is a best rank-r approximation to τ̂ in trace norm. Since τ has rank at most r, ∥τ̂ − τ̂(r) ∥1 ≤ ∥τ̂ − τ ∥1 ≤ η.

(4.66)

tr [(I − ΠW )τ ] = tr [(I − ΠW )(τ − τ̂ )] + tr [(I − ΠW )τ̂ ]

(4.67)

≤ ∥τ − τ̂ ∥1 + ∥τ̂ − τ̂(r) ∥1

(4.68)

≤ 2η.

(4.69)

Now,

This proves the lemma. The next corollary gives the form of Lemma 4.8 used in the iterative algorithms. It shows that a unitary which maps the top r-dimensional eigenspace of the estimate into the subspace where the state on subsystem A is fixed to |0|A| ⟩ can be followed by postselection with a loss of at most 2η in squared branch norm. Corollary 4.9 (Approximate disentangling of a subnormalised branch). Let |Ψ⟩ ∈ HS ⊗ HB be a subnormalised pure state, and write µ = ⟨Ψ|Ψ⟩,

τS = trB [|Ψ⟩⟨Ψ|] .

38

(4.70)

Assume that rank(τS ) ≤ r,

µ > 0,

(4.71)

and let τ̂S ≥ 0 satisfy ∥τS − τ̂S ∥1 ≤ η.

(4.72)

Let W be the span of the eigenvectors associated with the r largest eigenvalues of τ̂S . Let A ⊆ S satisfy d|S|−|A| ≥ r, (4.73) and let U be a unitary on HS such that  ⊗(|S|−|A|) U W ⊆ |0|A| ⟩A ⊗ Cd .

(4.74)

PA = |0|A| ⟩⟨0|A| |A ⊗ IS\A .

(4.75)

∥(PA U ⊗ IB )|Ψ⟩∥2 ≥ µ − 2η.

(4.76)

|Ψ⟩ |ψ⟩ = √ , µ

(4.77)

p = ∥(PA U ⊗ IB )|ψ⟩∥2 .

(4.78)

Define Then For the normalised state

let Then

2η . µ

(4.79)

(PA U ⊗ IB )|ψ⟩ √ p

(4.80)

p≥1− If η < µ/2, the normalised postselected state |ψ ′ ⟩ = satisfies

r 2η (U ⊗ IB )|ψ⟩⟨ψ|(U ⊗ IB ) − |ψ ⟩⟨ψ | ≤ 2 . µ 1 †

′

′

(4.81)

Proof. Let ΠW be the orthogonal projector onto W , and define Π = U † PA U.

(4.82)

Since U W lies in the range of PA , the range of Π contains W . It follows that I − Π ≤ I − ΠW .

(4.83)

∥(PA U ⊗ IB )|Ψ⟩∥2 = tr [ΠτS ]

(4.84)

Using Lemma 4.8, we obtain

= µ − tr [(I − Π)τS ]

(4.85)

≥ µ − tr [(I − ΠW )τS ]

(4.86)

≥ µ − 2η.

(4.87)

Dividing by µ gives the lower bound on p. 39

If η < µ/2, then p > 0. Since PA is an orthogonal projector, ⟨ψ ′ |(U ⊗ IB )|ψ⟩

2

= p.

(4.88)

The trace norm identity for pure states now gives (U ⊗ IB )|ψ⟩⟨ψ|(U † ⊗ IB ) − |ψ ′ ⟩⟨ψ ′ |

p =2 1−p 1 r 2η ≤2 . µ

(4.89) (4.90)

Equation (4.76) is the estimate used in the iterative learners. Each disentangling step removes at most 2η from the squared norm of the current branch. We also need the following rank bound for the active blocks in the MPS learner. Lemma 4.10 (Rank bound for active MPS blocks). Let |ψ⟩ ∈ Sd (Pn , χ), and let κ = max{1, ⌈logd χ⌉}. Consider the first i − 1 iterations of Algorithm 3, and let Ki−1 = Pi−1 Ui−1 · · · P1 U1

(4.91)

be the resulting cumulative postselection operation. Let Si = {i, i + 1, . . . , i + κ}.

(4.92)

Then the subnormalised reduced state h i † σi = tr[n]\Si Ki−1 |ψ⟩⟨ψ|Ki−1

(4.93)

has rank at most χ. Proof. All unitaries and projections appearing in Ki−1 are supported on qudits contained in the prefix {1, 2, . . . , i + κ − 1}. (4.94) If i + κ < n, then Ki−1 acts only on the left side of the MPS cut between qudits i + κ and i + κ + 1. The Schmidt rank across this cut is at most χ for the original MPS, and local operations on one side of a bipartition cannot increase Schmidt rank. After the first i − 1 successful projections, the qudits 1, . . . , i − 1 are fixed to |0i−1 ⟩. Projecting onto a fixed product state and then discarding those projected qudits cannot increase the rank of the reduced state on the remaining active block. Hence the reduced state on Si has rank at most χ. If i + κ = n, then Si contains every qudit that has not already been projected. Conditioned on the previous successful projections, the global postselected state is pure and factors as |0i−1 ⟩ ⊗ |φ⟩Si . Thus the reduced state on Si has rank 1 ≤ χ. We first prove correctness conditioned on every call to subnormalised tomography succeeding. Proposition 4.11 (Correctness of the sequential MPS learner). Assume that every call to Sub-Tomography in Algorithm 3 succeeds with trace-norm error at most η. If η≤

1 , 8n

40

(4.95)

then the state |ψ̂⟩ output by Algorithm 3 satisfies |ψ⟩⟨ψ| − |ψ̂⟩⟨ψ̂|

1

p √ ≤ 2 2nη + 4 η.

(4.96)

In particular, the choice ϵ2 128n is sufficient to make the final trace norm error at most ϵ for every ϵ ∈ (0, 1]. η=

(4.97)

Proof. Let µi = ∥Ki |ψ⟩∥2

(4.98)

be the true cumulative success probability after the first i disentangling steps. We prove by induction that µi ≥ 1 − 2iη. (4.99) The case i = 0 is immediate because the initial state is normalised. Assume the claim holds for i − 1. By Lemma 4.10, the active reduced state at step i has rank at most χ. Since the tomography call has trace norm error at most η, Equation (4.76) shows that the next projection decreases the squared branch norm by at most 2η. Hence µi ≥ µi−1 − 2η ≥ 1 − 2iη.

(4.100)

1 µm ≥ 1 − 2mη ≥ , 2

(4.101)

This completes the induction. Thus, for m ≤ n,

where we used η ≤ 1/8n. Let U≤m = Um Um−1 · · · U1

and

P≤m = Pm Pm−1 · · · P1 .

(4.102)

Since Uj is supported on {j, j + 1, . . . , j + κ}, it does not act on qudit i when j > i. Hence Pi commutes with every subsequent unitary Uj , and Km = P≤m U≤m .

(4.103)

Define the exact postselected reconstruction state as † |ψ ⋆ ⟩ = U≤m

P≤m U≤m |ψ⟩ . √ µm

(4.104)

Then |⟨ψ|ψ ⋆ ⟩|2 = µm ,

(4.105)

p p p ∥|ψ⟩⟨ψ| − |ψ ⋆ ⟩⟨ψ ⋆ |∥1 = 2 1 − µm ≤ 2 2mη ≤ 2 2nη.

(4.106)

and hence It remains to account for the final tomography step on the residual system. Since the branch after m projections lies in the subspace where the first m qudits are equal to |0m ⟩, there exists a pure residual state |φ⟩ on R such that P≤m U≤m |ψ⟩ = |0m ⟩ ⊗ |φ⟩. √ µm

41

(4.107)

The ideal subnormalised residual state is τ = µm |φ⟩⟨φ|.

(4.108)

The final tomography call outputs τ̂ with ∥τ − τ̂ ∥1 ≤ η.

(4.109)

Let |φ̂⟩ be a top eigenvector of τ̂ . By the variational characterisation of the largest eigenvalue, ⟨φ̂|τ |φ̂⟩ ≥ ⟨φ̂|τ̂ |φ̂⟩ − η

(4.110)

≥ ⟨φ|τ̂ |φ⟩ − η

(4.111)

≥ ⟨φ|τ |φ⟩ − 2η

(4.112)

= µm − 2η.

(4.113)

Since τ = µm |φ⟩⟨φ|, this gives 2η ≥ 1 − 4η. µm

(4.114)

√ ∥|φ⟩⟨φ| − |φ̂⟩⟨φ̂|∥1 ≤ 4 η.

(4.115)

|⟨φ̂|φ⟩|2 ≥ 1 − Thus

† Tensoring with a fixed state and applying the unitary U≤m both preserve trace norm, † so the same bound holds between |ψ ⋆ ⟩ = U≤m (|0m ⟩ ⊗ |φ⟩) and the actual output |ψ̂⟩ = † U≤m (|0m ⟩ ⊗ |φ̂⟩). The triangle inequality gives

|ψ⟩⟨ψ| − |ψ̂⟩⟨ψ̂|

1

p √ ≤ 2 2nη + 4 η.

(4.116)

The choice η = ϵ2 /(128n) makes the right-hand side at most ϵ. The sample complexity follows from this correctness guarantee. Theorem 4.12 (Sample complexity of the sequential MPS learner). Suppose that Algorithm 3 uses the sample-optimal rank-constrained subnormalised tomography primitive from Section 4.1. Then an unknown state |ψ⟩ ∈ Sd (Pn , χ) can be learned to trace norm error at most ϵ with success probability at least 1 − δ using  3 
n κ+1 O χd + log(n/δ) (4.117) ϵ4 copies, where κ = max{1, ⌈logd χ⌉}. In particular, since dκ ≤ dχ, this is at most  3 
n 2 2 O d χ + log(n/δ) . ϵ4

(4.118)

(4.119)

The runtime is polynomial in n, dκ+1 , χ, 1/ϵ, and log(1/δ), assuming the tomography primitive and the eigendecompositions on the active blocks are implemented in polynomial time in the respective dimension. 42

Proof. There are at most n calls to Sub-Tomography: at most n − 1 local calls and one final residual call. Allocate failure probability δ/(2n) to each call. By Proposition 4.11, it suffices to take ϵ2 η= . (4.120) 128n The lower bounds µ ei used in the algorithm satisfy 1 (4.121) 2 for this choice of η. Hence the dependence on success probability in Corollary 4.5 contributes only a constant factor. For each local disentangling step, the active subsystem has dimension dκ+1 and rank at most χ. One local call uses   κ+1 χd + log(n/δ) (4.122) O η2 µ ei ≥

copies. Multiplying by at most n such calls and substituting the value of η gives  3 
n κ+1 O (4.123) χd + log(n/δ) . ϵ4 The final residual tomography call is lower order, since the residual system has dimension dκ ≤ dκ+1 . The runtime statement follows from the fact that all classical linear-algebra operations are performed on matrices of dimension at most dκ+1 . Sections 4.3 and 4.5 generalise this procedure to trees and to arbitrary graphs, and the path case is recovered in Remarks 4.18 and 4.39. Remark 4.13 (Comparison with the logarithmic-depth learner of [LCH25]). The guarantee of [LCH25] is stated in infidelity. Writing α for their target infidelity, their algorithm outputs |ψ̂⟩ with |⟨ψ|ψ̂⟩|2 ≥ 1 − α using  6 4 3  χ d n log(n/δ) NLCH (α, δ) = O (4.124) max{1, logd χ}3 α4 copies and a reconstruction circuit of depth O(log n). For pure states, q |ψ⟩⟨ψ| − |ψ̂⟩⟨ψ̂| = 2 1 − |⟨ψ|ψ̂⟩|2 . 1

(4.125)

Thus trace norm error ϵ corresponds to α = ϵ2 /4, under which their bound reads O(χ6 d4 n3 log(n/δ)/(max{1, logd χ}3 ϵ8 )). Conversely, Theorem 4.12 in the infidelity con
3 vention reads O αn2 (χdκ+1 + log(n/δ)) . The two bounds give different tradeoffs, and neither uniformly dominates the other. The sequential bound has better dependence on χ and on the target accuracy for two reasons. First, every block learned by the sequential procedure is separated from the unprocessed suffix by one virtual edge, so its rank is at most χ and one call costs at most χdκ+1 ≤ d2 χ2 . A middle block in the parallel schedule can be separated by two virtual edges and can have rank as large as χ2 . Second, the sequential analysis tracks the subnormalised branch directly. Each step removes at most O(η) probability mass, the losses add, and the square root relating this loss to trace norm error is taken only at the end. The sequential reconstruction has depth linear in n, while the learner of [LCH25] has depth O(log n). We use the latter in Theorem 4.20 when logarithmic depth is required. 43

4.3

TTN state tomography via iterated disentangling

We extend the sequential disentangling method from MPSs to TTNs of known topology. Algorithm 4 processes the rooted tree from leaves to root. After processing a subtree, it retains only a small residual subsystem. The parent step acts on the parent vertex and the residual subsystems of its children. For a rooted tree T , let ch(u) denote the set of children of u, and let Tu be the subtree rooted at u, with vertex set Vu . For S ⊆ [n], write HS = (Cd )⊗|S| ,

|0⟩S = |0⟩⊗|S| .

(4.126)

Throughout this subsection we set κ = max{1, ⌈logd χ⌉}.

(4.127)

Thus dκ ≥ χ. The residual subsystem left after processing Tu will be denoted by Ru ⊆ Vu , and it will always satisfy |Ru | ≤ κ. The required unitary exists because dim(Wu ) ≤ χ ≤ dκ = dim(HRu ). Choose an orthonormal basis of Wu , map it isometrically into |0|Qu | ⟩Qu ⊗ HRu , and extend the isometry to a unitary on HSu . We next establish the invariants used to analyse Algorithm 4. Lemma 4.14 (Residual-subsystem invariant). During Algorithm 4, after a vertex u has been processed, the following hold: 1. Ru ⊆ Vu and |Ru | ≤ κ. 2. Every qudit in Vu \Ru has been projected onto |0⟩ in the current postselected branch. 3. The sets Qu introduced at different nontrivial disentangling steps are pairwise disjoint. Moreover, there are at most n − 1 nontrivial disentangling steps. Consequently, if b = max | ch(u)|

(4.131)

u∈V (T )

denotes the maximum number of children in the chosen rooting, then every subsystem Su on which Algorithm 4 performs tomography satisfies |Su | ≤ 1 + bκ.

(4.132)

Finally, with the rooting used in the algorithm, b ≤ 1 for n ≤ 2, and b ≤ ∆(T ) − 1 for n ≥ 3. Proof. We prove the first two claims by induction over the traversal from leaves to root. If u has no children, then Su = {u}. Since κ ≥ 1, the algorithm sets Ru = {u} and no projection is applied, so the claims are immediate. Now suppose that all children of u have already been processed. By the induction hypothesis, for each child v, every qudit in Vv \ Rv has already been projected onto |0⟩. Hence, immediately before processing u, the qudits in Vu that have not yet been projected onto |0⟩ are [ Su = {u} ∪ Rv . (4.133) v∈ch(u)

44

Algorithm 4 LearnTTN Input: Tree T on vertex set [n], bond dimension χ, physical dimension d ≥ 2, copies of |ψ⟩ ∈ Sd (T, χ), accuracy parameter ϵ ∈ (0, 1], confidence parameter δ ∈ (0, 1). Output: A classical description of a pure state |ψ̂⟩. 1: If n = 1, root T at its only vertex. If n ≥ 2, choose a vertex r with degT (r) = 1 and root T at r. 2: Let h be the height of the rooted tree. 3: κ ← max{1, ⌈logd χ⌉} and η ← ϵ2 /(128n). 4: K0 ← I, µ e0 ← 1, Q0 ← ∅, and c ← 0. 5: for i = h − 1 down to 0 do 6: for all u ∈ V (TS ) with depth(u) = i do 7: Su ← {u} ∪ v∈ch(u) Rv . 8: if |Su | ≤ κ then 9: Ru ← Su . 10: else 11: Choose Ru ⊆ Su such that u ∈ Ru and |Ru | = κ. 12: Qu ← Su \ Ru . 13: σ̂u ← Sub-Tomography (Kc , Su , χ, η, δ/(2n), [e µc , 1]) . 14: Let Wu be the span of the eigenvectors associated with the χ largest eigenvalues of σ̂u . eu supported on Su such that 15: Compute a unitary U eu Wu ⊆ |0|Qu | ⟩Qu ⊗ HRu . U 16: 17:

eu ⊗ I[n]\S . Let Uc+1 = U u Let Pc+1 = |0|Qu | ⟩⟨0|Qu | |Qu ⊗ I[n]\Qu .

Kc+1 ← Pc+1 Uc+1 Kc . µ ec+1 ← µ ec − 2η. 20: Qc+1 ← Qc ∪ Qu and c ← c + 1. 21: end if 22: end for 23: end for 24: τ̂ ← Sub-Tomography (Kc , Rr , 1, η, δ/(2n), [e µc , 1]) . 25: Let |φ̂⟩ be a top eigenvector of τ̂ . 26: return   |ψ̂⟩ = U1† U2† · · · Uc† |0|Qc | ⟩Qc ⊗ |φ̂⟩Rr ,

(4.128)

(4.129)

18:

19:

(4.130)

where the tensor product is interpreted according to the canonical ordering of the qudits.

45

If |Su | ≤ κ, the algorithm sets Ru = Su , and the invariant follows. If |Su | > κ, the algorithm chooses Ru ⊆ Su with |Ru | = κ and projects Qu = Su \ Ru onto |0⟩. After this step, the only qudits that have not already been projected in Vu are those in Ru . At each nontrivial step, Qu is chosen from qudits that have not yet been projected onto |0⟩. Hence Qu is disjoint from all sets projected at earlier steps, which proves pairwise disjointness. Each nontrivial step has Qu ̸= ∅, and after the root has been processed the residual set Rr is nonempty. Since the projected sets are pairwise disjoint, at most n − 1 nontrivial disentangling steps can occur. The size bound follows from |Rv | ≤ κ for every child v: |Su | ≤ 1 + | ch(u)|κ ≤ 1 + bκ

(4.134)

by (4.133). If n = 1, then b = 0. If n = 2, the chosen root has one child and the other vertex has none, so b = 1. If n ≥ 3, the root has one child because it was chosen to have degree one, and every non-root vertex has at most ∆(T ) − 1 children. Since ∆(T ) ≥ 2 in this case, b ≤ ∆(T ) − 1. Lemma 4.15 (Rank bound for TTN residual subsystems). Let |ψ⟩ ∈ Sd (T, χ), and consider Algorithm 4. Immediately before a vertex u is processed, let K<u be the cumulative postselection map constructed so far, and define h i † σu = tr[n]\Su K<u |ψ⟩⟨ψ|K<u . (4.135) Then rank(σu ) ≤ χ.

(4.136)

Proof. The cut between Vu and [n] \ Vu in the tree T contains at most one edge: it contains the edge from u to its parent if u is not the root, and it is empty if u is the root. By Claim 2.17, the Schmidt rank of |ψ⟩ across the bipartition Vu | [n] \ Vu is at most χ. All operations appearing in K<u are supported either entirely inside Vu or entirely outside Vu . Indeed, operations associated with descendants of u are supported in Vu , while any previously processed vertex that is not a descendant of u lies in a rooted subtree disjoint from Vu . No ancestor of u has been processed yet. Thus K<u is local with respect to the bipartition Vu | [n] \ Vu . Local linear maps cannot increase Schmidt rank, so the subnormalised reduced state on Vu after applying K<u has rank at most χ. By the second item of Lemma 4.14, all qudits in Vu \ Su have already been projected onto the product state |0⟩Vu \Su . Removing a fixed product factor cannot increase rank. Hence the reduced state on Su has rank at most χ. Proposition 4.16 (Correctness of TTN learner). Assume that every Sub-Tomography call in Algorithm 4 succeeds with trace-norm error at most η. If η≤

1 , 8n

then the state |ψ̂⟩ output by Algorithm 4 satisfies p √ |ψ⟩⟨ψ| − |ψ̂⟩⟨ψ̂| ≤ 2 2nη + 4 η. 1

(4.137)

(4.138)

In particular, the choice η = ϵ2 /(128n) is sufficient to make the final trace norm error at most ϵ for every ϵ ∈ (0, 1]. 46

Proof. Index the nontrivial disentangling steps by t = 1, . . . , c in the order in which they are performed, and let µt = ∥Kt |ψ⟩∥2 (4.139) be the true cumulative success probability after the first t such steps. We first show that µt ≥ 1 − 2tη

(4.140)

for all t. The claim is trivial for t = 0. Suppose it holds before the next disentangling step, which processes some vertex u. By Lemma 4.15, the ideal subnormalised reduced state on Su has rank at most χ. Since the corresponding tomography call succeeds to trace-norm error at most η, Corollary 4.9 implies that the projection chosen by the algorithm decreases the branch weight by at most 2η. Hence µt+1 ≥ µt − 2η ≥ 1 − 2(t + 1)η.

(4.141)

There are at most n − 1 nontrivial disentangling steps, so 1 µc ≥ 1 − 2nη ≥ . 2

(4.142)

U≤c = Uc Uc−1 · · · U1 .

(4.143)

Let Once a qudit has been projected, it is never included in any subsequent residual subsystem. Hence a unitary applied at a subsequent step acts trivially on every previously projected qudit, so each projection commutes with all unitaries that follow it. Thus Kc = PQc U≤c ,

PQc = |0|Qc | ⟩⟨0|Qc | |Qc ⊗ IRr ,

(4.144)

where Qc is the final value of the projected set maintained by Algorithm 4. Define the exact postselected reconstruction † |ψ ⋆ ⟩ = U≤c

PQc U≤c |ψ⟩ . √ µc

(4.145)

Then |⟨ψ|ψ ⋆ ⟩|2 = µc ,

(4.146)

p p ∥|ψ⟩⟨ψ| − |ψ ⋆ ⟩⟨ψ ⋆ |∥1 = 2 1 − µc ≤ 2 2nη.

(4.147)

and By the second item of Lemma 4.14, applied at the root, every qudit in Vr \ Rr = [n]\Rr has been projected onto |0⟩ and hence lies in Qc , so that [n]\Rr ⊆ Qc . Conversely, once a qudit has been projected, it cannot belong to Rr . Hence Qc ∩Rr = ∅, Qc ∪Rr = [n]. Hence, the normalised postselected state has the form PQc U≤c |ψ⟩ = |0|Qc | ⟩Qc ⊗ |φ⟩Rr √ µc for some pure state |φ⟩ on Rr . The ideal final subnormalised residual state is h i τ = tr[n]\Rr Kc |ψ⟩⟨ψ|Kc† = µc |φ⟩⟨φ|.

47

(4.148)

(4.149)

The final tomography call outputs τ̂ with ∥τ − τ̂ ∥1 ≤ η.

(4.150)

Let |φ̂⟩ be a top eigenvector of τ̂ . By the variational characterisation of the largest eigenvalue, ⟨φ̂|τ |φ̂⟩ ≥ ⟨φ̂|τ̂ |φ̂⟩ − η

(4.151)

≥ ⟨φ|τ̂ |φ⟩ − η

(4.152)

≥ ⟨φ|τ |φ⟩ − 2η

(4.153)

= µc − 2η.

(4.154)

Since τ = µc |φ⟩⟨φ|, this implies 2η ≥ 1 − 4η. µc

(4.155)

√ ∥|φ⟩⟨φ| − |φ̂⟩⟨φ̂|∥1 ≤ 4 η.

(4.156)

|⟨φ̂|φ⟩|2 ≥ 1 − Therefore,

† Tensoring with a fixed state and applying the unitary U≤c preserves trace norm, so the ⋆ same bound holds between |ψ ⟩ and the output |ψ̂⟩. The triangle inequality gives p √ |ψ⟩⟨ψ| − |ψ̂⟩⟨ψ̂| ≤ 2 2nη + 4 η. (4.157) 1

Finally, substituting η = ϵ2 /(128n) gives a bound at most ϵ for ϵ ∈ (0, 1]. The same argument gives the sample complexity of TTN state tomography. Theorem 4.17 (TTN state tomography). Let T be a tree on n ≥ 1 vertices with maximum degree ∆ = ∆(T ), and let |ψ⟩ ∈ Sd (T, χ) be unknown, where d ≥ 2. Given T , d, and χ, and implementing Sub-Tomography with the sample-optimal rank-constrained primitive from Section 4.1, Algorithm 4 learns |ψ⟩ to trace norm error at most ϵ with success probability at least 1 − δ using  3  n 1+bκ O χd + log(n/δ) (4.158) ϵ4 copies, where κ = max{1, ⌈logd χ⌉} and b = maxu∈V (T ) | ch(u)| is computed after the rooting chosen in the algorithm. In particular, χd1+bκ ≤ (dχ)max{2,∆} ,

(4.159)

χd1+bκ ≤ (dχ)∆ .

(4.160)

and, for n ≥ 3, Thus, for n ≥ 3, the copy complexity is  3 
n ∆ O (dχ) + log(n/δ) . ϵ4

(4.161)

The classical runtime is polynomial in n, d1+bκ , χ, 1/ϵ, and log(1/δ), assuming the rank constrained tomography procedure and the relevant eigendecompositions are implemented in time polynomial in their input dimension. 48

Proof. By Proposition 4.16, it suffices to take ϵ2 . (4.162) 128n There are at most n − 1 nontrivial disentangling calls and one final residual tomography call, hence at most n calls to Sub-Tomography in total. Since each call is assigned failure probability δ/(2n), a union bound gives total failure probability at most δ/2 ≤ δ. For this choice of η, all lower estimates on success probability used by the algorithm satisfy 1 µ et = 1 − 2tη ≥ (4.163) 2 for every t ≤ n. The dependence on the lower bound on success probability in Corollary 4.5 thus contributes only a constant factor. Each tomography call used to construct a disentangling unitary acts on a subsystem Su satisfying η=

|Su | ≤ 1 + bκ

(4.164)

by Lemma 4.14. The corresponding reduced state has rank at most χ by Lemma 4.15. Hence one such call uses   1+bκ χd + log(n/δ) (4.165) O η2 copies. Multiplying by at most n calls and substituting the value of η yields  3  n 1+bκ χd + log(n/δ) . (4.166) O ϵ4 The final residual tomography call has rank one and acts on |Rr | ≤ κ qudits. If n = 1, then Rr = {r}, so this call has dimension d and is bounded by the above expression because χ ≥ 1. If n ≥ 2, then b ≥ 1 and dκ ≤ χd1+bκ , so the final call is again no larger than the bound. It remains to simplify the degree dependence. Since dκ ≤ dχ, we have χd1+bκ ≤ χd(dχ)b = (dχ)b+1 .

(4.167)

By Lemma 4.14, b + 1 ≤ max{2, ∆} for all n ≥ 1, and b + 1 ≤ ∆ for n ≥ 3. This proves the simplified bounds. The runtime statement follows because all linear-algebra operations are performed on matrices of dimension at most d1+bκ , up to polynomial overhead in the number of vertices and the accuracy parameters. Remark 4.18 (Relation to the MPS learner). If T is a path and n ≥ 3, the rooting chosen by Algorithm 4 is an endpoint rooting, so b = 1. Every tomography call is on a subsystem of size at most κ + 1, and the copy bound becomes   3
n κ+1 χd + log(n/δ) , O (4.168) ϵ4 matching the sequential MPS bound in Theorem 4.12. Thus Algorithm 4 is the tree analogue of Algorithm 3, with the path order replaced by the traversal from leaves to root. Remark 4.19. Vertices at the same depth have disjoint rooted subtrees, and thus the operations on the corresponding disjoint sets of qudits commute. This means that parts of Algorithm 4 can be parallellised. Algorithm 4 is nevertheless stated sequentially, because this makes the cumulative postselection map Kc and the estimates of the success probability identical to the MPS analysis in Section 4.2. 49

4.4

TNS tomography of general graphs via entanglement rerouting

We now combine the representation results of Section 3 with the MPS and TTN learners. Rerouting shows that a state in Sd (G, χ) also belongs to a simpler TNS class, with larger bond or local physical dimension. We then apply the learner for that class. The input consists only of G, χ, and the promise that such a representation exists. An explicit TN description of the unknown state is not required. Tomography via reduction to an MPS. Theorem 4.20 (Black-box tomography via an MPS representation). Let G = ([n], E) be a graph, and let π : [n] → [n] be a linear ordering of the vertices. Set κc = max {1, ⌈logd (χc )⌉} .

c = cw(π),

(4.169)

Then an unknown state |ψ⟩ ∈ Sd (G, χ) can be learned to trace norm error at most ϵ with success probability at least 1 − δ using  3 
n c κc +1 O χ d + log(n/δ) (4.170) ϵ4 copies. In particular, if π is chosen to have optimal cutwidth, then  3  n 2 2 cw(G) O d χ + log(n/δ) ϵ4

(4.171)

copies suffice. If the ordering π is not supplied, an optimal cutwidth ordering can first be computed 2 in time 2O(cw(G) ) n. Apart from this graph preprocessing step, the classical postprocessing time of the sequential learner is polynomial in n, dκc +1 , χc , 1/ϵ, and log(1/δ), assuming the local rank-constrained tomography primitive and eigendecompositions are implemented in time polynomial in their input dimension. Proof. By Theorem 3.3, the ordering π gives a path Pnπ such that |ψ⟩ ∈ Sd (G, χ)

=⇒

|ψ⟩ ∈ Sd (Pnπ , χc ).

(4.172)

After relabelling the qudits according to π, the conditions of the MPS learner are satisfied with path Pnπ and bond dimension χc . Applying Theorem 4.12 with bond dimension χc gives a sufficient number of  3 
n c κc +1 O χd + log(n/δ) (4.173) ϵ4 copies. Since dκc ≤ dχc , we have χc dκc +1 ≤ d2 χ2c .

(4.174)

Choosing c = cw(G) proves (4.171). The runtime statement follows from the runtime of the cutwidth ordering algorithm in Theorem 3.3 and the runtime statement in Theorem 4.12. The output is finally relabelled back to the original ordering of the qudits. Remark 4.21 (Logarithmic-depth variant). The reduction in Theorem 4.20 is modular in the choice of MPS learner. If circuit depth is a concern, one may instead invoke the logarithmic-depth MPS learner of [LCH25] (see Remark 4.13) with bond dimension χc . This yields a reconstruction circuit of depth O(log n), at the cost of a worse copy complexity of  4 6c 3  d χ n log(n/δ) . (4.175) O max{1, c logd χ}3 ϵ8 50

Tomography via reduction to a TTN. Theorem 4.22 (Black-box tomography via a tree-cut decomposition). Let G = ([n], E) be a graph, and let (T , X ) be a tree-cut decomposition of G of width k ≥ 1. Let (T̂ , X̂ ) be the tree-indexed partition obtained from (T , X ) after removing empty bags as in Lemma 3.5, and write m = |V (T̂ )|. (4.176) Root T̂ as in Algorithm 4, and let bT̂ = max | ch(u)|

(4.177)

u∈V (T̂ )

be the maximum number of children in this rooting. Set κ = max{1, ⌈logd χ⌉}.

(4.178)

Then an unknown state |ψ⟩ ∈ Sd (G, χ) can be learned to trace norm error at most ϵ with success probability at least 1 − δ using  3  m k k(1+bT̂ κ) O χ d + log(m/δ) (4.179) ϵ4 copies. Consequently,  O

 n3  k max{2,∆(T̂ )} (dχ) + log(n/δ) ϵ4

copies suffice. If m ≥ 3, this simplifies further to  3  n k∆(T̂ ) (dχ) + log(n/δ) . O ϵ4

(4.180)

(4.181)

If no tree-cut decomposition is supplied, one may first compute a decomposition of 2 width k ≤ 2 tcw(G) in time 2O(tcw(G) log tcw(G)) n2 . For the tree T̂ obtained from this computed decomposition, (4.180) becomes  3  n 2 tcw(G) max{2,∆(T̂ )} O (dχ) + log(n/δ) . (4.182) ϵ4 The classical postprocessing time, after the tree-cut decomposition has been chosen, is polynomial in m, dk(1+bT̂ κ) , χk , 1/ϵ, and log(1/δ), assuming the local tomography primitive and eigendecompositions are implemented in time polynomial in their input dimension. Proof. By Theorem 3.6, grouping the qudits according to the nonempty bags of X̂ gives a TTN representation on the tree T̂ with local physical dimension at most d′ = dk

(4.183)

χ′ = χk .

(4.184)

and bond dimension at most The number of grouped physical subsystems is m ≤ n. Two points ensure that the TTN learner below applies to the grouped state. First, grouping is merely a reinterpretation 51

N N of the tensor factors under the canonical identification v∈[n] Cd ∼ = t∈V (T̂ ) (Cd )⊗|X̂t | , so the represented state is unchanged. Second, bags of size smaller than k give local dimensions smaller than dk . Padding each local Hilbert space to dimension exactly dk by tensoring with unused ancilla directions does not affect the state and lets us apply Theorem 4.17 with a uniform local dimension d′ = dk . Apply Theorem 4.17 to this grouped TTN. The residual-size parameter for local dimension d′ and bond dimension χ′ is max{1, ⌈logd′ χ′ ⌉} = max{1, ⌈logdk χk ⌉} = max{1, ⌈logd χ⌉} = κ. The TTN tomography bound from Theorem 4.17 gives  3  3   m m ′ ′ 1+bT̂ κ k k(1+bT̂ κ) =O + log(m/δ) + log(m/δ) . O χ (d ) χ d ϵ4 ϵ4

(4.185)

(4.186)

This proves the first displayed bound. For the simplified bound, use dκ ≤ dχ to obtain χk dk(1+bT̂ κ) ≤ χk dk (dχ)kbT̂ = (dχ)k(bT̂ +1) .

(4.187)

By the rooting convention in Algorithm 4, bT̂ + 1 ≤ max{2, ∆(T̂ )},

(4.188)

and, if m ≥ 3, then bT̂ + 1 ≤ ∆(T̂ ). Since m ≤ n, this proves (4.180) and (4.181). The statement for a computed approximate tree-cut decomposition follows from the approximation guarantee quoted in Theorem 3.6. Finally, the output of the TTN learner on the grouped systems is interpreted as an n-qudit state by undoing the canonical grouping of the physical indices. Remark 4.23 (Choosing the better black-box reduction). If both an ordering π and a tree-cut decomposition are available, one can simply run the cheaper of the two black-box reductions. Using the simplified sequential bounds, this gives the combined guarantee  3 o  n n 2 2 cw(π) k max{2,∆(T̂ )} O + log(n/δ) , (4.189) min d χ , (dχ) ϵ4 with cw(π) replaced by cw(G) if an optimal ordering is used. If the tree T̂ obtained after removing empty bags has at least three vertices, i.e., m ≥ 3, the second term in the minimum can be replaced by (dχ)k∆(T̂ ) . Remark 4.24 (Degree of the tree-cut decomposition). The dependence on ∆(T̂ ) is intentionally left explicit. Tree-cutwidth controls the size of the bags and the adhesions of the decomposition, but it does not by itself bound the maximum degree of the decomposition tree, so ∆(T̂ ) has to be treated as a property of the chosen decomposition rather than of G. Whenever a decomposition of width k with ∆(T̂ ) ≤ f (G) can be constructed for some graph parameter f , (4.180) immediately improves by replacing ∆(T̂ ) with f (G). We note that both black-box reductions above rely only on the realisable learners from Sections 4.2 and 4.3. No agnostic learning machinery is needed under the promise |ψ⟩ ∈ Sd (G, χ). 52

4.5

Direct TNS tomography for graphs

The black-box procedures first replace the tensor-network graph by a path or tree and then apply the corresponding MPS or TTN learner. This can lose useful information because the learning cost is estimated using the chosen target representation. We instead choose the active subsystems directly from the original graph while retaining the same iterative-disentangling mechanism. The learner uses a sequence of subsets describing how the full vertex set is assembled. After processing a subset, it retains only a small residual subsystem. A larger subset is processed using its fresh vertices and the residual subsystems retained by its children. The rank of the resulting active state is bounded by the cut of the larger subset in the original graph. The input to the learner is a sequence of subsets that describes how the vertex set is assembled. After a subset has been processed, all but a small residual subsystem of that subset have been disentangled and projected onto |0⟩. When a larger subset is processed, the learner only sees the fresh vertices introduced at that step together with the residual subsystems left by its children. The rank of the corresponding reduced state is determined by the cut of the larger subset in the original graph. 4.5.1

Learning sequences

We begin by introducing learning sequences, the combinatorial objects used by our direct learner. A learning sequence records an order in which subsets of the vertex set are assembled into the full vertex set. Beyond the subsets Si themselves, a learning sequence specifies which previously assembled subsets are combined at each step, through the child sets Ii , and which vertices are introduced for the first time, through the fresh sets Fi . This determines which residual subsystems are combined at each step of the tomography algorithm in Algorithm 5. Definition 4.25 (Learning sequence). Let G = (V, E) be a graph. A learning sequence for G is a finite family L = (Si , Ii , Fi )L (4.190) i=1 with the following properties: 1. Si ⊆ V is nonempty, Ii ⊆ [i − 1], and Fi ⊆ V for every i ∈ [L]. 2. For every i ∈ [L], Si = Fi ⊔

G

Sj ,

(4.191)

j∈Ii

where ⊔ indicates that the union is disjoint. 3. The sets F1 , . . . , FL are pairwise disjoint. 4. The directed graph on vertex set [L] with an edge i → j whenever j ∈ Ii is a rooted tree with root L. 5. SL = V . The elements of Ii are indices of earlier steps, not vertices of G. They are the children of i in the dependency tree. The set Fi contains the vertices first introduced at step i. We call L the length of the learning sequence.

53

Remark 4.26 (Analogy with contraction sequences). Learning sequences are the tomography analogue of the contraction sequences of Markov and Shi [MS08]. A contraction sequence records how tensor-network components are merged during simulation. A learning sequence records how subsystems are assembled and disentangled during tomography. Lemma 4.33 constructs a learning sequence from any contraction sequence. The condition that the dependency graph in Definition 4.25 is a rooted tree implies that the sets S1 , . . . , SL form a laminar family, a standard notion from combinatorial optimisation [Sch03]: any two sets in the family are either disjoint or nested. Lemma 4.27 (Laminarity of learning sequences). Let L = (Si , Ii , Fi )L i=1 be a learning sequence. For any two indices i, j ∈ [L], the sets Si and Sj are either disjoint, or one contains the other. In particular, if j < i, then either Sj ⊆ Si or Sj ∩ Si = ∅. Proof. Let D(i) be the set containing i and all descendants of i in the rooted tree on [L] from Definition 4.25. We claim that G Si = Fℓ . (4.192) ℓ∈D(i)

F This follows by induction from the defining identity Si = Fi ⊔ j∈Ii Sj . Since the dependency graph is a rooted tree, for any two indices i and j, the descendant sets D(i) and D(j) are either disjoint, or one is contained in the other. In the nested case, say F F D(j) ⊆ D(i), the union representation directly gives Sj = ℓ∈D(j) Fℓ ⊆ ℓ∈D(i) Fℓ = Si . In the disjoint case, D(i) ∩ D(j) = ∅, the two unions run over disjoint index sets, and since the sets F1 , . . . , FL are pairwise disjoint, no vertex can appear in both unions, so Si ∩ Sj = ∅. If j < i, then j cannot be an ancestor of i, because edges always point from a larger index to a smaller index. Hence either j is a descendant of i, giving Sj ⊆ Si , or the two sets are disjoint. Laminarity ensures that every earlier postselection map is local with respect to the cut used at the current step. For a learning sequence L, define Y ri := w(e), qi := ⌈logd ri ⌉. (4.193) e∈cutG (Si )

Here the empty product is equal to 1. The quantity ri is the rank bound from Claim 2.17. The quantity qi is the number of qudits needed for a residual subsystem that can support a state of rank at most ri , as follows from Corollary 4.7. In particular, qi = 0 when ri = 1, in which case the residual register may be empty. We also define X ai := |Fi | + qj , (4.194) j∈Ii

and the weighted learning complexity of L by lcd,w (L) := max(ai + qi ).

(4.195)

i∈[L]

Thus ai bounds the size of the active subsystem at step i, while qi is the size of the residual subsystem retained after that step.

54

If one only wants to use the uniform bond dimension bound w(e) ≤ χ, then one may replace ri and qi by X r̄i = χ| cutG (Si )| , q̄i = ⌈| cutG (Si )| logd χ⌉, āi := |Fi | + q̄j . (4.196) j∈Ii

and define lcd,χ (L) := max (āi + q̄i ) .

(4.197)

i∈[L]

Then lcd,w (L) ≤ lcd,χ (L). Finally, define lcd,χ (G) := min lcd,χ (L), L

(4.198)

where the minimum is over all learning sequences for G. Such a sequence always exists: for instance, take L = 1, S1 = F1 = V , and I1 = ∅. Remark 4.28 (Normalising learning sequences). The proof of Lemma 4.27 gives G Si = Fℓ . (4.199) ℓ∈D(i)

Applying PL this identity at i = L shows that the fresh sets partition the vertex set, so that i=1 |Fi | = n. Moreover, we may assume without loss of generality that every step satisfies Fi ̸= ∅ or |Ii | ≥ 2. Indeed, a step with Fi = ∅ and Ii = {j} satisfies Si = Sj . Deleting this step, while replacing i by j in the child set of the parent of i (or making j the root if i = L), yields a learning sequence for G with the same sets. Since cutG (Si ) = cutG (Sj ), this deletion leaves every remaining quantity rk , qk , and ak unchanged and removes the term ai + qi from the maximum in (4.195), so it does not increase the learning complexity. Under this normalisation, every step either introduces a fresh vertex or has at least two children. There are at most n steps of the first kind, because the fresh sets are nonempty and pairwise disjoint. There are at most n − 1 steps of the second kind, because every leaf of the dependency tree has Ii = ∅ and hence Fi = Si ̸= ∅, so the tree has at most n leaves, and a rooted tree with at most n leaves has at most n − 1 vertices with two or more children. Hence L ≤ 2n − 1. 4.5.2

Tomography using a learning sequence

Algorithm 5 applies the iterative disentangling procedure according to a supplied learning sequence. For each processed set Si , it stores a residual subsystem Ri ⊆ Si with |Ri | ≤ qi . When processing Si , the subsystem to be learned is [ Mi := Fi ∪ Rj . (4.200) j∈Ii

If Mi already has size at most qi , no tomography is needed at that step and we set Ri = Mi . Otherwise we learn the reduced state on Mi , map the learned rank-ri support into a subspace supported on qi qudits, and project the remaining qudits onto |0⟩. When only G and an upper bound χ on the bond dimension are known, Algorithm 5 uses r̄i and q̄i in place of ri and qi . The individual edge dimensions w(e) need not be known. The unitary in Algorithm 5 exists because dim(Wi ) ≤ ri ≤ dqi and dim(HRi ) = dqi whenever the nontrivial branch |Mi | > qi is entered. As before, one constructs it by 55

Algorithm 5 LearnTNSFromSequence Input: graph G = ([n], E), edge-dimension function w : E → N, physical dimension d ≥ 2, learning sequence L = (Si , Ii , Fi )L i=1 , copies of |ψ⟩ ∈ Sd (G, w), accuracy parameter ϵ ∈ (0, 1], confidence parameter δ ∈ (0, 1) Output: Classical description of a pure state |ψ̂⟩. 1: For every i ∈ [L], compute ri and qi as in Equation (4.193). 2: η ← ϵ2 /(128L). 3: K0 ← I, µ e0 ← 1, Q ← ∅, and c ← 0. 4: for i = 1 to L do S 5: Mi ← Fi ∪ j∈Ii Rj . 6: if |Mi | ≤ qi then 7: Ri ← Mi . 8: else 9: Choose Ri ⊆ Mi with |Ri | = qi . 10: Qi ← Mi \ Ri . 11: σ̂i ← Sub-Tomography (Kc , Mi , ri , η, δ/(2L), [e µc , 1]) . 12: Let Wi be the span of the eigenvectors associated with the ri largest eigenvalues of σ̂i . ei supported on Mi such that 13: Compute a unitary U ei Wi ⊆ |0|Qi | ⟩Q ⊗ HR . U i i 14: 15:

ei tensored with the identity outside Mi , Uc+1 = U ei ⊗ IM c . Let Uc+1 be U i Let Pc+1 = |0|Qi | ⟩⟨0|Qi | |Qi ⊗ I[n]\Qi .

Kc+1 ← Pc+1 Uc+1 Kc . µ ec+1 ← µ ec − 2η. 18: Q ← Q ∪ Qi and c ← c + 1. 19: end if 20: end for 21: τ̂ ← Sub-Tomography (Kc , RL , 1, η, δ/(2L), [e µc , 1]) . 22: Let |φ̂⟩ be a top eigenvector of τ̂ . 23: return   |ψ̂⟩ = U1† U2† · · · Uc† |0|Q| ⟩Q ⊗ |φ̂⟩RL , 16: 17:

where the tensor product is interpreted according to the canonical ordering of the qudits.

56

choosing an orthonormal basis of Wi , mapping this basis isometrically into |0|Qi | ⟩Qi ⊗ HRi , and extending the isometry to a unitary on HMi . When only the bound χ is known, the same argument uses dim(Wi ) ≤ r̄i ≤ dq̄i . We next establish correctness and sample complexity. Lemma 4.29 (Residual invariant). During Algorithm 5, after step i has been processed, the following hold: 1. Ri ⊆ Si and |Ri | ≤ qi . 2. Every qudit in Si \Ri has been projected onto |0⟩ in the current postselected branch. 3. The sets projected at different nontrivial steps are pairwise disjoint. Moreover, for every i ∈ [L], |Mi | ≤ ai = |Fi | +

X

qj .

(4.201)

j∈Ii

Proof. We prove the first two claims by induction over i. If Ii = ∅, then Mi = Fi = Si . If |Mi | ≤ qi , the algorithm sets Ri = Mi = Si , and there is nothing to project. If |Mi | > qi , it chooses Ri ⊆ Mi and projects Qi = Mi \ Ri onto |0⟩, so the invariant holds. Now suppose Ii ̸= ∅ and that the invariant has been proved for all children j ∈ Ii . By Equation (4.191), G Si = Fi ⊔ Sj . (4.202) j∈Ii

For each child j, the only qudits in Sj not already projected are those in Rj . Hence, immediately before processing i, the qudits in Si that have not yet been projected onto |0⟩ are precisely [ Mi = Fi ∪ Rj . (4.203) j∈Ii

If |Mi | ≤ qi , the algorithm sets Ri = Mi . If |Mi | > qi , it projects Mi \ Ri and leaves only Ri . This proves the first two claims for i. At a nontrivial step, the projected set is chosen from qudits that have not yet been projected onto |0⟩. Hence it is disjoint from every set projected earlier. This proves pairwise disjointness. Finally, the size bound for Mi follows from |Rj | ≤ qj for all j ∈ Ii . Lemma 4.30 (Rank bound for subsystems). Let |ψ⟩ ∈ Sd (G, w), and consider Algorithm 5. Immediately before step i is processed, let K<i be the cumulative postselection map constructed so far, i.e., the map Kc for the value of the counter c at that moment. (Note that K<i ̸= Ki−1 in general, since trivial steps with |Mj | ≤ qj do not increment c.) Define h i † σi = tr[n]\Mi K<i |ψ⟩⟨ψ|K<i . (4.204) Then rank(σi ) ≤ ri .

(4.205)

Proof. By Claim 2.17, the Schmidt rank of |ψ⟩ across the bipartition Si | [n] \ Si

57

(4.206)

is at most Y

ri =

w(e).

(4.207)

e∈cutG (Si )

We claim that all operations appearing in K<i are supported either entirely inside Si or entirely outside Si . Indeed, by Lemma 4.27, for every earlier index j < i we have either Sj ⊆ Si or Sj ∩ Si = ∅. The operation associated with step j, if nontrivial, is supported on Mj ⊆ Sj . Hence it is local with respect to the bipartition Si | [n] \ Si . Local linear maps cannot increase Schmidt rank across this bipartition. The subnormalised reduced state on Si after applying K<i has rank at most ri . By Lemma 4.29, all qudits in Si \ Mi have already been projected onto the product state |0⟩Si \Mi . Removing a fixed product factor cannot increase rank. Thus the reduced state on Mi has rank at most ri . Proposition 4.31 (Correctness). Assume that every call to Sub-Tomography in Algorithm 5 succeeds with trace-norm error at most η. If η≤

1 , 8L

(4.208)

p √ ≤ 2 2Lη + 4 η.

(4.209)

then the output state |ψ̂⟩ satisfies |ψ⟩⟨ψ| − |ψ̂⟩⟨ψ̂|

1

In particular, the choice η = ϵ2 /(128L) is sufficient to make the final trace norm error at most ϵ for every ϵ ∈ (0, 1]. Proof. Index the nontrivial disentangling steps by t = 1, . . . , c in the order in which they are performed, and let µt = ∥Kt |ψ⟩∥2 (4.210) be the true cumulative success probability after the first t such steps. We prove by induction that µt ≥ 1 − 2tη. (4.211) The claim is immediate for t = 0. Suppose it holds before the next nontrivial step, which processes some index i. By Lemma 4.30, the ideal subnormalised reduced state on Mi has rank at most ri . Since the tomography call succeeds to trace-norm error at most η, Corollary 4.9 implies that the projection chosen by the algorithm decreases the branch weight by at most 2η. Hence µt+1 ≥ µt − 2η ≥ 1 − 2(t + 1)η.

(4.212)

Since there is at most one nontrivial disentangling step per index, c ≤ L. Therefore 1 µc ≥ 1 − 2Lη ≥ . 2

(4.213)

U≤c = Uc Uc−1 · · · U1 .

(4.214)

Let Once a qudit has been projected, it is excluded from every residual subsystem. Hence no subsequent unitary acts on that qudit, so each projection commutes with all unitaries applied after it, and Kc = PQ U≤c , PQ = |0|Q| ⟩⟨0|Q| |Q ⊗ IRL , 58

(4.215)

F where Q = i: |Mi |>qi Qi is the final value of the projected set maintained by Algorithm 5. Define the exact postselected reconstruction † |ψ ⋆ ⟩ = U≤c

PQ U≤c |ψ⟩ . √ µc

(4.216)

Then |⟨ψ|ψ ⋆ ⟩|2 = µc , and hence p p ∥|ψ⟩⟨ψ| − |ψ ⋆ ⟩⟨ψ ⋆ |∥1 = 2 1 − µc ≤ 2 2Lη.

(4.217)

By Lemma 4.29 applied to the final set SL = V , we have Q∪RL = [n] and Q∩RL = ∅. Hence the normalised postselected state has the form PQ U≤c |ψ⟩ = |0|Q| ⟩Q ⊗ |φ⟩RL √ µc for some pure state |φ⟩ on RL . The ideal final subnormalised residual state is h i τ = tr[n]\RL Kc |ψ⟩⟨ψ|Kc† = µc |φ⟩⟨φ|.

(4.218)

(4.219)

The final tomography call outputs τ̂ with ∥τ − τ̂ ∥1 ≤ η. If |φ̂⟩ is a top eigenvector of τ̂ , the same variational argument as in Propositions 4.11 and 4.16 gives 2η ≥ 1 − 4η. µc

(4.220)

√ ∥|φ⟩⟨φ| − |φ̂⟩⟨φ̂|∥1 ≤ 4 η.

(4.221)

|⟨φ̂|φ⟩|2 ≥ 1 − Thus

† Applying U≤c preserves trace norm, and the triangle inequality proves the bound. Substituting η = ϵ2 /(128L) gives a bound at most ϵ for ϵ ∈ (0, 1].

Theorem 4.32 (Tomography using a learning sequence). Let G = ([n], E) be a graph, let w : E → N, and let L = (Si , Ii , Fi )L i=1 be a learning sequence for G. Given G, w, d, and L, Algorithm 5 learns any unknown |ψ⟩ ∈ Sd (G, w) to trace norm error at most ϵ with success probability at least 1 − δ using  3  L ai O max ri d + log(L/δ) (4.222) ϵ4 i∈[L] copies, where ri and ai are defined in Equations (4.193) and (4.194). In particular,  3  L lcd,w (L) d + log(L/δ) (4.223) O ϵ4 copies suffice. If the input is only promised to lie in Sd (G, χ), the algorithm instead uses r̄i , q̄i , and āi from Equation (4.196). It uses  3  L āi O max r̄i d + log(L/δ) (4.224) ϵ4 i∈[L] copies. In particular,  O

 L3  lcd,χ (L) d + log(L/δ) ϵ4 59

(4.225)

copies suffice. The classical postprocessing time is polynomial in L, the largest local Hilbert-space dimension, the largest rank parameter, 1/ϵ, and log(1/δ), assuming that the rankconstrained tomography primitive and the relevant eigendecompositions are implemented in time polynomial in their input dimension. Proof. By Proposition 4.31, it suffices to set η=

ϵ2 . 128L

(4.226)

There are at most L nontrivial disentangling calls and one final residual tomography call. Since each call is assigned failure probability δ/(2L), a union bound gives total failure probability at most δ. For this choice of η, all lower estimates for success probability used by the algorithm satisfy 1 µ et = 1 − 2tη ≥ (4.227) 2 for all t ≤ L. Hence the dependence on the success probability in Corollary 4.5 contributes only a constant factor. For a nontrivial disentangling call at step i, Lemma 4.30 gives rank at most ri , and Lemma 4.29 gives |Mi | ≤ ai . Thus this call uses  ai  ri d + log(L/δ) O (4.228) η2 copies. The final residual tomography call has rank one and acts on |RL | ≤ qL qudits. It is bounded by the same maximum because RL ⊆ ML if no final disentangling occurs, while |RL | = qL ≤ aL whenever a final disentangling occurs. Multiplying by at most L + 1 calls and substituting the value of η gives (4.222). Since ri ≤ dqi , we have ri dai ≤ dai +qi ≤ dlcd,w (L) . (4.229) This proves (4.223). Now suppose that |ψ⟩ ∈ Sd (G, χ). By definition, there exists a weight function wψ : E → [χ] such that |ψ⟩ ∈ Sd (G, wψ ). For every i ∈ [L], Y

wψ (e) ≤ χ| cutG (Si )| = r̄i .

(4.230)

e∈cutG (Si )

Hence the rank bound used at step i is at most r̄i , a residual register of size q̄i suffices, and the active subsystem has size at most āi . Repeating the preceding argument with these parameters proves (4.224). Since r̄i ≤ dq̄i , we also have r̄i dāi ≤ dāi +q̄i ≤ dlcd,χ (L) ,

(4.231)

which proves (4.225). The runtime statement follows because all linear-algebra operations are performed on matrices whose dimension and rank are bounded by the corresponding parameters defined from the individual edge dimensions or from the common bound χ, up to polynomial overhead in L and the accuracy parameters.

60

4.5.3

Constructing learning sequences from contraction sequences

Learning sequences can be supplied directly, but they can also be obtained from graph contraction sequences. We use the following standard interpretation of a contraction sequence: during the contraction process, every current vertex represents a subset of the original vertex set, and the degree of a current vertex counts incident edges with multiplicity. With this convention, the degree of the current vertex representing a set S ⊆ V is | cutG (S)|. Lemma 4.33 (From contraction sequences to learning sequences). Let G = (V, E) be a connected graph with n ≥ 2, and let π be a contraction sequence of contraction complexity C. Then π induces a learning sequence Lπ = (Si , Ii , Fi )L i=1 for G with L≤n−1

(4.232)

and | cutG (Si )| ≤ C

for every i ∈ [L].

(4.233)

Moreover, the sequence can be constructed from π in polynomial time. Proof. Run the contraction process described by π. At every moment, each current vertex corresponds to the subset of original vertices that have been merged into it. We build the learning sequence alongside this process. When the next contraction merges two distinct current vertices corresponding to disjoint sets A and B, create a new index i. If A was created by an earlier contraction, include its corresponding index in Ii . Otherwise, A is a singleton original vertex and we include that vertex in Fi . Do the same for B. Finally set Si = A ∪ B. (4.234) Because each nontrivial contraction reduces the number of current vertices by one, a connected n-vertex graph has at most n − 1 such contractions, and the final set is V . Each earlier constructed set is used once, namely when its current vertex is merged into a larger current vertex. The fresh vertices are introduced when their singleton current vertices are first merged. Hence the data (Si , Ii , Fi )L i=1 satisfy the conditions of Definition 4.25. Immediately after the contraction creating Si , the incident edges of the new current vertex are precisely the original edges crossing the cut cutG (Si ), counted with multiplicity. Since π has contraction complexity C, this degree is at most C. The construction only requires maintaining the current partition of V and the index associated with each current part, so it is polynomial-time in the length of π and the size of G. Remark 4.34 (Disconnected graphs). The tomography theorem for a fixed learning sequence (Theorem 4.32) applies to arbitrary graphs. For a disconnected graph, one may construct a learning sequence for each connected component, introduce isolated vertices as fresh systems, and combine the component sequences in a final step. We state the contraction-complexity corollaries below for connected graphs to keep the bounds and notation simple. The conversion of Lemma 4.33 also yields an upper bound on the learning complexity in terms of contraction complexity, and hence, via Theorem 2.6, in terms of degree and treewidth.

61

Corollary 4.35 (Learning complexity from contraction complexity). Let G be a connected graph with n ≥ 2 vertices, and let C = cc(G) be its contraction complexity. Then lcd,χ (G) ≤ min {n, 3 max{1, ⌈C logd χ⌉}} ≤ 3∆(G) (tw(G) + 1) max{1, ⌈logd χ⌉}. (4.235) Proof. Let π be an optimal contraction sequence, and let Lπ be the learning sequence induced by Lemma 4.33. Every set of Lπ satisfies | cutG (Si )| ≤ C, so q̄i ≤ Q := max{1, ⌈C logd χ⌉}

(4.236)

for every i. Each step of Lπ combines the two endpoints of a contraction, and each endpoint contributes either one fresh vertex or the residual register of an earlier set, so X |Fi | + q̄j ≤ 2Q, (4.237) j∈Ii

using Q ≥ 1. Together with q̄i ≤ Q, this gives lcd,χ (Lπ ) ≤ 3Q. The one-step learning sequence with S1 = F1 = V and I1 = ∅ has q̄1 = 0 and ā1 = n, and hence lcd,χ (G) ≤ n. Combining these two bounds proves the first inequality. For the second inequality, ⌈ab⌉ ≤ a⌈b⌉ for a ∈ N gives Q ≤ max{1, C⌈logd χ⌉} ≤ max{1, C} max{1, ⌈logd χ⌉}. Since G is connected and has at least two vertices, ∆(G) ≥ 1 and tw(G) ≥ 1. Hence max{1, C} ≤ ∆(G)(tw(G) + 1) − 1

(4.238)

by Theorem 2.6. Combining this construction with the sequence learner gives sample complexity bounds for TNS tomography in terms of contraction complexity. Corollary 4.36 (Direct tomography from contraction complexity). Let G = ([n], E) be a connected graph with bond dimension bound χ, and let C = cc(G) be its contraction complexity. Then an unknown state |ψ⟩ ∈ Sd (G, χ) can be learned to trace norm error at most ϵ with success probability at least 1 − δ using  3 
n 2 3C O d χ + log(n/δ) (4.239) ϵ4 copies, given a contraction sequence of complexity C. If no such sequence is supplied, one may first compute an optimal contraction sequence using the algorithm described after Theorem 2.6. Proof. If n = 1, the claim is immediate from ordinary tomography on one qudit. Assume n ≥ 2. Apply Lemma 4.33 to a contraction sequence of complexity C, obtaining a learning sequence L of length L = n − 1 with | cutG (Si )| ≤ C for every i. Hence r̄i = χ| cutG (Si )| ≤ χC .

(4.240)

At a contraction step, the subsystem Mi is built from the two current contraction endpoints. Each endpoint is either a fresh original vertex, contributing dimension d, or the residual subsystem of a previously created set Sj , contributing dimension at most dq̄j ≤ dr̄j ≤ dχC . 62

(4.241)

Since χC ≥ 1, each endpoint contributes dimension at most dχC . Therefore dāi ≤ d2 χ2C

(4.242)

max r̄i dāi ≤ d2 χ3C .

(4.243)

for every i, and so i∈[L]

The stated sample complexity follows from (4.224), using L ≤ n. Since contraction complexity can be bounded in terms of treewidth and degree, these parameters also give sample complexity bounds for TNS tomography. Corollary 4.37 (A treewidth and degree bound). Let G = ([n], E) be a connected graph with bond dimension bound χ, and let ∆ = ∆(G) be its maximum degree. Then an unknown state |ψ⟩ ∈ Sd (G, χ) can be learned to trace norm error at most ϵ with success probability at least 1 − δ using  3  n 2 3(∆(tw(G)+1)−1) (4.244) O d χ + log(n/δ) ϵ4 copies. A contraction sequence with the stated width bound is computed first. Equivalently, the exponential dependence is d2 χO(∆ tw(G)) .

(4.245)

Proof. This follows from Corollary 4.36 and the bound cc(G) ≤ ∆(G)(tw(G) + 1) − 1

(4.246)

from Theorem 2.6. Remark 4.38 (Relation to the black-box reductions). The learning sequence approach includes the schedules used by the two black-box reductions. For a linear ordering π with c = cw(π), take Si = {v1 , . . . , vi }, Fi = {vi }, with I1 = ∅ and Ii = {i − 1} for i ≥ 2. Then r̄i ≤ χc , q̄i ≤ κc := max {1, ⌈c logd χ⌉} , (4.247) and hence āi ≤ 1 + κc .

(4.248)

The precise bound in Theorem 4.32 then gives the same dependence χc dκc +1

(4.249)

as Theorem 4.20. Likewise, root the tree obtained from a tree-cut decomposition of width k, and let Si be the union of the bags in a rooted subtree, with Fi equal to the bag at its root. If b is the maximum number of children, then r̄i ≤ χk ,

q̄i ≤ k max {1, ⌈logd χ⌉} ,

(4.250)

and āi ≤ k (1 + b max {1, ⌈logd χ⌉}) .

(4.251)

This recovers the dependence in Theorem 4.22. Thus the precise learning sequence bound can reproduce the two black-box estimates and may improve them for other choices of learning sequence. The bounds obtained from contraction complexity in Corollaries 4.36 and 4.37 use a particular learning sequence and replace its individual cuts by a common upper bound. These estimates can be less sharp than the specialised path or tree bounds. 63

Remark 4.39 (Relation to the TTN learner). When G is itself a tree T and the learning sequence is chosen from a rooted traversal of subtrees, the sets Si are the rooted subtrees of T . For the step associated with a vertex u, the fresh set Fi consists of u itself, and the child set Ii collects the indices of the steps associated with the children of u in T , so that children in the dependency tree correspond exactly to children in T . Then S Mi = Fi ∪ j∈Ii Rj is the vertex u together with the residual subsystems left by the subtrees below it. Thus the learner above yields the residual-subsystem formulation of Algorithm 4 as a special case. The separate TTN theorem in Section 4.3 keeps the tree degree explicit and gives the sharper bound for that special case.

4.6

Agnostic TNS tomography

The previous subsections considered the realisable setting: the input state was promised to be a pure tensor network state in the relevant class. We now consider the agnostic setting. Here, the input is an arbitrary density operator ρ on (Cd )⊗n , and the goal is to output a pure state whose overlap with ρ is nearly as large as the best overlap achieved by a tensor network state in the target class. This is the natural TN analogue of closest-product-state and closest-MPS learning [Bak+25, LCH25]. For a graph G = ([n], E) and a bond dimension bound χ, define OPTG,χ (ρ) :=

sup

⟨ϕ|ρ|ϕ⟩.

(4.252)

|ϕ⟩∈Sd (G,χ)

An agnostic learner with accuracy ϵ must, with high success probability, output a pure state |ψ̂⟩ such that ⟨ψ̂|ρ|ψ̂⟩ ≥ OPTG,χ (ρ) − ϵ. (4.253) The output need not belong to Sd (G, χ), so we allow the learner to be improper: it may return a state from a larger efficiently described family. For pure states, trace norm and overlap are related by p ∥|ψ⟩⟨ψ| − |ϕ⟩⟨ϕ|∥1 = 2 1 − |⟨ψ|ϕ⟩|2 . (4.254) In the agnostic setting, error is measured by the additive loss in overlap in (4.253), following [Bak+25, LCH25]. When the input is pure, (4.254) relates this overlap to trace norm error. The main difference from the realisable setting is that the reduced states of ρ may have full rank. We retain a larger residual subsystem and show that each learned projection approximately preserves overlap with every reference TNS satisfying the relevant Schmidt-rank bound. The rank restriction is imposed on the reference state (and not on the input). 4.6.1

Projection estimates for agnostic learning

We first prove the projection estimate used throughout the agnostic analysis. Compared √ with [Bak+25, Lemma B.12], it improves the rank dependence from r to r by applying Cauchy–Schwarz to the positive semidefinite form induced by ρ. Lemma 4.40 (Agnostic projection bound). Let HA and HB be finite-dimensional Hilbert spaces, and let ρ ≥ 0 be a subnormalised state on HA ⊗ HB , with tr(ρ) ≤ 1. Let |ϕ⟩ ∈ HA ⊗ HB be a vector with ∥ϕ∥ ≤ 1 and Schmidt rank at most r across the

64

bipartition A | B. Let W ⊆ HA , let ΠW be the orthogonal projector onto W , and set Q = IA − ΠW . If ∥Q trB (ρ) Q∥∞ ≤ η, (4.255) then

√ |⟨ϕ|(ΠW ⊗ IB )ρ(ΠW ⊗ IB )|ϕ⟩ − ⟨ϕ|ρ|ϕ⟩| ≤ 2 rη.

(4.256)

More generally, the same conclusion holds with ΠW replaced by any orthogonal projector Π on HA whose range contains W , i.e., with Π ⊗ IB in place of ΠW ⊗ IB . Proof. We first prove the claim for P = ΠW ⊗ IB . Put R = Q ⊗ IB ,

|ζ⟩ = R|ϕ⟩,

a = ⟨ζ|ρ|ζ⟩.

(4.257)

e = |ζ⟩/∥ζ∥, and We claim that a ≤ rη. If |ζ⟩ = 0, this is immediate. Otherwise, let |ζ⟩ write a Schmidt decomposition e = |ζ⟩

s X p λj |aj ⟩|bj ⟩,

s ≤ r,

(4.258)

j=1

where the vectors |aj ⟩ lie in the range of Q. Define Mij = ⟨ai , bi |ρ|aj , bj ⟩.

(4.259)

The matrix M is positive semidefinite, being the Gram matrix of the vectors |aj , bj ⟩ with s respect to the positive semidefinite sesquilinear p v∈C , Ps form (x, y) 7→ ⟨x|ρ|y⟩: for every † we have v M v = ⟨w|ρ|w⟩ ≥ 0 with |w⟩ = j=1 vj |aj , bj ⟩. Hence |Mij | ≤ Mii Mjj . Therefore  2 s s s X X X p e ζ⟩ e ≤ ⟨ζ|ρ| λj Mjj  ≤ Mjj ≤ ⟨aj |Q trB (ρ) Q|aj ⟩ ≤ sη ≤ rη. (4.260) j=1

j=1

j=1

Since ∥ζ∥ ≤ ∥ϕ∥ ≤ 1, this gives a ≤ rη. Now use Cauchy–Schwarz for the positive semidefinite sesquilinear form (x, y) 7→ ⟨x|ρ|y⟩. Since P + R = I, ⟨ϕ|ρ|ϕ⟩ − ⟨ϕ|P ρP |ϕ⟩ = ⟨ϕ|ρR|ϕ⟩ + ⟨Rϕ|ρP |ϕ⟩.

(4.261)

Thus p p ⟨ϕ|ρ|ϕ⟩ a + a ⟨P ϕ|ρ|P ϕ⟩ √ √ ≤ 2 a ≤ 2 rη,

|⟨ϕ|ρ|ϕ⟩ − ⟨ϕ|P ρP |ϕ⟩| ≤

(4.262) (4.263)

because tr(ρ) ≤ 1 and ∥ϕ∥ ≤ 1. If Π is any projector on HA whose range contains W , then IA − Π ≤ Q in PSD order. Hence ∥(IA − Π) trB (ρ) (IA − Π)∥∞ ≤ η. (4.264) Repeating the same argument as above with IA − Π in place of Q gives the claimed generalisation. The next lemma derives the operator-norm condition in Lemma 4.40 from a tomography estimate. It is the agnostic counterpart of the top-eigenspace result used in the realisable analysis. 65

Lemma 4.41 (Top subspace from an approximate state). Let σ ≥ 0 be a subnormalised state on a D-dimensional Hilbert space, and let σ̂ ≥ 0 satisfy ∥σ − σ̂∥∞ ≤ γ.

(4.265)

Let 1 ≤ Λ < D, let W be the span of the eigenvectors associated with the Λ largest eigenvalues of σ̂, and let Q = I − ΠW . Then ∥QσQ∥∞ ≤

1 tr(σ) + 2γ ≤ + 2γ. Λ+1 Λ+1

(4.266)

If Λ ≥ D, then Q = 0 and the left-hand side is zero. Proof. Assume Λ < D. By Weyl’s inequality, λΛ+1 (σ̂) ≤ λΛ+1 (σ) + γ.

(4.267)

Since σ ≥ 0, λΛ+1 (σ) ≤

tr(σ) . Λ+1

(4.268)

For every unit vector |x⟩ ∈ W ⊥ , the variational characterisation of λΛ+1 (σ̂) gives ⟨x|σ̂|x⟩ ≤ λΛ+1 (σ̂). Therefore ⟨x|σ|x⟩ ≤ ⟨x|σ̂|x⟩ + ∥σ − σ̂∥∞ ≤

(4.269) tr(σ) + 2γ. Λ+1

(4.270)

Taking the supremum over unit vectors in W ⊥ proves the claim. Combining the two lemmas gives the one-step agnostic disentangling estimate used by the algorithm. Corollary 4.42 (One-step agnostic disentangling). Let ρ ≥ 0 be a subnormalised state on HA ⊗ HB , with tr(ρ) ≤ 1, and let |ϕ⟩ be a vector of norm at most one and Schmidt rank at most r across A | B. Let σA = trB (ρ),

(4.271)

∥σA − σ̂A ∥1 ≤ γ.

(4.272)

and suppose σ̂A ≥ 0 satisfies Let W be the span of the eigenvectors associated with the Λ largest eigenvalues of σ̂A . Let Π be any orthogonal projector on HA whose range contains W . Then s   1 |⟨ϕ|(Π ⊗ IB )ρ(Π ⊗ IB )|ϕ⟩ − ⟨ϕ|ρ|ϕ⟩| ≤ 2 r + 2γ . (4.273) Λ+1 Proof. The trace-norm estimate implies ∥σA − σ̂A ∥∞ ≤ γ. Apply Lemma 4.41 to bound the discarded operator norm, and then apply Lemma 4.40.

66

4.6.2

The agnostic sequence learner

We now adapt the sequence algorithm from Section 4.5 to the agnostic setting. Let L = (Si , Ii , Fi )L i=1 be a learning sequence for G. Set ri = χ| cutG (Si )| .

(4.274)

By Claim 2.17, every state in Sd (G, χ) has Schmidt rank at most ri across Si | [n] \ Si . When a weight function w is known and the reference class is restricted to Sd (G, w), one may instead use Y w(e). (4.275) ri = e∈cutG (Si )

This may give a smaller value of ri . The agnostic learner retains a larger residual subsystem than the realisable learner. Fix an overlap lower bound ϑ ∈ (0, 1], and assume that OPTG,χ (ρ) ≥ ϑ.

(4.276)

For ϵ ∈ (0, 1], define α2 . 128ri (4.277) The number Λi is the dimension of the learned top subspace, pi is the number of qudits retained after processing Si , and γi is the trace-norm accuracy of the corresponding subnormalised tomography call. Define also X agn aagn := |F | + pj , aagn rmax := max ri . (4.278) i max := max ai , i α :=

min{ϵ, ϑ} , 4L



Λi :=

j∈Ii

 64ri , α2

pi := max{1, ⌈logd Λi ⌉},

i∈[L]

γi :=

i∈[L]

The unitary in Algorithm 6 exists because Λi ≤ dpi = dim(HRi ). It is constructed by mapping an orthonormal basis of Wi isometrically into |0|Qi | ⟩Qi ⊗ HRi and extending the isometry to a unitary on HMi . The residual-subsystem invariant from Lemma 4.29 continues to hold with qi replaced by pi : after step i, the only qudits in Si that have not been projected onto |0⟩ are those in Ri , and |Ri | ≤ pi . Consequently X |Mi | ≤ aagn = |F | + pj . (4.279) i i j∈Ii

The proof is identical to the proof of Lemma 4.29. We also require a rank invariant for each reference TNS. Lemma 4.43 (Rank invariant for reference TNSs). Let |ϕ⟩ ∈ Sd (G, χ). Consider Algorithm 6, and suppose step i is about to be processed. Let K<i be the cumulative postselection map constructed so far, i.e., the map Kc for the value of the counter c at that moment. (As in Lemma 4.30, K<i ̸= Ki−1 in general, since trivial steps with |Mj | ≤ pj do not increment c.) Then the vector K<i |ϕ⟩, viewed across the bipartition Mi | [n] \ Mi , has Schmidt rank at most ri . 67

(4.280)

Algorithm 6 AgnosticLearnTNSFromSequence Input: graph G = ([n], E), bond dimension bound χ, physical dimension d ≥ 2, learning sequence L = (Si , Ii , Fi )L i=1 , copies of an arbitrary state ρ, accuracy parameter ϵ ∈ (0, 1], confidence parameter δ ∈ (0, 1), and lower-overlap parameter ϑ ∈ (0, 1] Output: Classical description of a pure state |ψ̂⟩. 1: Compute ri , Λi , pi , γi as in Equations (4.274) and (4.277). 2: K0 ← I, Q ← ∅, and c ← 0. 3: for i = 1 to L do S 4: Mi ← Fi ∪ j∈Ii Rj . 5: if |Mi | ≤ pi then 6: Ri ← Mi . 7: else 8: Choose Ri ⊆ Mi with |Ri | = pi . 9: Qi ← Mi \ Ri .
10: σ̂i ← Sub-Tomography Kc , Mi , d|Mi | , γi , δ/(2L + 2), [ϑ/2, 1] . 11: Let Wi be the span of the eigenvectors associated with the Λi largest eigenvalues of σ̂i . ei supported on Mi such that 12: Compute a unitary U ei Wi ⊆ |0|Qi | ⟩Q ⊗ HR . U i i 13: 14:

ei tensored with the identity outside Mi , Uc+1 = U ei ⊗ IM c . Let Uc+1 be U i Let Pc+1 = |0|Qi | ⟩⟨0|Qi | |Qi ⊗ I[n]\Qi .

Kc+1 ← Pc+1 Uc+1 Kc . Q ← Q ∪ Qi and c ← c + 1. 17: end if 18: end for 19: γfin ← ϵ/8.
20: τ̂ ← Sub-Tomography Kc , RL , d|RL | , γfin , δ/(2L + 2), [ϑ/2, 1] . 21: Let |φ̂⟩ be a top eigenvector of τ̂ . 22: return   |ψ̂⟩ = U1† U2† · · · Uc† |0|Q| ⟩Q ⊗ |φ̂⟩RL , 15:

16:

with the tensor product interpreted according to the canonical ordering of the qudits.

68

Proof. Since |ϕ⟩ ∈ Sd (G, χ), there exists a weight function wϕ : E → [χ] such that |ϕ⟩ ∈ Sd (G, wϕ ). By Claim 2.17, the Schmidt rank of |ϕ⟩ across Si | [n] \ Si is at most Y wϕ (e) ≤ χ| cutG (Si )| = ri . (4.281) e∈cutG (Si )

By Lemma 4.27, every earlier set Sj , with j < i, is either contained in Si or disjoint from Si . The operation associated with step j is supported on a subset of Sj . Hence every operation in K<i is local with respect to the bipartition Si | [n] \ Si , and local linear maps cannot increase Schmidt rank across this bipartition. Finally, by the residual-subsystem invariant, the qudits in Si \ Mi have already been projected onto the product state |0⟩Si \Mi . Removing this fixed product factor cannot increase the Schmidt rank. Therefore K<i |ϕ⟩ has Schmidt rank at most ri across Mi | [n] \ Mi . 4.6.3

Correctness

We first prove a deterministic statement conditioned on all tomography calls succeeding. Proposition 4.44 (Correctness of the agnostic sequence learner). Let ρ be an arbitrary n-qudit state, and suppose that OPTG,χ (ρ) ≥ ϑ. (4.282) Assume that every call to Sub-Tomography in Algorithm 6 succeeds with its stated tracenorm accuracy. Then the output state |ψ̂⟩ satisfies ⟨ψ̂|ρ|ψ̂⟩ ≥ OPTG,χ (ρ) − ϵ.

(4.283)

Moreover, each postselection map used by the algorithm has success probability at least ϑ/2. Proof. Set min{ϵ, ϑ} . 4 Fix a reference state |ϕ⟩ ∈ Sd (G, χ) satisfying β := Lα =

⟨ϕ|ρ|ϕ⟩ ≥ OPTG,χ (ρ) − β.

(4.284)

(4.285)

Such a reference state exists by the definition of the supremum in (4.252). Index the nontrivial disentangling steps by t = 1, . . . , c. Let Kt be the cumulative postselection map after the first t such steps, and define Bt := ⟨ϕ|Kt† Kt ρ Kt† Kt |ϕ⟩,

B0 = ⟨ϕ|ρ|ϕ⟩.

(4.286)

We now prove that Bt ≥ B0 − tα

(4.287)

for all t. Suppose the next nontrivial disentangling step processes the index i. Put ρt = Kt ρKt† ,

|ϕt ⟩ = Kt |ϕ⟩.

(4.288)

The reduced state learned by the algorithm is σi = tr[n]\Mi (ρt ). 69

(4.289)

By assumption, the tomography estimate satisfies ∥σi − σ̂i ∥1 ≤ γi .

(4.290)

By Lemma 4.43, the vector |ϕt ⟩ has Schmidt rank at most ri across the bipartition ei , the projection used at the current Mi | [n] \ Mi . In the coordinates before applying U step is   e † |0|Qi | ⟩⟨0|Qi | |Q ⊗ IR U ei Πi := U (4.291) i i i on Mi , tensored with the identity outside Mi . Its range on Mi contains Wi by definition ei . Corollary 4.42 now gives of U s   1 (4.292) |Bt+1 − Bt | ≤ 2 ri + 2γi . Λi + 1 Using the parameter choices in Equation (4.277), 1 α2 ≤ , Λi + 1 64ri and hence

2γi = r

α2 , 64ri

(4.293)

α2 < α. 32

(4.294)

Bc ≥ B0 − Lα = B0 − β.

(4.295)

|Bt+1 − Bt | ≤ 2 This proves (4.287) by induction. Since c ≤ L,

The same bound also implies the claimed lower bound on success probability. Indeed,   tr Kt ρKt† ≥ Bt ≥ B0 − Lα ≥ OPTG,χ (ρ) − 2β ≥ ϑ/2, (4.296) for every postselection map encountered by the algorithm. This justifies the success probability interval [ϑ/2, 1] used in the tomography calls. We note that this is the only place in the correctness argument where ϑ enters: the last inequality requires 2β ≤ ϑ/2, and this is precisely why the parameter α = min{ϵ, ϑ}/(4L) carries the minimum with ϑ, whereas the accuracy guarantee below uses only β ≤ ϵ/4. It remains to analyse the final residual step. As in the realisable learners, the residual-subsystem invariant implies that Kc = PQ U≤c , U≤c = Uc Uc−1 · · · U1 , PQ = |0|Q| ⟩⟨0|Q| |Q ⊗ IRL , (4.297) F where Q = i: |Mi |>pi Qi is the final value of the projected set maintained by Algorithm 6. Let h i τ = tr[n]\RL Kc ρKc† (4.298) be the ideal final residual state. Since PQ is an orthogonal projector and U≤c is unitary, † Kc† Kc = U≤c PQ U≤c

(4.299)

is an orthogonal projector. As PQ projects the qubits in [n] \ RL into the all-zero state, Kc ρKc† = 0|Q| 0|Q| Q ⊗ τRL , so the largest eigenvalue of τ equals the largest eigenvalue

70

of Kc ρKc† , which is the maximum of ⟨ξ|ρ|ξ⟩ over normalised states |ξ⟩ in the range of the projection Kc† Kc . Moreover, Bc = ⟨ϕ|Kc† Kc ρKc† Kc |ϕ⟩.

(4.300)

Normalising the subnormalised vector Kc† Kc |ϕ⟩, if it is nonzero, shows that λmax (τ ) ≥ Bc /∥Kc† Kc |ϕ⟩∥2 ≥ Bc .

(4.301)

The final tomography call gives ∥τ − τ̂ ∥1 ≤ γfin , where γfin = ϵ/8. If |φ̂⟩ is a top eigenvector of τ̂ , then the variational principle gives ⟨φ̂|τ |φ̂⟩ ≥ λmax (τ ) − 2γfin .

(4.302)

The state returned by the algorithm is   † |ψ̂⟩ = U≤c |0|Q| ⟩Q ⊗ |φ̂⟩RL ,

(4.303)

⟨ψ̂|ρ|ψ̂⟩ = ⟨φ̂|τ |φ̂⟩.

(4.304)

and Combining Equations (4.285), (4.295), (4.301), (4.302), and (4.304), we obtain ⟨ψ̂|ρ|ψ̂⟩ ≥ OPTG,χ (ρ) − 2β − 2γfin ≥ OPTG,χ (ρ) − ϵ,

(4.305)

because 2β ≤ ϵ/2 and 2γfin = ϵ/4. This proves the proposition. Theorem 4.45 (Agnostic tomography from a learning sequence). Let G = ([n], E) be a graph with bond dimension bound χ, and let L = (Si , Ii , Fi )L i=1 be a learning sequence for G. Let ρ be an arbitrary n-qudit state satisfying OPTG,χ (ρ) ≥ ϑ

(4.306)

for a known ϑ ∈ (0, 1]. Then Algorithm 6 outputs a pure state |ψ̂⟩ satisfying ⟨ψ̂|ρ|ψ̂⟩ ≥ OPTG,χ (ρ) − ϵ with probability at least 1 − δ, using   agn  2 L5 rmax 2amax O d + log(L/δ) ϑ min{ϵ, ϑ}4

(4.307)

(4.308)

copies, where rmax and aagn max are defined in Equation (4.278). The classical postprocessing agn time is polynomial in L, damax , maxi Λi , 1/ϵ, 1/ϑ, and log(1/δ), assuming the full-rank tomography primitive and the relevant eigendecompositions are implemented in time polynomial in their input dimension. Proof. The lower bound on success probability used in each call is valid inductively: conditioned on all previous tomography   calls succeeding, the proof of Proposition 4.44 up to the current step gives tr Kc ρKc† ≥ ϑ/2. Thus each subnormalised tomography call has the advertised guarantee. There are at most L nontrivial disentangling calls and one final residual call. Each call is assigned failure probability δ/(2L + 2), so

71

a union bound gives total failure probability at most δ. Conditioned on this event, Proposition 4.44 gives the claimed overlap guarantee. It remains to count copies. At a disentangling step i, the state being learned is an arbitrary subnormalised state on |Mi | qudits. This allows us to invoke the full-rank case of the subnormalised tomography primitive from Section 4.1, with rank parameter d|Mi | and Hilbert space dimension d|Mi | . Since the success probability is lower bounded by ϑ/2, Corollary 4.5 gives copy complexity ! d2|Mi | + log(L/δ) O (4.309) ϑγi2 for this call. By (4.279), |Mi | ≤ aagn max , and by (4.277),   2 rmax L4 1 (128ri )2 . ≤O = α4 min{ϵ, ϑ}4 γi2

(4.310)

Multiplying by at most L disentangling calls gives the stated bound. The final residual tomography call acts on at most aagn max qudits and has accuracy ϵ/8. Its cost is absorbed into (4.308) for L ≥ 1, rmax ≥ 1, and ϵ, ϑ ≤ 1. The runtime statement follows from the dimensions of the matrices on which tomography and eigendecomposition are performed. Remark 4.46. The theorem assumes a known lower bound ϑ ≤ OPTG,χ (ρ). This parameter is used only to lower-bound the success probabilities of the postselected branches. If no such bound is known, one can run the algorithm over a geometric grid of candidate values for ϑ and validate the final candidates by estimating ⟨ψ̂|ρ|ψ̂⟩. This adds only logarithmic overhead in the grid size, but we keep ϑ explicit in the theorem statements. 4.6.4

Applications

We first specialise the agnostic theorem to learning sequences obtained from contraction sequences. Corollary 4.47 (Agnostic tomography from contraction complexity). Let G = ([n], E) be a connected graph with bond dimension bound χ, and let C = cc(G) be its contraction complexity. Suppose ρ is an arbitrary n-qudit state satisfying OPTG,χ (ρ) ≥ ϑ. Given a contraction sequence of complexity C, one can output |ψ̂⟩ such that ⟨ψ̂|ρ|ψ̂⟩ ≥ OPTG,χ (ρ) − ϵ with probability at least 1 − δ, using  
n5 χ2C 4pC O d + log(n/δ) ϑ min{ϵ, ϑ}4

(4.311)

(4.312)

copies, where     2048n2 χC pC := max 1, logd . min{ϵ, ϑ}2

(4.313)

Using Theorem 2.6, one may take C ≤ ∆(G)(tw(G) + 1) − 1, after computing a contraction sequence with this width bound. 72

(4.314)

Proof. By Lemma 4.33, a contraction sequence of complexity C induces a learning sequence of length L ≤ n − 1 satisfying | cutG (Si )| ≤ C for every i. Hence ri ≤ χC and rmax ≤ χC . Since min{ϵ, ϑ} min{ϵ, ϑ} α= ≥ , (4.315) 4L 4n we have   64ri 1024 ri n2 2048 ri n2 Λi = ≤ + 1 ≤ , (4.316) α2 min{ϵ, ϑ}2 min{ϵ, ϑ}2 and hence, using ri ≤ χC , we get pi ≤ pC for all i. Each contraction step combines two current vertices. Each current vertex contributes either one fresh physical qudit or one residual subsystem of size at most pC . Since pC ≥ 1, every step has aagn ≤ 2pC . i

(4.317)

Substituting L ≤ n, rmax ≤ χC , and aagn max ≤ 2pC into Theorem 4.45 proves (4.312). The statement in terms of treewidth and degree follows from Theorem 2.6. Agnostic TTN state tomography is obtained as a special case by using the learning sequence built from rooted subtrees that is implicit in Section 4.3. Corollary 4.48 (Agnostic TTN tomography). Let T be a tree on n vertices with maximum degree ∆ = ∆(T ), and let ρ be an arbitrary n-qudit state satisfying OPTT,χ (ρ) :=

sup

⟨ϕ|ρ|ϕ⟩ ≥ ϑ.

(4.318)

|ϕ⟩∈Sd (T,χ)

Then one can output |ψ̂⟩ satisfying ⟨ψ̂|ρ|ψ̂⟩ ≥ OPTT,χ (ρ) − ϵ with probability at least 1 − δ, using    n 5 χ2 2(1+bpT ) O d + log(n/δ) ϑ min{ϵ, ϑ}4

(4.319)

(4.320)

copies, where b is the maximum number of children after rooting T at a leaf and     2048n2 χ pT := max 1, logd . (4.321) min{ϵ, ϑ}2 For n ≥ 3, one may take b ≤ ∆ − 1. Proof. Use the learning sequence whose sets are the rooted subtrees of T , ordered from leaves to root. Every set in this sequence other than the final one is a rooted subtree Tu with u ̸= r and is separated from its complement by the single edge joining u to its parent, so ri ≤ χ for these sets. The final set is all of V , whose cut is empty, so rL = 1. The length is at most n. Since α ≥ min{ϵ, ϑ}/(4n) and ri ≤ χ, the estimate from the proof of Corollary 4.47 gives Λi ≤ 2048 χn2 / min{ϵ, ϑ}2 and hence pi ≤ pT for all i. At any step, the learner acts on the parent vertex together with the residual subsystems of its children, so aagn ≤ 1 + bpT . (4.322) i Substituting L ≤ n, rmax ≤ χ, and aagn max ≤ 1 + bpT into Theorem 4.45 proves the stated bound. The degree statement follows from the rooting convention used in Algorithm 4.

73

Remark 4.49 (Comparison with closest product state and closest MPS learning). Bakshi et al. [Bak+25] give a proper closest-product-state learner and, in Appendix B, an improper closest-MPS learner. Their MPS guarantee uses MPSs of a given bond dimension as the reference class, while the output may have larger bond dimension. Lin, Chia, and Hung [LCH25] also give an improper closest-MPS learner, with better dependence on the system size and logarithmic reconstruction depth. Theorem 4.45 allows an arbitrary known graph, while Corollary 4.48 gives the tree case. Our result extends the available graph families from edgeless graphs and paths to trees and arbitrary known graphs. The closest-product-state learner of [Bak+25] is proper. Their MPS extension, the MPS learner of [LCH25], and our general-graph learner may return states outside the corresponding reference class and are improper. All these results use an overlap guarantee of the form (4.253). The path case gives a different tradeoff from [LCH25]. Specialising Corollary 4.48 to a path gives at most   d4 χ4 n9 e O (4.323) ϑ min{ϵ, ϑ}8 copies and a reconstruction circuit of depth linear in n. The closest-MPS learner of e 7 D12 /ϵ12 ) copies and has logarithmic depth, improving the dependence [LCH25] uses O(n on n at the cost of a worse dependence on the bond dimension and accuracy. Thus our path specialisation does not improve the system-size dependence or circuit depth, but neither bound uniformly dominates the other. The difference has three sources: the retained dimension Λi is of order ri /α2 rather than ri because no rank is assumed on the input, the sequential schedule forces α = min{ϵ, ϑ}/(4L) with L ≤ n, and every tomography call runs at the full-rank rate d2|Mi | . Compared with [Bak+25], our result covers a broader family of reference TNSs and uses a sharper projection estimate. Lemma 4.40 improves [Bak+25, Lemma B.12] from √ √ 2r η to 2 rη. The two estimates agree for product states, where r = 1. For general graphs, the sharper estimate saves a factor of ri in the retained dimension. The weaker estimate would require Λi of order ri2 /α2 , doubling the exponent of χ arising from | cutG (Si )| in every residual register.

74

Acknowledgements We thank Václav Blažej for collating information on graph parameters through the HOPS project [Bc], and Václav Blažej and Ramanujan Sridharan for helpful discussions of parameterised complexity. We also thank Nikhil Bansil, Neha Rino, Jedrzej Olkowski, Peter Strulo, Rafid Ameer Mahmud and Hirak Ghosh for helpful discussions. NM acknowledges support from the EPSRC DTP 2224 University of Warwick (Grant number EP/W524645/1). SS acknowledges support from the Wellcome Leap as part of the Q4Bio Program and the Royal Society University Research Fellowship. No AI tools were used in writing this paper.

75

References [ACQ22]

Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi. “Quantum algorithmic measurement”. In: Nature Communications 13.1 (2022), pp. 1–9. doi: 10. 1038/s41467-021-27922-0 (cited on p. 11).

[AD25]

Srinivasan Arunachalam and Arkopal Dutt. “Polynomial-Time Tolerant Testing Stabilizer States”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC ’25. Prague, Czechia: Association for Computing Machinery, 2025, pp. 1234–1241. isbn: 9798400715105. doi: 10.1145/3717823.3718277. url: https://doi.org/10.1145/3717823. 3718277 (cited on p. 11).

[AG04]

Scott Aaronson and Daniel Gottesman. “Improved simulation of stabilizer circuits”. In: Physical Review A—Atomic, Molecular, and Optical Physics 70.5 (2004), p. 052328. doi: 10 . 1103 / PhysRevA . 70 . 052328 (cited on p. 10).

[AG08]

Scott Aaronson and Daniel Gottesman. Identifying Stabilizer States. en. PIRSA:08080052 see, https : / / pirsa . org. Aug. 2008. doi: 10 . 48660 / 08080052. url: https://pirsa.org/08080052 (cited on p. 10).

[AG23]

Scott Aaronson and Sabee Grewal. “Efficient Tomography of NonInteracting-Fermion States”. In: 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Ed. by Omar Fawzi and Michael Walter. Vol. 266. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, 12:1–12:18. isbn: 978-3-95977-283-9. doi: 10.4230/LIPIcs.TQC.2023.12. url: https://drops.dagstuhl.de/ entities/document/10.4230/LIPIcs.TQC.2023.12 (cited on p. 10).

[AL10]

Itai Arad and Zeph Landau. “Quantum computation and the evaluation of tensor networks”. In: SIAM Journal on Computing 39.7 (2010), pp. 3089– 3121. doi: 10.1137/080739379 (cited on pp. 3, 9).

[Ali+25]

Maryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, and Yuhan Liu. Adversarially robust quantum state learning and testing. 2025. arXiv: 2508. 13959 [quant-ph]. url: https://arxiv.org/abs/2508.13959 (cited on p. 11).

[Ayr+23]

Thomas Ayral, Thibaud Louvet, Yiqing Zhou, Cyprien Lambert, E Miles Stoudenmire, and Xavier Waintal. “Density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity”. In: PRX Quantum 4.2 (2023), p. 020304. doi: 10 . 1103 / PRXQuantum . 4 . 020304 (cited on pp. 3, 12).

[Bak+24]

Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. “Structure Learning of Hamiltonians from Real-Time Evolution”. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). 2024, pp. 1037– 1050. doi: 10.1109/FOCS61266.2024.00069 (cited on p. 10).

76

[Bak+25]

Ainesh Bakshi, John Bostanci, William Kretschmer, Zeph Landau, Jerry Li, Allen Liu, Ryan O’Donnell, and Ewin Tang. “Learning the Closest Product State”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC ’25. Prague, Czechia: Association for Computing Machinery, 2025, pp. 1212–1221. isbn: 9798400715105. doi: 10.1145/ 3717823.3718207. url: https://doi.org/10.1145/3717823.3718207 (cited on pp. 1, 3, 9, 64, 74).

[Bc]

Václav Blažej and contributors. Hierarchy of Parameters (HOPS). https: //vaclavblazej.github.io/parameters/ (cited on p. 75).

[BC17]

Jacob C. Bridgeman and Christopher T. Chubb. “Hand-waving and interpretive dance: an introductory course on tensor networks”. In: Journal of Physics A: Mathematical and Theoretical 50.22 (2017), p. 223001. doi: 10.1088/1751-8121/aa6dc3 (cited on p. 19).

[BCO26]

Andreas Bluhm, Matthias C. Caro, and Aadil Oufkir. Hamiltonian Property Testing. 2026. arXiv: 2403.02968 [quant-ph]. url: https://arxiv.org/ abs/2403.02968 (cited on pp. 10, 11).

[BDH25]

Zongbo Bao, Philippe van Dordrecht, and Jonas Helsen. Tolerant testing of stabilizer states with a polynomial gap via a generalized uncertainty relation. 2025. arXiv: 2410.21811 [quant-ph]. url: https://arxiv.org/abs/ 2410.21811 (cited on p. 11).

[Bec+25]

Jacob Beckey, Luke Coffman, Ariel Shlosberg, Louis Schatzki, and Felix Leditzky. Product testing with single-copy measurements. 2025. arXiv: 2510 . 07820 [quant-ph]. url: https : / / arxiv . org / abs / 2510 . 07820 (cited on p. 11).

[BG16]

Sergey Bravyi and David Gosset. “Improved classical simulation of quantum circuits dominated by Clifford gates”. In: Physical review letters 116.25 (2016), p. 250501. doi: 10 . 1103 / PhysRevLett . 116 . 250501 (cited on p. 10).

[Bit+25a]

Lennart Bittel, Antonio Anna Mele, Jens Eisert, and Lorenzo Leone. “Optimal Trace-Distance Bounds for Free-Fermionic States: Testing and Improved Tomography”. In: PRX Quantum 6 (3 Sept. 2025), p. 030341. doi: 10.1103/pzx6-nkfb. url: https://link.aps.org/doi/10.1103/pzx6nkfb (cited on p. 10).

[Bit+25b]

Lennart Bittel, Francesco A. Mele, Jens Eisert, and Antonio A. Mele. Energy-independent tomography of Gaussian states. 2025. arXiv: 2508 . 14979 [quant-ph]. url: https : / / arxiv . org / abs / 2508 . 14979 (cited on p. 10).

[Bit+25c]

Lennart Bittel, Francesco Anna Mele, Antonio Anna Mele, Salvatore Tirone, and Ludovico Lami. “Optimal estimates of trace distance between bosonic Gaussian states and applications to learning”. In: Quantum 9 (June 2025), p. 1769. issn: 2521-327X. doi: 10.22331/q-2025-06-12-1769. url: https://doi.org/10.22331/q-2025-06-12-1769 (cited on p. 10).

[Blu+25]

Andreas Bluhm, Matthias C. Caro, Francisco Escudero Gutiérrez, Aadil Oufkir, and Cambyse Rouzé. Certifying and learning quantum Ising Hamiltonians. 2025. arXiv: 2509.10239 [quant-ph]. url: https://arxiv.org/ abs/2509.10239 (cited on p. 11). 77

[BOW19]

Costin Bădescu, Ryan O’Donnell, and John Wright. “Quantum state certification”. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC 2019. Phoenix, AZ, USA: Association for Computing Machinery, 2019, pp. 503–514. isbn: 9781450367059. doi: 10.1145/3313276.3316344. url: https://doi.org/10.1145/3313276. 3316344 (cited on p. 11).

[Bre15]

Guy Bresler. “Efficiently Learning Ising Models on Arbitrary Graphs”. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC ’15. Portland, Oregon, USA: Association for Computing Machinery, 2015, pp. 771–782. isbn: 9781450335362. doi: 10 . 1145 / 2746539.2746631. url: https://doi.org/10.1145/2746539.2746631 (cited on p. 10).

[BSV14]

Sergey Bravyi, Martin Suchara, and Alexander Vargo. “Efficient algorithms for maximum likelihood decoding in the surface code”. In: Physical Review A 90.3 (2014), p. 032326. doi: 10.1103/PhysRevA.90.032326 (cited on p. 3).

[BY25]

Zongbo Bao and Penghui Yao. “On Testing and Learning Quantum Junta Channels”. In: IEEE Transactions on Pattern Analysis and Machine Intelligence 47.4 (2025), pp. 2991–3002. doi: 10.1109/TPAMI.2025.3528648 (cited on p. 11).

[Cer+25]

Marco Cerezo, Martin Larocca, Diego Garcı́a-Martı́n, Nelson L Diaz, Paolo Braccia, Enrico Fontana, Manuel S Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, et al. “Does provable absence of barren plateaus imply classical simulability?” In: Nature Communications 16.1 (2025), p. 7907. doi: 10.1038/s41467-025-63099-6 (cited on p. 10).

[Che+23]

Sitan Chen, Brice Huang, Jerry Li, Allen Liu, and Mark Sellke. “When Does Adaptivity Help for Quantum State Learning?” In: 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS). 2023, pp. 391–404. doi: 10.1109/FOCS57990.2023.00029 (cited on p. 30).

[Che+25]

Bin Cheng, Ziyuan Wang, Ruixuan Deng, Jianxin Chen, and Zhengfeng Ji. Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams. 2025. arXiv: 2510 . 06775 [quant-ph]. url: https : //arxiv.org/abs/2510.06775 (cited on pp. 9, 10).

[Chu85]

Fan R. K. Chung. “On the Cutwidth and the Topological Bandwidth of a Tree”. In: SIAM Journal on Algebraic Discrete Methods 6.2 (1985), pp. 268– 277. doi: 10.1137/0606026. eprint: https://doi.org/10.1137/0606026. url: https://doi.org/10.1137/0606026 (cited on p. 15).

[Cir+21]

J. Ignacio Cirac, David Pérez-Garcı́a, Norbert Schuch, and Frank Verstraete. “Matrix product states and projected entangled pair states: Concepts, symmetries, theorems”. In: Reviews of Modern Physics 93.4 (Dec. 2021). issn: 1539-0756. doi: 10.1103/revmodphys.93.045003. url: http: //dx.doi.org/10.1103/RevModPhys.93.045003 (cited on p. 17).

[CLL24]

Sitan Chen, Jerry Li, and Allen Liu. “An Optimal Tradeoff between Entanglement and Copy Complexity for State Tomography”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC 2024. Vancouver, BC, Canada: Association for Computing Machinery, 2024, 78

pp. 1331–1342. isbn: 9798400703836. doi: 10 . 1145 / 3618260 . 3649704. url: https://doi.org/10.1145/3618260.3649704 (cited on p. 30). [CNS25]

Matthias C. Caro, Preksha Naik, and Joseph Slote. Testing classical properties from quantum data. 2025. arXiv: 2411.12730 [quant-ph]. url: https: //arxiv.org/abs/2411.12730 (cited on p. 11).

[CNY]

Thomas Chen, Shivam Nadimpalli, and Henry Yuen. “Testing and Learning Quantum Juntas Nearly Optimally”. In: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1163–1185. doi: 10.1137/1.9781611977554.ch43. eprint: https://epubs.siam.org/ doi/pdf/10.1137/1.9781611977554.ch43. url: https://epubs.siam. org/doi/abs/10.1137/1.9781611977554.ch43 (cited on p. 11).

[Cra+10]

Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Landon-Cardinal, David Poulin, and Yi-Kai Liu. “Efficient quantum state tomography”. In: Nature Communications 1.1 (Dec. 2010). issn: 2041-1723. doi: 10.1038/ncomms1147. url: http://dx.doi.org/10.1038/ncomms1147 (cited on pp. 1, 3, 6, 8–10, 32, 35).

[CS24]

Josh Cudby and Sergii Strelchuk. “Learning Gaussian Operations and the Matchgate Hierarchy”. In: 2024 IEEE International Conference on Quantum Computing and Engineering (QCE). Vol. 01. 2024, pp. 141–149. doi: 10.1109/QCE60285.2024.00026 (cited on p. 10).

[CS25]

Joshua Cudby and Sergii Strelchuk. Gaussian decomposition of magic states for matchgate computations. 2025. arXiv: 2307.12654 [quant-ph]. url: https://arxiv.org/abs/2307.12654 (cited on p. 10).

[Cyg+15]

Marek Cygan, Fedor V Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized algorithms. Vol. 5. 4. Springer, 2015. doi: 10.1007/978- 3- 31921275-3 (cited on p. 13).

[DDV20]

Jeffrey M. Dudek, Leonardo Dueñas-Osorio, and Moshe Y. Vardi. Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions. 2020. arXiv: 1908 . 04381 [cs.DS]. url: https://arxiv.org/abs/1908.04381 (cited on p. 9).

[DK24a]

Beatriz Dias and Robert Koenig. “Classical simulation of non-Gaussian fermionic circuits”. In: Quantum 8 (May 2024), p. 1350. issn: 2521-327X. doi: 10.22331/q-2024-05-21-1350. url: https://doi.org/10.22331/ q-2024-05-21-1350 (cited on p. 10).

[DK24b]

Beatriz Dias and Robert König. “Classical simulation of non-Gaussian bosonic circuits”. In: Physical Review A 110.4 (2024), p. 042402. doi: 10. 1103/PhysRevA.110.042402 (cited on p. 10).

[Dum+18]

Eugene F Dumitrescu, Allison L Fisher, Timothy D Goodrich, Travis S Humble, Blair D Sullivan, and Andrew L Wright. “Benchmarking treewidth as a practical component of tensor network simulations”. In: PloS one 13.12 (2018), e0207827. doi: 10.1371/journal.pone.0207827 (cited on pp. 9, 12).

79

[Fan+25]

Marco Fanizza, Vishnu Iyer, Junseo Lee, Antonio A. Mele, and Francesco A. Mele. Efficient learning of bosonic Gaussian unitaries. 2025. arXiv: 2510. 05531 [quant-ph]. url: https://arxiv.org/abs/2510.05531 (cited on p. 10).

[FO24]

Steven T. Flammia and Ryan O’Donnell. “Quantum chi-squared tomography and mutual information testing”. In: Quantum 8 (June 2024), p. 1381. issn: 2521-327X. doi: 10 . 22331 / q - 2024 - 06 - 20 - 1381. url: https : //doi.org/10.22331/q-2024-06-20-1381 (cited on p. 11).

[Gao+25]

Minbo Gao, Zhengfeng Ji, Qisheng Wang, Wenjun Yu, and Qi Zhao. Quantum Hamiltonian Certification. 2025. arXiv: 2505.13217 [quant-ph]. url: https://arxiv.org/abs/2505.13217 (cited on p. 11).

[GC24]

Johnnie Gray and Garnet Kin-Lic Chan. “Hyperoptimized approximate contraction of tensor networks with arbitrary geometry”. In: Physical Review X 14.1 (2024), p. 011009. doi: 10.1103/PhysRevX.14.011009 (cited on pp. 9, 12).

[GE07]

David Gross and Jens Eisert. “Novel schemes for measurement-based quantum computation”. In: Physical review letters 98.22 (2007), p. 220503. doi: 10.1103/PhysRevLett.98.220503 (cited on p. 3).

[Gir+25]

Filippo Girardi, Freek Witteveen, Francesco Anna Mele, Lennart Bittel, Salvatore F. E. Oliviero, David Gross, and Michael Walter. Is it Gaussian? Testing bosonic quantum states. 2025. arXiv: 2510.07305 [quant-ph]. url: https://arxiv.org/abs/2510.07305 (cited on p. 11).

[GK21]

Johnnie Gray and Stefanos Kourtis. “Hyper-optimized tensor network contraction”. In: Quantum 5 (2021), p. 410. doi: 10.22331/q-2021-03-15410 (cited on pp. 3, 9, 12).

[GNW21]

David Gross, Sepehr Nezami, and Michael Walter. “Schur–Weyl duality for the Clifford group with applications: Property testing, a robust Hudson theorem, and de Finetti representations”. In: Communications in Mathematical Physics 385.3 (2021), pp. 1325–1393. doi: 10.1007/s00220-021-04118-7 (cited on p. 11).

[Got98]

Daniel Gottesman. The Heisenberg Representation of Quantum Computers. 1998. arXiv: quant-ph/9807006 [quant-ph]. url: https://arxiv.org/ abs/quant-ph/9807006 (cited on p. 10).

[Gra10]

Lars Grasedyck. “Hierarchical singular value decomposition of tensors”. In: SIAM journal on matrix analysis and applications 31.4 (2010), pp. 2029– 2054. doi: 10.1137/090764189 (cited on p. 12).

[Gre+24]

Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. “Improved Stabilizer Estimation via Bell Difference Sampling”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. STOC 2024. Vancouver, BC, Canada: Association for Computing Machinery, 2024, pp. 1352–1363. isbn: 9798400703836. doi: 10 . 1145 / 3618260 . 3649738. url: https://doi.org/10.1145/3618260.3649738 (cited on p. 11).

80

[Gre+25]

Sabee Grewal, Vishnu Iyer, William Kretschmer, and Daniel Liang. “Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates”. In: Quantum 9 (Nov. 2025), p. 1907. issn: 2521-327X. doi: 10.22331/q2025- 11- 06- 1907. url: https://doi.org/10.22331/q- 2025- 11- 061907 (cited on p. 10).

[Gun+18]

Klaas Gunst, Frank Verstraete, Sebastian Wouters, Ors Legeza, and Dimitri Van Neck. “T3NS: Three-legged tree tensor network states”. In: Journal of chemical theory and computation 14.4 (2018), pp. 2026–2033. doi: 10.1021/ acs.jctc.8b00098 (cited on p. 12).

[Haa+17]

Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu. “Sample-optimal tomography of quantum states”. In: IEEE Transactions on Information Theory (2017), pp. 1–1. issn: 1557-9654. doi: 10 . 1109/tit.2017.2719044. url: http://dx.doi.org/10.1109/TIT.2017. 2719044 (cited on p. 30).

[Has+21]

Meraj Hashemizadeh, Michelle Liu, Jacob Miller, and Guillaume Rabusseau. Adaptive Learning of Tensor Network Structures. 2021. arXiv: 2008.05437 [cs.LG]. url: https://arxiv.org/abs/2008.05437 (cited on pp. 3, 9).

[HH25]

Marcel Hinsche and Jonas Helsen. “Single-Copy Stabilizer Testing”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC ’25. Prague, Czechia: Association for Computing Machinery, 2025, pp. 439–450. isbn: 9798400715105. doi: 10.1145/3717823.3718169. url: https://doi.org/10.1145/3717823.3718169 (cited on p. 11).

[HM13]

Aram W. Harrow and Ashley Montanaro. “Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization”. In: J. ACM 60.1 (Feb. 2013). issn: 0004-5411. doi: 10.1145/2432622.2432625. url: https: //doi.org/10.1145/2432622.2432625 (cited on pp. 3, 11).

[Hu+25]

Hong-Ye Hu, Muzhou Ma, Weiyuan Gong, Qi Ye, Yu Tong, Steven T. Flammia, and Susanne F. Yelin. “Ansatz-Free Hamiltonian Learning with Heisenberg-Limited Scaling”. In: PRX Quantum 6 (4 Oct. 2025), p. 040315. doi: 10.1103/j7b8-pb77. url: https://link.aps.org/doi/10.1103/ j7b8-pb77 (cited on p. 10).

[IL25]

Vishnu Iyer and Daniel Liang. Tolerant Testing of Stabilizer States with Mixed State Inputs. 2025. arXiv: 2411 . 08765 [quant-ph]. url: https : //arxiv.org/abs/2411.08765 (cited on p. 11).

[Iye25]

Vishnu Iyer. Mildly-Interacting Fermionic Unitaries are Efficiently Learnable. 2025. arXiv: 2504.11318 [quant-ph]. url: https://arxiv.org/ abs/2504.11318 (cited on p. 10).

[JAW19]

J. Jakes-Schauer, D. Anekstein, and P. Wocjan. Carving-width and contraction trees for tensor networks. 2019. arXiv: 1908.11034 [cs.DM]. url: https://arxiv.org/abs/1908.11034 (cited on p. 9).

[Jun08]

Dieter Jungnickel. Graphs, networks and algorithms. Springer, 2008. doi: 10.1007/978-3-642-32278-5 (cited on p. 13).

81

[Kim+18]

Eun Jung Kim, Sang-il Oum, Christophe Paul, Ignasi Sau, and Dimitrios M. Thilikos. “An FPT 2-Approximation for Tree-Cut Decomposition”. In: Algorithmica 80.1 (Jan. 2018), pp. 116–135. issn: 1432-0541. doi: 10.1007/ s00453- 016- 0245- 5. url: https://doi.org/10.1007/s00453- 0160245-5 (cited on pp. 12, 17).

[KL23]

Tuukka Korhonen and Daniel Lokshtanov. An Improved Parameterized Algorithm for Treewidth. 2023. arXiv: 2211 . 07154 [cs.DS]. url: https : //arxiv.org/abs/2211.07154 (cited on p. 15).

[KL25]

John Kallaugher and Daniel Liang. “Hamiltonian Locality Testing via Trotterized Postselection”. In: 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Ed. by Bill Fefferman. Vol. 350. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, 10:1–10:20. isbn: 978-3-95977-392-8. doi: 10 . 4230 / LIPIcs . TQC . 2025.10. url: https://drops.dagstuhl.de/entities/document/10. 4230/LIPIcs.TQC.2025.10 (cited on p. 11).

[KM17]

Adam Klivans and Raghu Meka. “Learning Graphical Models Using Multiplicative Weights”. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 2017, pp. 343–354. doi: 10 . 1109 / FOCS . 2017.39 (cited on p. 10).

[LC22]

Ching-Yi Lai and Hao-Chung Cheng. “Learning Quantum Circuits of Some T Gates”. In: IEEE Transactions on Information Theory 68.6 (2022), pp. 3951–3964. doi: 10.1109/TIT.2022.3151760 (cited on p. 10).

[LCH25]

Chia-Ying Lin, Nai-Hui Chia, and Shih-Han Hung. Efficient Closest Matrix Product State Learning in Logarithmic Depth. 2025. arXiv: 2510 . 07798 [quant-ph]. url: https://arxiv.org/abs/2510.07798 (cited on pp. 1, 3, 9, 35, 38, 43, 50, 64, 74).

[LL24]

Benjamin Lovitz and Angus Lowe. Nearly tight bounds for testing tree tensor network states. 2024. arXiv: 2410.21417 [quant-ph]. url: https://arxi v.org/abs/2410.21417 (cited on pp. 11, 12).

[LLP10]

Olivier Landon-Cardinal, Yi-Kai Liu, and David Poulin. Efficient Direct Tomography for Matrix Product States. 2010. arXiv: 1002.4632 [quant-ph]. url: https://arxiv.org/abs/1002.4632 (cited on pp. 3, 6, 9, 10).

[LOH24]

Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. “Learning t-doped stabilizer states”. In: Quantum 8 (May 2024), p. 1361. issn: 2521327X. doi: 10.22331/q-2024-05-27-1361. url: https://doi.org/10. 22331/q-2024-05-27-1361 (cited on p. 10).

[Low09]

Richard A Low. “Learning and testing algorithms for the Clifford group”. In: Physical Review A—Atomic, Molecular, and Optical Physics 80.5 (2009), p. 052314. doi: 10.1103/PhysRevA.80.052314 (cited on pp. 10, 11).

[LS03]

Örs Legeza and Jeno Sólyom. “Optimizing the density-matrix renormalization group method using quantum information entropy”. In: Physical Review B 68.19 (2003), p. 195116. doi: 10.1103/PhysRevB.68.195116 (cited on p. 12).

82

[LS25]

Junseo Lee and Myeongjin Shin. Optimal certification of constant-local Hamiltonians. 2025. arXiv: 2512.09778 [quant-ph]. url: https://arxiv. org/abs/2512.09778 (cited on p. 11).

[LTW26]

Laura Lewis, Ewin Tang, and John Wright. Learning the structure of open quantum systems. 2026. arXiv: 2606.30358 [quant-ph]. url: https:// arxiv.org/abs/2606.30358 (cited on p. 10).

[LW22]

Margarite L LaBorde and Mark M Wilde. “Quantum algorithms for testing Hamiltonian symmetry”. In: Physical Review Letters 129.16 (2022), p. 160503. doi: 10.1103/PhysRevLett.129.160503 (cited on p. 11).

[Mel+25]

Francesco A Mele, Antonio A Mele, Lennart Bittel, Jens Eisert, Vittorio Giovannetti, Ludovico Lami, Lorenzo Leone, and Salvatore FE Oliviero. “Learning quantum states of continuous-variable systems”. In: Nature Physics (2025), pp. 1–7. doi: 10.1038/s41567- 025- 03086- 2 (cited on p. 10).

[MH25]

Antonio Anna Mele and Yaroslav Herasymenko. “Efficient learning of quantum states prepared with few fermionic non-Gaussian gates”. In: PRX Quantum 6.1 (2025), p. 010319. doi: 10 . 1103 / PRXQuantum . 6 . 010319 (cited on p. 10).

[Mon17]

Ashley Montanaro. Learning stabilizer states by Bell sampling. 2017. arXiv: 1707 . 04012 [quant-ph]. url: https : / / arxiv . org / abs / 1707 . 04012 (cited on p. 10).

[MS08]

Igor L. Markov and Yaoyun Shi. “Simulating Quantum Computation by Contracting Tensor Networks”. In: SIAM Journal on Computing 38.3 (Jan. 2008), pp. 963–981. issn: 1095-7111. doi: 10.1137/050644756. url: http: //dx.doi.org/10.1137/050644756 (cited on pp. 1, 3, 6, 9, 10, 15, 54).

[MW16]

Ashley Montanaro and Ronald de Wolf. A Survey of Quantum Property Testing. Graduate Surveys 7. Theory of Computing Library, 2016, pp. 1– 81. doi: 10.4086/toc.gs.2016.007 (cited on p. 11).

[OGo19]

Bryan O’Gorman. “Parameterization of Tensor Network Contraction”. In: 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Ed. by Wim van Dam and Laura Mančinska. Vol. 135. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019, 10:1–10:19. isbn: 978-3-95977-112-2. doi: 10.4230/LIPIcs. TQC.2019.10. url: https://drops.dagstuhl.de/entities/document/ 10.4230/LIPIcs.TQC.2019.10 (cited on pp. 3, 9).

[Orú14]

Román Orús. “A practical introduction to tensor networks: Matrix product states and projected entangled pair states”. In: Annals of physics 349 (2014), pp. 117–158. doi: 10.1016/j.aop.2014.06.013 (cited on p. 3).

[OW15a]

Ryan O’Donnell and John Wright. Efficient quantum tomography. 2015. arXiv: 1508.01907 [quant-ph]. url: https://arxiv.org/abs/1508. 01907 (cited on p. 30).

83

[OW15b]

Ryan O’Donnell and John Wright. “Quantum Spectrum Testing”. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing. STOC ’15. Portland, Oregon, USA: Association for Computing Machinery, 2015, pp. 529–538. isbn: 9781450335362. doi: 10.1145/2746539. 2746582. url: https://doi.org/10.1145/2746539.2746582 (cited on p. 11).

[PCR24]

Christophe Piveteau, Christopher T Chubb, and Joseph M Renes. “Tensornetwork decoding beyond 2d”. In: PRX Quantum 5.4 (2024), p. 040303. doi: 10.1103/PRXQuantum.5.040303 (cited on p. 3).

[Pel+25]

Angelos Pelecanos, Jack Spilecki, Ewin Tang, and John Wright. Mixed state tomography reduces to pure state tomography. 2025. arXiv: 2511 . 15806 [quant-ph]. url: https://arxiv.org/abs/2511.15806 (cited on p. 30).

[PSW25]

Angelos Pelecanos, Jack Spilecki, and John Wright. The debiased Keyl’s algorithm: a new unbiased estimator for full state tomography. 2025. arXiv: 2510 . 07788 [quant-ph]. url: https : / / arxiv . org / abs / 2510 . 07788 (cited on p. 30).

[RF23]

Cambyse Rouzé and Daniel Stilck França. Efficient learning of the structure and parameters of local Pauli noise channels. 2023. arXiv: 2307 . 02959 [quant-ph]. url: https://arxiv.org/abs/2307.02959 (cited on p. 10).

[RNW06]

Jörg Rissler, Reinhard M Noack, and Steven R White. “Measuring orbital interaction using quantum information theory”. In: Chemical Physics 323.23 (2006), pp. 519–531. doi: 10.1016/j.chemphys.2005.10.018 (cited on p. 12).

[RÖ07]

Stefan Rommer and Stellan Östlund. “Thermodynamic limit and matrixproduct states”. In: Density-Matrix Renormalization: A New Numerical Method in Physics Lectures of a Seminar and Workshop Held at the MaxPlanck-Institut für Physik komplexer Systeme Dresden, Germany, August 24th to September 18th, 1998. Springer. 2007, pp. 67–89. doi: 10.1007/ BFb0106065 (cited on p. 3).

[Roc18]

Andrea Rocchetto. “Stabiliser states are efficiently PAC-learnable”. In: Quantum Info. Comput. 18.7–8 (June 2018), pp. 541–552. issn: 1533-7146. doi: 10.26421/QIC18.7-8-1 (cited on p. 10).

[ROK24]

Oliver Reardon-Smith, Michal Oszmaniec, and Kamil Korzekwa. “Improved simulation of quantum circuits dominated by free fermionic operations”. In: Quantum 8 (Dec. 2024), p. 1549. issn: 2521-327X. doi: 10.22331/q-202412- 04- 1549. url: https://doi.org/10.22331/q- 2024- 12- 04- 1549 (cited on p. 10).

[RS86]

Neil Robertson and Paul D. Seymour. “Graph minors. II. Algorithmic aspects of tree-width”. In: Journal of Algorithms 7 (3 Sept. 1986), pp. 309– 322. doi: 10.1016/0196-6774(86)90023-4 (cited on p. 14).

[Sch+07]

Norbert Schuch, Michael M Wolf, Frank Verstraete, and J Ignacio Cirac. “Computational complexity of projected entangled pair states”. In: Physical review letters 98.14 (2007), p. 140506. doi: 10 .1103 / PhysRevLett. 98 . 140506 (cited on pp. 3, 9).

84

[Sch03]

Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Berlin: Springer, 2003. url: https://link.springer.com/book/ 9783540443896 (cited on p. 54).

[Sch11]

Ulrich Schollwöck. “The density-matrix renormalization group in the age of matrix product states”. In: Annals of physics 326.1 (2011), pp. 96–192. doi: 10.1016/j.aop.2010.09.012 (cited on pp. 3, 12).

[SDV06]

Y-Y Shi, L-M Duan, and Guifre Vidal. “Classical simulation of quantum many-body systems with a tree tensor network”. In: Physical Review A—Atomic, Molecular, and Optical Physics 74.2 (2006), p. 022320. doi: 10.1103/PhysRevA.74.022320 (cited on p. 3).

[SSW25]

Thilo Scharnhorst, Jack Spilecki, and John Wright. Optimal lower bounds for quantum state tomography. 2025. arXiv: 2510.07699 [quant-ph]. url: https://arxiv.org/abs/2510.07699 (cited on p. 30).

[ST25]

Savar D. Sinha and Yu Tong. Improved Hamiltonian learning and sparsity testing through Bell sampling. 2025. arXiv: 2509.07937 [quant-ph]. url: https://arxiv.org/abs/2509.07937 (cited on p. 11).

[SW22]

Mehdi Soleimanifar and John Wright. “Testing matrix product states”. In: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. 2022, pp. 1679–1701. doi: 10 . 1137 / 1 . 9781611977073.68 (cited on pp. 3, 11).

[TD02]

Barbara M Terhal and David P DiVincenzo. “Classical simulation of noninteracting-fermion quantum circuits”. In: Physical Review A 65.3 (2002), p. 032325. doi: 10.1103/PhysRevA.65.032325 (cited on p. 10).

[TSB05a]

Dimitrios M. Thilikos, Maria Serna, and Hans L. Bodlaender. “Cutwidth I: A linear time fixed parameter algorithm”. In: Journal of Algorithms 56.1 (2005), pp. 1–24. issn: 0196-6774. doi: https://doi.org/10.1016/j. jalgor.2004.12.001. url: https://www.sciencedirect.com/science/ article/pii/S0196677405000167 (cited on pp. 12, 15).

[TSB05b]

Dimitrios M. Thilikos, Maria Serna, and Hans L. Bodlaender. “Cutwidth II: Algorithms for partial w-trees of bounded degree”. In: Journal of Algorithms 56.1 (2005), pp. 25–49. issn: 0196-6774. doi: https://doi.org/10.1016/ j.jalgor.2004.12.003. url: https://www.sciencedirect.com/scienc e/article/pii/S0196677405000179 (cited on pp. 12, 15).

[Val01]

Leslie G. Valiant. “Quantum computers that can be simulated classically in polynomial time”. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing. STOC ’01. Hersonissos, Greece: Association for Computing Machinery, 2001, pp. 114–123. isbn: 1581133499. doi: 10. 1145/380752.380785. url: https://doi.org/10.1145/380752.380785 (cited on p. 10).

[VC04]

F. Verstraete and J. I. Cirac. Renormalization algorithms for QuantumMany Body Systems in two and higher dimensions. 2004. arXiv: cond mat/0407066 [cond-mat.str-el]. url: https://arxiv.org/abs/condmat/0407066 (cited on p. 3).

[Vid03]

Guifré Vidal. “Efficient classical simulation of slightly entangled quantum computations”. In: Physical review letters 91.14 (2003), p. 147902. doi: 10.1103/PhysRevLett.91.147902 (cited on pp. 3, 10). 85

[Vuf+16]

Marc Vuffray, Sidhant Misra, Andrey Lokhov, and Michael Chertkov. “Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models”. In: Advances in Neural Information Processing Systems. Ed. by D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett. Vol. 29. Curran Associates, Inc., 2016. url: https : / / proceedings . neurips . cc / paper_files/paper/2016/file/861dc9bd7f4e7dd3cccd534d0ae2a2e9Paper.pdf (cited on p. 10).

[Wei+09]

Andreas Weichselbaum, Frank Verstraete, Ulrich Schollwöck, J Ignacio Cirac, and Jan von Delft. “Variational matrix-product-state approach to quantum impurity models”. In: Physical Review B—Condensed Matter and Materials Physics 80.16 (2009), p. 165117. doi: 10.1103/PhysRevB.80. 165117 (cited on p. 3).

[Wol15]

Paul Wollan. “The structure of graphs not admitting a fixed immersion”. In: Journal of Combinatorial Theory, Series B 110 (2015), pp. 47–66. issn: 0095-8956. doi: https : / / doi . org / 10 . 1016 / j . jctb . 2014 . 07 . 003. url: https : / / www . sciencedirect . com / science / article / pii / S0095895614000914 (cited on p. 15).

[Wou+15]

Sebastian Wouters, Ward Poelmans, Stijn De Baerdemacker, Paul W Ayers, and Dimitri Van Neck. “CheMPS2: Improved DMRG-SCF routine and correlation functions”. In: Computer Physics Communications 191 (2015), pp. 235–237. doi: 10.1016/j.cpc.2015.01.007 (cited on p. 12).

[WS23]

Thorsten B Wahl and Sergii Strelchuk. “Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound”. In: Physical Review Letters 131.18 (2023), p. 180601. doi: 10 . 1103/PhysRevLett.131.180601 (cited on pp. 3, 9).

[Yog19]

Mithuna Yoganathan. A condition under which classical simulability implies efficient state learnability. 2019. arXiv: 1907.08163 [quant-ph]. url: htt ps://arxiv.org/abs/1907.08163 (cited on p. 10).

[Zha25]

Andrew Zhao. “Learning the Structure of Any Hamiltonian from Minimal Assumptions”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC ’25. Prague, Czechia: Association for Computing Machinery, 2025, pp. 1201–1211. isbn: 9798400715105. doi: 10.1145/ 3717823.3718115. url: https://doi.org/10.1145/3717823.3718115 (cited on p. 10).

[ZSW20]

Yiqing Zhou, E Miles Stoudenmire, and Xavier Waintal. “What limits the simulation of quantum computers?” In: Physical Review X 10.4 (2020), p. 041038. doi: 10.1103/PhysRevX.10.041038 (cited on pp. 3, 12).

86

Related documents

• Multivariate quantum state preparation with optimized tensor networks#987066
• Highly Entangled 2D Ground States: Tensor Network, Order Parameter and Correlation#665477
• Highly Entangled 2D Ground States: Tensor Network, Order Parameter and Correlation#663977
• Proper Agnostic Learning of Matrix Product States and Tree Tensor Networks#1078219
• Efficient Finite Initialization with Partial Norms for Tensorized Neural Networks and Tensor Networks Algorithms#189172