2026-07-24T18:14:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18294 2024-03-06T11:01:32Z ddc:004 open_access

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree Ambainis, Andris Belovs, Aleksandrs Polynomials Quantum Adversary Bound Separations in Query Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andris Ambainis and Aleksandrs Belovs 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.24 urn:nbn:de:0030-drops-182943 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.24 eng https://creativecommons.org/licenses/by/4.0/legalcode