Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.30148

Proper Agnostic Learning of Matrix Product States and Tree Tensor Networks

Constantin Cedillo Vayson de Pradenne, Jordan Cotler

quant-phSubmitted Sep 24, 2026• Announced Sep 25, 2026• 0 citations
arXivHTMLPDF

Abstract

We establish proper agnostic learning of matrix product states and tree tensor networks. Given copies of an arbitrary quantum state $ρ$, our algorithms return a state $|ψ\rangle$ of chosen bond dimension such that $\langleψ| ρ|ψ\rangle$ is within $\varepsilon$ of the optimum over the model class, without assuming that $ρ$ itself belongs to or is well approximated by that class. The main idea is to use improper learning to compress the mixed-state objective, reducing proper agnostic learning to optimization against a finite collection of explicitly specified pure states. We then introduce a comparator-dual compression procedure that reduces the bond dimension of these targets while uniformly preserving their overlaps with all bounded-bond comparators, with an error independent of system size. For matrix product states, this gives polynomial copy complexity in the system size, local dimension, bond dimension, and $1/\varepsilon$, together with polynomial runtime in the system size for fixed local dimension, bond dimension, and accuracy. The same framework yields proper agnostic learning of tree tensor networks on bounded-degree trees, with both copy complexity and runtime polynomial in the system size when the remaining parameters are fixed.

AI Summary

The paper addresses proper agnostic learning of matrix product states (MPSs): given copies of an arbitrary mixed state $\rho$, find a normalized bond-$D$ MPS whose score $\langle\psi|\rho|\psi\rangle$ is within $\varepsilon$ of the optimum over that class, without assuming tensor-network structure in $\rho$. It also treats tree tensor networks (TTNs) on known bounded-degree trees. For MPSs, copy complexity is $\operatorname{poly}(n,d,D,1/\varepsilon,\log(1/\delta))$, with success probability $1-\delta$. Runtime is a polynomial prefactor times $(Cn\sqrt D/\varepsilon)^{O(D^2/\varepsilon^2+dD^2)}$, hence polynomial in $n$ only when the other parameters are fixed. For TTNs, copies and runtime are polynomial in $n$ for fixed local dimension, bond dimension, degree, and accuracy. The method repeatedly invokes an existing improper learner to construct an $O(\varepsilon^{-2})$-dimensional subspace preserving all comparator scores approximately. Spectral cutoff reduces optimization to $(C/\varepsilon)^{O(1/\varepsilon)}$ explicit pure-target problems. Singular-value shrinkage then compresses each target to bond $K$, with overlap error at most $\|u\|_2\sqrt{D/(K+1)}$ uniformly over bond-$D$ comparators, independently of chain length. Dynamic programming over discretized cross environments produces a proper output. The compression also gives squared Euclidean error within $1+\alpha$ of the best bond-$D$ approximation using bond $O(D/\alpha)$. Limitations include expensive classical search, adaptive projections and postselection rather than local single-copy measurements, and additional TTN copy overhead from embedding into MPSs. Near-optimal score need not imply reconstruction of $\rho$. Proper learning for periodic MPSs or networks with cycles is not established.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
15+37 pages

Related papers

Proper Agnostic Learning of Matrix Product States and Tree Tensor Networks — E8 Intelligence Research

Andrew Stewart Caldin

We establish proper agnostic learning of matrix product states and tree tensor networks. Given copies of an arbitrary quantum state $ρ$, our algorithms return a state $|ψ\rangle$ of chosen bond dimension such that $\langleψ| ρ|ψ\rangle$ is within $\varepsilon$ of the optimum over the model class, without assuming that $ρ$ itself belongs to or is well approximated by that class. The main idea is to use improper learning to compress the mixed-state objective, reducing proper agnostic learning to optimization against a finite collection of explicitly specified pure states. We then introduce a comparator-dual compression procedure that reduces the bond dimension of these targets while uniformly preserving their overlaps with all bounded-bond comparators, with an error independent of system size. For matrix product states, this gives polynomial copy complexity in the system size, local dimension, bond dimension, and $1/\varepsilon$, together with polynomial runtime in the system size for fi Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 13, 2026•0 citations

