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.
\[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.