An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Andris Ambainis; Aleksandrs Belovs

doi:10.1007/s00037-025-00277-4

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Andris Ambainis
, Aleksandrs Belovs^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

While it is known that there is at most a polynomial separationbetween quantum query complexity and the polynomial degree fortotal functions, the precise relationship between the two is not clear forpartial functions. In this paper, we demonstrate an exponential separationbetween exact polynomial degree and approximate quantum querycomplexity for a partial Boolean function. For an unbounded alphabetsize, we have a constant versus polynomial separation.

Original language	English
Article number	14
Pages (from-to)	1-25
Journal	Computational Complexity
Volume	34
Issue number	2
DOIs	https://doi.org/10.1007/s00037-025-00277-4
Publication status	Published - Dec 2025

Keywords

68Q12
68Q17
polynomial method
quantum adversary bound
quantum lower bounds
query complexity

Access to Document

10.1007/s00037-025-00277-4

Cite this

@article{454a977864da41c09957acc575740e43,

title = "An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree",

abstract = "While it is known that there is at most a polynomial separationbetween quantum query complexity and the polynomial degree fortotal functions, the precise relationship between the two is not clear forpartial functions. In this paper, we demonstrate an exponential separationbetween exact polynomial degree and approximate quantum querycomplexity for a partial Boolean function. For an unbounded alphabetsize, we have a constant versus polynomial separation.",

keywords = "68Q12, 68Q17, polynomial method, quantum adversary bound, quantum lower bounds, query complexity",

author = "Andris Ambainis and Aleksandrs Belovs",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive licence to Springer Nature Switzerland AG 2025.",

year = "2025",

month = dec,

doi = "10.1007/s00037-025-00277-4",

language = "English",

volume = "34",

pages = "1--25",

journal = "Computational Complexity",

issn = "1016-3328",

publisher = "Springer International Publishing",

number = "2",

}

TY - JOUR

T1 - An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

AU - Ambainis, Andris

AU - Belovs, Aleksandrs

N1 - Publisher Copyright: © The Author(s), under exclusive licence to Springer Nature Switzerland AG 2025.

PY - 2025/12

Y1 - 2025/12

N2 - While it is known that there is at most a polynomial separationbetween quantum query complexity and the polynomial degree fortotal functions, the precise relationship between the two is not clear forpartial functions. In this paper, we demonstrate an exponential separationbetween exact polynomial degree and approximate quantum querycomplexity for a partial Boolean function. For an unbounded alphabetsize, we have a constant versus polynomial separation.

AB - While it is known that there is at most a polynomial separationbetween quantum query complexity and the polynomial degree fortotal functions, the precise relationship between the two is not clear forpartial functions. In this paper, we demonstrate an exponential separationbetween exact polynomial degree and approximate quantum querycomplexity for a partial Boolean function. For an unbounded alphabetsize, we have a constant versus polynomial separation.

KW - 68Q12

KW - 68Q17

KW - polynomial method

KW - quantum adversary bound

KW - quantum lower bounds

KW - query complexity

UR - https://link.springer.com/article/10.1007/s00037-025-00277-4

UR - https://www.scopus.com/pages/publications/105018188024

U2 - 10.1007/s00037-025-00277-4

DO - 10.1007/s00037-025-00277-4

M3 - Article

SN - 1016-3328

VL - 34

SP - 1

EP - 25

JO - Computational Complexity

JF - Computational Complexity

IS - 2

M1 - 14

ER -

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this