Tensor Network States with Low-Rank Tensors

Hao Chen, Thomas Barthel

Tensor networks are used to efficiently approximate states of strongly-correlated quantum many-body systems. More generally, tensor network approximations may allow to reduce the costs for operating on an order-$N$ tensor from exponential to polynomial in $N$, and this has become a popular approach for machine learning. We introduce the idea of imposing low-rank constraints on the tensors that compose the tensor network. With this modification, the time and space complexities for the network optimization can be substantially reduced while maintaining high accuracy. We detail this idea for tree tensor network states (TTNS) and projected entangled-pair states. Simulations of spin models on Cayley trees with low-rank TTNS exemplify the effect of rank constraints on the expressive power. We find that choosing the tensor rank $r$ to be on the order of the bond dimension $m$, is sufficient to obtain high-accuracy groundstate approximations and to substantially outperform standard TTNS computations. Thus low-rank tensor networks are a promising route for the simulation of quantum matter and machine learning on large data sets.

arXiv:2205.15296•May 30, 2022•5 citations

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

Matthias C. Caro, Natalie McHugh, Sergii Strelchuk

Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state? We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In the TTN case, tree-cutwidth also bounds the local dimension of the grouped subsystems. The proofs are based on entanglement rerouting, a tensor-network analogue of rerouting information in a classical network. Second, we derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth. We obtain these results by extending the disentangling MPS learner of (Cramer et al., 2010), as analysed further in (Bakshi et al., 2025; Lin et al., 2025), to TTNs and to tensor networks on arbitrary known graphs. Finally, we extend the framework beyond the realisable setting. For an arbitrary input state, our agnostic learner outputs a pure state whose fidelity is within additive error $ε$ of the optimum over tensor-network states on the given graph with a given bond dimension, with explicit graph-dependent bounds on sample and computational complexity.

quant-pharXiv:2609.04165•Sep 4, 2026•0 citations

Tree tensor network states represent low-energy states faithfully

Thomas Barthel

Extending corresponding results for matrix product states [Verstraete and Cirac, PRB 73, 094423 (2006); Schuch et al. PRL 100, 030504 (2008)], it is shown how the approximation error of tree tensor network states (TTNS) can be bounded using Schmidt spectra or Rényi entanglement entropies of the target quantum state. Conversely, one obtains bounds on TTNS bond dimensions needed to achieve a specific approximation accuracy. For tree lattices, the result implies that efficient TTNS approximations exist if $α<1$ Rényi entanglement entropies for single-branch cuts obey an area law, as in ground and low-energy states of certain gapped systems.

quant-pharXiv:2512.20215•Journal of Statistical Mechanics Theory and Experiment•Dec 24, 2025•2 citations

Agnostic Product Mixed State Tomography via Robust Statistics

Alvan Caleb Arulandu, Ilias Diakonikolas, Daniel M. Kane +1 more

We study the complexity of two closely related learning problems, one quantum and one classical. In the quantum setting, we consider agnostic tomography for the natural class of product mixed states. Given $N$ copies of an $n$-qubit state $ρ$, the goal is to output a nearly optimal product mixed state approximation in trace distance. While recent work has focused on pure-state ansatz (e.g., product or stabilizer states), no polynomial-time guarantees were previously known for mixed-state ansatz. In the classical setting, we study robust learning of binary product distributions: given samples from an unknown distribution on ${0,1}^n$, the goal is to output a nearly optimal product approximation. Our main contributions are as follows. (1) We give a semi-agnostic tomography algorithm for product mixed states with polynomial sample and computational complexity achieving error $O(\mathrm{opt}\log(1/\mathrm{opt}))$, where $\mathrm{opt}$ is the trace distance to the best product approximation. This is the first efficient algorithm with any nontrivial agnostic guarantee for mixed-state ansatz, using only single-qubit, single-copy measurements. We also prove a Quantum Statistical Query lower bound showing near-optimality, and an unconditional lower bound demonstrating that adaptivity is necessary under single-qubit measurements. (2) We give a semi-agnostic algorithm for robustly learning binary product distributions with matching guarantees and establish a Statistical Query lower bound, essentially resolving the efficient robust learnability of this class and improving on prior work since Diakonikolas et al. (2016).

