Quantum Fourier transform – Zhian Jia

A key application of the quantum Fourier transform (see this post) is the Quantum Phase Estimation algorithm. This algorithm allows one to estimate the phase (or eigenvalue) of a unitary operator and serves as a central component of many quantum algorithms, including Shor’s factoring algorithm and quantum simulation.

Consider a unitary matrix $U$ . Since $U^\dagger U = I$ , all eigenvalues of $U$ have the form $e^{2\pi i \theta}$ with $0 \leq \theta < 1$ . Expressing $\theta$ in binary gives

$\theta = 0.\theta_1 \theta_2 \theta_3 \cdots = \sum_{k=1}^\infty \theta_k \, 2^{-k},$

where each $\theta_k \in {0,1}$ . The task is to estimate $\theta$ to $n$ binary digits of precision.

More precisely, the quantum phase estimation algorithm aims to determine the phase $\theta$ in the eigenvalue equation

$U |\psi\rangle = e^{2\pi i \theta} |\psi\rangle$ ,

where $U$ is the given unitary operator, $|\psi\rangle$ is an eigenstate of $U$ that can be prepared as an input state, and $\theta$ is the phase to be determined. We further assume that controlled- $U^{2^l}$ operations can be implemented for arbitrary non-negative integer $l$ . The goal is to estimate $\theta$ to the desired number of digits with high probability.

Now suppose that we express $\theta$ in $n$ binary digits,

$\theta = 0.\theta_1\theta_2\cdots \theta_n$ .

Then, we have

$U^{2^l} \lvert \psi \rangle = e^{2 \pi i 0.\theta_1\theta_2\cdots\theta_n 2^l} \lvert \psi \rangle = e^{2 \pi i \theta_1\cdots\theta_l.\theta_{l+1}\cdots\theta_n} \lvert \psi \rangle$

where the integer part of $\theta_1\cdots \theta_l.\theta_{l+1}\cdots \theta_n$ can be omitted, as it contributes only a trivial phase factor of $1$ .

For the controlled unitary $C(U^{2^l})$ , its action on $|+\rangle|\psi\rangle$ (with $|+\rangle$ the control qubit) is:

$C(U^{2^l}) \frac{1}{\sqrt{2}} ( \lvert 0 \rangle + \lvert 1 \rangle ) \lvert \psi \rangle = \frac{1}{\sqrt{2}} \lvert 0 \rangle \otimes \lvert \psi \rangle + e^{2 \pi i 0.\theta_{l+1}\cdots \theta_n} \lvert 1 \rangle \otimes \lvert \psi \rangle$

$= \frac{1}{\sqrt{2}} (|0\rangle + e^{2\pi i 0.\theta_{l+1}\cdots \theta_n} |1\rangle) \otimes |\psi\rangle$

It is convenient to view this control qubit as representing the $(l+1)$-th digit of a binary number $k = k_1 k_2 \cdots k_n = k_1 \times 2^0 + k_2 \times 2^1 + \cdots + k_n \times 2^{n-1}$ .

With this notation, the above expression can be rewritten as

$C(U^{2^l}) \frac{1}{\sqrt{2}} (\lvert0\rangle + \lvert1\rangle)\lvert\psi\rangle = \frac{1}{\sqrt{2}} \sum_{k_{l+1}=0}^1 e^{2 \pi i \theta k_{l+1} 2^l} \lvert k_{l+1}\rangle \lvert\psi\rangle$

This expression for the first qubit is familiar from our earlier discussion of the quantum Fourier transform, and it naturally suggests that the quantum Fourier transform should be applied here. The eigenstate $\lvert \psi \rangle$ therefore remains unchanged and can be reused in subsequent steps.

Fig 1: quantum circuit for quantum phase estimation algorithm.

The quantum phase estimation algorithm uses two quantum registers as shown in Figure 1:

First register (phase record): Contains $n$ qubits, which will store the estimated phase.
Second register (eigenstate): Contains the eigenstate $\lvert \psi \rangle$ , which is an eigenstate of the unitary operator $U$ .

The quantum phase estimation algorithm consists of the following steps:

Prepare Initial State

The system starts with two registers:

The first register is initialized in the state $\lvert 0 \rangle^{\otimes n}$ .
The second register is initialized in the eigenstate $\lvert \psi \rangle$ of $U$ .

The initial state is: $\lvert 0 \rangle^{\otimes n} \otimes \lvert \psi \rangle$ .

Apply Hadamard Gates

Apply Hadamard gates to each qubit in the first register, thereby creating a uniform superposition over all possible computational basis states:

$\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \lvert k \rangle \otimes \lvert \psi \rangle$

Here, $k = k_1 k_2 \cdots k_n$ denotes the binary representation of the integer $k$ , with the bits encoded from the bottom to the top qubit in the first register.

Apply Controlled- $U^{2^l}$ Operations

For each qubit $k_l$ in the first register, apply the controlled- $U^{2^l}$ operation.
This step entangles the first and second registers, yielding the state:

$\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} \lvert k \rangle \otimes U^k \lvert \psi \rangle$

Since $U \lvert \psi \rangle = e^{2 \pi i \theta} \lvert \psi \rangle$ , this becomes:

$\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2 \pi i k \theta} \lvert k \rangle \otimes \lvert \psi \rangle$

At this stage, the second register is no longer needed, as all phase information is now encoded in the first register.

Apply the Inverse Quantum Fourier Transform

Apply the inverse quantum Fourier transform ( $U_{\rm QFT}^\dagger$ ) on the first register to extract the phase information:

$\frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n-1} e^{2 \pi i k \theta} \lvert k \rangle$

Measure the First Register

Finally, measure the qubits in the first register. The measurement will yield the binary representation of the phase $\theta$ with an $n$ -bit approximation.
The output will be an $n$ -bit approximation of the phase $\theta$ , such that:

$\theta \approx 0.\theta_1 \theta_2 \dots \theta_n$

where $\theta_1, \theta_2, \dots, \theta_n$ are the binary digits of $\theta$ .

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.$