Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Preprint
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 (STOC'2015, arxiv:1411.5729). 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, 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.
Keywords
All Related Versions
This publication has 10 references indexed in Scilit:
- Separations in query complexity using cheat sheets2016
- A polarization identity for multilinear mapsIndagationes Mathematicae, 2014
- Grothendieck’s Theorem, past and presentBulletin of the American Mathematical Society, 2012
- Unbounded-error quantum query complexityTheoretical Computer Science, 2011
- Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum ComputerSIAM Journal on Computing, 2010
- Lower bounds in communication complexity based on factorization normsRandom Structures & Algorithms, 2008
- Quantum lower bounds for the collision and the element distinctness problemsJournal of the ACM, 2004
- On the degree of boolean functions as real polynomialscomputational complexity, 1994
- Decoupling Inequalities for Polynomial ChaosThe Annals of Probability, 1987
- Proposed Experiment to Test Local Hidden-Variable TheoriesPhysical Review Letters, 1969