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).

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.

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).

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.