Study goals of this lecture

The aim of this lecture is step-by-step understand one of the most powerful quantum algorithms that has been discovered so far, namely the Quantum Fourier Transform.

Topics covered in this section are

  • Quantum Parallelism
  • Classical Fourier transformation
  • Quantum Fourier Transform

Literature: Rieffel and Polak (2011)


Quantum circuits are generated using Quirk by Craig Gidney, licensed under Apache-2.0 License.

1 Motivation

It’s re-assuring that classical algorithms can be quantumized. So far, however, we don’t have any gain through using a quantum computer, as there is nothing we can do now that we couldn’t do before!

Very specifically, we didn’t explot yet:

  • superposition of qubits

  • entanglement of qubits

2 Quantum Parallelism

Walsh-Hadamard Transformation

The Walsh-Hadamard Transformation W is a generalization of the Hadamard gate and brings \(n\) qubits into superposition:

\[\begin{align} &W | 0 \rangle = \left(H \otimes H \otimes ... \otimes H \right) | 00...0 \rangle\\ & \qquad = \frac{1}{\sqrt{2^n}} \left((| 0 \rangle + | 1 \rangle) \otimes (| 0 \rangle + | 1 \rangle) \otimes ... \otimes (| 0 \rangle + | 1 \rangle) \right) \\ & \qquad = \frac{1}{\sqrt{2^n}} \left(| 00...00 \rangle +| 00...01 \rangle + ... + | 11...11 \rangle \right) \\ & \qquad =\frac{1}{\sqrt{2^n}} \sum_{j=1}^{2^n - 1} | j \rangle \end{align} \]

Quantum parallelism

Any tranformation of the form

\[U_f = | x,y \rangle \mapsto | x, y \oplus f(x) \rangle\]

is linear and therefore acts on a superposition \(\sum a_j | j \rangle\) of input values as follows

\[U_f = \sum a_j | x,0 \rangle \mapsto \sum a_j | x, f(x) \rangle\]

The true benefit of quantum computers become obvious, when applying \(U_f\) to the superposition of values from \(0\) to \(2^{n}-1\), which reads

\[U_f = \sum a_j | x,0 \rangle \mapsto \sum a_j | x, f(x) \rangle\]

What are (classes of) algorithms that exploit these possibilities?

3 Classical Fourier Transform

Background of the Fourier Analysis

A Fourier analysis converts a signal from temporal or spatial domain into frequncy domain and back.

  • The Fourier analysis dates back to the early 18 hundreds, and is named after Jean-Baptiste Fourier.

Fourier developed the Fourier analysis for studying heat transfer and applications involving vibrations.

  • localization in space and/or time leads to wide-spread distribution in frequency domain
  • localization in frequency domain leads to wide-spread distribution in space and time.

This is also referred to as the uncertainty principle!

Today, the Fourier transform and its fast implementation FFT is crucial to many computational tasks!

Fourier transform

The Fourier transform of a function \(f(x)\) in one dimension (space or time) is given by

\[ \widehat{f} (k) = \int^\infty_{-\infty} f(x) e^{-i 2 \pi k x} dx \]

The inverse Fourier transform is given by

\[ f(x) = \frac{1}{N} \int^\infty_{-\infty} \widehat{f}(x) e^{i 2 \pi k x} dk \]

When Fourier invented this, he had the solution of the heat equation in mind …

Solving the heat equation with Fourier transformation

The heat equation is given by the following partial differential equation

\[ \partial_t u(x,t) = \alpha \partial_{xx} u(x,t) \]

in which \(\alpha\) is a material parameter.

Fourier transforming the time derivative yields

\[ \begin{align} \widehat{\partial_t u}(k,t) = \int^\infty_{-\infty} \partial_t u(x,t) e^{-i 2 \pi k x} dx = \int^\infty_{-\infty} \partial_t \left( u(x,t) e^{-i 2 \pi k x} \right) dx = \partial_t \widehat u (k,t) \end{align} \]

Fourier transforming the spatial derivative yields

\[ \begin{align} \widehat{\partial_{xx} u}(k,t) = \int^\infty_{-\infty} \partial_{xx} u(x,t) e^{-i 2 \pi k x} dx &= (ik)^2 \int^\infty_{-\infty} u(x,t) e^{-i 2 \pi k x} dx = -k^2 \widehat u (k,t) \end{align} \]

Solving the heat equation with Fourier transformation

The heat equation is given by the following partial differetial equation

\[ \partial_t u(x,t) = \alpha \partial_{xx} u(x,t) \]

in which \(\alpha\) is a material parameter.

The Fourier transform of the complete heat equation hence reads

\[ \widehat u(k,t) = - \alpha k^2 \widehat u(k,t), \]

