Revised: July 10, 2014

Published: August 12, 2014

**Keywords:**decision trees, adversary method, collision problem, Fourier analysis, influences, quantum computing, query complexity

**Categories:**complexity theory, quantum computing, query complexity, decision tree, collision, Fourier analysis, influence

**ACM Classification:**F.1.2, F.1.3

**AMS Classification:**81P68, 68Q12, 68Q17

**Abstract:**
[Plain Text Version]

Is there a general theorem that tells us when we can hope for exponential speedups from quantum algorithms, and when we cannot? In this paper, we make two advances toward such a theorem, in the black-box model where most quantum algorithms operate.

First, we show that for any problem that is invariant under permuting inputs and outputs and that has sufficiently many outputs (like the collision and element distinctness problems), the quantum query complexity is at least the $7^{\text{th}}$ root of the classical randomized query complexity. (An earlier version of this paper gave the $9^{\text{th}}$ root.) This resolves a conjecture of Watrous from 2002.

Second, inspired by work of O'Donnell et al. (2005) and Dinur et al. (2006),
we conjecture that every bounded low-degree polynomial has a
“highly influential” variable.
(A multivariate polynomial $p$ is said to be *bounded*
if $0\le p(x)\le 1$ for all $x$ in the Boolean cube.)
Assuming this conjecture, we
show that every $T$-query quantum algorithm can be simulated on *most*
inputs by a $T^{O(1)}$-query classical algorithm, and that one essentially
cannot hope to prove $\mathsf{P}\neq\mathsf{BQP}$ relative to a random oracle.

A preliminary version of this paper appeared in the Proc. 2nd “Innovations in Computer Science” Conference (ICS 2011). See Sec. 1.3 for a comparison with the present paper.