The Quantum Fourier Transform

In the previously introduced algorithms, the Hadamard transform played an essential role in being able to created a certain superposition of states that was exploited in the various ways by the algorithms. Recall the action of the Hadamard transform \(H^{\otimes n}\) on an arbitrary basis state \(\left|\mathbf{x}\right>\in\mathcal{H}^{2^n}\):
\[H^{\otimes n}\left|\mathbf{x}\right>=\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{y}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot\mathbf{y}}\left|\mathbf{y}\right>,\]
which can be thought of as effectively encoding the string \(\mathbf{x}\) into the relative paste factors present in the amplitudes of the states in the superposition. Since \(H^{\otimes n}\) is its own inverse appying applying \(H^{\otimes n}\) to the state \(H^{\otimes n}\left|\mathbf{x}\right>\) returns the state \(\left|\mathbf{x}\right>\):
\[(H^{\otimes n}\left(\displaystyle \frac{1}{\sqrt{2^{n}}}\displaystyle\sum\limits_{\mathbf{y}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot\mathbf{y}}\left|\mathbf{y}\right>\right) =H^{\otimes n}H^{\otimes n}\left|\mathbf{x}\right>=\left|\mathbf{x}\right>/\]In this regard, the Hadamard transform can also be thought of as decoding the information of the string \(\mathbf{x}\) in the phase factors into the state \(\left|\mathbf{x}\right>\).

Notice that all of the amplitudes defining the superposition of states in the Hadamard transform are either \(\pm 1\). The quantum Fourier Transform will generalize the Hadamard transform by constructing certain weighted superpositions of basis states that possess more general phase factors of the form \(e^{i2\pi\omega}\), for some real number \(\omega\in(0,1)\subset\mathbb{R}\). In the case of the Hadamard transform, \(\omega=0\) and \(\omega=1/2\) making \(e^{i2\pi\omega}=\pm1\). The quantum Fourier Transform will allow certain specially weighted superposition of states to be constructed, which will then be used in algorithms that can perform faster than known classical approaches.

The Quantum Fourier Transform

Consider an \(N\)--tuple of \(N\) complex numbers \(x_j\in\mathbb{C}\), where \(j\in\{0,1, \dots, N-1\}\). The discrete \emph{classical} Fourier transform is a function \(\mathcal{F}\) that takes these \(N\) numbers and constructs \(N\) other complex numbers in terms of the \(x_j\):
\[\begin{array}{r c l}
\mathcal{F}:  \mathbb{C}^N &\rightarrow&\mathbb{C}^N \\
  (x_0, x_1, \dots, x_{N-1})& \mapsto &(y_0, y_1, \dots, y_{N-1}),
\end{array}\]
where each of the \(y_k\) complex numbers are given by
\[y_k=\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{j=0}^{N-1}e^{\frac{i2\pi jk}{N}}x_j.\]
The quantum Fourier transform has a related action on the \(N\) computational basis states \(\left|j\right>\in\mathcal{H}^{N}\). Here, the basis states are represented in the \emph{decimal representation} where each state is indexed by the integer \(j\in\{0,1,\dots, N-1\}\). The quantum Fourier transform, denoted by \(\mathbf{QFT}\), maps these computational basis states to another basis called the Fourier basis consisting of weighted superpositions of the computational basis states as
\[\begin{array}{r c l}
QFT:  \mathcal{H}^N &\rightarrow&\mathcal{H}^N \\
  \left|j\right>& \mapsto &\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}\left|k\right>.
\end{array}\]
In terms of the discrete classcical Fourier transform, the action of the \(QFT\) can be expressed more concisely as
\[\left|j\right> \mapsto \displaystyle \frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}y_k\left|k\right>.\]
Now, consider the action of the \(QFT\) on the \(n\) qubit basis state \(\left|0\right>\) where \(N=2^n\),
\[QFT\left|0\right>=\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k\cdot 0}{N}}\left|k\right>=\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}\left|k\right>=H^{\otimes n}\left|0\right>,\]
which is an equally weighted superposition of all \(N\) basis states and this precisely the same state produced  when Hadamard gates are applied to each qubit. Thus, in the case where \(\left|j\right>=\left|0\right>\), \(QFT\left|j\right>=H^{\otimes n}\left|j\right>\). In general though, \(QFT\left|j\right>\neq H^{\otimes n}\left|j\right>\). In this regard, The quantum Fourier transform can be seen as a generalization of the Hadamard transform.