which by multiplication with \(e^{\alpha k^2 t}\) can be compactly written as

\[ \alpha k^2 e^{\alpha k^2 t} \widehat u (k,t) + e^{\alpha k^2 t} \partial_t \widehat u (k,t) = \partial_t \left( e^{\alpha k^2 t} \widehat u (k,t) \right) = 0 \]

Solving the heat equation with Fourier transformation

The heat equation is given by the following partial differetial equation

\[ \partial_t u(x,t) = \alpha \partial_{xx} u(x,t) \]

in which \(\alpha\) is a material parameter.

Integration then yields

\[ e^{\alpha k^2 t} \widehat u (k,t) = f(k) \quad \Rightarrow \widehat u (k,t) = e^{- \alpha k^2 t} f(k), \]

in which the integration constant is given by the Fourier transform of the IC \(f(k) = \widehat u (x,0)\)

To recover the solution, we need to transform back into spatial / temporal domain. A building block of each solution is the following

\[ S(x,t) = \frac{1}{2 \pi} \int_{-\infty}^{\infty} e^{-\alpha k^2 t} e^{i k x} dk = \frac{1}{2 \pi} \int_{-\infty}^{\infty} e^{-\alpha k^2 t + i k x} dk = \frac{1}{\sqrt{4 \pi \alpha t}} e^{-\frac{1}{4 \alpha t}x^2} \]

Solving the heat equation with Fourier transformation

The heat equation is given by the following partial differetial equation

\[ \partial_t u(x,t) = \alpha \partial_{xx} u(x,t) \]

in which \(\alpha\) is a material parameter.

The full solution requires to convolute with the initial condition

\[ u(x,t) = \frac{1}{\sqrt{4 \pi \alpha t}} \int_{-\infty}^{\infty} e^{-\frac{-(x-k)^2}{4 \alpha t}} \widehat u (x,0) dk \]

Today, the Fourier transform is found is many more applications:

  • analysis of audio spectra
  • image analysis (MRI)
  • literally any type of signal processing
  • quantum computing

Discrete Fourier transform

The discrete Fourier transform converts a finite sequence of equally-spaced, complex-valued samples of a function into the same length sequence of complex-valued samples in frequency domain (Fourier space).

The interval length in Fourier space corresponds to 1/ duration of the signal (analogous interpretation if signal is not a time series, but spatial information).

For a given signal / data set of \(N\) complex numbers

\[ \{x_0,...,x_{N-1}\} \qquad x_i \in \mathbb C \]

is the discrete Fourier is transform given by

\[ d_k = \frac{1}{N} \sum_{j=0}^{N-1} x_j e^{-i j k \tfrac{2 \pi}{N}} \qquad k \in \{0,...,N-1\} \]

Discrete Fourier transform

The discrete Fourier transform hence constitutes a linear function \(\mathcal F: \mathbb C^N \rightarrow \mathbb C^N\)

\[ \mathcal F [x_0,...,x_{N-1}] = [d_0,...,d_{N-1}], \]

Function \(\mathcal F\) can be written as a matrix-vector product:

\[ \begin{pmatrix} d_0 & ... & d_{N-1} \end{pmatrix}^T= \frac{1}{N} A^\dagger \begin{pmatrix} x_0 & ... & x_{N-1} \end{pmatrix}^T \]

with \(A^\dagger \in \mathbb C^{N \times N}\) being the conjugate complex of matrix \(A \in \mathbb C^{N \times N}\) defined as

\[ A:= \begin{pmatrix} 1 & 1 & 1 & ... & 1 \\ 1 & \omega & \omega^2 & ... & \omega^{N-1} \\ \vdots & & & ... & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & ... & \omega^{(N-1)^2} \end{pmatrix} \]

in which \(\omega := e^{i 2 \pi / N}\).

Discrete Fourier transform

The discrete Fourier transform is hence given by a linear function \(\mathcal F: \mathbb C^N \rightarrow \mathbb C^N\)

\[ \mathcal F [x_0,...,x_{N-1}] = [d_0,...,d_{N-1}], \]

Function \(\mathcal F\) can be written as a matrix-vector product

\[ \begin{pmatrix} d_0 & ... & d_{N-1} \end{pmatrix}^T= \frac{1}{N} A^\dagger \begin{pmatrix} x_0 & ... & x_{N-1} \end{pmatrix}^T \]

  • For an arbitrary matrix \(A\) this matrix vector product is of (complex) complexity \(N^2\).

  • For an arbitrary, densely populated matrix \(A\) the inversion is of complexity \(N^3\).

Discrete Fourier transform

The discrete Fourier transform is hence given by a linear function \(\mathcal F: \mathbb C^N \rightarrow \mathbb C^N\)

\[ \mathcal F [x_0,...,x_{N-1}] = [d_0,...,d_{N-1}], \]

