Theory of Computing
-------------------
Title : The Need for Structure in Quantum Speedups
Authors : Scott Aaronson and Andris Ambainis
Volume : 10
Number : 6
Pages : 133-166
URL : https://theoryofcomputing.org/articles/v010a006
Abstract
--------
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-th root of the classical
randomized query complexity. (An earlier version of this paper
gave the 9-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 $P \neq BQP$ relative to a random oracle.
A preliminary version of this paper appeared in the
Proc. of the 2nd "Innovations in Computer Science" Conference
(ICS 2011). See Sec. 1.3 for a comparison with the present
paper.