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:2301.09218 · Computational Complexity

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Andris Ambainis, Aleksandrs Belovs

Published Oct 3, 2025• 2 citations
arXivHTMLPDF
DOI
10.1007/s00037-025-00277-4

Related papers

Polynomial degree vs. quantum query complexity

Andris Ambainis

arXiv:quant-ph/0305028•Journal of Computer and System Sciences•Nov 30, 2005•175 citations

Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory

Rūsiņš Freivalds, Liva Garkaje

The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponential. On the other hand, we use a computerized exhaustive search to prove tightness of this bound.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2007•0 citations

Polynomial degree vs. quantum query complexity

Andris Ambainis

The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with polynomial degree M and quantum query complexity (M/sup 1.321.../). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a new, more general version of quantum adversary method.

Annual Symposium on Foundations of Computer Science•Feb 3, 2004•55 citations

The Quantum Query Complexity of Algebraic Properties

Sebastian Dörn, Thomas Thierauf

Lecture notes in computer science•Aug 27, 2007•20 citations

Parameterized query complexity in quantum computation

Parijat Prashun Purohit

•Jan 1, 2017•0 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
The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponential. On the other hand, we use a computerized exhaustive search to prove tightness of this bound.
The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with polynomial degree M and quantum query complexity (M/sup 1.321.../). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a new, more general version of quantum adversary method.
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.