arXiv:2609.30148
Proper Agnostic Learning of Matrix Product States and Tree Tensor Networks
Constantin Cedillo Vayson de Pradenne, Jordan Cotler
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.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 15+37 pages