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:1506.08106

A Super-Grover Separation Between Randomized and Quantum Query Complexities

Shalev Ben-David

Published Jun 26, 2015• 7 citations
arXivHTMLPDF

Abstract

We construct a total Boolean function $f$ satisfying $R(f)=\tildeΩ(Q(f)^{5/2})$, refuting the long-standing conjecture that $R(f)=O(Q(f)^2)$ for all total Boolean functions. Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions, we improve this to $R(f)=\tildeΩ(Q(f)^3)$. Our construction is motivated by the Göös-Pitassi-Watson function but does not use it.

DOI
10.48550/arxiv.1506.08106

Related papers

Randomized query complexity can beat certificate complexity

Shalev Ben-David, Robin Kothari

A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.

cs.CCCross-listedarXiv:2609.15063•Sep 15, 2026•0 citations

A Nearly Quartic Separation Between Randomized and Quantum Query Complexity

OpenAI

We construct total Boolean functions with a nearly quartic separation between bounded-error randomized and quantum query complexity. Writing these complexities as \mathrm R(f) and \mathrm Q(f), the examples rule out every universal bound \mathrm R(f)=O((1+\mathrm Q(f))^\alpha) with α < 4. Thus the known quartic upper bound has the optimal exponent, disproving the conjectured cubic bound. Both complexities count worst-case bit queries with error at most 1/3 on every input.

•Oct 6, 2026•0 citations

Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity

Andris Ambainis, Jānis Iraids, Martins Kokainis

We study how large the certificate complexity ${C}(f)$ of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function $f$ whose randomized query complexity with one-sided error satisfies ${R}_1(f) = Θ(\sqrt{{C}(f)})$. This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function $F$ with bounded-error quantum query complexity ${Q}(F) = \widetilde O({C}(F)^{1/4})$, attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are $\widetilde O(\sqrt{{C}(F)})$. We also prove matching lower bounds for these two measures on $F$.

quant-pharXiv:2609.11664•Sep 11, 2026•0 citations

Quantum Implications of Huang's Sensitivity Theorem

Shafi Goldwasser, Ben-David, Shalev, Kothari, Robin +1 more

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We also use the result to resolve the quantum analogue of the Aanderaa-Karp-Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $Q(f) = Ω(n)$, which is also optimal.

arXiv:2004.13231•Apr 28, 2020•8 citations

Separations in query complexity using cheat sheets

Scott Aaronson, Shalev Ben-David, Robin Kothari

We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity and approximate polynomial degree, showing severe limitations on the power of the polynomial method. Finally, we exhibit a total function with a quadratic gap between quantum query complexity and certificate complexity, which is optimal (up to log factors). These separations are shown using a new, general technique that we call the cheat sheet technique, which builds upon the techniques of Ambainis et al. [STOC 2016]. The technique is based on a generic transformation that converts any (possibly partial) function into a new total function with desirable properties for showing separations. The framework also allows many known separations, including some recent breakthrough results of Ambainis et al. [STOC 2016], to be shown in a unified manner.

arXiv:1511.01937•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•74 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•28 citations
We construct a total Boolean function fff satisfying R(f)=Ω~(Q(f)5/2)R(f)=\tildeΩ(Q(f)^{5/2})R(f)=Ω~(Q(f)5/2), refuting the long-standing conjecture that R(f)=O(Q(f)2)R(f)=O(Q(f)^2)R(f)=O(Q(f)2) for all total Boolean functions. Assuming a conjecture of Aaronson and Ambainis about optimal quantum speedups for partial functions, we improve this to R(f)=Ω~(Q(f)3)R(f)=\tildeΩ(Q(f)^3)R(f)=Ω~(Q(f)3). Our construction is motivated by the Göös-Pitassi-Watson function but does not use it.
We study how large the certificate complexity C(f){C}(f)C(f) of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function fff whose randomized query complexity with one-sided error satisfies R1(f)=Θ(C(f)){R}_1(f) = Θ(\sqrt{{C}(f)})R1​(f)=Θ(C(f)​). This separation is optimal even when two-sided error is allowed. From this construction, we obtain another total Boolean function FFF with bounded-error quantum query complexity Q(F)=O~(C(F)1/4){Q}(F) = \widetilde O({C}(F)^{1/4})Q(F)=O(C(F)1/4), attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are O~(C(F))\widetilde O(\sqrt{{C}(F)})O(C(F)​). We also prove matching lower bounds for these two measures on FFF.
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function fff, the deterministic query complexity, D(f)D(f)D(f), is at most quartic in the quantum query complexity, Q(f)Q(f)Q(f): D(f)=O(Q(f)4)D(f) = O(Q(f)^4)D(f)=O(Q(f)4). This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We also use the result to resolve the quantum analogue of the Aanderaa-Karp-Rosenberg conjecture. We show that if fff is a nontrivial monotone graph property of an nnn-vertex graph specified by its adjacency matrix, then Q(f)=Ω(n)Q(f) = Ω(n)Q(f)=Ω(n), which is also optimal.
We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm). We also present a total function with a power 4 separation between quantum query complexity and approximate polynomial degree, showing severe limitations on the power of the polynomial method. Finally, we exhibit a total function with a quadratic gap between quantum query complexity and certificate complexity, which is optimal (up to log factors). These separations are shown using a new, general technique that we call the cheat sheet technique, which builds upon the techniques of Ambainis et al. [STOC 2016]. The technique is based on a generic transformation that converts any (possibly partial) function into a new total function with desirable properties for showing separations. The framework also allows many known separations, including some recent breakthrough results of Ambainis et al. [STOC 2016], to be shown in a unified manner.
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.