arXiv:2510.08472•Oct 9, 2025•2 citations

Efficient Matrix Product State Learning in Logarithmic Depth

Chia-Ying Lin, Nai-Hui Chia, Hung, Shih-Han

Learning the closest matrix product state (MPS) representation of a quantum state enables useful tools for quantum machine learning and analysis of complex quantum systems. In this work, we study the problem of learning MPS in the following setting: given many copies of an input MPS, the task is to recover a classical description of the state. The best known polynomial-time algorithm, introduced by [LCLP10, CPF+10], requires linear circuit depth and $\widetilde O(n^5)$ samples, and has seen no improvement in over a decade. These costs, neither known to be optimal, renders existing algorithms impractical for near-term quantum devices with limited resources. We introduce parallel disentangling algorithms for MPS learning. For exact MPS learning, our algorithm runs in polynomial time and uses circuit depth $O(\log n)$ and sample complexity $\widetilde O(n^3)$, improving both the depth and the dependence on the system size $n$. The key idea is to exploit the bounded-rank structure of reduced states on middle blocks of an MPS and organize the disentangling operations in a tree structure. We further extend the algorithm to closest MPS learning, improving the sample complexity dependence on $n$ from $n^9$ to $n^7$ and complement the algorithms with an $Ω(n)$ product-state lower bound. We also investigate MPS learning under hardware constraints, including restricted measurements and geometric connectivity. Under the Learning Parity with Noise (LPN) assumption, we show computational hardness for learning an MPS(2) family with non-adaptive single-qubit measurements. Finally, we show that our algorithm can be implemented with depth $O(q n^{1/q})$ on a $q$-dimensional hypercubic lattice, giving an asymptotic reduction in depth. Together, our work provides a complete characterization of the quantum resources needed for efficient MPS learning.

