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

arXiv:2008.10223 · SIAM Journal on Computing

An Optimal Separation of Randomized and Quantum Query Complexity

Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu

Published Apr 26, 2023• 23 citations
arXivHTMLPDF

Abstract

Abstract. We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order [Formula: see text] sum to at most [Formula: see text], where [Formula: see text] is the number of variables, [Formula: see text] is the tree depth, and [Formula: see text] is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal [ Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. The bounds prior to our work degraded rapidly with [Formula: see text], becoming trivial already at [Formula: see text]. As an application, we obtain, for every integer [Formula: see text], a partial Boolean function on [Formula: see text] bits that has bounded-error quantum query complexity at most [Formula: see text] and randomized query complexity [Formula: see text]. This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [ SIAM J. Comput., 47 (2018), pp. 982–1038] and Bravyi et al. [ Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: [Formula: see text] versus [Formula: see text] for any [Formula: see text] [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. As another application, we obtain an essentially optimal separation of [Formula: see text] versus [Formula: see text] for bounded-error quantum versus randomized communication complexity for any [Formula: see text]. The best previous separation was polynomially weaker: [Formula: see text] versus [Formula: see text] (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]).

DOI
10.1137/22m1468943

Related papers

An optimal separation of randomized and Quantum query complexity

Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu

We prove that for every decision tree, the absolute values of the Fourier coefficients of given order t≥1 sum to at most (cd/t)t/2(1+logn)(t−1)/2, where n is the number of variables, d is the tree depth, and c>0 is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal (arxiv 2019; FOCS 2020). The bounds prior to our work degraded rapidly with t, becoming trivial already at t=√d.

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2021•17 citations

Towards Optimal Separations between Quantum and Randomized Query Complexities

Avishay Tal

The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of O(1) vs. √N between quantum and randomized query complexities remain the state-of-the-art (where N is the input length), leaving open the question of whether O(1) vs. N1/2+Ω(1)separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. We show that our variant: 1)Can be solved by a quantum algorithm making 2O(k)queries to the inputs. 2)Requires at least ~Ω(N2(k-1)/(3k-1)) queries for any randomized algorithm. For any constant , this gives a O(1) vs. N1/2-εseparation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal O(1) vs. N1-εseparations between the quantum and randomized query complexities of partial Boolean functions.

arXiv:1912.12561•Annual Symposium on Foundations of Computer Science•Nov 1, 2020•32 citations

Fourier Growth of Parity Decision Trees.

Uma Girish, Avishay Tal, Kewen Wu

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$. Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound for standard decision trees by Sherstov, Storozhenko, and Wu (STOC, 2021). As an application of our Fourier bounds, using the results of Bansal and Sinha (STOC, 2021), we show that the $k$-fold Forrelation problem has (randomized) parity decision tree complexity $\tilde{\Omega}\left(n^{1-1/k}\right)$, while having quantum query complexity $\lceil k/2\rceil$. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-$\ell$ Fourier expression. To carry the argument, we apply a careful cleanup procedure to the parity decision tree, ensuring that the value of the random walk is bounded with high probability. We observe that step sizes for the level-$\ell$ walks can be computed by the intermediate values of level $\le \ell-1$ walks, which calls for an inductive argument. Our approach differs from previous proofs of Tal (FOCS, 2020) and Sherstov, Storozhenko, and Wu (STOC, 2021) that relied on decompositions of the tree. In particular, for the special case of standard decision trees we view our proof as slightly simpler and more intuitive. In addition, we prove a similar bound for noisy decision trees of cost at most $d$ -- a model that was recently introduced by Ben-David and Blais (FOCS, 2020).

Electronic colloquium on computational complexity•Jan 1, 2021•0 citations

Fourier Growth of Parity Decision Trees

Uma Girish, Avishay Tal, Kewen Wu

We prove that for every parity decision tree of depth $d$ on $n$ variables, the sum of absolute values of Fourier coefficients at level $\ell$ is at most $d^{\ell/2} \cdot O(\ell \cdot \log(n))^\ell$. Our result is nearly tight for small values of $\ell$ and extends a previous Fourier bound for standard decision trees by Sherstov, Storozhenko, and Wu (STOC, 2021). As an application of our Fourier bounds, using the results of Bansal and Sinha (STOC, 2021), we show that the $k$-fold Forrelation problem has (randomized) parity decision tree complexity $\tildeΩ\left(n^{1-1/k}\right)$, while having quantum query complexity $\lceil k/2\rceil$. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-$\ell$ Fourier expression. To carry the argument, we apply a careful cleanup procedure to the parity decision tree, ensuring that the value of the random walk is bounded with high probability. We observe that step sizes for the level-$\ell$ walks can be computed by the intermediate values of level $\le \ell-1$ walks, which calls for an inductive argument. Our approach differs from previous proofs of Tal (FOCS, 2020) and Sherstov, Storozhenko, and Wu (STOC, 2021) that relied on decompositions of the tree. In particular, for the special case of standard decision trees we view our proof as slightly simpler and more intuitive. In addition, we prove a similar bound for noisy decision trees of cost at most $d$ -- a model that was recently introduced by Ben-David and Blais (FOCS, 2020).

