Example 3: Quantum Fourier Transform (QFT)

Purpose

This Quantum Fourier Transform (QFT) is an important building block of many quantum algorithms, including Quantum Phase Estimation and Shor's algorithm. These are the subject of subsequent example notebooks. Here, we look at some of properties of the QFT and show how it is implemented using quantum gates.

Imports and Definitions

The examples will make use of the following imports and definitions.

U_PI = '\u03C0'  # Unicode PI
from math import pi
import numpy as np
from tinyqsim.qcircuit import QCircuit

Introduction

The Fourier transform is widely used in science and engineering to transform data between two different domains. It provides two perspectives on the same data. For example, in signal processing a waveform in the time domain may be transformed into a spectrum in the frequency domain or vice versa. It is often useful to transform data to a different domain where it can be analysed or processed more easily. Then the result can be transformed back to the original domain.

In Quantum Mechanics, the two domains are usually the position basis and the momentum basis. The Fourier Transform provides a good way to understand Heisenberg's Uncertainty Principle which relates the measurement uncertainty in these two bases.

In quantum computing, we use the Quantum Fourier Transform (QFT) to transform quantum states between the Computational Basis and the Fourier Basis. The QFT is equivalent to the application of an ordinary inverse Discrete Fourier Transform (DFT) to the quantum state vector. The inverse arises simply because a different sign convention is normally used for the QFT.

An \(n\)-qubit QFT maps an input state \(\ket{x}\) onto a sum of basis states \(\ket{k}\) in the Fourier basis:

\[QFT: \ket{x}\mapsto{\small\frac{1}{\sqrt{N}}}\sum_{k=0}^{N-1}e^{\large\frac{2\pi i\ xk}{N}}\ket{k},\\ \quad\text{where }N=2^n \]

If the input \(\ket{x}\) is a basis state, then the output is an equal-magnitude superposition with linearly increasing phase. The rate at which the phase increases going along the state vector is proportional to the value \(k\).

For example, consider a 4-qubit (N=16) QFT applied to the basis state \(\ket{x}=\ket{4}=\ket{0100}\).

\[\begin{align*} QFT_4(\ket{4}) &= {\small\frac{1}{\sqrt{16}}}\sum_{k=0}^{15} e^{\large\frac{2\pi i\ 4k}{16}}\ket{k}\\ &={\small\frac{1}{4}}(\ket{0}+e^{i\pi\frac{1}{4}}\ket{1}+e^{i\pi\frac{2}{4}}\ket{2}+e^{i\pi\frac{3}{4}}\ket{3}+\dots+e^{i\pi\frac{15}{4}}\ket{15}) \end{align*} \]

The phase increases by \(\frac{4\pi}{16}\) per step because \(x=4\) and \(N=16\).

We normally write the phases as principal values in the interval \([0,2\pi)\).

Note: The symbol \(\ket{4}\) denotes the same vector as \(\ket{0100}\) but written with a decimal label instead of a binary one. This is often convenient when we are using qubits to encode numerical values. It is usually clear from context which is meant.

QFT Implemementation

An N-qubit QFT can be created using the following Python function:

