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:1511.01937 · ACM Symposium on Theory of Computing (STOC)

Separations in query complexity using cheat sheets

Scott Aaronson, Shalev Ben-David, Robin Kothari

Published Jun 10, 2016• 117 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1145/2897518.2897644

Related papers

Separations in Communication Complexity Using Cheat Sheets and Information Complexity

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David +5 more

While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2.5 gap. We further present a 1.5 power separation between exact quantum and randomized communication complexity, improving on the previous ≅ 1.15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1.5 separation due to Goos, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.

arXiv:1605.01142•Annual Symposium on Foundations of Computer Science•Oct 1, 2016•22 citations

Quantum speedups in query complexity

Shalev Ben-David

In this thesis, we study randomized and quantum algorithms in the query complexity model.We investigate when and by how much quantum algorithms provide a speedup over the best possible classical algorithm in the query complexity setting.We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared to the best possible randomized algorithm.In the process, we introduce the "cheat sheet" method for turning partial Boolean functions into total Boolean functions, and examine some of its other applications.We also study lower bound techniques for randomized algorithms.We introduce a measure called randomized sabotage complexity which lower bounds randomized query complexity and behaves well under compositions.This tool for controlling the randomized query complexity of composed functions combines nicely with the cheat sheet technique, which often features composed functions in its applications.In addition, we study the quantum analogue of this tool, and use it to show a new power 5 relationship between zero-error and bounded-error quantum query complexity.Finally, we characterize the total Boolean functions that exhibit exponential quantum speedups when their domain is restricted to an arbitrarily chosen set.We show that such a "sculpting" of a quantum speedup is possible if and only if the original total function has many inputs with large certificate complexity.Along the way, we also show that functions defined on very small domains or that are very unbalanced can display at most a quadratic quantum speedup.

•Jan 1, 2017•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•1 citation

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

Quantum Advantage and Lower Bounds in Parallel Query Complexity

Joseph Carolan, Amin Shiraz Gilani, Mahathi Vempati

