Learning the Closest 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 = n poly(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. a quantum computer, by preparing copies of the state and running the algorithm to estimate OPT, giving an advantage when such states are classically intractable. Despite the apparent simplicity of the problem, relatively little was known about the computational complexity of Problem 1. From a statistical point of view, one can obtain sampleefficient learners via classical shadow estimation [HKP20] or shadow tomography [Aar20], but these estimators require exponential runtime. On the other hand, efficient algorithms were known only for highly restricted versions of the problem [GIKL24]. This lack of efficient algorithms might be surprising, as when when the unknown state ρ is a product state, i.e. OPT = 1, this task is easy: many algorithms work, including learning every register separately. However, these algorithms are brittle, and fail catastrophically when OPT < 0.99. Even algorithms for the related problem of product state testing, initiated by the important work of Harrow and Montanaro [HM13], do not admit estimates of OPT when OPT is bounded away from 1. In contrast, one would hope to obtain efficient algorithms even when OPT is a small constant (say, 0.1): product states with constant fidelity are still great approximations, considering that almost all product states will have fidelity exponentially small in n. Beyond specific applications, we hope that understanding this algorithmic task can shed light on a broader program in quantum learning theory. An emerging line of work has been studying "learning the closest state in a hypothesis class", also known as agnostic tomography: formally, this problem is Problem 1, except the class of product states P is replaced with a different hypothesis class C. Product states appear as a special case of several well-studied classes of quantum states, including states described by low-depth quantum circuits, matrix product states, and Gibbs states and ground states of local Hamiltonians. Understanding the computational complexity of agnostic tomography of product states is therefore an important stepping stone to building up to richer approximations. As we demonstrate below, it turns out that learning the closest product state is already a surprisingly deep problem.