[quant-ph] – Zhian Jia

In this post, we focus on the quantum Fourier transform (QFT), which is the most fundamental and widely used example of a quantum discrete integral transform (see this post). The corresponding unitary matrix is ${U_{\mathrm{QFT}} = (K_{jk})}$ , where the kernel matrix is

$\displaystyle K_{jk} = \frac{1}{\sqrt{N}} e^{2\pi i \frac{jk}{N}} = \frac{\omega_N^{jk}}{\sqrt{N}}$ where ${\omega_N=e^{ \frac{2\pi i}{N}}}$ is the ${N}$ -th root of unit. We will construct a quantum circuit that efficiently implements the quantum Fourier transform.

Exercise Prove that the kernel matrix

$\displaystyle U_{\rm QFT} = K_{jk} = \frac{1}{\sqrt{N}} e^{2\pi i \frac{jk}{N}} = \frac{\omega_N^{jk}}{\sqrt{N}}$

is unitary. You may find the following formula useful:

$\displaystyle \sum_{a=0}^{N-1} \omega_N^{a(b-c)} = N \, \delta_{b,c},$

where ${b,c\in {0,\cdots, N-1}}$ .

The discrete Fourier transform (DFT) is defined as

$\displaystyle y_k = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} e^{2\pi i \frac{jk}{N}} x_j. \ \ \ \ \ (1)$

which is ubiquitous in fields such as digital signal processing, speech recognition, image analysis, and data compression. It can transform a problem into some other problem for which the solution is easier to found.

The most efficient classical algorithms for computing the discrete Fourier transform (DFT) on ${N}$ elements are based on the fast Fourier transform (FFT), which has a computational complexity of ${O(N \log N)}$ . In quantum computation, the DFT is implemented via the quantum Fourier transform, which can be realized on a quantum computer using only ${O((\log N)^2)}$ elementary gates. This exponential speedup over classical FFTs is a central feature of several landmark quantum algorithms, including Shor’s algorithm for integer factorization and the quantum phase estimation subroutine.

As explained in this post, in quantum computing we consider the mapping of basis states ${|j\rangle \mapsto U_{\rm QFT} |j\rangle}$ with ${j = 0, \ldots, N-1}$ , so that the focus is on the indices of ${\vec{x}}$ and ${\vec{y}}$ . The quantum Fourier transform (QFT) is thus a unitary map on the computational basis states:

$\displaystyle |j\rangle \;\mapsto\; \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk / N} |k\rangle, \ \ \ \ \ (2)$

or equivalently, for a general quantum state,

$\displaystyle |\psi_{\vec{x}}\rangle = \sum_{j=0}^{N-1} x_j |j\rangle \;\mapsto\; |\psi_{\vec{y}}\rangle = \sum_{k=0}^{N-1} y_k |k\rangle. \ \ \ \ \ (3)$

The amplitude ${y_k}$ after applying the unitary ${U_{\rm QFT}}$ corresponds to the discrete Fourier transform of ${\vec{x}}$ given in Eq. (1).

We now assume that $N = 2^n$ is the number of basis states, so we can work in an $n$ -qubit space $(\mathbb{C}^2)^{\otimes n}$ . To understand the quantum Fourier transform (QFT) effectively, it is essential to have a solid grasp of binary number operations, since we will treat the basis label of $\lvert j \rangle = \lvert j_1 j_2 \cdots j_n \rangle$ as a binary number.

Suppose we represent an integer $j$ in binary as $j = j_1 j_2 \cdots j_n$ , which corresponds to

$j = j_1 2^{n-1} + j_2 2^{n-2} + \cdots + j_n 2^0.$

This implies that

$\frac{j}{N} = 0.j_1 j_2 \cdots j_n = \frac{j_1}{2} + \frac{j_2}{2^2} + \cdots + \frac{j_n}{2^n}.$

Essentially, the QFT exploits the binary representation of $j$ in the phase factor
$e^{2\pi i k j / N}$ , which involves

