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:2510.07798

Efficient Matrix Product State Learning in Logarithmic Depth

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

Published Oct 9, 2025• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2510.07798

Related papers

Learning the Closest Product State

Ainesh Bakshi, John Bostanci, William Kretschmer +5 more

We study the problem of finding a (pure) product state with optimal fidelity to an unknown $n$-qubit quantum state $ρ$, given copies of $ρ$. This is a basic instance of a fundamental question in quantum learning: is it possible to efficiently learn a simple approximation to an arbitrary state? We give an algorithm which finds a product state with fidelity $\varepsilon$-close to optimal, using $N = n^{\text{poly}(1/\varepsilon)}$ copies of $ρ$ and $\text{poly}(N)$ classical overhead. We further show that estimating the optimal fidelity is NP-hard for error $\varepsilon = 1/\text{poly}(n)$, showing that the error dependence cannot be significantly improved. For our algorithm, we build a carefully-defined cover over candidate product states, qubit by qubit, and then demonstrate that extending the cover can be reduced to approximate constrained polynomial optimization. For our proof of hardness, we give a formal reduction from polynomial optimization to finding the closest product state. Together, these results demonstrate a fundamental connection between these two seemingly unrelated questions. Building on our general approach, we also develop more efficient algorithms in three simpler settings: when the optimal fidelity exceeds $5/6$; when we restrict ourselves to a discrete class of product states; and when we are allowed to output a matrix product state.

arXiv:2411.04283•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•1 citation

Exact log-depth preparation of highly entangled matrix product states

Keisuke Murota, Frédéric Sauvage, Marco Ballarin +2 more

Preparing matrix product states (MPS) on a quantum device is a key subroutine in many quantum algorithms. The most competitive methods, based on the renormalisation group, prepare translationally invariant MPS of size $L$ and bond dimension $χ$, up to an error $\varepsilon$, in circuit depth $\tilde O(χ^{4}\log(L/\varepsilon))$ or $\tilde O(χ^{6}\log\log(L/\varepsilon))$. We improve multiple aspects of these methods. First, using block-encoded correction maps, whose post-selection succeeds with constant probability, we render the preparation exact without sacrificing the scaling in $L$. Second, through a generalisation of oblivious amplitude amplification to isometries, we reduce the bond-dimension dependence, improving the depth to $\tilde O(χ^{2}\log L + χ^{4})$ or $\tilde O(χ^{2}\log\log L + χ^{4})$, and even to $\tilde O(χ^{3}\log L)$ for incoherent preparations. Finally, we extend the framework to non-translationally invariant MPS and prove logarithmic-depth exact preparation for independent and identically distributed random tensor sequences. Confirmed by numerical studies, these results constitute, to the best of our knowledge, the most efficient exact MPS preparation protocols in the relevant parameter regimes.

quant-pharXiv:2606.24475•Jun 24, 2026•0 citations

Efficient Learning of Clifford-Scrambled Product States

Tobias Haug

Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn $n$-qubit states prepared by random $T$-doped Clifford circuits with $T$-gate density below one via $O(n^2)$ Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn $T$-depth-one circuits using $O(n^2)$ queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.

quant-pharXiv:2609.27128•Sep 24, 2026•0 citations

Quantum State Preparation by Improved MPS Method

Chao Wang, Zhou, Pengrui, Xi‐Ning Zhuang +4 more

Efficient encoding of classical information plays a fundamental role in numerous practical quantum algorithms. However, the preparation of an arbitrary amplitude-encoded state has been proven to be time-consuming, and its deployment on current noisy devices can be challenging. In this work, we propose an improved Matrix Product State(MPS) method preparation protocol with an exponential reduction on the circuit depth, as well as topological adaptability. By refined utilization of the disentangling principle, we also reduce approximately 33% two-qubit gate count. To validate our method, we study various families of functions and distributions with provably bounded MPS rank. Numerical experiments show that our method significantly reduces circuit depth while achieving higher fidelity for states arising in financial and other applications.

arXiv:2508.12821•Aug 18, 2025•1 citation

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

Efficient Noisy Quantum State and Process Tomography

Chenyang Li, Shengxin Zhuang, Yukun Zhang +4 more

Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy $n$-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit ($γ= 0$) and the strong-decoherence regime ($γ= Θ(1)$). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.

