We consider a generalization of the standard oracle model in which the oracle acts on the target with a permutation selected according to internal random coins. We describe several problems that are impossible to solve classically but can be solved by a quantum algorithm using a single query; we show that such infinity-vs-one separations between classical and quantum query complexities can be constructed from much weaker separations. We also give conditions to determine when oracle problems -- either in the standard model, or in any of the generalizations we consider -- cannot be solved with success probability better than random guessing would achieve. In the oracle model with internal randomness where the goal is to gain any nonzero advantage over guessing, we prove (roughly speaking) that k quantum queries are equivalent in power to 2k classical queries, thus extending results of Meyer and Pommersheim.
One of the most basic conjectures in quantum complexity theory states that every
t-query quantum algorithm can be simulated on most inputs by a
poly(t)-query classical algorithm. If true, this would provide broad justification for the need for structure in quantum speedups.
We settle this conjecture for parallel quantum algorithms, showing that every
t-query
d-round quantum algorithm can be simulated on most inputs with
tO(d2) classical queries. This suggests that for unstructured problems, superpolynomial speedups would require quantum circuits of superconstant depth, and exponential speedups would further require polynomial depth. In contrast, most known speedups for structured problems are achieved by highly parallel, low-depth algorithms.
Our techniques also carry new implications for the status of
BPP vs.
BQP relative to a random oracle, a similarly longstanding problem.