License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2016.25
URN: urn:nbn:de:0030-drops-58394
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5839/
Aaronson, Scott ;
Ambainis, Andris ;
Iraids, Janis ;
Kokainis, Martins ;
Smotrovs, Juris
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Abstract
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function f is computable by a 1-query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree-2 polynomial with error bounded by epsilon'<1/2. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [Aaronson/Ambainis, STOC 2015]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms.
We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ~Omega(n) quantum queries but can be represented by a block-multilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms.
Second, for any constant degree k, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from [Aaronson/Ambainis, STOC 2015], showing that one can estimate the value of any bounded degree-k polynomial p:{0,1}^n -> [-1,1] with O(n^{1-1/(2k)) queries.
BibTeX - Entry
@InProceedings{aaronson_et_al:LIPIcs:2016:5839,
author = {Scott Aaronson and Andris Ambainis and Janis Iraids and Martins Kokainis and Juris Smotrovs},
title = {{Polynomials, Quantum Query Complexity, and Grothendieck's Inequality}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {25:1--25:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-008-8},
ISSN = {1868-8969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5839},
URN = {urn:nbn:de:0030-drops-58394},
doi = {10.4230/LIPIcs.CCC.2016.25},
annote = {Keywords: quantum algorithms, Boolean functions, approximation by polynomials, Grothendieck's inequality}
}
|
Keywords: |
|
quantum algorithms, Boolean functions, approximation by polynomials, Grothendieck's inequality |
|
Collection: |
|
31st Conference on Computational Complexity (CCC 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.05.2016 |