Function \(\mathcal F\) can be written as a matrix-vector product

\[ \begin{pmatrix} d_0 & ... & d_{N-1} \end{pmatrix}^T= \frac{1}{N} A^\dagger \begin{pmatrix} x_0 & ... & x_{N-1} \end{pmatrix}^T \]

Can we exploit the structure of the discrete Fourier transform to speed up calculation?

Yes!

  • \(A\) is unitary, hence \(A A^\dagger = A^\dagger A = I\), which means that we have direct access to the inverse discrete Fourier transform (and it can be translated into quantum)
  • What about the matrix vector multiplication?

Towards Fast Fourier Transform

The fundamental idea of the Fast Fourier Transform can be understood, when interpreting the previous matrix as a Vandermonde matrix to evaluate a polynomial

\[ p(x) = \sum_{j=0}^{N-1} a_j x^j \]

as a matrix vector product \[ \begin{pmatrix} p(x_0) \\ \vdots \\ p(x_{N-1}) \end{pmatrix} = \begin{pmatrix} 1 & x_0 & x_0^2 & ... & x_0^{N-1} \\ 1 & x_1 & x_1^2 & ... & x_1^{N-1} \\ \vdots & & & ... & \vdots \\ 1 & x_N & x_N^2 & ... & x_{N-1}^{N-1} \\ \end{pmatrix} \begin{pmatrix} a_0 \\ \vdots \\ a_{N-1} \end{pmatrix} \]

Comparison with before: \(x_j\) would be the coefficients, and powers of the \(N\)-th unit root \(\omega = e^{i j 2 \pi /N}\) the evaluation points.

Towards Fast Fourier Transform

Fundamental idea:

The Fast Fourier Transform (FFT) exploits symmetries of this polynomial with respect to even and odd powers of the \(N\)-th unit root

\[ \begin{pmatrix} p(x_0) \\ \vdots \\ p(x_{N-1}) \end{pmatrix} = \begin{pmatrix} 1 & x_0 & x_0^2 & ... & x_0^{N-1} \\ 1 & x_1 & x_1^2 & ... & x_1^{N-1} \\ \vdots & & & ... & \vdots \\ 1 & x_N & x_N^2 & ... & x_{N-1}^{N-1} \\ \end{pmatrix} \begin{pmatrix} a_0 \\ \vdots \\ a_{N-1} \end{pmatrix} \]

The idea can be turned into an hierarchical approach to constructing the discrete Fourier transform in complexity \(N log_2 N\), which is more effective that previous complexity \(N^2\) for the general case.

For details on derivation and algorithmic technicalities of the FFT, we refer to the many textbooks available in the field. Also Rieffel and Polak (2011) has a subchapter on the classical Fourier transform and the FFT.

4 Quantum Fourier Transform

Idea

The quantum Fourier transform is a variant of the discrete Fourier transform, which assumes \(N=2^n\), in which \(n\) is the number of qubits that we will use.

We interpret the amplitudes of the quantum state that we can capture with \(n\) qubits as a function of \(x\). The quantum Fourier transform (QFT) then operates on a quantum state by mapping

\[ \sum_x a(x) | x \rangle \mapsto \sum_x A(x) | x \rangle \]

The resulting state \(| x \rangle\) of the \(n\)-qubit state is hence (in the standard basis) measured with probability \(|A(x)|^2\).

The quantum Fourier transform hence reads \[ QFT: \sum_{k=0}^{N-1} \omega_N^{xk} | k \rangle \]

Idea

The quantum Fourier transform is a variant of the discrete Fourier transform, which assumes \(N=2^n\), in which \(n\) is the number of qubits that we will use.

We interpret the amplitudes of the quantum state that we can capture with \(n\) qubits as a function of \(x\). The quantum Fourier transform then operates on a quantum state by sending

\[ \sum_x a(x) | x \rangle \mapsto \sum_x A(x) | x \rangle \]

The resulting state \(| x \rangle\) is hence (in standard basis) measured with probability \(|A(x)|^2\).

A crucial observation is now that the QFT can alternatively be decomposed into a tensor product: \[ QFT: \otimes_{k=1}^n \left( | 0 \rangle + \omega_N^{x 2^{n-k}} | 1 \rangle\right) \] which reduces complexity (in this case number of quantum gates) below the FFT complexity.

Quirk - QFT 3 qubits

Quantum circuit realizing a quantum fouriert transform with 3 bits.

Quirk - QFT 8 qubits

Quantum circuit realizing a quantum fouriert transform with 8 bits.

References

Rieffel, Eleanor G, and Wolfgang H Polak. 2011. Quantum Computing: A Gentle Introduction. MIT press.

Quantum Computing for Engineering - Quantum Fourier Transform