Aaronson, Scott ;
Ambainis, Andris ;
Iraids, Janis ;
Kokainis, Martins ;
Smotrovs, Juris
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Abstract
We show an equivalence between 1query quantum algorithms and representations by degree2 polynomials. Namely, a partial Boolean function f is computable by a 1query quantum algorithm with error bounded by epsilon<1/2 iff f can be approximated by a degree2 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 blockmultilinear 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 blockmultilinear polynomial of degree ~O(sqrt(n)). Thus, in the general case (for an arbitrary number of queries), blockmultilinear 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 blockmultilinear) 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 degreek polynomial p:{0,1}^n > [1,1] with O(n^{11/(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:125:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5839},
URN = {urn:nbn:de:0030drops58394},
doi = {10.4230/LIPIcs.CCC.2016.25},
annote = {Keywords: quantum algorithms, Boolean functions, approximation by polynomials, Grothendieck's inequality}
}
2016
Keywords: 

quantum algorithms, Boolean functions, approximation by polynomials, Grothendieck's inequality 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 