It is well known that quantum, randomized and deterministic (sequential) query complexities are polynomially related for total boolean functions. We find that significantly larger separations between the parallel generalizations of these measures are possible. In particular, 1) We employ the cheatsheet framework to obtain an unbounded parallel quantum query advantage over its randomized analogue for a total function, falsifying a conjecture of [https://arxiv.org/abs/1309.6116]. 2) We strengthen 1 by constructing a total function which exhibits an unbounded parallel quantum query advantage despite having no sequential advantage, suggesting that genuine quantum advantage could occur entirely due to parallelism. 3) We construct a total function that exhibits a polynomial separation between 2-round quantum and randomized query complexities, contrasting a result of [https://arxiv.org/abs/1001.0018] that there is at most a constant separation for 1-round (nonadaptive) algorithms. 4) We develop a new technique for deriving parallel quantum lower bounds from sequential upper bounds. We employ this technique to give lower bounds for Boolean symmetric functions and read-once formulas, ruling out large parallel query advantages for them. We also provide separations between randomized and deterministic parallel query complexities analogous to items 1-3.

arXiv:2410.02665•Leibniz international proceedings in informatics•Oct 3, 2024•2 citations

Separations in query complexity for total search problems

Shalev Ben-David, Srijita Kundu

We study the query complexity analogue of the class TFNP of total search problems. We give a way to convert partial functions to total search problems under certain settings; we also give a way to convert search problems back into partial functions. As an application, we give new separations for degree-like measures. We give an exponential separation between quantum query complexity and approximate degree for a total search problem. We also give an exponential separation between approximate degree and the positive quantum adversary for a total search problem. We then strengthen the former separation to upper bound a larger measure: the two-sided approximate non-negative degree, also called the conical junta degree. This measure is often larger than quantum query complexity and even a separation from randomized query complexity was not known. We extend our results to communication complexity, and obtain an exponential separation between quantum information complexity and the relaxed partition bound for a total search problem. Even a weaker separation between randomized communication complexity and the relaxed partition bound was not known for total search problems (or even for partial functions). Most of our separations for total search problems can be converted to separations for partial functions. Using this, we reprove the recent exponential separation between quantum query complexity and approximate degree for a partial function by Ambainis and Belovs (2023), among other new results.

arXiv:2410.16245•Oct 21, 2024•3 citations
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.
While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized communication complexity for a total function, giving an example exhibiting a power 2.5 gap. We further present a 1.5 power separation between exact quantum and randomized communication complexity, improving on the previous ≅ 1.15 separation by Ambainis (STOC 2013). Finally, we present a nearly optimal quadratic separation between randomized communication complexity and the logarithm of the partition number, improving upon the previous best power 1.5 separation due to Goos, Jayram, Pitassi, and Watson. Our results are the communication analogues of separations in query complexity proved using the recent cheat sheet framework of Aaronson, Ben-David, and Kothari (STOC 2016). Our main technical results are randomized communication and information complexity lower bounds for a family of functions, called lookup functions, that generalize and port the cheat sheet framework to communication complexity.
In this thesis, we study randomized and quantum algorithms in the query complexity model.We investigate when and by how much quantum algorithms provide a speedup over the best possible classical algorithm in the query complexity setting.We introduce a total Boolean function that exhibits a power 2.5 quantum speedup compared to the best possible randomized algorithm.In the process, we introduce the "cheat sheet" method for turning partial Boolean functions into total Boolean functions, and examine some of its other applications.We also study lower bound techniques for randomized algorithms.We introduce a measure called randomized sabotage complexity which lower bounds randomized query complexity and behaves well under compositions.This tool for controlling the randomized query complexity of composed functions combines nicely with the cheat sheet technique, which often features composed functions in its applications.In addition, we study the quantum analogue of this tool, and use it to show a new power 5 relationship between zero-error and bounded-error quantum query complexity.Finally, we characterize the total Boolean functions that exhibit exponential quantum speedups when their domain is restricted to an arbitrarily chosen set.We show that such a "sculpting" of a quantum speedup is possible if and only if the original total function has many inputs with large certificate complexity.Along the way, we also show that functions defined on very small domains or that are very unbalanced can display at most a quadratic quantum speedup.
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.
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.
It is well known that quantum, randomized and deterministic (sequential) query complexities are polynomially related for total boolean functions. We find that significantly larger separations between the parallel generalizations of these measures are possible. In particular, 1) We employ the cheatsheet framework to obtain an unbounded parallel quantum query advantage over its randomized analogue for a total function, falsifying a conjecture of [https://arxiv.org/abs/1309.6116]. 2) We strengthen 1 by constructing a total function which exhibits an unbounded parallel quantum query advantage despite having no sequential advantage, suggesting that genuine quantum advantage could occur entirely due to parallelism. 3) We construct a total function that exhibits a polynomial separation between 2-round quantum and randomized query complexities, contrasting a result of [https://arxiv.org/abs/1001.0018] that there is at most a constant separation for 1-round (nonadaptive) algorithms. 4) We develop a new technique for deriving parallel quantum lower bounds from sequential upper bounds. We employ this technique to give lower bounds for Boolean symmetric functions and read-once formulas, ruling out large parallel query advantages for them. We also provide separations between randomized and deterministic parallel query complexities analogous to items 1-3.
We study the query complexity analogue of the class TFNP of total search problems. We give a way to convert partial functions to total search problems under certain settings; we also give a way to convert search problems back into partial functions. As an application, we give new separations for degree-like measures. We give an exponential separation between quantum query complexity and approximate degree for a total search problem. We also give an exponential separation between approximate degree and the positive quantum adversary for a total search problem. We then strengthen the former separation to upper bound a larger measure: the two-sided approximate non-negative degree, also called the conical junta degree. This measure is often larger than quantum query complexity and even a separation from randomized query complexity was not known. We extend our results to communication complexity, and obtain an exponential separation between quantum information complexity and the relaxed partition bound for a total search problem. Even a weaker separation between randomized communication complexity and the relaxed partition bound was not known for total search problems (or even for partial functions). Most of our separations for total search problems can be converted to separations for partial functions. Using this, we reprove the recent exponential separation between quantum query complexity and approximate degree for a partial function by Ambainis and Belovs (2023), among other new results.