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,1}^n$, 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(\mathrm{opt}\log(1/\mathrm{opt}))$, where $\mathrm{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).
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).
Preparing complex quantum states is of limited value without efficient methods for extracting useful classical information from them. This thesis studies when such information can be extracted efficiently, given copies of an unknown quantum state or query access to an unknown unitary transformation. We begin with pure state tomography. We present an algorithm that uses only nonadaptive single-qubit Pauli measurements yet achieves optimal copy and time complexities up to logarithmic factors. This is the first full state tomography algorithm with near-optimal running time. We then show how additional structure can make tomography time-efficient, giving algorithms for two structured classes of quantum states: non-interacting fermions and near-stabilizer states. We also introduce a new learning task, agnostic tomography, where the goal is to find the best approximation to an arbitrary quantum state from a structured class of states, and give efficient algorithms in this model. Turning to property testing, we give an efficient tester for stabilizer dimension, which implies that Ω(n) T-gates are necessary for any Clifford+T circuit to prepare n-qubit computationally pseudorandom states. We also prove copy-complexity lower bounds for testing low-degree phase states, showing that testing is nearly as hard as learning these states. More strongly, for every fixed degree d, ensembles of n-qubit degree-d phase states form exponentially accurate approximate state t-designs for t=Ω(n^{⌊(d-1)/2⌋}). Finally, we extend these questions from states to unitary transformations. We develop a general framework for learning unitary transformations by exploiting low-complexity Pauli spectra. This framework unifies and extends prior learning algorithms for Clifford and near-Clifford circuits, shallow circuits, quantum juntas, and fermionic matchgate circuits.
We define a quantum learning task called agnostic tomography , where given copies of an arbitrary state ρ and a class of quantum states C , the goal is to output a succinct description of a state that approximates ρ at least as well as any state in C (up to some small error ε ). This task generalizes ordinary quantum tomography of states in C and is more challenging because the learning algorithm must be robust to perturbations of ρ .We give an efficient agnostic tomography algorithm for the class C of n -qubit stabilizer product states. Assuming ρ has fidelity at least τ with a stabilizer product state, the algorithm runs in time n O ( log ( 2 / τ ) ) / ε 2 , which is p o l y ( n / ε ) for any constant τ .
We study the task of agnostic tomography: given copies of an unknown n-qubit state ρ which has fidelity τ with some state in a given class C, find a state which has fidelity ≥τ−ε with ρ. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: Stabilizer states: We give a protocol that runs in time poly(n,1/ε)⋅(1/τ)O(log(1/τ)), answering an open question posed by Grewal, Iyer, Kretschmer, Liang [43] and Anshu and Arunachalam [6]. Previous protocols ran in time exp(Θ(n)) or required τ>cos2(π/8). States with stabilizer dimension n−t: We give a protocol that runs in time n3⋅(2t/τ)O(log(1/ε)), extending recent work on learning quantum states prepared by circuits with few non-Clifford gates, which only applied in the realizable setting where τ=1 [33, 40, 49, 66]. Discrete product states: If C=K⊗n for some μ-separated discrete set K of single-qubit states, we give a protocol that runs in time (n/μ)O((1+log(1/τ))/μ)/ε2. This strictly generalizes a prior guarantee which applied to stabilizer product states [42]. For stabilizer product states, we give a further improved protocol that runs in time (n2/ε2)⋅(1/τ)O(log(1/τ)). As a corollary, we give the first protocol for estimating stabilizer fidelity, a standard measure of magic for quantum states, to error ε in n3quasipoly(1/ε) time.
We give a general framework for tomography of states that have bounded-extent with respect to a structured class of states. Let C be a family of n-qubit states such that: (i)C is succinctly representable and (ii) there is a weak agnostic learner of C. We give a tomography protocol for an unknown state ∣ψ⟩ that is promised to admit a decomposition of the form ∣ψ⟩=∑ici∣φi⟩, where ∣φi⟩∈C with bounded ℓ1-norm of the coefficients (which we call extent). Our main contribution is to show that a weak agnostic learner for C can be boosted into a tomography algorithm for states with bounded extent with respect to C.
Our reduction is black-box and applies broadly across model classes. As an application, when C is the class of stabilizer states, we obtain tomography algorithms for states with stabilizer extent ξ up to trace distance ε, in time poly(n,(ξ/ε)log(ξ/ε)), which is improvable to $ \textsf{poly}(n,ξ,1/\varepsilon)$ assuming the algorithmic polynomial Freiman-Ruzsa conjecture in the high-doubling regime. When the unknown state ∣ψ⟩ is arbitrary, we give an algorithmic decomposition result in the spirit of a weak regularity lemma for quantum states with respect to C and show that the structure in ∣ψ⟩ that is explainable by C can be efficiently learned. Our main conceptual message is that agnostic learning of a structured base class automatically yields learnability of its low-complexity linear span.
We study the problem of tomography for k-sparse quantum states. In contrast to classical distribution learning, where tight sample and time complexity bounds in terms of support size are well understood, no non-trivial bounds were previously shown for this problem. We give the first near optimal algorithm for learning n-qubit k-sparse pure quantum states, obtaining fidelity at least 1−ε with high probability using O~(k/ε) copies of the state and O~(kn/ε) time. Both bounds are optimal up to polylogarithmic factors. As an implication, we also obtain an algorithm with near optimal O~(kr/ε) sample complexity for learning k-sparse rank-r mixed states, via the random purification channel technique. Obtaining time complexity nearly matching the sample complexity, for r>1, remains an important open question.
We study agnostic tomography of pure bosonic Gaussian states: given copies of an arbitrary n-mode bosonic state ρ, the goal is to output a pure Gaussian state whose infidelity with ρ is at most opt+ε, where opt is the minimum infidelity achievable by any pure Gaussian state.
We give efficient protocols achieving this in both the high and low fidelity regimes. When opt is below some universal constant, our protocol has runtime and copy complexity which is strongly polynomial in n,1/ε and loglogE, where E is the energy of the closest pure Gaussian state. For arbitrary opt, our protocol uses (n+1)poly(1/ε)poly(1+loglog(E)) copies and runtime. As a corollary, we obtain the first truly tolerant Gaussianity testing protocol for distinguishing whether opt>c+ε or opt<c−ε, for any threshold c∈(0,1). We also prove poly(n,1/ε) runtime is impossible, unless NP⊆BQP.
Our protocols follow a shared paradigm: first, we iteratively use general Gaussian measurements combined with techniques from classical robust statistics to obtain a good warm start estimate, then we leverage non-Gaussian measurements to refine this warm start using convex and non-convex optimization methods. Interestingly, we prove that non-Gaussian measurements are necessary to match the strong agnostic guarantees we obtain, and in fact these guarantees are provably superior to what is possible for robustly estimating classical Gaussians.