Quantum speedups need structure

Nathan Keller, Ohad Klein

We prove the following conjecture, raised by Aaronson and Ambainis in 2008: Let $f:\{-1,1{\}}^n\to [-1,1]$ be a multilinear polynomial of degree $d$. Then there exists a var…