Polynomials, quantum query complexity, and Grothendieck's inequality

DOI10.4230/LIPIcs.CCC.2016.25zbMath1380.68184arXiv1511.08682OpenAlexW2963739445MaRDI QIDQ5368759

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

Publication date: 10 October 2017

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

zbMATH Keywords

quantum algorithmsBoolean functionsapproximation by polynomialsGrothendieck's inequality

Mathematics Subject Classification ID

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

Related Items (7)

Failure of the trilinear operator space Grothendieck theorem ⋮ Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ⋮ From the sum-of-squares representation of a Boolean function to an optimal exact quantum query algorithm ⋮ Revisiting Deutsch-Jozsa algorithm ⋮ Quantum Query Algorithms are Completely Bounded Forms. ⋮ Quantum Query Algorithms Are Completely Bounded Forms ⋮ Fourier 1-norm and quantum speed-up

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