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

中国科学通报:英文版

What is the largest separation between quantum and classical query complexity?

Shao-Ming Fei

Published Jun 13, 2017• 0 citations
Publisher
DOI
10.1016/j.scib.2017.06.002

Related papers

Sharp Quantum versus Classical Query Complexity Separations

Niel de Beaudrap, Not Available Not Available, Not Available Not Available

arXiv:quant-ph/0011065•Algorithmica•Nov 6, 2002•42 citations

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Andris Ambainis, Aleksandrs Belovs

arXiv:2301.09218•Computational Complexity•Oct 3, 2025•2 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

On quantum versus classical query complexity.

Scott Aaronson, Andris Ambainis, Andrej Bogdanov +2 more

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

On Exact Quantum Query Complexity

Ashley Montanaro, Richard Jozsa, Graeme Mitchison

arXiv:1111.0475•Algorithmica•Aug 29, 2013•48 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 Ω(√(N)log(N)) queries (improving an Ω(N1/4) lower bound of Aaronson). Conversely, we show that this 1 versus Ω(√(N)) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N1-1/2t)-query randomized algorithm. Thus, resolving an open question of Buhrman et al. 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 Ω(N1-1/2t) separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what's arguably the simplest BQP-complete problem yet known, and gives a second sense in which Forrelation "captures the maximum power of quantum computation."

ACM Symposium on Theory of Computing (STOC)•Jun 3, 2015•81 citations
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.”
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)) queries (improving an Ω(N1/4) lower bound of Aaronson). Conversely, we show that this 1 versus Ω(√(N)) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O(N1-1/2t)-query randomized algorithm. Thus, resolving an open question of Buhrman et al. 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 Ω(N1-1/2t) separation for all t. As a bonus, we show that this generalization is BQP-complete. This yields what's arguably the simplest BQP-complete problem yet known, and gives a second sense in which Forrelation "captures the maximum power of quantum computation."