  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 $\epsilon,\delta > 0$. Then there exists a deterministic classical
algorithm that makes $\mathrm{poly}(T,1/\epsilon,1/\delta)$ queries to the
input and that approximates $Q$'s acceptance probability to within an additive
error $\epsilon$ on a $1-\delta$ 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.
