We now have sufficient ingredients to understand how a quantum computer can perform logical operations and compute just like an ordinary computer. In this section we describe an algorithm which makes use of the quantum parallelism that we have hinted at already: finding the period of a long sequence.

Consider the sequence

where ; we shall use quantum parallelism to find its period. We start with a set of initially spin-down particles which we group into two sets (two quantum registers, or quantum variables):

the first set having **k** bits; the next having sufficient for our needs.
(In fact other registers are required, but by applying Bennett's solution
to space management they may be suppressed in our discussion here.)
On each bit of the first register we perform the one-bit
operation, yielding a superposition of every possible bit-string of
length **k** in this register:

The next stage is to break down the computation, corresponding to
the function , into a set of one-bit and two-bit unitary operations.
The sequence of operations is designed to map the state
to the state for any input **a**. Now we see
that the number of bits required for this second register must
be at least sufficient to store the longest result for
any of these computations. When, however, this sequence of operations
is applied to our exponentially large superposition, instead of the
single input, we obtain

An exponentially large amount of computation has been performed essentially for free.

The final computational step, like the first, is again a purely quantum mechanical one. Consider a discrete ``quantum'' Fourier transform on the first register

It is easy to see that this is reversible via the inverse transform and indeed it is readily verified to be unitary. Further, an efficient way to compute this transform with one-bit and two-bit gates has been described by Coppersmith (Fig. 10) [23,24,6].

**Fig. 10** Circuit for the quantum Fourier transform of the variable
using Coppersmith's fast
Fourier transformation approach [23,24,6].
The two-bit ``'' gate may itself be decomposed into various
one-bit and XOR gates [14].

When this quantum Fourier transform is applied to our superposition, we obtain

The computation is now complete and we retrieve the output from
the quantum computer by measuring the state of all spins in the first
register (the first **k** bits). Indeed, once the Fourier transform
has been performed the second register may even be discarded
[27].

What will the output look like? Suppose has period **r**
so . The sum over **a** will yield constructive
interference from the coefficients only when
is a multiple of the reciprocal period [25]. All
other values of will produce destructive interference to a greater
or lesser extent. Thus, the probability distribution for finding the
first register with various values is shown schematically by Fig. 11.

**Fig. 11** Plot of the probability of each result
versus . Constructive
interference produces narrow peaks at multiples of the inverse period
of the sequence .

One complete run of the quantum computer yields a random
value of underneath one of the peaks in the probability of each
result .
That is, we obtain a random multiple of the inverse period.
To extract the period itself we need only repeat this quantum computation
roughly times in order to have a high
probability for at least one of the multiples to be relatively
prime to the period **r**---uniquely determining it [1].
Thus, this algorithm yields only a probabilistic result. Fortunately,
we can make this probability as high as we like.

All the above work may appear a little anti-climactic. We have gone
to a lot of trouble to design a quantum computer to find the period
of a sequence. The point is, however, that the sequence is calculated
in parallel and is exponentially long---even for a small value of say
**k=140** bits in the first register the quantum computer has calculated
and stored more results than there are particles in the universe. We
now describe the simple structure that exists in the mathematical
problem of factoring which allows us to apply the above quantum computer
algorithm.

Wed Aug 23 11:54:31 IDT 1995