Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Leibniz international proceedings in informatics

Fractional Certificates for Bounded Functions

Shachar Lovett, Jiapeng Zhang

Published Jan 1, 2023• 2 citations
Publisher

Abstract

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.

DOI
10.4230/lipics.itcs.2023.84

Related papers

A short proof of the Aaronson-Ambainis Conjecture via the completion framework

Thomas Huffstutler, David Miloschewsky, Supartha Podder

We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function $f$ is defined on a $δ$-fraction of all $n$-bit strings and have quantum query complexity $Q(f)$, then, for every $0<ε<1$, a deterministic algorithm computes $f$ correctly on at least a $1-ε$ fraction of its domain using $O( Q(f)^6 / (εδ)^2)$ queries. Our proof uses the completion framework and establishes a more general bound in terms of the classical adversary measure. The only result we use from Turturean's recent proof is a special case of his certificate inequality, for which we provide a self-contained proof. We also derive the stronger variant of the Aaronson-Ambainis Conjecture, the bounded-polynomial influence conjecture, from our main result in the appendix.

arXiv:2611.12795•Nov 9, 2026•0 citations

Distributional Variants of the Aaronson-Ambainis Conjecture

Uma Girish, Kunal Mittal, Barak Nehoran +1 more

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 \in (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 $\lfloor pn \rfloor$ 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.

quant-pharXiv:2609.35327•Sep 29, 2026•2 citations

On the Fine-Grained Query Complexity of Symmetric Functions

Supartha Podder, Penghui Yao, Zekun Ye

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+\beta$$ 1 / 2 + β , then there exists a randomized algorithm using $$O(T^2)$$ O ( T 2 ) queries to compute $$f$$ f with success probability $$1/2+\Omega{\delta\beta^2}$$ 1 / 2 + Ω δ β 2 on a $$1-\delta$$ 1 - δ fraction of inputs, where $$\beta,\delta$$ β , δ 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.

arXiv:2309.11279•Computational Complexity•Feb 6, 2025•4 citations

Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms

Francisco Escudero Gutiérrez, Miquel Saucedo, Carlos Palazuelos

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\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2$, which is stronger than the bound appearing in the Aaronson-Ambainis conjecture. We find the optimal constant in that inequality: $\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[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\|_{\text{cb}}\leq 1,$ our inequality shows that they satisfy $t\geq \sum_i\sqrt{\mathrm{Inf}_i[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 $\|\widehat p_{2t}\|_{\ell_1}$, satisfies $\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{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\|_{\text{cb}}\leq 1$, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).

quant-pharXiv:2609.05201•Sep 7, 2026•2 citations

A proof of the Aaronson-Ambainis conjecture

David Turturean

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 $\mathrm{poly}(T)$ queries. We prove their conjecture: every function $f\colon\{-1,1\}^n\to[-1,1]$ of degree at most $d\ge1$ has a variable of influence at least $c\,\operatorname{Var}(f)^{5/2}/d^{6}$, 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 $\varepsilon$, this gives a variable of influence at least $(\varepsilon/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.

arXiv:2611.09773•Nov 6, 2026•2 citations

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Scott Aaronson, Andris Ambainis, Jānis Iraids +2 more

We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.

arXiv:1511.08682•Leibniz international proceedings in informatics•Nov 27, 2015•31 citations
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.
We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function fff is defined on a δδδ-fraction of all nnn-bit strings and have quantum query complexity Q(f)Q(f)Q(f), then, for every 0<ε<10<ε<10<ε<1, a deterministic algorithm computes fff correctly on at least a 1−ε1-ε1−ε fraction of its domain using O(Q(f)6/(εδ)2)O( Q(f)^6 / (εδ)^2)O(Q(f)6/(εδ)2) queries. Our proof uses the completion framework and establishes a more general bound in terms of the classical adversary measure. The only result we use from Turturean's recent proof is a special case of his certificate inequality, for which we provide a self-contained proof. We also derive the stronger variant of the Aaronson-Ambainis Conjecture, the bounded-polynomial influence conjecture, from our main result in the appendix.
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μ_pμp​, where the input bits are independent Bernoulli variables with fixed bias ppp. We show that for every fixed p∈(0,1)p \in (0, 1)p∈(0,1), quantum query algorithms under the μpμ_pμp​ distribution admit polynomial-overhead classical simulations if and only if the same holds under the uniform distribution. Second, we consider the distribution νpν_pνp​ that is uniform over the slice of strings with Hamming weight ⌊pn⌋\lfloor pn \rfloor⌊pn⌋ and prove a similar equivalence for the νpν_pν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/21/21/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 fff f , if a quantum algorithm uses TTT T queries to compute fff f with success probability 1/2+β1/2+\beta1/2+β 1 / 2 + β , then there exists a randomized algorithm using O(T2)O(T^2)O(T2) O ( T 2 ) queries to compute fff f with success probability 1/2+Ωδβ21/2+\Omega{\delta\beta^2}1/2+Ωδβ2 1 / 2 + Ω δ β 2 on a 1−δ1-\delta1−δ 1 - δ fraction of inputs, where β,δ\beta,\deltaβ,δ β , δ 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 ppp of degree ttt satisfy a root-influence bound, ∥p∥cb≥∑iInfi[p]/t2\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t^2∥p∥cb​≥∑i​Infi​[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\|p\|_{\text{cb}}\geq \sum_i \sqrt{\mathrm{Inf}_i[p]}/t∥p∥cb​≥∑i​Infi​[p]​/t. Since the amplitudes of quantum algorithms that query disjoint blocks of inputs-such as ttt-fold forrelation- are block-multilinear polynomials with ∥p∥cb≤1,\|p\|_{\text{cb}}\leq 1,∥p∥cb​≤1, our inequality shows that they satisfy t≥∑iInfi[p]t\geq \sum_i\sqrt{\mathrm{Inf}_i[p]}t≥∑i​Infi​[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 ppp defined on {−1,1}n\{-1,1\}^n{−1,1}n of degree 2t2t2t, the Fourier Growth at the level 2t,2t,2t, namely ∥p^2t∥ℓ1\|\widehat p_{2t}\|_{\ell_1}∥p​2t​∥ℓ1​​, satisfies ∥p^2t∥ℓ1≤(en/(2t−1))2t−12∥p∥cb\|\widehat p_{2t}\|_{\ell_1}\leq (en/(2t-1))^{\frac{2t-1}{2}}\|p\|_{\text{cb}}∥p​2t​∥ℓ1​​≤(en/(2t−1))22t−1​∥p∥cb​. This is optimal up to the factor eee, as witnessed by 2t2t2t-fold forrelation. As quantum query algorithms that make ttt queries (to the whole input) satisfy ∥p∥cb≤1\|p\|_{\text{cb}}\leq 1∥p∥cb​≤1, this yields a Fourier growth bound for these algorithms, partially resolving a question by Girish (STOC, 2026).
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 TTT queries can be approximated on most inputs by a classical algorithm making poly(T)\mathrm{poly}(T)poly(T) queries. We prove their conjecture: every function f ⁣:{−1,1}n→[−1,1]f\colon\{-1,1\}^n\to[-1,1]f:{−1,1}n→[−1,1] of degree at most d≥1d\ge1d≥1 has a variable of influence at least c Var⁡(f)5/2/d6c\,\operatorname{Var}(f)^{5/2}/d^{6}cVar(f)5/2/d6, where c>0c>0c>0 is an absolute constant. In the original formulation, for polynomials of degree at most ddd with values in [0,1][0,1][0,1] on {0,1}n\{0,1\}^n{0,1}n and variance at least ε\varepsilonε, this gives a variable of influence at least (ε/d)7(\varepsilon/d)^{7}(ε/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.
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms. Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.