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^*

^*Šī darba korespondējošais autors

Zinātniskās darbības rezultāts: Devums žurnālam › Zinātniskais raksts (žurnālā) › koleģiāli recenzēts

Kopsavilkums

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.

Oriģinālvaloda	Angļu
Raksta numurs	14
Lapas (no-līdz)	1-25
Žurnāls	Computational Complexity
Sējums	34
Izdevuma numurs	2
DOIs	https://doi.org/10.1007/s00037-025-00277-4
Publikācijas statuss	Publicēts - dec. 2025

OECD Zinātnes nozare

1.2 Datorzinātne un informātika

Piekļuve Dokumentiem

10.1007/s00037-025-00277-4

Citi faili un saites

Citēt šo

@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

Kopsavilkums

OECD Zinātnes nozare

Piekļuve Dokumentiem

Citi faili un saites

Nospiedums

Citēt šo