It remains to be checked that the \(QFT\) is a unitary transformation, which will now be done by verifying that \(QFT^\dagger=QFT^{-1}\). To see that this is indeed the case, consider the matrix representation of \(QFT\) whose matrix coefficient \(q_{jk}\) contained in the \(j^{th}\) row and \(k^{th}\) column is given by \(q_{jk}= e^{ \frac{i2\pi jk}{N}}\). Then the conjugate transpose \(QFT^\dagger\) of \(QFT\) has  the corresponding matrix coefficient \(q'_{jk}=\overline{q_{kj}}=e^{ \frac{-i2\pi kj}{N}}\)
in its \(j^{th}\) row and \(k^{th}\) column.
Therefore, the action of \(QFT^\dagger\) on some basis state \(\left|k\right>\in\mathcal{H}^N\) is given as
\[\begin{array}{r c l}
QFT^\dagger:  \mathcal{H}^N &\rightarrow&\mathcal{H}^N \\

  \left|k\right>& \mapsto &\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{j=0}^{N-1}e^{\frac{-i2\pi kj}{N}}\left|j\right>.
\end{array}\]
Now consider what happens when the composition of \(QFT\) with \(QFT^\dagger\) acts on a basis state \(\left|j\right>\)
\[\begin{array}{r  l}
QFT^\dagger QFT\left|j\right>=&QFT^\dagger\left(\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}\left|k\right> \right) \\
=&\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}QFT^\dagger\left|k\right> \\
=& \displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}\left(\displaystyle\frac{1}{\sqrt{N}}\displaystyle\sum\limits_{l=0}^{N-1}e^{\frac{-i2\pi kl}{N}}\left|l\right>\right) \\
=&\displaystyle\frac{1}{N}\displaystyle\sum\limits_{l=0}^{N-1}\left(\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi jk}{N}}e^{\frac{-i2\pi kl}{N}}\right)\left|l\right> \\
&= \displaystyle\frac{1}{N}\displaystyle\sum\limits_{l=0}^{N-1}\left(\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k(j-l)}{N}}\right)\left|l\right>.
\end{array}\]
Let \(\alpha_s\) denote the amplitude of the basis state \(\left|s\right>\) in this superposition.  Then assuming \(s\neq j\),
\[\alpha_s=\displaystyle\frac{1}{N}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k(j-s)}{N}}=\displaystyle\frac{1}{N}\displaystyle\frac{e^{\frac{i2\pi k(j-s)}{N}N}-1}{e^{\frac{i2\pi k(j-s)}{N}}-1}=\displaystyle\frac{1}{N}\displaystyle\frac{(1-1)}{e^{\frac{i2\pi k(j-s)}{N}}-1}=0,\]
where the formula for the geometric series
 \[\displaystyle\sum\limits_{k=0}^{N-1}z^{k}=\displaystyle \frac{z^{N}-1}{z-1}\]
 was used together with
