Next: Factoring Up: Quantum Computing Notes Previous: Quantum Computing Notes

# The Quantum Fourier Transform

 (1)

which is the bit representation of the digit number with being th value of the least significant bit, and that value of the most significant bit. Thus the number is given by
 (2)

with the taking the values or 1. We now want to take this state to the state
 (3)

where is the number represented by
 (4)

Note that we have reversed the representation for so that the least significant bit is represented by the first qubit state, and the most significant is represented by the last qubit state.

Now, the phase factor can be rewritten as

 (5)

since if . We thus notice that the phase for any given value of (ie the n-th least significant bit of k) depends only on the values of the bits of of order less that . If we line up the bit representations of and we have

 ... ... ... ....

The Fourier factor which depends on is

 (6)

and depends only on those bits of the representation of which lie at or to the right of that bit in the representation of . Furthermore, we note that in the factor which depends on , the phase which depends on the largest bit, namely is which has only values of plus or minus 1 .

We can now perform the Fourier Transform bit by bit starting with the lowest digit of , namely . Let me assume that we have managed to transform the state by replacing the highest digits of with the lowest digits of . I.e., I have created, by some sequence of transformations, the state

 (7)

I now show how to advance this to next stage where we will create the expression up to the bit. . We can accomplish this by generating a transformation of the form
 (8)

This transformation can be decomposed into the two sets of transformations
 (9)

and
 (10)

The first transformation is just a rotation of the bit.
 (11)

The second set just correspond to a series of controlled one bit phase rotations.
 (12)

I.e., these are transformations which phase rotate the bit depending on whether bit is one or zero.

Thus given the transform up to bits, it requires a single rotation of a single bit, and controlled single-bit phase rotations, for a total of operations. Thus the whole Fourier transformation requires operations (, we recall is the number of bits in each of the numbers).

If we apply this Fourier transform to a state of the form

 (13)

we get for the Quantum Fourier Transform
 (14)

The term in the brackets is just the discrete Fourier transform of .

Note again that the representation is the bit reversed of the representation of . While one could do a bit reversal operation to get into the same bit order as , there is no point.

Next: Factoring Up: Quantum Computing Notes Previous: Quantum Computing Notes
Bill Unruh
2000-03-15