Optimal quantum query bounds for almost all Boolean functions
| Authors |
|
|---|---|
| Publication date | 02-2013 |
| Host editors |
|
| Book title | 30th International Symposium on Theoretical Aspects of Computer Science |
| Book subtitle | STACS '13, February 27th to March 2nd, 2013, Kiel, Germany |
| ISBN (electronic) |
|
| Series | Leibniz International Proceedings in Informatics |
| Event | 30th International Symposium on Theoretical Aspects of Computer Science |
| Pages (from-to) | 446-453 |
| Publisher | Saarbrücken/Wadern: Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
| Organisations |
|
| Abstract | We show that almost all n-bit Boolean functions have bounded-error quantum query complexity at least n/2, up to lower-order terms. This improves over an earlier n/4 lower bound of Ambainis (A. Ambainis, 1999), and shows that van Dam's oracle interrogation (W. van Dam, 1998) is essentially optimal for almost all functions. Our proof uses the fact that the acceptance probability of a T-query algorithm can be written as the sum of squares of degree-T polynomials. |
| Document type | Conference contribution |
| Language | English |
| Published at | https://doi.org/10.4230/LIPIcs.STACS.2013.446 |
| Other links | https://drops.dagstuhl.de/opus/portals/lipics/index.php?semnr=13002 |
| Downloads |
Optimal quantum query bounds for almost all Boolean functions
(Final published version)
|
| Permalink to this page | |