ECCC-Report TR15-196https://eccc.weizmann.ac.il/report/2015/196Comments and Revisions published for TR15-196en-usFri, 04 Dec 2015 20:04:35 +0200
Revision 1
| Polynomials, Quantum Query Complexity, and Grothendieck's Inequality |
Andris Ambainis,
Scott Aaronson,
J?nis Iraids,
Martins Kokainis,
Juris Smotrovs
https://eccc.weizmann.ac.il/report/2015/196#revision1We 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 (STOC'2015).
We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires $\tilde{\Omega}(n)$ quantum queries but can be represented by a block-multilinear polynomial of degree $\tilde{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 of Aaronson and Ambainis (STOC'2015), showing that one can estimate the value of any bounded degree-$k$ polynomial $p:\{0, 1\}^n \rightarrow [-1, 1]$ with $O(n^{1-\frac{1}{2k}})$ queries.Fri, 04 Dec 2015 20:04:35 +0200https://eccc.weizmann.ac.il/report/2015/196#revision1
Paper TR15-196
| Polynomials, Quantum Query Complexity, and Grothendieck's Inequality |
Andris Ambainis
https://eccc.weizmann.ac.il/report/2015/196We 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 (STOC'2015).
We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires $\tilde{\Omega}(n)$ quantum queries but can be represented by a block-multilinear polynomial of degree $\tilde{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 of Aaronson and Ambainis (STOC'2015), showing that one can estimate the value of any bounded degree-$k$ polynomial $p:\{0, 1\}^n \rightarrow [-1, 1]$ with $O(n^{1-\frac{1}{2k}})$ queries.Fri, 04 Dec 2015 16:47:09 +0200https://eccc.weizmann.ac.il/report/2015/196