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 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.
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.
k-Clustering in Rd (e.g., k-median and k-means) is a fundamental machine learning problem. While near-linear time approximation algorithms were known in the classical setting for a dataset with cardinality n, it remains open to find sublinear-time quantum algorithms. We give quantum algorithms that find coresets for k-clustering in Rd with O~(nkd3/2) query complexity. Our coreset reduces the input size from n to poly(kε−1d), so that existing α-approximation algorithms for clustering can run on top of it and yield (1+ε)α-approximation. This eventually yields a quadratic speedup for various k-clustering approximation algorithms. We complement our algorithm with a nearly matching lower bound, that any quantum algorithm must make Ω(nk) queries in order to achieve even O(1)-approximation for k-clustering.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R the ratio of the maximum value of f to the maximum (over T∈Q) standard deviation of f on a subcube whose free variables are exactly T.'
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
The problem of minimizing the maximum of N convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring O(Nε−2/3+ε−8/3) queries to a first-order oracle to compute an ε-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of N convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of O~(Nε−5/3+ε−8/3). On the other hand, we prove that quantum algorithms must take Ω~(Nε−2/3) queries to a first order quantum oracle, showing that our dependence on N is optimal up to poly-logarithmic factors.
We investigate the Goldreich-Levin Theorem in the context of quantum information. This result is a reduction from the computational problem of inverting a one-way function to the problem of predicting a particular bit associated with that function. We show that the quantum version of the reduction -- between quantum one-way functions and quantum hard-predicates -- is quantitatively more efficient than the known classical version. Roughly speaking, if the one-way function acts on n-bit strings then the overhead in the reduction is by a factor of O(n/epsilon^2) in the classical case but only by a factor of O(1/epsilon) in the quantum case, where 1/2 + epsilon is the probability of predicting the hard-predicate. Moreover, we prove via a lower bound that, in a black-box framework, the classical version of the reduction cannot have overhead less than order n/epsilon^2. We also show that, using this reduction, a quantum bit commitment scheme that is perfectly binding and computationally concealing can be obtained from any quantum one-way permutation. This complements a recent result by Dumais, Mayers and Salvail, where the bit commitment scheme is perfectly concealing and computationally binding. We also show how to perform qubit commitment by a similar approach.
In the quantum linear systems problem (QLSP), we are given query access to a d-sparse N×N matrix A with condition number κ, and the ability to prepare a quantum state proportional to a vector b. The goal is to output an ε-approximation to the quantum state proportional to the solution x of Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κd(κd/ε)o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κd). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×N unitary can be implemented with bounded error using O(N) queries to its matrix entries.