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.
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.
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.
Watrous conjectured that the randomized and quantum query complexities of symmetric functions are polynomially equivalent, which was resolved by Aaronson & Ambainis (2014) and was later improved by Chailloux (2019) and Ben-David et al. (2020). This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to 1/2 1 / 2 . Our contributions include the following: 1. We analyze the optimal success probabilities of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of queries. 2. We establish that for any total symmetric Boolean function f f , if a quantum algorithm uses T T queries to compute f f with success probability 1/2+β 1 / 2 + β , then there exists a randomized algorithm using O(T2) O ( T 2 ) queries to compute f f with success probability 1/2+Ωδβ2 1 / 2 + Ω δ β 2 on a 1−δ 1 - δ fraction of inputs, where β,δ β , δ can be arbitrarily small positive values. Moreover, we prove a randomized version of Aaronson-Ambainis Conjecture (Aaronson & Ambainis 2014) for symmetric Boolean functions in the regime where the success probability of algorithms can be arbitrarily close to 1/2. 3. We present tight polynomial equivalence for several fundamental complexity measures of partial symmetric Boolean functions.
We consider the problem of establishing limitations on the power of quantum query algorithms via the completely bounded polynomial method. In particular, we prove several optimal functional inequalities involving different notions of completely bounded polynomials. These inequalities lead to limiting theorems for the power of quantum query algorithms that improve on prior works.
1. An optimal root-influence bound for block-multilinear polynomials. Prior work showed that block-multilinear polynomials p of degree t satisfy a root-influence bound, ∥p∥cb≥∑iInfi[p]/t2, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: ∥p∥cb≥∑iInfi[p]/t. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as t-fold forrelation- are block-multilinear polynomials with ∥p∥cb≤1, our inequality shows that they satisfy t≥∑iInfi[p]. We prove that this inequality yields both a more efficient classical simulation than prior results based on the Aaronson-Ambainis argument, and a qualitative improvement: all classical queries are nonadaptive.
2. Optimal Fourier growth of the highest level of quantum query algorithms. We show that for every polynomial p defined on {−1,1}n of degree 2t, the Fourier Growth at the level 2t, namely ∥p2t∥ℓ1, satisfies ∥p2t∥ℓ1≤(en/(2t−1))22t−1∥p∥cb. This is optimal up to the factor e, as witnessed by 2t-fold forrelation. As quantum query algorithms that make t queries (to the whole input) satisfy ∥p∥cb≤1, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).
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.
In this thesis, Quantum computing, norms, and polynomials, we investigate the interplay between quantum mechanics, complexity theory, and functional analysis, three central areas of physics, computer science, and mathematics, respectively. The unifying theme throughout the thesis is the dynamic exchange between quantum computing and functional analysis: we explore new applications of functional inequalities in quantum computing, and, in the process, establish novel results in functional analysis itself. In the first part, we study quantum query algorithms through their correspondence with completely bounded polynomials, as established in earlier work. We begin by revisiting this correspondence, extending it, and presenting it in a new form. Building on this foundation, we draw an analogy between quantum query algorithms and the Grothendieck inequality. Finally, we conclude this part by employing completely bounded polynomials to solve a special case of one of the main open problems in quantum query complexity, the Aaronson–Ambainis conjecture. In the second part, we turn to quantum learning theory, which seeks to determine how much information must be extracted from a quantum system to fully characterize it. We begin by applying existing versions of the Bohnenblust–Hille inequalities and deriving new ones to obtain results in the learning of low-degree quantum objects. We conclude by presenting some of the first results in the emerging area of Hamiltonian testing and learning. We also include a third part, as a bonus, where we gather three new proofs, that we find elegant and concise, of known results related to the analysis of Boolean functions.
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.