\[z^N=e^{ \frac{i2\pi (j-s)}{N}N}=e^{i2\pi (j-s)}=1\]
since \(e^{i2\pi m}=1\) for any integer \(m\). This implies that all basis states \(\left|s\right>\neq\left|j\right>\) have \(\alpha_s=0\) amplitude and do not appear in the above superposition. Then examining the amplitude of the state \(\left|j\right>\) shows that
\[\alpha_j=\displaystyle\frac{1}{N}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k(j-j)}{N}}=\displaystyle\frac{1}{N}\displaystyle\sum\limits_{k=0}^{N-1}e^{\frac{i2\pi k(0)}{N}}=\displaystyle\frac{1}{N}\displaystyle\sum\limits_{k=0}^{N-1}1=\displaystyle\frac{N}{N}=1,\]
which shows that \(QFT^\dagger QFT\left|j\right>=\left|j\right>\). A similar argument also shows that \(QFT QFT^\dagger\left|j\right>=\left|j\right>\). This implies that \(QFT^\dagger=QFT^{-1}\) proving that \(QFT\) is indeed a unitary operator.

The proof just presented that the quantum Fourier transform \(QFT\) is a unitary operator shows that the \(QFT\) can be used to define transformations on quantum states. However, the proof does not provide a constructive means for actually implementing the \(QFT\), since unitarity was shown directly using the definition of the \(QFT\). In the next section, an explicit circuit using elementary quantum gates will be constructed. The existence of such a circuit will also provide proof that the \(QFT\) is unitary provided that all gates used in this construction are themselves unitary.

Generalized Hadamard Gates

Consider the action of the Hadamard gate \(H\) when acting on the basis states \(\left|0\right>\) and \(\left|1\right>\), and observe that this can be expressed as
 \[\begin{array}{r l}
  H\left|x\right> &= \frac{1}{\sqrt{2}}\big(\left|0\right>+(-1)^{x}\left|1\right>\big) \\
  & =\frac{1}{\sqrt{2}}\displaystyle\sum\limits_{y\in\{0,1\}}(-1)^{x\cdot y}\left|y\right>.
   \end{array}\]
Denote some bitstring \(\mathbf{x}\in\{0,1\}^n\) as \(\mathbf{x}=x_1x_2\dots x_n\), where each \(x_i\in\{0,1\}\), and define the  following operation on bitsrings
\[\mathbf{x}\cdot \mathbf{y}=(x_1y_1+x_2y_2+\dots +x_ny_n)mod2.\]
      The tensor product of Hadamard gate \(H\) with itself \(n\) times creates a gate similar to \(H\), denoted by \(H^{\otimes n}\), which operates on \(n\) qubits. Its action is the same as applying the single qubit Hadamard transform \(H\) to each of the \(n\) qubits of the register. This gate sends the \(n\) qubit register \(\left|\mathbf{x}\right>=\left|x_1x_2\dots x_3\right>=\left|x_1\right>\left|x_2\right>\dots\left|x_n\right>\) to the state
\[\begin{array}{r l}
H^{\otimes n}\left|\mathbf{x}\right>&=H^{\otimes n}\left|x_1x_2\dots x_3\right> \\ & =H\left|x_1\right>H\left|x_2\right>\dots H\left|x_n\right>\\
& = \big(\frac{\left|0\right>+(-1)^{x_1}\left|1\right>}{\sqrt{2}}\big)\big(\frac{\left|0\right>+(-1)^{x_2}\left|1\right>}{\sqrt{2}} \big)\dots \big(\frac{\left|0\right>+(-1)^{x_n}\left|1\right>}{\sqrt{2}}\big) \\
& = \frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{y_1y_2\dots y_n\in\{0,1\}^n}(-1)^{x_1y_1+x_2y_2+\dots +x_ny_n}\left|y_1\right>\left|y_2\right>\dots\left|y_n\right> \\
& = \frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{y}\in\{0,1\}^n}(-1)^{\mathbf{x}\cdot \mathbf{y}}\left|\mathbf{y}\right>.
\end{array}\]
In the case where \(\left|\mathbf{0}\right>=\left|00\dots 0\right>=\left|0\right>\left|0\right>\dots\left|0\right>,\)
\[H^{\otimes n}\left|\mathbf{0}\right>= \frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{\mathbf{y}\in\{0,1\}^n}\left|\mathbf{y}\right>,\]
since \((-1)^{\mathbf{x}\cdot \mathbf{0}}=1\), which is an equally weighted superposition of all bases states in the Hilbert space of dimension \(2^n\).