$k \times 0.j_1 j_2 \cdots j_n.$

We only need to consider the fractional part, as the integer part contributes a factor of $1$ to the exponential.

Now consider $k = k_1 k_2 \cdots k_n$ as a binary number, so that

$k = k_1 2^{n-1} + k_2 2^{n-2} + \cdots + k_n 2^0.$

Calculating the multiplication with $j/N = 0.j_1 j_2 \cdots j_n$ , we have

$\displaystyle k_n 2^0 \times 0.j_1 j_2 \cdots j_n = \begin{cases} 0, & k_n = 0,\\ 0.j_1 j_2 \cdots j_n, & k_n = 1. \end{cases}$

$\displaystyle k_{n-1} 2^1 \times 0.j_1 j_2 \cdots j_n = \begin{cases} 0, & k_{n-1} = 0,\\ j_1.j_2 \cdots j_n, & k_{n-1} = 1. \end{cases}$

so on and so forth, the final term is

$\displaystyle k_1 2^{n-1} \times 0.j_1 j_2 \cdots j_n = \begin{cases} 0, & k_1 = 0,\\ j_1 j_2 \cdots j_{n-1}.j_n, & k_1 = 1. \end{cases}$

We then drop the integer part when $k_s = 1$ for all $s=1,\cdots, n$ since their contributions for exponential factor are all one. This means that for the $s$ -th qubit $k_s$ , it contributes to the exponential $e^{2\pi i k j / N}$ as $1 = e^0$ if $k_s = 0$ , and as $e^{2\pi i 0.j_{n-s+1}\cdots j_n}$ if $k_s = 1$ .

Thus, the quantum Fourier transform on $\lvert j \rangle$ can be written as

$\displaystyle U_{\rm QFT} |j\rangle = \frac{(|0\rangle + e^{2 \pi i 0.j_n} |1\rangle)(|0\rangle + e^{2 \pi i 0.j_{n-1} j_n} |1\rangle)\cdots(|0\rangle + e^{2 \pi i 0.j_1 j_2 \cdots j_n} |1\rangle)}{\sqrt{N}}. \ \ \ \ \ (4)$

Designing a quantum circuit to realize this transformation is the next step in constructing the quantum Fourier transform algorithm.

Exercise. The equation above can also be derived from the following calculation:

$U_{\rm QFT}\lvert j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i j k / N} \lvert k\rangle$

$= \frac{1}{\sqrt{N}} \sum_{k_1=0}^{1} \cdots \sum_{k_n=0}^{1} e^{2\pi i j \left( \sum_{l=1}^n k_l 2^{-l} \right)} \lvert k_1 \cdots k_n\rangle$

$= \frac{1}{\sqrt{N}} \sum_{k_1=0}^{1} \cdots \sum_{k_n=0}^{1} \bigotimes_{l=1}^n e^{2\pi i j k_l 2^{-l}} \lvert k_l\rangle$

$= \frac{1}{\sqrt{N}} \bigotimes_{l=1}^n \left[ \sum_{k_l=0}^{1} e^{2\pi i j k_l 2^{-l}} \lvert k_l\rangle \right]$

$= \frac{1}{\sqrt{N}} \bigotimes_{l=1}^n \left[ \lvert 0\rangle + e^{2\pi i j 2^{-l}} \lvert 1\rangle \right]$

$= \frac{(\lvert 0\rangle + e^{2\pi i 0.j_n} \lvert 1\rangle)(\lvert 0\rangle + e^{2\pi i 0.j_{n-1}j_n} \lvert 1\rangle)\cdots(\lvert 0\rangle + e^{2\pi i 0.j_1j_2\cdots j_n} \lvert 1\rangle)}{\sqrt{N}}.$

Take $n=3$ as an example to check the expression.

The product form in Eq.(4) naturally guides us in designing a quantum circuit that implements $U_{\rm QFT}$ . To construct this circuit, we employ the Hadamard gate together with a series of controlled rotation gates of the form

