An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

Autor:	Ambainis, Andris, Belovs, Aleksandrs
Jazyk:	angličtina
Rok vydání:	2023
Předmět:	Quantum Physics Quantum Adversary Bound Separations in Query Complexity FOS: Physical sciences Theory of computation → Quantum query complexity Quantum Physics (quant-ph) Polynomials
DOI:	10.4230/lipics.ccc.2023.24
Popis:	While it is known that there is at most a polynomial separation between quantum query complexity and the polynomial degree for total functions, the precise relationship between the two is not clear for partial functions. In this paper, we demonstrate an exponential separation between exact polynomial degree and approximate quantum query complexity for a partial Boolean function. For an unbounded alphabet size, we have a constant versus polynomial separation. LIPIcs, Vol. 264, 38th Computational Complexity Conference (CCC 2023), pages 24:1-24:13
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::80eaf569554b1e7c42d9ed35bda2943c Zobrazit plný text záznamu