Quantum interference as a resource for quantum speedup

Quantum states can, in a sense, be thought of as generalizations of classical probability distributions, but are more powerful than probability distributions when used for computation or communication. Quantum speedup therefore requires some feature of quantum states that classical probability distributions lack. One such feature is interference. We quantify interference and show that there can be no quantum speedup due to a small number of operations incapable of generating large amounts of interference (although large numbers of such operations can, in fact, lead to quantum speedup). Low-interference operations include sparse unitaries, Grover reflections, short-time and low-energy Hamiltonian evolutions, and the Haar wavelet transform. Circuits built from such operations can be classically simulated via a Monte Carlo technique making use of a convex combination of two Markov chains. Applications to query complexity, communication complexity, and the Wigner representation are discussed.

Figure 1

An example of the type of circuit that can be simulated in $poly\left(n\right)$ time using the techniques of this paper. The circuit is divided into four sections: The first section is considered to be the initial state, the middle two sections are unitary matrices, and the last section is a projector. The block labeled $y=g\left(x\right)$ represents a classical computation step that outputs “yes” if the first and second measurement operations result in values that are related by an arbitrary [but $poly\left(n\right)$ time computable] function $g$.

Figure 2

(a) A depiction of the decisional version of Shor's algorithm, which outputs “yes” if there is a prime factor within some given range. (b) The Haar wavelet transform (Definition 10 ) plays a similar role as the Fourier transform in classical signal processing. However, substituting the Haar transform for the Fourier transform in Shor's algorithm yields a circuit that can be efficiently simulated on a classical computer. Note that the resulting circuit will not factor numbers and, in fact, probably has no practical use.

Figure 3

A quantum communication protocol. The expectation value of the final measurement is given by (80).

Figure 4

This circuit implements the Haar transform of Definition 10, on three qubits [39]. The gates in this circuit are controlled-Hadamard gates, and the open circles denote that the Hadamard gates are active when all of the controls are in the $|0\rangle$ state.