Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Understand

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.