License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.24
URN: urn:nbn:de:0030-drops-182943
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18294/
Ambainis, Andris ;
Belovs, Aleksandrs
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
Abstract
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.
BibTeX - Entry
@InProceedings{ambainis_et_al:LIPIcs.CCC.2023.24,
author = {Ambainis, Andris and Belovs, Aleksandrs},
title = {{An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {24:1--24:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18294},
URN = {urn:nbn:de:0030-drops-182943},
doi = {10.4230/LIPIcs.CCC.2023.24},
annote = {Keywords: Polynomials, Quantum Adversary Bound, Separations in Query Complexity}
}
|
Keywords: |
|
Polynomials, Quantum Adversary Bound, Separations in Query Complexity |
|
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
10.07.2023 |
