At the heart of Shor's Algorithm is the Quantum Fourier Transform (QFT), which we shall now examine. That this function should be of interest to us is perhaps not surprising. Recall that for simple oracle problems the aim is to determine some global property of a function. Within quantum mechanics, we are very much used to this sort of situation -- how often have you simplified a problem by transforming it from a position representation to a momentum representation i.e. applied the Fourier Transform? Formally, the QFT is expected to be useful in determining the period 
of a function i.e. when 
for all 
.
We shall start by defining the QFT operation acting on 
qubits (
),
We can verify that this is a unitary operator by calculating
separately analyzing the cases of 
and 
. In the latter, we must sum a geometric progression,
How should we construct a circuit to implement this operation? We should start with a more careful examination of the representations of the number . The number has a decimal representation in the range 
to 
, but it also has a binary representation with digits 
where 
is the 
least significant bit. The decimal and binary descriptions can be related by
This means that the state
(
) can be written as
Inserting the expansion for , the term
Given that this is being exponentiated, any term 
that is an integer contributes a factor of 
to the phase, and makes no difference to the final result. This means that the state we wish to create can be written as
To make life easier, we will now swap the order of qubits in the register i.e. if we have a register of qubits where the most significant bit of the input is at the top, and the least significant bit at the bottom, then we shall read our output as having the least significant bit at the top, and the most significant at the bottom:
This means that the state of the output qubit only depends on qubits to 
, and requires the addition of a phase 
if the input bit 
and output bit are both in the 
state (i.e. we should be looking at applying controlled-phase gates). When 
, this simply requires the application of a Hadamard gate (giving a phase of 
). Thefore, we should start from qubit 
and apply a Hadamard gate. Then, we apply controlled-phases from all other inputs. Then we move up to qubit 
, apply Hadamard, and controlled-phases from all qubits except qubit . This should work down towards qubit , on which we apply just a Hadamard.