quant-pharXiv:2603.01521•Quantum Science and Technology•Mar 3, 2026•0 citations
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.
We study the problem of finding a (pure) product state with optimal fidelity to an unknown nnn-qubit quantum state ρρρ, given copies of ρρρ. This is a basic instance of a fundamental question in quantum learning: is it possible to efficiently learn a simple approximation to an arbitrary state? We give an algorithm which finds a product state with fidelity ε\varepsilonε-close to optimal, using N=npoly(1/ε)N = n^{\text{poly}(1/\varepsilon)}N=npoly(1/ε) copies of ρρρ and poly(N)\text{poly}(N)poly(N) classical overhead. We further show that estimating the optimal fidelity is NP-hard for error ε=1/poly(n)\varepsilon = 1/\text{poly}(n)ε=1/poly(n), showing that the error dependence cannot be significantly improved. For our algorithm, we build a carefully-defined cover over candidate product states, qubit by qubit, and then demonstrate that extending the cover can be reduced to approximate constrained polynomial optimization. For our proof of hardness, we give a formal reduction from polynomial optimization to finding the closest product state. Together, these results demonstrate a fundamental connection between these two seemingly unrelated questions. Building on our general approach, we also develop more efficient algorithms in three simpler settings: when the optimal fidelity exceeds 5/65/65/6; when we restrict ourselves to a discrete class of product states; and when we are allowed to output a matrix product state.
Preparing matrix product states (MPS) on a quantum device is a key subroutine in many quantum algorithms. The most competitive methods, based on the renormalisation group, prepare translationally invariant MPS of size LLL and bond dimension χχχ, up to an error ε\varepsilonε, in circuit depth O~(χ4log⁡(L/ε))\tilde O(χ^{4}\log(L/\varepsilon))O~(χ4log(L/ε)) or O~(χ6log⁡log⁡(L/ε))\tilde O(χ^{6}\log\log(L/\varepsilon))O~(χ6loglog(L/ε)). We improve multiple aspects of these methods. First, using block-encoded correction maps, whose post-selection succeeds with constant probability, we render the preparation exact without sacrificing the scaling in LLL. Second, through a generalisation of oblivious amplitude amplification to isometries, we reduce the bond-dimension dependence, improving the depth to O~(χ2log⁡L+χ4)\tilde O(χ^{2}\log L + χ^{4})O~(χ2logL+χ4) or O~(χ2log⁡log⁡L+χ4)\tilde O(χ^{2}\log\log L + χ^{4})O~(χ2loglogL+χ4), and even to O~(χ3log⁡L)\tilde O(χ^{3}\log L)O~(χ3logL) for incoherent preparations. Finally, we extend the framework to non-translationally invariant MPS and prove logarithmic-depth exact preparation for independent and identically distributed random tensor sequences. Confirmed by numerical studies, these results constitute, to the best of our knowledge, the most efficient exact MPS preparation protocols in the relevant parameter regimes.
Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn nnn-qubit states prepared by random TTT-doped Clifford circuits with TTT-gate density below one via O(n2)O(n^2)O(n2) Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn TTT-depth-one circuits using O(n2)O(n^2)O(n2) queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.
Efficient encoding of classical information plays a fundamental role in numerous practical quantum algorithms. However, the preparation of an arbitrary amplitude-encoded state has been proven to be time-consuming, and its deployment on current noisy devices can be challenging. In this work, we propose an improved Matrix Product State(MPS) method preparation protocol with an exponential reduction on the circuit depth, as well as topological adaptability. By refined utilization of the disentangling principle, we also reduce approximately 33% two-qubit gate count. To validate our method, we study various families of functions and distributions with provably bounded MPS rank. Numerical experiments show that our method significantly reduces circuit depth while achieving higher fidelity for states arising in financial and other applications.
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.
Efficiently characterizing large quantum states and processes is a central yet notoriously challenging task in quantum information science, as conventional tomography methods typically require resources that grow exponentially with system size. Here, we introduce a structure-agnostic learning framework for noisy nnn-qubit quantum circuits under~i.i.d.~single-qubit noise. We first prove that quantum states with unital noise channels admit an efficient learnable representation in the logarithmic-depth regime. We then extend this framework to quantum process tomography under constant noise, deriving a unified protocol that applies to both unital and non-unital noisy channels and retains efficient guarantees for logarithmic-depth circuits. This process-learning formulation is input-agnostic and imposes no distributional assumptions on the input quantum states. We further study a more general regime with arbitrary noise strength. In this setting, low-weight Pauli propagation induces a terminal truncation whose threshold depends logarithmically on the inverse accuracy, leading to quasi-polynomial complexity and near-unit success probability in the average case. In contrast to the preceding two results, this arbitrary-noise guarantee does not impose any restriction on the circuit depth, and therefore covers arbitrary-depth circuits, including both the noiseless limit (γ=0γ= 0γ=0) and the strong-decoherence regime (γ=Θ(1)γ= Θ(1)γ=Θ(1)). Numerical simulations of two-dimensional Hamiltonian dynamics further demonstrate the accuracy and robustness of the approach, including for structured circuits beyond the random-circuit setting assumed in the theoretical analysis. These results provide a scalable and practically relevant route toward characterizing large-scale noisy quantum devices, addressing a key bottleneck in the development of quantum technologies.