# Quantum Fourier transform

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 r of a function i.e. when f(x)=f(x+r) for all x.

We shall start by defining the QFT operation acting on n qubits (N=2^n),

U_{\text{QFT}}=\frac{1}{\sqrt{N}}\sum_{x,y=0}^{N-1}e^{2i\pi xy/N}\left | y \right>\left < x \right |.

We can verify that this is a unitary operator by calculating

U_{\text{QFT}}U_{\text{QFT}}^\dagger=\frac{1}{N}\sum_{xyz}e^{2i\pi x(y-z)/N}\left | y \right>\left < z \right |=\leavevmode\hbox{\small1\kern-3.8pt\normalsize1},

separately analyzing the cases of y=z and y\neq z. In the latter, we must sum a geometric progression,

\frac{1}{N}\sum_{x}e^{2i\pi x(y-z)/N}=\frac{1-e^{2i\pi(y-z)}}{1-e^{2i\pi(y-z)/N}}=0.

How should we construct a circuit to implement this operation? We should start with a more careful examination of the representations of the number x. The number x has a decimal representation in the range 0 to 2^n-1, but it also has a binary representation with digits x_i\in\{0,1\} where x_i is the i^{th} least significant bit. The decimal and binary descriptions can be related by

x=\sum_{i=0}^{n-1}2^ix_i.

This means that the state

U_{\text{QFT}}\left | x \right>=\frac{1}{\sqrt{N}}\sum_ye^{i\phi y}\left | y \right>

(\phi=2\pi x/2^n) can be written as

\bigotimes_{i=0}^{n-1}\left(\left | 0 \right>+e^{i\phi 2^i}\left | 1 \right>\right)/\sqrt{2}.

Inserting the expansion for x, the term

\phi 2^i=\frac{2\pi}{N}2^i\sum_{j=0}^{n-1}2^jx_j.

Given that this is being exponentiated, any term 2^{i+j-n} that is an integer contributes a factor of 2\pi to the phase, and makes no difference to the final result. This means that the state we wish to create can be written as

\bigotimes_{i=0}^{n-1}\left(\left | 0 \right>+e^{i2\pi \sum_{j=0}^{n-i-1}x_j2^{i+j-n}}\left | 1 \right>\right)/\sqrt{2}.

To make life easier, we will now swap the order of qubits in the register i.e. if we have a register of n 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:

\tilde{U}_{\text{QFT}}\left | x \right>:=\bigotimes_{i=0}^{n-1}\left(\left | 0 \right>+e^{i2\pi \sum_{j=0}^{i}x_j2^{j-i-1}}\left | 1 \right>\right)/\sqrt{2}.

This means that the state of the i^{th} output qubit only depends on qubits 0 to i, and requires the addition of a phase 2\pi 2^{j-i-1} if the input bit x_j and output bit i are both in the \left | 1 \right> state (i.e. we should be looking at applying controlled-phase gates). When j=i, this simply requires the application of a Hadamard gate (giving a phase of \pi). Thefore, we should start from qubit n-1 and apply a Hadamard gate. Then, we apply controlled-phases from all other inputs. Then we move up to qubit n-2, apply Hadamard, and controlled-phases from all qubits except qubit n-1. This should work down towards qubit 0, on which we apply just a Hadamard.