arXiv:2510.07798•Oct 9, 2025•3 citations
We establish proper agnostic learning of matrix product states and tree tensor networks. Given copies of an arbitrary quantum state ρρρ, our algorithms return a state ∣ψ⟩|ψ\rangle∣ψ⟩ of chosen bond dimension such that ⟨ψ∣ρ∣ψ⟩\langleψ| ρ|ψ\rangle⟨ψ∣ρ∣ψ⟩ is within ε\varepsilonε of the optimum over the model class, without assuming that ρρρ itself belongs to or is well approximated by that class. The main idea is to use improper learning to compress the mixed-state objective, reducing proper agnostic learning to optimization against a finite collection of explicitly specified pure states. We then introduce a comparator-dual compression procedure that reduces the bond dimension of these targets while uniformly preserving their overlaps with all bounded-bond comparators, with an error independent of system size. For matrix product states, this gives polynomial copy complexity in the system size, local dimension, bond dimension, and 1/ε1/\varepsilon1/ε, together with polynomial runtime in the system size for fixed local dimension, bond dimension, and accuracy. The same framework yields proper agnostic learning of tree tensor networks on bounded-degree trees, with both copy complexity and runtime polynomial in the system size when the remaining parameters are fixed.
The paper addresses proper agnostic learning of matrix product states (MPSs): given copies of an arbitrary mixed state ρ\rhoρ, find a normalized bond-DDD MPS whose score ⟨ψ∣ρ∣ψ⟩\langle\psi|\rho|\psi\rangle⟨ψ∣ρ∣ψ⟩ is within ε\varepsilonε of the optimum over that class, without assuming tensor-network structure in ρ\rhoρ. It also treats tree tensor networks (TTNs) on known bounded-degree trees.
For MPSs, copy complexity is poly⁡(n,d,D,1/ε,log⁡(1/δ))\operatorname{poly}(n,d,D,1/\varepsilon,\log(1/\delta))poly(n,d,D,1/ε,log(1/δ)), with success probability 1−δ1-\delta1−δ. Runtime is a polynomial prefactor times (CnD/ε)O(D2/ε2+dD2)(Cn\sqrt D/\varepsilon)^{O(D^2/\varepsilon^2+dD^2)}(CnD​/ε)O(D2/ε2+dD2), hence polynomial in nnn only when the other parameters are fixed. For TTNs, copies and runtime are polynomial in nnn for fixed local dimension, bond dimension, degree, and accuracy.
The method repeatedly invokes an existing improper learner to construct an O(ε−2)O(\varepsilon^{-2})O(ε−2)-dimensional subspace preserving all comparator scores approximately. Spectral cutoff reduces optimization to (C/ε)O(1/ε)(C/\varepsilon)^{O(1/\varepsilon)}(C/ε)O(1/ε) explicit pure-target problems. Singular-value shrinkage then compresses each target to bond KKK, with overlap error at most ∥u∥2D/(K+1)\|u\|_2\sqrt{D/(K+1)}∥u∥2​D/(K+1)​ uniformly over bond-DDD comparators, independently of chain length. Dynamic programming over discretized cross environments produces a proper output. The compression also gives squared Euclidean error within 1+α1+\alpha1+α of the best bond-DDD approximation using bond O(D/α)O(D/\alpha)O(D/α).
Limitations include expensive classical search, adaptive projections and postselection rather than local single-copy measurements, and additional TTN copy overhead from embedding into MPSs. Near-optimal score need not imply reconstruction of ρ\rhoρ. Proper learning for periodic MPSs or networks with cycles is not established.
We establish proper agnostic learning of matrix product states and tree tensor networks. Given copies of an arbitrary quantum state ρρρ, our algorithms return a state ∣ψ⟩|ψ\rangle∣ψ⟩ of chosen bond dimension such that ⟨ψ∣ρ∣ψ⟩\langleψ| ρ|ψ\rangle⟨ψ∣ρ∣ψ⟩ is within ε\varepsilonε of the optimum over the model class, without assuming that ρρρ itself belongs to or is well approximated by that class. The main idea is to use improper learning to compress the mixed-state objective, reducing proper agnostic learning to optimization against a finite collection of explicitly specified pure states. We then introduce a comparator-dual compression procedure that reduces the bond dimension of these targets while uniformly preserving their overlaps with all bounded-bond comparators, with an error independent of system size. For matrix product states, this gives polynomial copy complexity in the system size, local dimension, bond dimension, and 1/ε1/\varepsilon1/ε, together with polynomial runtime in the system size for fi Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Tensor networks are used to efficiently approximate states of strongly-correlated quantum many-body systems. More generally, tensor network approximations may allow to reduce the costs for operating on an order-NNN tensor from exponential to polynomial in NNN, and this has become a popular approach for machine learning. We introduce the idea of imposing low-rank constraints on the tensors that compose the tensor network. With this modification, the time and space complexities for the network optimization can be substantially reduced while maintaining high accuracy. We detail this idea for tree tensor network states (TTNS) and projected entangled-pair states. Simulations of spin models on Cayley trees with low-rank TTNS exemplify the effect of rank constraints on the expressive power. We find that choosing the tensor rank rrr to be on the order of the bond dimension mmm, is sufficient to obtain high-accuracy groundstate approximations and to substantially outperform standard TTNS computations. Thus low-rank tensor networks are a promising route for the simulation of quantum matter and machine learning on large data sets.
Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state? We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In the TTN case, tree-cutwidth also bounds the local dimension of the grouped subsystems. The proofs are based on entanglement rerouting, a tensor-network analogue of rerouting information in a classical network. Second, we derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth. We obtain these results by extending the disentangling MPS learner of (Cramer et al., 2010), as analysed further in (Bakshi et al., 2025; Lin et al., 2025), to TTNs and to tensor networks on arbitrary known graphs. Finally, we extend the framework beyond the realisable setting. For an arbitrary input state, our agnostic learner outputs a pure state whose fidelity is within additive error εεε of the optimum over tensor-network states on the given graph with a given bond dimension, with explicit graph-dependent bounds on sample and computational complexity.
Extending corresponding results for matrix product states [Verstraete and Cirac, PRB 73, 094423 (2006); Schuch et al. PRL 100, 030504 (2008)], it is shown how the approximation error of tree tensor network states (TTNS) can be bounded using Schmidt spectra or Rényi entanglement entropies of the target quantum state. Conversely, one obtains bounds on TTNS bond dimensions needed to achieve a specific approximation accuracy. For tree lattices, the result implies that efficient TTNS approximations exist if α<1α<1α<1 Rényi entanglement entropies for single-branch cuts obey an area law, as in ground and low-energy states of certain gapped systems.
We study the complexity of two closely related learning problems, one quantum and one classical. In the quantum setting, we consider agnostic tomography for the natural class of product mixed states. Given NNN copies of an nnn-qubit state ρρρ, the goal is to output a nearly optimal product mixed state approximation in trace distance. While recent work has focused on pure-state ansatz (e.g., product or stabilizer states), no polynomial-time guarantees were previously known for mixed-state ansatz. In the classical setting, we study robust learning of binary product distributions: given samples from an unknown distribution on 0,1n{0,1}^n0,1n, the goal is to output a nearly optimal product approximation. Our main contributions are as follows. (1) We give a semi-agnostic tomography algorithm for product mixed states with polynomial sample and computational complexity achieving error O(optlog⁡(1/opt))O(\mathrm{opt}\log(1/\mathrm{opt}))O(optlog(1/opt)), where opt\mathrm{opt}opt is the trace distance to the best product approximation. This is the first efficient algorithm with any nontrivial agnostic guarantee for mixed-state ansatz, using only single-qubit, single-copy measurements. We also prove a Quantum Statistical Query lower bound showing near-optimality, and an unconditional lower bound demonstrating that adaptivity is necessary under single-qubit measurements. (2) We give a semi-agnostic algorithm for robustly learning binary product distributions with matching guarantees and establish a Statistical Query lower bound, essentially resolving the efficient robust learnability of this class and improving on prior work since Diakonikolas et al. (2016).
Learning the closest matrix product state (MPS) representation of a quantum state enables useful tools for quantum machine learning and analysis of complex quantum systems. In this work, we study the problem of learning MPS in the following setting: given many copies of an input MPS, the task is to recover a classical description of the state. The best known polynomial-time algorithm, introduced by [LCLP10, CPF+10], requires linear circuit depth and O~(n5)\widetilde O(n^5)O(n5) samples, and has seen no improvement in over a decade. These costs, neither known to be optimal, renders existing algorithms impractical for near-term quantum devices with limited resources. We introduce parallel disentangling algorithms for MPS learning. For exact MPS learning, our algorithm runs in polynomial time and uses circuit depth O(log⁡n)O(\log n)O(logn) and sample complexity O~(n3)\widetilde O(n^3)O(n3), improving both the depth and the dependence on the system size nnn. The key idea is to exploit the bounded-rank structure of reduced states on middle blocks of an MPS and organize the disentangling operations in a tree structure. We further extend the algorithm to closest MPS learning, improving the sample complexity dependence on nnn from n9n^9n9 to n7n^7n7 and complement the algorithms with an Ω(n)Ω(n)Ω(n) product-state lower bound. We also investigate MPS learning under hardware constraints, including restricted measurements and geometric connectivity. Under the Learning Parity with Noise (LPN) assumption, we show computational hardness for learning an MPS(2) family with non-adaptive single-qubit measurements. Finally, we show that our algorithm can be implemented with depth O(qn1/q)O(q n^{1/q})O(qn1/q) on a qqq-dimensional hypercubic lattice, giving an asymptotic reduction in depth. Together, our work provides a complete characterization of the quantum resources needed for efficient MPS learning.