Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman-Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampling and membership-oracle access to a set $A \subseteq \mathbb{F}_2^n$ with doubling constant at most $K$, our algorithm outputs a subspace of size at most $|A|$ whose $K^{O(1)}$ translates cover $A$. The algorithm runs in $\textsf{poly}(n,K)$ time. As applications, we obtain polynomial-time algorithms for a variety of learning problems, including quadratic Goldreich-Levin, improper agnostic tomography of stabilizer states, and tomography of quantum states with bounded stabilizer extent.
Gowers, Green, Manners, and Tao (Annals '25) recently resolved Marton's polynomial Freiman-Ruzsa conjecture. We give an algorithmic counterpart to their result: given uniform sampling and membership-oracle access to a set A⊆F2n with doubling constant at most K, our algorithm outputs a subspace of size at most ∣A∣ whose KO(1) translates cover A. The algorithm runs in poly(n,K) time. As applications, we obtain polynomial-time algorithms for a variety of learning problems, including quadratic Goldreich-Levin, improper agnostic tomography of stabilizer states, and tomography of quantum states with bounded stabilizer extent.
We present a quadratic Goldreich–Levin algorithm that is nearly optimal in the following ways. Given a bounded function f:F2n→R and any ε>0, the algorithm outputs a quadratic polynomial q:F2n→F2 whose correlation with (−1)q is within an additive ε of the maximum achievable correlation with any quadratic phase function. It runs in Oε(n3) time and makes Oε(n2logn) queries to f, matching the information-theoretic lower bound up to a logarithmic factor. The design of our algorithm draws on ideas from recent advances in quantum learning theory and departs from previous approaches based on algorithmic proofs of the inverse theorem for the Gowers uniformity norms.
We study quantum random self-reductions for linear problems over finite fields. Let M∈Fn×n be an arbitrary matrix, and let O be an oracle that agrees with the linear map x↦Mx on an ε-fraction of inputs x∼Fn. Given coherent access to O and coherent entry access to M, we give a uniform quantum reduction that computes Mx on any prescribed input x with probability at least 2/3 in time O(nT1/3), for n≤T≤n3/2 and constant field size and ε, where T is the cost of one coherent query to O. In particular, when T=O(n), the reduction runs in time O(n4/3), improving the O(n3/2+T) reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024).
Our reduction uses the Bogolyubov--Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov--Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.
We consider the following task: suppose an algorithm is given copies of an unknown n-qubit quantum state ∣ψ⟩ promised (i)∣ψ⟩ is ε1-close to a stabilizer state in fidelity or (ii)∣ψ⟩ is ε2-far from all stabilizer states, decide which is the case. We show that for every ε1>0 and ε2≤ε1C, there is a poly(1/ε1)-sample and n⋅poly(1/ε1)-time algorithm that decides which is the case (where C>1 is a universal constant). Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-3 norm of quantum states and new bounds on stabilizer covering for structured subsets of Paulis using results in additive combinatorics.
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 show an improved inverse theorem for the Gowers-3 norm of n-qubit quantum states ∣ψ⟩ which states that: for every γ≥0, if the Gowers(∣ψ⟩,3)8≥γ then the stabilizer fidelity of ∣ψ⟩ is at least γC for some constant C>1. This implies a constant-sample polynomial-time tolerant testing algorithm for stabilizer states which accepts if an unknown state is ε1-close to a stabilizer state in fidelity and rejects when ∣ψ⟩ is ε2≤ε1C-far from all stabilizer states, promised one of them is the case.
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.