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

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

Andrew Stewart Caldin

Published Nov 13, 2026• 0 citations
Publisher

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 fi Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

DOI
10.5281/zenodo.24186731

Related papers

Proper Agnostic Learning of Matrix Product States and Tree Tensor Networks

Constantin Cedillo Vayson de Pradenne, Jordan Cotler

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.

quant-pharXiv:2609.30148•Sep 25, 2026•0 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

Optimal spectrum estimation — E8 Intelligence Research

Andrew Stewart Caldin

We prove that the spectrum of an unknown $d$-dimensional quantum state can be estimated to error $\varepsilon$ in total variation distance using \[ O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) \] copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of $d$ in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound. Source: http://arxiv.org/abs/2609.30171v1 (arXiv:2609.30171v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 13, 2026•0 citations

Tensor Networks Link Non-Local Symmetries to Root Lattice Entanglement in Quantum Verification — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Tensor networks encode non-local symmetries via matrix product operators, linking entanglement structure to root system lattice symmetries in quantum verification protocols. | MATH: Tensor product Hilbert space \( \mathcal{H} = \bigotimes_i \mathcal{H}_i \); matrix product operator (MPO) form \( \hat{O} = \sum_{\{a\}} \text{Tr}(A^{a_1} \cdots A^{a_n}) |a_1 \cdots a_n\rangle\langle a_1 \cdots a_n| \); entanglement entropy \( S = -\text{Tr}(\rho \log \rho) \) scales with boundary area; root system lattice symmetries (e.g., \( A_n, D_n, E_8 \)) appear in tensor network bond dimensions and symmetry groups. | CONNECTION: Root system lattices (e.g., \( E_8 \) with Coxeter number 30, ratio 0.618 appears in golden angle \( \pi(1-\phi) \)) map to tensor network symmetries; bond dimension \( \chi \) often relates to Fibonacci numbers (1,1,2,3,5,8,...) giving ratios 0.618, 1.618; base-60 emerges in hexagonal lattice symmetries (60° rotations) of \( A_2 \) root system. | DEPTH: 8 — Direct Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Jul 31, 2026•0 citations

Agnostic learning of qudit stabilizer states

Wentao Qi, Boyan Xu, Shiguang Feng +1 more

Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown $n$-qudit pure state $|ψ\rangle$ that has fidelity $τ$ with some stabilizer state, our algorithm outputs a stabilizer state $|φ\rangle$ such that $\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon$ with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as $(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)$, where the dimension $d$ is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime $τ> \cos^2(π/8)$, establishing a qudit analogue of the threshold-based approach in prior qubit work.

quant-pharXiv:2607.15559•Jul 20, 2026•1 citation

Parallel quantum channel discrimination and numerical ranges in tensor product subspaces — E8 Intelligence Research

Andrew Stewart Caldin

