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.
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 ε-close to optimal, using N=npoly(1/ε) copies of ρ and poly(N) classical overhead. We further show that estimating the optimal fidelity is NP-hard for error ε=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/6; when we restrict ourselves to a discrete class of product states; and when we are allowed to output a matrix product state.
We address the problem of testing whether an unknown n-qudit state ρ is a-close to a product state or b-far away from any product state, as measured in terms of state overlap. We provide a time-efficient algorithm to solve this problem that requires an n-independent number of copies of the unknown state. Our random coloring argument shows that for any unknown state there always exists a partition of [n] into q parts such that the square of the overlap with the closest product state with respect to this partition is only an additive factor O(1/q) larger. This reduces the problem to tolerant testing of q parties, with potentially growing local dimensions. Combining this insight with blockwise spectral projection arguments we can show that the natural k-copy generalization of Harrow & Montanaro's product state test provides an efficient tolerant tester.
We use the same random coloring and blockwise spectral projection techniques to obtain a substantially improved algorithm for closest product state learning. In particular we give an algorithm that takes in O((nd)2)2O(1/ε8) copies of the unknown state and produces an ε-approximately optimal product state. The key technical components of this learner are a qudit variant of the Bakshi et al. high-fidelity product state learning algorithm and a sampling technique based on Werner's optimal cloning channel.
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) 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(logn) and sample complexity O(n3), 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 n9 to n7 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(qn1/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.
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 ∣ψ⟩ of chosen bond dimension such that ⟨ψ∣ρ∣ψ⟩ is within ε 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/ε, 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.
Learning compact, interpretable descriptions of quantum many-body states is an important task in quantum science. We study the task of learning the Slater determinant with maximum fidelity to an arbitrary fermionic many-body state, with motivation from both Hartree-Fock methods and agnostic tomography. Given an n-fermion wavefunction built from m fermionic modes, we provide classical and quantum algorithms returning a Slater determinant with fidelity within ε of maximal in time mpoly(n,1/ε). We prove matching hardness lower bounds, assuming standard complexity conjectures, along some parameter axes. Given access to quantum copies, we prove this can be accomplished with poly(m,n,1/ε) copies of ρ. We also show that above a fidelity of 2/3 any stationary point is the unique global maximum while below 2/3 the optimization landscape can have spurious stationary points, and hence 2/3 marks a transition point in the optimization landscape for this problem. We apply the algorithm to the Fermi-Hubbard model, extracting the closest Slater determinant from neural quantum state solutions. Together, our results provide algorithmic tools with provable guarantees in understanding fermionic many-body systems with classical or quantum simulation.
It is well-known that learning a pure n-qubit stabilizer state ∣ψ⟩ both requires, and can be accomplished with, access to a number of copies of ∣ψ⟩ linear in n. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that Lδ(n), the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most 0<δ<1/8, satisfies n+⌈log2(1/δ)⌉−3≤Lδ(n)≤n+⌈log2(1/δ)⌉+4. We present a polynomial-time quantum learning algorithm that saturates this bound, achieving a constant factor improvement in sample-complexity over previously known approaches. As an immediate corollary, we obtain via the Choi-Jamiolkowski isomorphism an algorithm for learning an unknown n-qubit Clifford unitary from 2n+⌈log2(1/δ)⌉+4 queries, the n-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group Z4n×F2n(n−1)/2, seems to be qualitatively different to previous approaches to stabilizer state learning, and may be of some independent interest; in particular, it admits natural generalisations to further problems in quantum learning theory.
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,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)), where 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).