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: https://drops.dagstuhl.de/opus/volltexte/2023/18294/
Go to the corresponding LIPIcs Volume Portal


Ambainis, Andris ; Belovs, Aleksandrs

An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree

pdf-format:
LIPIcs-CCC-2023-24.pdf (0.7 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI