Polynomials, Quantum Query Complexity, and Grothendieck's Inequality

Scott Aaronson, Andris Ambainis, Jānis Iraids +2

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 alg…