Learning the closest product state

Abstract

We study the problem of finding a (pure) product state with optimal fidelity to an unknown $n$-qubit quantum state $\rho$, given copies of $\rho$. 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 $\epsilon$-close to optimal, using $N=n^{\text{poly}(1/\epsilon )}$ copies of $\rho$ and $\text{poly}(N)$ classical overhead. We further show that estimating the optimal fidelity is NP-hard for error $\epsilon =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.

75 pages. V3: writing improvements in the introduction. To appear in STOC 2025

References in corpus (12)

• The density-matrix renormalization group in the age of matrix product states
• Barren plateaus in quantum neural network training landscapes
• Quantifying Entanglement
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Geometric measure of entanglement and applications to bipartite and multipartite quantum states
• Efficient quantum state tomography
• Is there evidence for exponential quantum advantage in quantum chemistry?
• Concurrence of mixed multi-partite quantum states
• Equivalence of critical scaling laws for many-body entanglement in the Lipkin-Meshkov-Glick model
• Global entanglement and quantum criticality in spin chains
• Visualizing elusive phase transitions with geometric entanglement
• Improved quantum data analysis

Cited by in corpus (1)

• Agnostic Tomography of Stabilizer Product States