Polynomials, quantum query complexity, and Grothendieck's inequality

DOI10.4230/LIPICS.CCC.2016.25MaRDI QIDQ5368759zbMATH OpenOpenAlexFDO

Authors Scott Aaronson, Jānis Iraids, Martins Kokainis, J. Smotrovs, Andris Ambainis

Publication date 10 October 2017

Full work available at URL https://arxiv.org/abs/1511.08682

zbMATH Keywords

approximation by polynomialsBoolean functionsGrothendieck's inequalityquantum algorithms

Mathematics Subject Classification ID

Boolean functions (06E30) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: 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 $epsilo{n}^{\prime }<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. First, there is a total Boolean function which requires $ildeOmega(n)$ quantum queries but can be represented by a block-multilinear polynomial of degree $ildeO(sqrtn)$. 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, showing that one can estimate the value of any bounded degree-$k$ polynomial $p:{0,1}^{n}ightarrow[-1,1]$ with $O(n^{1-frac12k})$ queries.

Recommendations

• Quantum query algorithms are completely bounded forms
• Quantum query algorithms are completely bounded forms
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• The polynomial method strikes back: tight quantum query bounds via dual polynomials
• SOFSEM 2005: Theory and Practice of Computer Science

Cited in

(23)

• Revisiting Deutsch-Jozsa algorithm
• Polynomial degree vs. quantum query complexity
• From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm
• scientific article; zbMATH DE number 5899233 (Why is no real title available?)
• Uniform approximation by (quantum) polynomials
• Query complexity in expectation
• scientific article; zbMATH DE number 5320307 (Why is no real title available?)
• A note on quantum algorithms and the minimal degree of -error polynomials for symmetric functions
• The quantum query complexity of learning multilinear polynomials
• Quantum algorithm for multivariate polynomial interpolation
• Forrelation: a problem that optimally separates quantum from classical computing
• scientific article; zbMATH DE number 6829271 (Why is no real title available?)
• Quantum query algorithms are completely bounded forms
• Quantum query algorithms are completely bounded forms
• Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time
• Grover's algorithm and the secant varieties
• Failure of the trilinear operator space Grothendieck theorem
• A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY
• A polynomial quantum algorithm for approximating the Jones polynomial
• Influences of Fourier completely bounded polynomials and classical simulation of quantum algorithms
• Fourier 1-norm and quantum speed-up
• Quantum property testing in sparse directed graphs
• On zeros of exponential polynomials and quantum algorithms

This page was built for publication: Polynomials, quantum query complexity, and Grothendieck's inequality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368759)