Quantum Gates: Single-Qubit Gates

The axioms of quantum mechanics say that an isolated quantum system undergoes unitary evolution. Therefore, such operations are the natural means for governing the time evolution of the quantum computer. Whereas in the classical case ordinary Boolean logic gates are used to manipulate the bits, unitary transformations on the state space of the quantum computer are used to manipulate the qubits. In quantum computing these unitary transformations are also referred to as quantum gates. Due to the linearity of quantum mechanics, unitary operators have the ability to transform arbitrary superpositions of basis states. In this case, a quantum computer is essentially able to exploit an exponential degree of parallelism in its information processing tasks.

The vector space nature of a quantum system allows quantum gates to be represented by matrices by specifying the action on a particular choice of basis states. Therefore, the matrix representation will be a useful way to describe quantum operations. 

Single Qubit Gates

The unitary \(U:\mathcal{H}^2\rightarrow\mathcal{H}^2\) operators that act on a single qubit can be represented as \(2\times2\) matrices called single qubit gates. An important set of 1-qubit quantum gates represented as a matrix in the computational basis
\[\left|0\right>=\begin{pmatrix}1\\0\end{pmatrix}, \left|1\right>=\begin{pmatrix}0\\1\end{pmatrix}\]
 is the following set
 \[I=\begin{pmatrix}1&0 \\ 0 &1\end{pmatrix},
X=\begin{pmatrix}0&1 \\ 1&0 \end{pmatrix},
Y=\begin{pmatrix}0&i \\ -i&0 \end{pmatrix},
Z=\begin{pmatrix}1&0 \\ 0&-1 \end{pmatrix}.\]
The acquainted reader might recognize these as the Pauli matrices. They all satisfy the properties that \(U^\dagger=U^{-1}\) for all \(U\in\{X,Y,Z\}\) and
\[\begin{align*}
XY&=-YX=iZ, \\
YZ &=-ZY=iX, \\
 ZX &=-XZ=iY.
\end{align*}\]
A consequence of these relations is that any unitary operator \(U\) acting a single qubit can be represented in terms of the Pauli matrices as
\[U=c_II+c_Xx+c_YY+c_ZZ\]
for some real coefficients \(c_I, c_X, c_Y\) and \(c_Z\).

 Another important quantum gate acting on a single qubit is the Hadamard gate \(H\). Its action can be given by specifying the way it acts on the basis states \(\left|0\right>\) and \(\left|1\right>\):
\[\begin{align*}
 H\left|0\right> &=\frac{1}{\sqrt2}(\left|0\right>+\left|1\right>), \\
 H\left|1\right> &= \frac{1}{\sqrt2}(\left|0\right>-\left|1\right>)
 \end{align*}\]
The corresponding matrix representation for \(H\) is thus given by
\[H= \frac{1}{\sqrt{2}}\begin{pmatrix}
  1&1 \\
 1&-1  \\
\end{pmatrix}
\]
Using this matrix representation of \(H\) it is easily verified that \(H\) is indeed a unitary operator. In fact, since \(H=H^\dagger\), \(H\) can be regarded as its own inverse.  The Hadamard gate \(H\) takes one of the basis states  and creates a weighted superposition of the two basis states as shown.

The single qubit gates parameterized by an angle \(\theta\) defined as
\[R_\theta=\begin{pmatrix}
  1& 0     \\
 0&e^{i\theta}
\end{pmatrix}\]
is called the \(\theta\)-phase gate since
\[R_\theta(\alpha\left|0\right>+ \beta\left|1\right>)=\alpha\left|0\right>+e^{i\theta}\beta\left|1\right>,\]
and a general qubit \(\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>\) can be thought of as picking up a relative phase factor of \(e^{i\theta}\).