We prove algorithmic versions of the polynomial Freiman-Ruzsa theorem of Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) in additive combinatorics. In particular, we give classical and quantum polynomial-time algorithms that, for $A \subseteq \mathbb{F}_2^n$ with doubling constant $K$, learn an explicit description of a subspace $V \subseteq \mathbb{F}_2^n$ of size $|V| \leq |A|$ such that $A$ can be covered by $K^C$ translates of $V$, for a universal constant $C>1$.

We introduce a systematic study of "symmetric quantum circuits", a new restricted model of quantum computation that preserves the symmetries of the problems it solves. This model is well-adapted for studying the role of symmetry in quantum speedups, extending a central notion of symmetric computation studied in the classical setting. Our results establish that symmetric quantum circuits are fundamentally more powerful than their classical counterparts. First, we give efficient symmetric circuits for key quantum techniques such as amplitude amplification, phase estimation and linear combination of unitaries. In addition, we show how the task of symmetric state preparation can be performed efficiently in several natural cases. Finally, we demonstrate an exponential separation in the symmetric setting for the problem XOR-SAT, which requires exponential-size symmetric classical circuits but can be solved by polynomial-size symmetric quantum circuits.

We present a quadratic Goldreich–Levin algorithm that is nearly optimal in the following ways. Given a bounded function \(f : \mathbb{F}_2^n \to \mathbb{R}\) and any \(\varepsilon \gt 0\), the algorithm outputs a quadratic polynomial \(q : \mathbb{F}_2^n \to \mathbb{F}_2\) whose correlation with \((-1)^q\) is within an additive \(\varepsilon\) of the maximum achievable correlation with any quadratic phase function. It runs in \(O_\varepsilon(n^3)\) time and makes \(O_\varepsilon(n^2 \log n)\) 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 consider the problem of decoding corrupted error correcting codes with NC0[⊕] circuits in the classical and quantum settings. We show that any such classical circuit can correctly recover only a vanishingly small fraction of messages, if the codewords are sent over a noisy channel with positive error rate. Previously this was known only for linear codes with large dual distance, whereas our result applies to any code. By contrast, we give a simple quantum circuit that correctly decodes the Hadamard code with probability Ω(ε2) even if a (1/2 − ε)-fraction of a codeword is adversarially corrupted. Our classical hardness result is based on an equidistribution phenomenon for multivariate polynomials over a finite field under biased input-distributions. This is proved using a structure- versus-randomness strategy based on a new notion of rank for high-dimensional polynomial maps that may be of independent interest. Our quantum circuit is inspired by a non-local version of the Bernstein-Vazirani problem, a technique to generate “poor man’s cat states” by Watts et al., and a constant-depth quantum circuit for the OR function by Takahashi and Tani.