$R_l =\begin{pmatrix}1 & 0 \\ 0 & e^{2\pi i / 2^l}\end{pmatrix},$

as suggested by the derivation above.

The quantum circuit for quantum Fourier transform is as follows:

Figure 1 quantum circuit for quantum Fourier transform.

For convenience, let us denote

$|q_1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle + e^{2\pi i\, 0.j_1 j_2 \cdots j_n} |1\rangle\right),$

$|q_2\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle + e^{2\pi i\, 0.j_2 j_3 \cdots j_n} |1\rangle\right),$

$\vdots$

$|q_n\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle + e^{2\pi i\, 0.j_n} |1\rangle\right).$

Using this notation, we have

$\displaystyle U_{\rm QFT}\, |j_1\rangle |j_2\rangle \cdots |j_n\rangle = |q_n\rangle |q_{n-1}\rangle \cdots |q_1\rangle. \ \ \ \ \ (5)$

The reversed order of the indices in $|q_l\rangle$ is intentional.

The product form of the state after applying the quantum Fourier transform naturally guides the design of a quantum circuit that implements $U_{\rm QFT}$ , as illustrated in Figure 1.
The circuit produces the output state

after which a sequence of SWAP gates is applied to reverse the qubit order. To construct this circuit, we employ the Hadamard gate together with a series of controlled rotation gates $C(R_l)$ , where each rotation gate $R_l$ takes the form

$R_l = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^l} \end{pmatrix}.$

Although we will not use it here, notice that $R_1 = Z$ is the Pauli- $Z$ operator, which flips the phase of the $|1\rangle$ basis.

We have already encountered several equivalent expressions for the Hadamard operator that play crucial roles in different context;
here is yet another useful representation:

$H |x\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle + e^{2\pi i\, 0.x} |1\rangle\right).$

The action of the controlled- $R_l$ gate, denoted $C(R_l)$ , is as follows:

$C(R_l) |b\rangle \otimes |\psi\rangle = \begin{cases} |0\rangle \otimes (\alpha |0\rangle + \beta |1\rangle), & b = 0, \\ |1\rangle \otimes (\alpha |0\rangle + \beta e^{2\pi i / 2^l} |1\rangle), & b = 1, \end{cases}$

$= |b\rangle \otimes \big(\alpha |0\rangle + \beta e^{2\pi i\, \frac{b} {2^l}} |1\rangle\big).$

where $|\psi\rangle =\alpha|0\rangle +\beta|1\rangle$ . Thus, the controlled rotation $C(R_l)$ injects the control qubit’s binary value $b$ into the phase of the target qubit, contributing a factor of $e^{2\pi i\, \frac{b} {2^l}}$ . With the above preparation, let us now examine the quantum circuit in Figure 1.

For the bottom quantum wire $|j_n\rangle$ , the Hadamard operator gives (see Eq. 1) $|j_n\rangle \;\to\; |q_n\rangle.$

For $|j_{n-1}\rangle$ , the Hadamard gate contributes a phase factor $e^{2\pi i 0.j_{n-1}}$ , and the controlled- $R_2$ gate controlled by $j_n$ contributes $e^{2\pi i 0.0 j_n}$ , so that the final phase factor is $e^{2\pi i \, 0.j_{n-1} j_n}$ . The state of this quantum wire becomes $|j_{n-1}\rangle \;\to\; |q_{n-1}\rangle.$

For $|j_{n-2}\rangle$ , the Hadamard gate contributes a phase factor $e^{2\pi i 0.j_{n-2}}$ , the controlled- $R_2$ gate controlled by $j_{n-1}$ contributes $e^{2\pi i 0.0 j_{n-1}}$ , and the controlled- $R_3$ gate controlled by $j_n$ contributes $e^{2\pi i 0.00 j_n}$ . The final phase factor is thus $e^{2\pi i \, 0.j_{n-2} j_{n-1} j_n}$ , and the state of this quantum wire becomes $|j_{n-2}\rangle \;\to\; |q_{n-2}\rangle.$