arXiv:2103.11604•Leibniz international proceedings in informatics•Jan 1, 2021•16 citations

Forrelation: A Problem That Optimally Separates Quantum from Classical Computing

Scott Aaronson, Andris Ambainis

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs $\Omega(\sqrt{N}/\log N)$ queries (improving an $\Omega(N^{1/4})$ lower bound of Aaronson). Conversely, we show that this 1 versus $\widetilde{\Omega}(\sqrt{N})$ separation is optimal: indeed, any $t$-query quantum algorithm whatsoever can be simulated by an $O(N^{1-1/2t})$-query randomized algorithm. Thus, resolving an open question of Buhrman et al. [ SIAM J. Comput., 37 (2008), pp. 1387--1400] from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal $t$ versus $\Omega(N^{1-1/2t})$ separation for all $t$. As a bonus, we show that this generalization is ${BQP}$-complete. This yields what is arguably the simplest ${BQP}$-complete problem yet known and gives a second sense in which Forrelation “captures the maximum power of quantum computation.”

arXiv:1411.5729•SIAM Journal on Computing•Jan 1, 2018•90 citations

Separations in Query Complexity Based on Pointer Functions

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3 more

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2 k bits defined by a complete binary tree of NAND gates of depth k , which achieves R 0 ( f ) = O ( D ( f ) 0.7537… ). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is Ω( n ) while its zero-error randomized query complexity is Õ(√ n ). We further show that the quantum query complexity of the same function is Õ( n 1/4 ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Ω( n / log ( n )) and bounded-error randomized query complexity R ( g ) = Õ(√ n ). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q E ( g ) = Õ(√ n ). These functions show that the relations D ( f ) = O ( R 1 ( f ) 2 ) and R 0 ( f ) = Õ( R ( f ) 2 ) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R 0 , a 3/2-power separation between Q E and R , and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Göös, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

arXiv:1506.04719•Journal of the ACM•Sep 4, 2017•60 citations
Abstract. We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order [Formula: see text] sum to at most [Formula: see text], where [Formula: see text] is the number of variables, [Formula: see text] is the tree depth, and [Formula: see text] is an absolute constant. This bound is essentially tight and settles a conjecture due to Tal [ Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. The bounds prior to our work degraded rapidly with [Formula: see text], becoming trivial already at [Formula: see text]. As an application, we obtain, for every integer [Formula: see text], a partial Boolean function on [Formula: see text] bits that has bounded-error quantum query complexity at most [Formula: see text] and randomized query complexity [Formula: see text]. This separation of bounded-error quantum versus randomized query complexity is best possible, by the results of Aaronson and Ambainis [ SIAM J. Comput., 47 (2018), pp. 982–1038] and Bravyi et al. [ Classical Algorithms for Forrelation, arXiv preprint, 2021]. Prior to our work, the best known separation was polynomially weaker: [Formula: see text] versus [Formula: see text] for any [Formula: see text] [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]. As another application, we obtain an essentially optimal separation of [Formula: see text] versus [Formula: see text] for bounded-error quantum versus randomized communication complexity for any [Formula: see text]. The best previous separation was polynomially weaker: [Formula: see text] versus [Formula: see text] (this is implicit in [A. Tal, Towards optimal separations between quantum and randomized query complexities, in Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020, pp. 228–239]).
The query model offers a concrete setting where quantum algorithms are provably superior to randomized algorithms. Beautiful results by Bernstein-Vazirani, Simon, Aaronson, and others presented partial Boolean functions that can be computed by quantum algorithms making much fewer queries compared to their randomized analogs. To date, separations of O(1) vs. √N between quantum and randomized query complexities remain the state-of-the-art (where N is the input length), leaving open the question of whether O(1) vs. N1/2+Ω(1)separations are possible? We answer this question in the affirmative. Our separating problem is a variant of the Aaronson-Ambainis k-fold Forrelation problem. We show that our variant: 1)Can be solved by a quantum algorithm making 2O(k)queries to the inputs. 2)Requires at least ~Ω(N2(k-1)/(3k-1)) queries for any randomized algorithm. For any constant , this gives a O(1) vs. N1/2-εseparation between the quantum and randomized query complexities of partial Boolean functions. Our proof is Fourier analytical and uses new bounds on the Fourier spectrum of classical decision trees, which could be of independent interest. Looking forward, we conjecture that the Fourier bounds could be further improved in a precise manner, and show that such conjectured bounds imply optimal O(1) vs. N1-εseparations between the quantum and randomized query complexities of partial Boolean functions.
We prove that for every parity decision tree of depth ddd on nnn variables, the sum of absolute values of Fourier coefficients at level ℓ\ellℓ is at most dℓ/2⋅O(ℓ⋅log⁡(n))ℓd^{\ell/2} \cdot O(\ell \cdot \log(n))^\elldℓ/2⋅O(ℓ⋅log(n))ℓ. Our result is nearly tight for small values of ℓ\ellℓ and extends a previous Fourier bound for standard decision trees by Sherstov, Storozhenko, and Wu (STOC, 2021). As an application of our Fourier bounds, using the results of Bansal and Sinha (STOC, 2021), we show that the kkk-fold Forrelation problem has (randomized) parity decision tree complexity Ω~(n1−1/k)\tilde{\Omega}\left(n^{1-1/k}\right)Ω~(n1−1/k), while having quantum query complexity ⌈k/2⌉\lceil k/2\rceil⌈k/2⌉. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-ℓ\ellℓ Fourier expression. To carry the argument, we apply a careful cleanup procedure to the parity decision tree, ensuring that the value of the random walk is bounded with high probability. We observe that step sizes for the level-ℓ\ellℓ walks can be computed by the intermediate values of level ≤ℓ−1\le \ell-1≤ℓ−1 walks, which calls for an inductive argument. Our approach differs from previous proofs of Tal (FOCS, 2020) and Sherstov, Storozhenko, and Wu (STOC, 2021) that relied on decompositions of the tree. In particular, for the special case of standard decision trees we view our proof as slightly simpler and more intuitive. In addition, we prove a similar bound for noisy decision trees of cost at most ddd -- a model that was recently introduced by Ben-David and Blais (FOCS, 2020).
We prove that for every parity decision tree of depth ddd on nnn variables, the sum of absolute values of Fourier coefficients at level ℓ\ellℓ is at most dℓ/2⋅O(ℓ⋅log⁡(n))ℓd^{\ell/2} \cdot O(\ell \cdot \log(n))^\elldℓ/2⋅O(ℓ⋅log(n))ℓ. Our result is nearly tight for small values of ℓ\ellℓ and extends a previous Fourier bound for standard decision trees by Sherstov, Storozhenko, and Wu (STOC, 2021). As an application of our Fourier bounds, using the results of Bansal and Sinha (STOC, 2021), we show that the kkk-fold Forrelation problem has (randomized) parity decision tree complexity Ω~(n1−1/k)\tildeΩ\left(n^{1-1/k}\right)Ω~(n1−1/k), while having quantum query complexity ⌈k/2⌉\lceil k/2\rceil⌈k/2⌉. Our proof follows a random-walk approach, analyzing the contribution of a random path in the decision tree to the level-ℓ\ellℓ Fourier expression. To carry the argument, we apply a careful cleanup procedure to the parity decision tree, ensuring that the value of the random walk is bounded with high probability. We observe that step sizes for the level-ℓ\ellℓ walks can be computed by the intermediate values of level ≤ℓ−1\le \ell-1≤ℓ−1 walks, which calls for an inductive argument. Our approach differs from previous proofs of Tal (FOCS, 2020) and Sherstov, Storozhenko, and Wu (STOC, 2021) that relied on decompositions of the tree. In particular, for the special case of standard decision trees we view our proof as slightly simpler and more intuitive. In addition, we prove a similar bound for noisy decision trees of cost at most ddd -- a model that was recently introduced by Ben-David and Blais (FOCS, 2020).
We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs Ω(N/log⁡N)\Omega(\sqrt{N}/\log N)Ω(N​/logN) queries (improving an Ω(N1/4)\Omega(N^{1/4})Ω(N1/4) lower bound of Aaronson). Conversely, we show that this 1 versus Ω~(N)\widetilde{\Omega}(\sqrt{N})Ω(N​) separation is optimal: indeed, any ttt-query quantum algorithm whatsoever can be simulated by an O(N1−1/2t)O(N^{1-1/2t})O(N1−1/2t)-query randomized algorithm. Thus, resolving an open question of Buhrman et al. [ SIAM J. Comput., 37 (2008), pp. 1387--1400] from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal ttt versus Ω(N1−1/2t)\Omega(N^{1-1/2t})Ω(N1−1/2t) separation for all ttt. As a bonus, we show that this generalization is BQP{BQP}BQP-complete. This yields what is arguably the simplest BQP{BQP}BQP-complete problem yet known and gives a second sense in which Forrelation “captures the maximum power of quantum computation.”
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2 k bits defined by a complete binary tree of NAND gates of depth k , which achieves R 0 ( f ) = O ( D ( f ) 0.7537… ). We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is Ω( n ) while its zero-error randomized query complexity is Õ(√ n ). We further show that the quantum query complexity of the same function is Õ( n 1/4 ), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Ω( n / log ( n )) and bounded-error randomized query complexity R ( g ) = Õ(√ n ). This is the first super-linear separation between these two complexity measures. The exact quantum query complexity of the same function is Q E ( g ) = Õ(√ n ). These functions show that the relations D ( f ) = O ( R 1 ( f ) 2 ) and R 0 ( f ) = Õ( R ( f ) 2 ) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: a cubic separation between Q and R 0 , a 3/2-power separation between Q E and R , and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Göös, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.