next up previous
Next: Factoring numbers: Up: Quantum computation: a tutorial Previous: Model quantum computer

Quantum parallelism: Period of a sequence:

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.

next up previous
Next: Factoring numbers: Up: Quantum computation: a tutorial Previous: Model quantum computer

Samuel L.~Braunstein
Wed Aug 23 11:54:31 IDT 1995