Quantum speedups need structure
This addresses a foundational problem in quantum computing theory by showing quantum speedups require structural constraints, potentially limiting their advantage for many algorithms.
The paper proves a conjecture about the influence of variables in multilinear polynomials, which implies that any quantum algorithm can be simulated classically with only polynomial slowdown in query complexity on most inputs, specifically showing a deterministic classical algorithm makes poly(T,1/ε,1/δ) queries to approximate quantum acceptance probability.
We prove the following conjecture, raised by Aaronson and Ambainis in 2008: Let $f:\{-1,1\}^n \rightarrow [-1,1]$ be a multilinear polynomial of degree $d$. Then there exists a variable $x_i$ whose influence on $f$ is at least $\mathrm{poly}(\mathrm{Var}(f)/d)$. As was shown by Aaronson and Ambainis, this result implies the following well-known conjecture on the power of quantum computing, dating back to 1999: Let $Q$ be a quantum algorithm that makes $T$ queries to a Boolean input and let $ε,δ> 0$. Then there exists a deterministic classical algorithm that makes $\mathrm{poly}(T,1/ε,1/δ)$ queries to the input and that approximates $Q$'s acceptance probability to within an additive error $ε$ on a $1-δ$ fraction of inputs. In other words, any quantum algorithm can be simulated on most inputs by a classical algorithm which is only polynomially slower, in terms of query complexity.