tage. What makes Grover’s algorithm possible is the fact that probabilities are the squares of amplitudes. Thus, a uniform superposition over 2n states assigns amplitude 1 2n to each one. Moreover, one can show that with effort comparable to that required to calculate f, it is possible to increase the amplitude of each target x (i.e. with f(x)= 1) by roughly 1 2 n . This breaks down only when their total amplitude is large. Thus, the total effort is on the order of 2n/2.

A more dramatic speedup over classical computing occurs with Shor’s algorithm for factoring integers. Shor’s algorithm has a substantial classical component, which reduces the problem of factoring to the more abstract problem of period finding. This problem takes as input a function f on the integers {0, 1, …, 2n- 1} with the property that f(x)=f(y) if and only if x-y is divisible by r for some hidden period r. The goal is to find r. Since r can be exponentially large in n, classical computers require exponential time to find it if they are required to treat f as a black box. (This assumption is important. Classical computers can factor n-bit numbers more quickly than).

However, quantum computers can find r much more quickly. The first step is to prepare the uniform superposition

Figure 3. Any function can be written as a sum of waves of different frequencies. The coefficients of this sum are called Fourier coefficients. The quantum Fourier transform (QF T) transforms a quantum state into one whose amplitudes are the Fourier coefficients of the original state. Measuring this state can be an incredibly efficient way to detect periodic structure.

1

2n ex x=0

2n 1"

Next, the quantum computer calcu-
lates f (x) and then measures the result.
Whatever the outcome is, the residual
state will be a superposition over those
xs compatible with the measurement
outcome, which takes the form z, z+r,
z+2r, … for some z between 0 and r− 1.
This quantum version of Bayes’ rule
leaves the state
r

2 n ez + ez+r + ez+ 2 r +… ( ) for a random z ∈{0,…,r− 1}. The next step is uniquely quantum, and involves applying a unitary matrix called a quantum Fourier transform (QFT). This matrix has y,z entry equal to

e2!iyz/2n 2n

Performing it efficiently is possible
by adapting the classical fast Fourier
transform (FFT) to the quantum set-
ting, but its action is dramatically dif-
ferent, since it transforms the ampli-
tudes of a quantum state rather than
transforming a list of numbers as the
classical FFT does. Applying the QFT
in this case maps our superposition to
a state where the amplitude of y is