TY - GEN
T1 - Polynomials, quantum query complexity, and grothendieck's inequality
AU - Aaronson, Scott
AU - Ambainis, Andris
AU - Iraids, Janis
AU - Kokainis, Martins
AU - Smotrovs, Juris
N1 - Publisher Copyright:
© Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis.
PY - 2016/5/1
Y1 - 2016/5/1
N2 - 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 ϵ < 1/2 iff f can be approximated by a degree-2 polynomial with error bounded by ϵ < 1/2. This result holds for two different notions of approximation by a polynomial: The standard definition of Nisan and Szegedy [21] and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [1]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ∼(n) quantum queries but can be represented by a block-multilinear polynomial of degree ∼O(p 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 from [1], showing that one can estimate the value of any bounded degree-k polynomial p : {0, 1}n ! [-1, 1] with O(n1- 1 2k ) queries.
AB - 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 ϵ < 1/2 iff f can be approximated by a degree-2 polynomial with error bounded by ϵ < 1/2. This result holds for two different notions of approximation by a polynomial: The standard definition of Nisan and Szegedy [21] and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis [1]. The proof uses Grothendieck's inequality to relate two matrix norms, with one norm corresponding to polynomial approximations and the other norm corresponding to quantum algorithms. We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires ∼(n) quantum queries but can be represented by a block-multilinear polynomial of degree ∼O(p 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 from [1], showing that one can estimate the value of any bounded degree-k polynomial p : {0, 1}n ! [-1, 1] with O(n1- 1 2k ) queries.
KW - Approximation by polynomials
KW - Boolean functions
KW - Grothendieck's inequality
KW - Quantum algorithms
UR - https://www.scopus.com/pages/publications/84973321145
U2 - 10.4230/LIPIcs.CCC.2016.25
DO - 10.4230/LIPIcs.CCC.2016.25
M3 - Conference paper
AN - SCOPUS:84973321145
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 25:1-25:19
BT - 31st Conference on Computational Complexity, CCC 2016
A2 - Raz, Ran
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 31st Conference on Computational Complexity, CCC 2016
Y2 - 29 May 2016 through 1 June 2016
ER -