Quantum channel discrimination plays a crucial role in quantum information theory. Of particular interest is the case in which the channels can be discriminated perfectly. In this work, we focus on the perfect quantum channel discrimination task in a parallel scheme. We develop an SDP formulation combined with a bisection procedure to compute a quantum state for perfect discrimination in time linear in the number of copies. In addition, we obtain the minimal number of copies of quantum channels to achieve perfect discrimination. Thanks to that, we settle in the affirmative Conjecture 1 of Duan, Guo, Li and Li [arXiv:1605.02294, IEEE ISIT 2016], which characterizes the number of parallel uses needed to discriminate perfectly a distinguished family of operator subspaces. All our results are obtained using the notion and basic properties of the numerical range. In particular, the key fact that we prove and use is that the minimal angle of the numerical range of a tensor product of matrix Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Nov 7, 2026•0 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 fi Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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.
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.
We prove that the spectrum of an unknown ddd-dimensional quantum state can be estimated to error ε\varepsilonε in total variation distance using O ⁣(d2min⁡{1(εlog⁡d)4,  1(εlog⁡d)2}) O\!\left(d^2\min\left\{ \frac{1}{(\varepsilon\log d)^4},\; \frac{1}{(\varepsilon\log d)^2} \right\}\right) O(d2min{(εlogd)41​,(εlogd)21​}) copies. This matches the recent lower bound of Wang. When restricted to unentangled measurements, we give an algorithm with an additional factor of ddd in copy complexity, which we conjecture to be optimal. We develop a framework for recovering the small eigenvalues of a quantum state by matching Chebyshev moments. We bound the variance of each Chebyshev moment estimate in terms of scalar derivatives of the corresponding polynomial, using classical and quantum Efron--Stein decompositions. Different rescalings of the Chebyshev polynomials balance approximation error and variance, yielding two regimes in our copy complexity bound. Source: http://arxiv.org/abs/2609.30171v1 (arXiv:2609.30171v1) Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
FINDING: Tensor networks encode non-local symmetries via matrix product operators, linking entanglement structure to root system lattice symmetries in quantum verification protocols. | MATH: Tensor product Hilbert space H=⨂iHi \mathcal{H} = \bigotimes_i \mathcal{H}_i H=⨂i​Hi​; matrix product operator (MPO) form O^=∑{a}Tr(Aa1⋯Aan)∣a1⋯an⟩⟨a1⋯an∣ \hat{O} = \sum_{\{a\}} \text{Tr}(A^{a_1} \cdots A^{a_n}) |a_1 \cdots a_n\rangle\langle a_1 \cdots a_n| O^=∑{a}​Tr(Aa1​⋯Aan​)∣a1​⋯an​⟩⟨a1​⋯an​∣; entanglement entropy S=−Tr(ρlog⁡ρ) S = -\text{Tr}(\rho \log \rho) S=−Tr(ρlogρ) scales with boundary area; root system lattice symmetries (e.g., An,Dn,E8 A_n, D_n, E_8 An​,Dn​,E8​) appear in tensor network bond dimensions and symmetry groups. | CONNECTION: Root system lattices (e.g., E8 E_8 E8​ with Coxeter number 30, ratio 0.618 appears in golden angle π(1−ϕ) \pi(1-\phi) π(1−ϕ)) map to tensor network symmetries; bond dimension χ \chi χ often relates to Fibonacci numbers (1,1,2,3,5,8,...) giving ratios 0.618, 1.618; base-60 emerges in hexagonal lattice symmetries (60° rotations) of A2 A_2 A2​ root system. | DEPTH: 8 — Direct Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Learning a classical description of a quantum state is a fundamental task in quantum computation. Among the most important classes of quantum states are stabilizer states, which play a central role in quantum error correction and fault-tolerant computation. To mitigate the effects of realistic noise, agnostic learning of stabilizer states has emerged as a natural and well-motivated problem. Recently, Chen \textit{et al.} [STOC'25, p. 429-438] resolved this problem for qubit systems by using a stabilizer bootstrapping framework. However, the agnostic learning of qudit stabilizer states remains largely unexplored, since the qudit setting introduces fundamental structural differences that prevent a direct generalization of existing qubit techniques. In this paper, we successfully generalize the stabilizer bootstrapping framework to qudit systems and present the first efficient quantum algorithm for agnostic learning of qudit stabilizer states. Specifically, given copies of an unknown nnn-qudit pure state ∣ψ⟩|ψ\rangle∣ψ⟩ that has fidelity τττ with some stabilizer state, our algorithm outputs a stabilizer state ∣φ⟩|φ\rangle∣φ⟩ such that ∣⟨φ∣ψ⟩∣2≥τ−ε\left| \braket{φ|ψ} \right|^2 \geq τ- \varepsilon∣⟨φ∣ψ⟩∣2≥τ−ε with high probability. The algorithm uses only single-copy and four-copy measurements, and its sample and time complexity scale as (d/τ)O(d2log⁡(1/τ))⋅poly(n,1/ε)(d/τ)^{O(d^2 \log(1/τ))} \cdot \mathrm{poly}(n, 1/\varepsilon)(d/τ)O(d2log(1/τ))⋅poly(n,1/ε), where the dimension ddd is an odd prime. As a direct corollary, our algorithm enables efficient estimation of the magic of a quantum state, as quantified by its stabilizer fidelity. Completing the picture, we also present a streamlined algorithm for the high-fidelity regime τ>cos⁡2(π/8)τ> \cos^2(π/8)τ>cos2(π/8), establishing a qudit analogue of the threshold-based approach in prior qubit work.
Quantum channel discrimination plays a crucial role in quantum information theory. Of particular interest is the case in which the channels can be discriminated perfectly. In this work, we focus on the perfect quantum channel discrimination task in a parallel scheme. We develop an SDP formulation combined with a bisection procedure to compute a quantum state for perfect discrimination in time linear in the number of copies. In addition, we obtain the minimal number of copies of quantum channels to achieve perfect discrimination. Thanks to that, we settle in the affirmative Conjecture 1 of Duan, Guo, Li and Li [arXiv:1605.02294, IEEE ISIT 2016], which characterizes the number of parallel uses needed to discriminate perfectly a distinguished family of operator subspaces. All our results are obtained using the notion and basic properties of the numerical range. In particular, the key fact that we prove and use is that the minimal angle of the numerical range of a tensor product of matrix Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com