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

Electronic colloquium on computational complexity

On quantum versus classical query complexity.

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Ming

Published Jan 1, 2021• 2 citations
OpenAlex

Related papers

Sharp Quantum versus Classical Query Complexity Separations

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

Algorithmica•Nov 6, 2002•34 citations

Two classical queries versus one quantum query

Joris W. M. van Dam

•Jan 1, 1998•3 citations

Query Complexity: Worst-Case Quantum Versus Average-Case Classical

Scott Aaronson

In this note we investigate the relationship between worst-case quantum query complexity and average-case classical query complexity. Specifically, we show that if a quantum computer can evaluate a total Boolean function f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^5) queries in the average case, under a uniform distribution of inputs. If f is monotone, we show furthermore that only O(T^3) queries are needed. Previously, Beals et al. (1998) showed that if a quantum computer can evaluate f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^6) queries in the worst case, or O(T^4) if f is monotone. The optimal bound is conjectured to be O(T^2), but improving on O(T^6) remains an open problem. Relating worst-case quantum complexity to average-case classical complexity may suggest new ways to reduce the polynomial gap in the ordinary worst-case versus worst-case setting.

arXiv:cs/0001013•Jan 19, 2000•0 citations

Quantum query complexity, with advice

Can H. Bostanci

•Sep 16, 2026•0 citations

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

Shao-Ming Fei

中国科学通报：英文版•Jun 13, 2017•0 citations

Enlarging the gap between quantum and classical query complexity of multifunctions

Alina Vasilieva, Elena Shishova, Taisia Mischenko-Slatenkova

Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: QUD(M') ≤ N versus CUD(M') ≥ 3N, and QRD(M'') = 1 versus N/2 + 1 ≤ CRD(M'') ≤ N.

International Conference on Natural Computation (ICNC)•Jul 1, 2013•0 citations
In this note we investigate the relationship between worst-case quantum query complexity and average-case classical query complexity. Specifically, we show that if a quantum computer can evaluate a total Boolean function f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^5) queries in the average case, under a uniform distribution of inputs. If f is monotone, we show furthermore that only O(T^3) queries are needed. Previously, Beals et al. (1998) showed that if a quantum computer can evaluate f with bounded error using T queries in the worst case, then a deterministic classical computer can evaluate f using O(T^6) queries in the worst case, or O(T^4) if f is monotone. The optimal bound is conjectured to be O(T^2), but improving on O(T^6) remains an open problem. Relating worst-case quantum complexity to average-case classical complexity may suggest new ways to reduce the polynomial gap in the ordinary worst-case versus worst-case setting.
Quantum computing aims to use quantum mechanical effects for the efficient performance of computational tasks. A popular research direction is enlarging the gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design for multivalued functions that allow to achieve a large quantum versus classical complexity separation. To compute a basic finite multifunction in a quantum model only one query is enough while classically three queries are required. Then, we present two generalizations and a modification of the original algorithm, and obtain the following complexity gaps: QUD(M') ≤ N versus CUD(M') ≥ 3N, and QRD(M'') = 1 versus N/2 + 1 ≤ CRD(M'') ≤ N.