We study the effects of random restrictions on low degree functions that are bounded on every point of the Boolean cube. Our main result shows that, with high probability, the restricted function can be approximated by a junta of arity that is just polynomial in the original degree. More precisely, let f: {± 1}ⁿ → [0,1] be a degree d polynomial (d ≥ 2) and let ρ denote a random restriction with survival probability O(log(d)/d). Then, with probability at least 1-d^{-Ω(1)}, there exists a function g: {± 1}ⁿ → [0,1] depending on at most d^O(1) coordinates such that ||f_{ρ}-g||_2^2 ≤ d^{-1-Ω(1)}. Our result has the following consequence for the well known, outstanding conjecture of Aaronson and Ambainis. The Aaronson-Ambainis conjecture was formulated to show that the acceptance probability of a quantum query algorithm can be well approximated almost everywhere by a classical query algorithm with a polynomial blow-up: it speculates that a polynomal f: {± 1}ⁿ → [0,1] with degree d has a coordinate with influence ≥ poly(1/d, Var[f]). Our result shows that this is true for a non-negligible fraction of random restrictions of f assuming Var[f] is not too low. Our work combines the ideas of Dinur, Friedgut, Kindler and O'Donnell [Dinur et al., 2006] with an approximation theoretic result, first reported in the recent work of Filmus, Hatami, Keller and Lifshitz [Yuval Filmus and Hamed Hatami, 2014].
In an attempt to show that the acceptance probability of a quantum query algorithm making
q queries can be well-approximated almost everywhere by a classical decision tree of depth
≤poly(q), Aaronson and Ambainis proposed the following conjecture: let
f:{±1}n→[0,1] be a degree
d polynomial with variance
≥ε. Then, there exists a coordinate of
f with influence
≥poly(ε,1/d). We show that for any polynomial
f:{±1}n→[0,1] of degree
d (d≥2) and variance
Var[f]≥1/d, if
ρ denotes a random restriction with survival probability
C1dlog(d),
Pr[fρ has a coordinate with influence≥dC2Var[f]2]≥50C1dVar[f]log(d) where
C1,C2>0 are universal constants. Thus, Aaronson-Ambainis conjecture is true for a non-negligible fraction of random restrictions of the given polynomial assuming its variance is not too low.
Aaronson and Ambainis conjectured that every bounded polynomial of low degree on the discrete cube has an influential variable. They showed that the conjecture implies that the acceptance probability of every quantum algorithm making
T queries can be approximated on most inputs by a classical algorithm making
poly(T) queries. We prove their conjecture: every function
f:{−1,1}n→[−1,1] of degree at most
d≥1 has a variable of influence at least
cVar(f)5/2/d6, where
c>0 is an absolute constant. In the original formulation, for polynomials of degree at most
d with values in
[0,1] on
{0,1}n and variance at least
ε, this gives a variable of influence at least
(ε/d)7. The proof is elementary, with steps inspired by works of others. Thus, as Aaronson and Ambainis anticipated, superpolynomial quantum speedups in the query model require structure, such as a promise on the inputs.
A longstanding conjecture in quantum complexity theory asserts that, under the uniform input distribution, quantum query algorithms can be polynomially simulated by classical query algorithms. More precisely, the acceptance probability of any quantum query algorithm can be approximated, on average over uniformly random inputs, by a classical query algorithm, with only polynomial query overhead. The conjecture is central to understanding whether exponential quantum advantages for decision problems necessarily rely on additional structure.
We study analogues of this conjecture under other natural input distributions and prove that they are all equivalent to the original uniform-distribution conjecture. We first consider the product distribution
μp, where the input bits are independent Bernoulli variables with fixed bias
p. We show that for every fixed
p∈(0,1), quantum query algorithms under the
μp distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution
νp that is uniform over the slice of strings with Hamming weight
⌊pn⌋ and prove a similar equivalence for the
νp distribution and the uniform distribution.
The Aaronson-Ambainis conjecture is a stronger statement that implies the above-mentioned conjecture and is formulated in terms of bounded low-degree polynomials on the Boolean hypercube. It asserts that under the uniform distribution, any such polynomial with nonnegligible variance must have an influential variable. We formulate analogues of this conjecture, where the underlying distribution is a biased product distribution or a uniform distribution over a slice, and prove that all these variants are equivalent to the original Aaronson-Ambainis conjecture.
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every
d-query quantum algorithm can be well-approximated almost everywhere (i.e., on almost all inputs) by a
poly(d)-query classical algorithm. We prove a special case of the conjecture: in every completely bounded degree-
d block-multilinear form with constant variance, there always exists a variable with influence at least
1/poly(d). In a certain sense, such polynomials characterize the acceptance probability of quantum query algorithms, as shown by Arunachalam, Briët and Palazuelos (SICOMP '19). As a corollary we obtain efficient classical almost-everywhere simulation for a particular class of quantum algorithms that includes for instance
k-fold Forrelation. Our main technical result relies on connections to free probability theory.
We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant
k-junta testing with high precision can be solved using
poly(k) quantum queries, whereas any classical algorithm requires at least
kΩ(logk) queries.
The problem of tolerant
k-junta testing is as follows: given parameters
(k,ε1,ε2), with
0≤ε1<ε2≤1/2, and black-box access to a Boolean function
f (defined on
n variables), distinguish whether
f is
ε1-close to some
k-junta or
ε2-far from every
k-junta.
We show the quantum advantage for a range of parameters close to
1/2, for example,
ε1=1/2−1/k and
ε2=1/2−1/(2k2). The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most
ε1 to
k-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick
k out of
n coordinates, and for each fixing of the
k coordinates, the
2n−k values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to
k-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making
ko(logk) queries.
A folklore conjecture in quantum computing is that the acceptance probability of a quantum query algorithm can be approximated by a classical decision tree, with only a polynomial increase in the number of queries. Motivated by this conjecture, Aaronson and Ambainis (Theory of Computing, 2014) conjectured that this should hold more generally for any bounded function computed by a low degree polynomial. In this work we prove two new results towards establishing this conjecture: first, that any such polynomial has a small fractional certificate complexity; and second, that many inputs have a small sensitive block. We show that these would imply the Aaronson and Ambainis conjecture, assuming a conjectured extension of Talagrand’s concentration inequality. On the technical side, many classical techniques used in the analysis of Boolean functions seem to fail when applied to bounded functions. Here, we develop a new technique, based on a mix of combinatorics, analysis and geometry, and which in part extends a recent technique of Knop et al. (STOC 2021) to bounded functions.