Polynomials, Quantum Query Complexity, and Grothendieck's Inequality
Scott T. Aaronson, Andris Ambainis, Jānis Iraids, Martins Kokainis, Juris Smotrovs · arXiv (Cornell University) · 2015
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,1] with O(n^{1-1/(2k)) queries.