def qft(qc, n: int|None = None, start: int = 0):
    """ N-qubit QFT starting at qubit index 'start'."""
    if not n:
        n = qc.n_qubits
    for i in range(n):
        j = i + start
        qc.h(j)
        for k in range(1, n - i):
            qc.cp(pi / 2 ** k, f'{U_PI}/{2 ** k}', j + k, j)
    for i in range(n // 2):  # Reverse order of qubits
        qc.swap(start + i, start + n - i - 1)

For example, we can create a 4-qubit QFT as follows:

qc = QCircuit(4)
qft(qc)
qc.draw()

Exploring the QFT

The following function will be used to run the QFT on a basis state \(\ket{x}\) and plot the results:

def qft_demo(x: int):
    # Apply a 4-qubit QFT to basis state |x>
    qc = QCircuit(4)
    s = np.zeros(16)
    s[x]=1
    qc.state_vector = s
    qc.display_state(r'\text{Input: }\ket{x} = ')
    qc.plot_mag_phase(height=0.75)  
    qft(qc)
    print(r'QFT Output:')
    qc.plot_mag_phase(height=0.7)  

Case 1: QFT\((\ket{0})\)

When the input is the "all-zero" state \(\ket{0000}\), the QFT produces an equal superposition state with zero phases:

qft_demo(x=0)

\(\displaystyle \text{Input: }\ket{x} = 1\ \ket{0000}\)

QFT Output:

From the definition of the QFT given earlier:

\[\begin{align*} QFT_4(\ket{0}) &= {\small\frac{1}{\sqrt{16}}}\sum_{k=0}^{15} e^0\ket{k}\\ &={\small\frac{1}{4}}(\ket{0}+\ket{1}+\ket{2}+\ket{3}+\dots+\ket{15}) \end{align*} \]

Looking at the QFT circuit above, when the input is \(\ket{0000}\), all of the control qubits for the phase gates are \(\ket{0}\), so the circuit could be reduced to four Hadamard gates and is equivalent to a Hadamard Transform.

Case 2: QFT\((\ket{1})\)

Let us try \(x=1\):

qft_demo(x=1)

\(\displaystyle \text{Input: }\ket{x} = 1\ \ket{0001}\)

QFT Output:

The phase is now increasing at \(\frac{2\pi}{16}\) per element in the transformed state vector. Note that the phase wraps round at \(\pi\) because the principal value is plotted.

\[\begin{align*} QFT_4(\ket{1}) &= {\small\frac{1}{\sqrt{16}}}\sum_{k=0}^{15} e^{\large\frac{2\pi i\ k}{16}}\ket{k}\\ &={\small\frac{1}{4}}(\ket{0}+e^{i\pi\frac{1}{8}}\ket{1}+e^{i\pi\frac{2}{8}}\ket{2}+e^{i\pi\frac{3}{8}}\ket{3}+\dots+e^{i\pi\frac{15}{8}}\ket{15}) \end{align*} \]

Case 3: QFT\((\ket{2})\)

If \(x=2\), the phase increases at twice the rate, i.e. \(2\times\frac{2\pi}{16}=\frac{\pi}{4}\).

qft_demo(x=2)

\(\displaystyle \text{Input: }\ket{x} = 1\ \ket{0010}\)

QFT Output:

\[\begin{align*} QFT_4(\ket{2}) &= {\small\frac{1}{\sqrt{16}}}\sum_{k=0}^{15} e^{\large\frac{2\pi i\ 2k}{16}}\ket{k}\\ &={\small\frac{1}{4}}(\ket{0}+e^{i\pi\frac{1}{4}}\ket{1}+e^{i\pi\frac{2}{4}}\ket{2}+e^{i\pi\frac{3}{4}}\ket{3}+\dots+e^{i\pi\frac{15}{4}}\ket{15}) \end{align*} \]

We normally write the phases as principal values in the interval \([0,2\pi)\).

The QFT transforms a basis state \(k\), in the computational basis, into a linear increase in phase in the Fourier basis. Consequently, we can use the inverse QFT to transform a linear increase in phase back into a single value \(k\) representing that rate of change. This is a key part of the Quantum Phase Estimation (QPE) algorithm which is discussed in the next example notebook.

Interference

Up to now, we have just looked at applying the QFT to a basis state. However, since unitary operators such as the QFT are linear, the QFT of a superposition of basis states is just the superposition of the QFTs of the individual basis states.

The QFT of a basis state is an equal-magnitude superposition of all basis states with associated phases. If we measure it, the result will be random because all states are equally likely. However, if we take the QFT of the superposition of two or more basis states, the results can interfere with one another, resulting in measurable amplitude variations.

For example, consider the superposition:

\[\ket{\psi}=\frac{1}{\sqrt{2}}(\ket{0001}+\ket{1111}) \]

We expect the result to be real as the input state has even symmetry, since \(\ 15 \equiv -1 \pmod{16}\).

qc = QCircuit(4)
qc.state_vector = np.array([0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1])/np.sqrt(2)
qc.display_state(r'\ket{\psi} = ')
qc.plot_mag_phase(height=0.7)

\(\displaystyle \ket{\psi} = 0.70711\ \ket{0001} + 0.70711\ \ket{1111}\)

If we take the QFT of this superposition, the resulting amplitudes follow a cosine curve as shown below. This time we will plot the real and imaginary parts, instead of magnitude and phase, to show the negative part of the cosine curve.

qft(qc)
qc.plot_real_imag(ylim=[-0.4,0.4])

The following plot shows the magnitude and phase. The magnitude is the absolute value of the complex amplitude, so there is a phase term of \(e^{i\pi}=-1\) to account for the sign change. The phases for \(\ket{0100}\) and \(\ket{1100}\) are meaningless because the magnitude is zero.

qc.plot_mag_phase(height=0.7)

The result can be quantified as follows:

\[\ket{\psi}=\frac{1}{\sqrt{2}}(\ket{1}+\ket{15}) \] \[\begin{align*}QFT(\ket{\psi})&={\small\frac{1}{\sqrt{2}}}(\frac{1}{4}\sum_{k=0}^{15} e^{{2\pi ik}\frac{1}{16}} + \frac{1}{4}\sum_{k=0}^{15} e^{{2\pi ik}\frac{15}{16}})\\ &={\small\frac{1}{4\sqrt{2}}}\sum_{k=0}^{15}(e^{{2\pi ik}\frac{1}{16}}+e^{-{2\pi ik}\frac{1}{16}}) \end{align*} \]

Using the identity \(\cos{\phi}=\frac{e^{i\phi}+e^{-i\phi}}{2}\), this simplifies to:

\[QFT(\ket{\psi})={\small\frac{1}{2\sqrt{2}}}\sum_{k=0}^{15}\cos(\frac{2\pi k}{16}) \]

Computational Complexity

The time complexity of the basic DFT algorithm is \(\mathcal{O}(N^2)\). However, it is usually implemented by the Fast Fourier Transform (FFT) algorithm which is \(\mathcal{O}(N\log{N})\). The QFT does even better than this.

From the quantum circuit of the QFT shown earlier, it is apparent that the number of gates needed for an n-qubit QFT is:

\[(1+2+3+\dots+n) +\left\lfloor\frac{n}{2}\right\rfloor=\frac{n(n+1)}{2} + \left\lfloor\frac{n}{2}\right\rfloor \]

The \( \left\lfloor\frac{n}{2}\right\rfloor\) term is for the swap gates.

If we assume that the gates all have the same execution time, the time complexity is:

\[\mathcal{O}(n^2) = \mathcal{O}(\log^2 N),\quad\text{where }N=2^n \]

This is exponentially faster than even the FFT. However, it assumes that we can efficiently implement a CP gate where the 2 qubits are non-adjacent. In practice, a quantum computer can normally only perform such operations on physically-adjacent qubits. This may lead to some overhead in performing 'swap' operations to move the qubits around.

Inverse QFT

The definitions of the QFT and inverse QFT are almost identical except that the inverse has a negative sign on the phase term in the exponent, so that the phase rotations are in the opposite direction.

\[QFT^{-1}: \ket{x}\mapsto{\small\frac{1}{\sqrt{N}}}\sum_{k=0}^{N-1}e^{\large-\frac{2\pi i\ xk}{N}}\ket{k},\\ \quad\text{where }N=2^n \]

We can also understand this from a circuit perspective. Quantum circuits (excluding collapse measurements) are reversible as they are unitary. To run a circuit in reverse, we reverse the order of the sequence of gates and replace each gate by its conjugate transpose:

\[\qquad (U_1 U_2\dots U_{n-1})^\dagger = U^\dagger_{n-1}\dots U^\dagger_2 U^\dagger_1 \]

In the QFT circuit above, the Hadamard and swap gates are Hermitian (i.e. equal to their own conjugates transposes). The conjugate transpose of the phase gate is given by:

\[\qquad P^\dagger(\phi) = P(-\phi) \]

Consequently, the inverse 4-qubit QFT can be constructed as follows:

def iqft(qc, n: int|None = None, start: int = 0):
    """ N-qubit inverse QFT starting at qubit index 'start'."""
    if not n:
        n = qc.n_qubits
    for i in range(n // 2 - 1, -1, -1):  # Reverse order of qubits
        qc.swap(start + i, start + n - i - 1)
    for i in range(n - 1, -1, -1):
        j = i + start
        for k in range(n - i - 1, 0, -1):
            qc.cp(-pi / 2 ** k, f'-{U_PI}/{2 ** k}', j + k, j)
        qc.h(j)

We can use this to create a 4-qubit inverse QFT as follows:

qc = QCircuit(4)
iqft(qc)
qc.draw()

Testing the Inverse QFT

We can check the inverse QFT by taking the forward QFT of a random state, followed by the inverse QFT and checking that we get the state that we started with:

qc = QCircuit(4, init='random')
initial_state = qc.state_vector
qft(qc)
qc.barrier()
iqft(qc)
qc.draw()
print('Result:', np.allclose(qc.state_vector, initial_state))

Result: True

This should print 'True', indicating that the inverse QFT has completely undone the effect of the forward QFT.

Observe how each step of the inverse QFT undoes the corresponding step of the forward QFT, working outwards from the centre, until we are just left with the original random state.

Comparing DFT and QFT

It was mentioned above that the QFT gives the same result as the inverse DFT applied to the quantum state vector. The following code creates a random state and generates both the QFT and FFT (DFT), then compares them.

qc = QCircuit(4, init='random')
qc.x(2)
state = np.array(qc.state_vector)  # Save copy of state

# Using QFT
qft(qc, 4)
qft_result = qc.state_vector

# Using DFT
dft_result = np.fft.ifft(state, norm='ortho')  # Numpy inverse FFT

# Compare the results
print(np.isclose(qft_result, dft_result).all())

True

This should print 'True', indicating that the two results are the same.