Chapter 5 Quantum Fourier Trasnform (QFT)
Quantum Fourier transformation (QFT) is one of the major quantum algorithms, and plays a key role in several quantum algorithms.
It is the quantum counterpart of the classical discrete Fourier transformation (DFT).
DFT transforms a vector of complex numbers \(x_0, x_1, \ldots, x_{N-1}\)
into \(y_0, y_1, \ldots, y_{N-1}\) such that:
\[ y_k \equiv \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j e^{2\pi ijk/N} \]
Example 5.1 Suppose you have a data set \(x_j=\sqrt{2},2\). Compute the DFT of this set.
Solution:
Thus, and Here \(x_0 = \sqrt{2}\) and \(N = 2\).
\[ y_k = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} x_j e^{\frac{2 \pi i j k}{2}} = \frac{1}{\sqrt{2}} \left( \sqrt{2} + 2 e^{i \pi k} \right) \]
Thus, \[ y_0 = \frac{1}{\sqrt{2}} \left( \sqrt{2} + 2 \right) = 1 + \sqrt{2}, \] and \[ y_1 = \frac{1}{\sqrt{2}} \left( \sqrt{2} + 2 e^{i \pi} \right) = \frac{1}{\sqrt{2}} \left( \sqrt{2} - 2 \right) = 1 - \sqrt{2}. \]
Resource: Pathak, A., 2013. Elements of quantum computation and quantum communication (pp. 92-98). Boca Raton: CRC Press
Example 5.2 Find \(y_0\) for \(x_j = \{1 + i, \sqrt{2}, 3 - 2i, 4\}\).
Solution :
Here \(N = 4\) and
\[
y_0 = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} x_j = \frac{1}{2} \left( (1 + i) + (\sqrt{2}) + (3 - 2i) + 4 \right) = 4 + \frac{\sqrt{2} - i}{2}.
\]
Resource: Pathak, A., 2013. Elements of quantum computation and quantum communication (pp. 92-98). Boca Raton: CRC Press
\[ \text{Primitive } n \text{ th root of unity }:\omega=e^{\frac{2\pi i}{n}} \]
\[ \frac{1}{\sqrt{N}} \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega^1 & \omega^2 & \cdots & \omega^{(N-1)} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(N-1)} \\ 1 & \omega^3 & \omega^6 & \cdots & \omega^{3(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{(N-1)} & \omega^{2(N-2)} & \cdots & \omega^{(N-1)(N-1)} \end{bmatrix} \] where \(\omega\) is the primitive \(n\)-th root of unity.
Runtime Analysis for Fourier Transforms:
- Naive Runtime: \(O(N^2)\)
- naive computation of the Discrete Fourier Transform (DFT) involves a double summation loop over \(N\) elements, resulting in a runtime complexity of \(O(N^2)\).
- Fast Fourier Transform (FFT) Runtime: \(O(N \log N)\)
- In practical applications, the DFT is computed using the FFT algorithm, which optimizes the process by reducing redundant calculations. This leads to a significant improvement in runtime complexity to \(O(N \log N)\).
- Quantum Fourier Transform (QFT) Runtime: \(O(\mathrm{polylog} N)\)
- The QFT, implemented on quantum computers, provides an exponential speedup over classical algorithms with a runtime complexity of \(O(\mathrm{polylog} N)\). This represents an exponential gain compared to both naive and FFT approaches.
Quantum version of DFT:
\[\text{QFT_N} \frac{1}{\sqrt{N}} \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \omega^1 & \omega^2 & \cdots & \omega^{(N-1)} \\ 1 & \omega^2 & \omega^4 & \cdots & \omega^{2(N-1)} \\ 1 & \omega^3 & \omega^6 & \cdots & \omega^{3(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{(N-1)} & \omega^{2(N-2)} & \cdots & \omega^{(N-1)(N-1)} \end{bmatrix} \] where \(\omega\) is the primitive \(n\)-th root of unity.
Recall: Suppose a single qubit quantum gate \(A\) transforms \(|0\rangle\) into \(|\psi_0\rangle\) and \(|1\rangle\) into \(|\psi_1\rangle\). Then the outer product representation of \(A\) is given by, \[ A=|\psi_0\rangle \langle 0|+|\psi_1\rangle \langle 1| \]
Quantum Fourier Transform (QFT) in Dirac notation:
\[ QFT_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} |y\rangle \langle x| \]
Example 5.3 Examples Lets take a look at \(QFT_2\). Because \(M =2,\omega=e^{i\pi}\). Therefore we have, \[ QFT_2=\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\ 1 & \omega \end{pmatrix}=\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix}\\\\ \]
As you can see, \(QFT_2\) is simply equal to \(H^\otimes 2\) How about \(QFT_4\)? The primitive 4th root of unity is \(i\), so that
\[ QFT_4 = \frac{1}{\sqrt{4}} \begin{pmatrix} 1 & 1 & 1 & 1\\ 1 & i & -1 & -i\\ 1 & -1 & 1 & -1\\ 1 & -i & -1 & -i\\ \end{pmatrix} \]
Exercise 5.1 Find QFT of following vectors. \[ \begin{eqnarray} | \psi_1 \rangle &=& | 00 \rangle\\ | \psi_2 \rangle &=& | 01 \rangle \\ | \psi_3 \rangle &=& \frac{1}{2} \left( | 00 \rangle + | 01 \rangle + | 10 \rangle + | 11 \rangle \right) \end{eqnarray} \]
Solution
First note that QFT\(_N\). We have to deal with 2 qubits. Then \(N = 2^2 = 4\)
\[ \text{QFT}_4 = \frac{1}{\sqrt{4}} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} \]
\[ \begin{eqnarray} \text{QFT}_4 |\psi_1\rangle &=&\text{QFT}_4 |00\rangle\\ &=& \frac{1}{\sqrt{4}}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \\ &=&\frac{1}{2}\begin{pmatrix} 1\\1\\1\\1 \end{pmatrix}\\ &=&\frac{1}{2}\begin{pmatrix} 1\\0\\0\\0 \end{pmatrix}+\frac{1}{2}\begin{pmatrix} 0\\1\\0\\0 \end{pmatrix}+\frac{1}{2}\begin{pmatrix} 0\\0\\1\\0 \end{pmatrix}+\frac{1}{2}\begin{pmatrix} 0\\0\\0\\1 \end{pmatrix}\\ &=& \frac{1}{2} |00\rangle + \frac{1}{2} |01\rangle + \frac{1}{2} |10\rangle + \frac{1}{2} |11\rangle\\\\ \text{QFT}_4 |\psi_2\rangle &=&\text{QFT}_4 |01\rangle\\ &=& \frac{1}{\sqrt{4}}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix} \\ &=&\frac{1}{2}\begin{pmatrix} 1\\i\\-1\\i \end{pmatrix}\\ &=&\frac{1}{2}\begin{pmatrix} 1\\0\\0\\0 \end{pmatrix}+\frac{i}{2}\begin{pmatrix} 0\\1\\0\\0 \end{pmatrix}+\frac{(-1)}{2}\begin{pmatrix} 0\\0\\1\\0 \end{pmatrix}+\frac{(-i)}{2}\begin{pmatrix} 0\\0\\0\\1 \end{pmatrix}\\ &=& \frac{1}{2} |00\rangle + \frac{i}{2} |01\rangle + \frac{(-1)}{2} |10\rangle + \frac{(-i)}{2} |11\rangle\\\\ \text{QFT}_4 |\psi_3\rangle &=&\text{QFT}_4 \big(\frac{1}{2}|00\rangle+\frac{1}{2}|01\rangle+\frac{1}{2}|10\rangle+\frac{1}{2}|11\rangle\big)\\ &=& \frac{1}{\sqrt{4}}\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} \frac{1}{2}\begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \\ &=&\frac{1}{4}\begin{pmatrix} 4\\0\\0\\0 \end{pmatrix}\\ &=& \begin{pmatrix} 1\\0\\0\\0 \end{pmatrix}\\ &=& |00\rangle \end{eqnarray} \]
QFT needs to be restated in a particular form to implement it on a quantum circuit. This requires some results.
Quantum Fourier Transform (QFT) in Dirac notation: \[ QFT_N = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} \omega_N^{xy} |y\rangle \langle x| \]
QFT on \(|x\rangle\) as a superposition: \[ QFT|x\rangle = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \omega_N^{xy} |y\rangle \]
Binary representation of \(y\): \[ y = y_n + 2y_{n-1} + \cdots + 2^{n-1}y_1 \]
QFT on \(|x\rangle\) as a product: \[ QFT|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y_k \in \{0,1\}} \bigotimes_{k=1}^n e^{\frac{2\pi i}{2^n} 2^{n-k} xy_k} |y_k\rangle \]
5.1 I will update this part ASAP.
Now, we state the QFT in a way that supports an efficient quantum circuit implementation.
\[ QFT|x\rangle = \frac{1}{\sqrt{2}} \left( |0\rangle + e^{2\pi i (0 \cdot x_n)} |1\rangle \right) \otimes \frac{1}{\sqrt{2}} \left( |0\rangle + e^{2\pi i (0 \cdot x_{n-1} x_n)} |1\rangle \right) \otimes \cdots \otimes \frac{1}{\sqrt{2}} \left( |0\rangle + e^{2\pi i (0 \cdot x_1 x_2 \ldots x_{n-1} x_n)} |1\rangle \right) \]
Recall:
We apply ‘controlled’ rotations. It’s like CNOT gate,
\[ \begin{eqnarray} \text{Controlled rotation:} &&\\ &&CR_k|0x_j\rangle = |0\rangle |x_j\rangle\\ &&CR_k|1x_j\rangle = |1\rangle |e^{\frac{2\pi i}{2^k} x_j}\rangle \end{eqnarray} \]
The circuit implementation of \(QFT\) on \(4\) qubits is as follows:
It is possible to generalise this and design the quantum circuit for \(QFT_{2^n}\) for an arbitrary \(n\).
\[ \begin{eqnarray} |\psi_0\rangle &=& |x_1\rangle |x_2\rangle |x_3\rangle |x_4\rangle\\ |\psi_1\rangle &=& H|x_1\rangle |x_2\rangle |x_3\rangle |x_4\rangle \\ &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} x_1} |1\rangle \big) |x_2\rangle |x_3\rangle |x_4\rangle\\ |\psi_2\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \cdot x_1}|1\rangle\big)|x_2\rangle |x_3\rangle |x_4\rangle\\ |\psi_3\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(x_1 + \frac{x_2}{2})}|1\rangle \big) |x_3\rangle |x_4\rangle\\ |\psi_4\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(x_1 + \frac{x_2}{2} + \frac{x_3}{4})}|1\rangle \big) |x_4\rangle\\ |\psi_5\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(x_1 + \frac{x_2}{2} + \frac{x_3}{4} + \frac{x_4}{8})}|1\rangle \big) H|x_2\rangle |x_3\rangle |x_4\rangle \\ &=&\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(x_1 + \frac{x_2}{2} + \frac{x_3}{4} + \frac{x_4}{8})}|1\rangle \big) \frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} x_2} |1\rangle \big) |x_3\rangle |x_4\rangle \\ |\psi_6\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(x_1 + \frac{x_2}{2} + \frac{x_3}{4} + \frac{x_4}{8})}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(x_2+\frac{x_3}{2}\right)} |1\rangle \big) |x_3\rangle |x_4\rangle \\ |\psi_7\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(x_1 + \frac{x_2}{2} + \frac{x_3}{4} + \frac{x_4}{8})}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(x_2+\frac{x_3}{2}+\frac{x_4}{4}\right)} |1\rangle \big) |x_3\rangle |x_4\rangle \\ &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(x_1 + \frac{x_2}{2} + \frac{x_3}{4} + \frac{x_4}{8})}|1\rangle \big) \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \left(\frac{x_2}{2}\frac{x_3}{4}+\frac{x_4}{8}\right)} |1\rangle \big) |x_3\rangle |x_4\rangle \\ &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i (.x_1x_2x_3x_4)}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i\left(0.x_2x_3x_4\right)} |1\rangle \big) |x_3\rangle |x_4\rangle \\ |\psi_8\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_1x_2x_3x_4)}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_2x_3x_4\right)} |1\rangle \big) H|x_3\rangle |x_4\rangle \\ &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_1x_2x_3x_4)}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_2x_3x_4\right)} |1\rangle \big) \frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(x_3\right)} |1\rangle \big)|x_4\rangle\\ |\psi_9\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_1x_2x_3x_4)}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_2x_3x_4\right)} |1\rangle \big) \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i \left(\frac{x_3}{2}+\frac{x_4}{4}\right)} |1\rangle \big)|x_4\rangle\\ &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_1x_2x_3x_4)}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_2x_3x_4\right)} |1\rangle \big) \frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_3x_4\right)} |1\rangle \big)|x_4\rangle\\ |\psi_{10}\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_1x_2x_3x_4)}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_2x_3x_4\right)} |1\rangle \big) \frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_3x_4\right)} |1\rangle \big)H|x_4\rangle\\ &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_1x_2x_3x_4)}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_2x_3x_4\right)} |1\rangle \big)\\ &&~~\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_3x_4\right)} |1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} x_4} |1\rangle \big)\\ &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_1x_2x_3x_4)}|1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_2x_3x_4\right)} |1\rangle \big)\\ &&~~\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_3x_4\right)} |1\rangle \big)\frac{1}{\sqrt{2}} \big(|0\rangle + e^{0.x_4} |1\rangle \big)\\ \end{eqnarray} \]
Now, apply a SWAP operation to interchange the 1st and 4th quantum registers and the 2nd and 3rd as well, to obtain the QFT of the input as the output of the circuit.
\[ \begin{eqnarray} |\psi_{11}\rangle &=& \frac{1}{\sqrt{2}} \big(|0\rangle + e^{0.x_4} |1\rangle \big) \frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_3x_4\right)} |1\rangle \big)\\ &&~~\frac{1}{\sqrt{2}} \big(|0\rangle + e^{\frac{2\pi i}{2} \left(0.x_2x_3x_4\right)} |1\rangle \big) \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_1x_2x_3x_4)}|1\rangle \big) \\ &=&\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_4)}|1\rangle \big) \otimes \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_3 x_4)}|1\rangle \big) \otimes \\ &&~~\frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_2 x_3 x_4)}|1\rangle \big) \otimes \frac{1}{\sqrt{2}} \big(|0\rangle + e^{2\pi i(0.x_1 x_2 x_3 x_4)}|1\rangle \big) \end{eqnarray} \]
This is the same as \(QFT_n\) \[\begin{eqnarray} QFT|x\rangle &=& \frac{1}{\sqrt{2}} \left( |0\rangle + e^{2\pi i (0 \cdot x_n)} |1\rangle \right) \otimes \frac{1}{\sqrt{2}} \left( |0\rangle + e^{2\pi i (0 \cdot x_{n-1} x_n)} |1\rangle \right) \otimes\\ &&~~~~\cdots \otimes \frac{1}{\sqrt{2}} \left( |0\rangle + e^{2\pi i (0 \cdot x_1 x_2 \ldots x_{n-1} x_n)} |1\rangle \right) \end{eqnarray} \]
5.1.1 Complexity
Complexity of quantum algorithms is generally measured by number of gates, number of qubits or the depth of the circuit.
It is clearly seen that the most significant contribution to the runtime in the QFT circuit is the number of gates. Considering an \(n\) qubit QFT circuit, number of gates is given by \[n +(n−1)+\cdots+2+1 = \frac{n(n+1)}{2}\] This demonstrates the exponential speedup of the QFT over the classical Fast Fourier Transform (FFT).
\[ \begin{eqnarray} \text{Naive runtime}&:& O( N^2 )\\ \text{(FFT) runtime}&:& O(N logN)\\ \text{QFT runtime} &:& O( polylog N )\\\\ \text{Classical FFT}&:&n 2^n\\ \text{QFT} &:& n^2 \end{eqnarray} \]
Example 5.4
- Converting a time-domain vector with 15000 variables to frequency domain:
- Classical computation time: 64 hours
- Quantum computation time: 3 minutes
- Converting a time-domain vector with 100000 variables to frequency domain:
- Classical computation time: 25 days
- Quantum computation time: 5 minutes