QC — Quantum Fourier Transform

Image for post
Image for post
Photo by Suzanne D. Williams

Quantum Fourier Transform (QFT) is a critical part of Shor’s Algorithm and many other quantum algorithms. Its classical cousin is the Fast Fourier Transform. But there are some significant differences between them. In this article, we will take a look at QFT. But if you miss the first part of the Shor’s algorithm series, here is the link for your reference.

Fast Fourier Transform FFT

FFT Properties

For engineerings and mathematician, FFT is no stranger. We use FFT to transform a signal in the time domain f(t) to the frequency domain ℱ(ω), or vice versa. One possible application is noise removal. We convert a signal to the frequency domain and remove the high-frequency noise. Then we convert the signal back to the time domain. In quantum computing, it is used for different purposes because of the limitation in measuring qubits.

If we have a sinusoidal wave with a 1Hz frequency, the corresponding frequency domain is a delta function with value equals 1.

Image for post
Image for post

FFT is symmetrical. If we have a delta function in the time domain, the FFT function becomes a sinusoidal function.

Image for post
Image for post

If it is a series of delta functions, the transformed function is a series of delta functions also.

If a function has a period r in the time domain, the transformed function has a period of 1/r in the frequency domain.

Image for post
Image for post

FFT Definition

The Fourier Transformation is mathematically defined as:

Image for post
Image for post

So it becomes natural that we can compute the Fourier Transformation with some phase shifting gates in quantum computing.

Image for post
Image for post

Quantum Fourier Transform (QFT)

The quantum Fourier transform is defined as:

Image for post
Image for post

As shown before, a delta function should be transformed to a sinusoidal function.

Image for post
Image for post

i.e., |10⟩ will transform into the superposition below:

Image for post
Image for post

As we know, Fourier Transform is reversible. Quantum Fourier Transform (QFT) is reversible also. To prove that QFT is implementable, we need to prove the transformation is unitary. i.e. the Fourier transform F fulfills the following condition:

Image for post
Image for post

Given F is defined as:

Image for post
Image for post

We can prove below that the operation is unitary. Multiple it with its conjugate transpose equals I.

Image for post
Image for post
Modified from source

Let’s reformulate the QFT as a linear operator:

Image for post
Image for post
Source

where

Image for post
Image for post

All the power polynomial of ω lie on the unit circle below:

Image for post
Image for post
Source

For N=4,

Image for post
Image for post

For example, to transform the vector:

Image for post
Image for post

We simply perform

Image for post
Image for post

Let ’s repeat the calculation with different inputs, and here are the results.

Image for post
Image for post

In Fourier Transform, we develop a faster version called Fast Fourier Transform to compute the transformation iteratively. Now, we are going to do the same thing on the quantum version.

First, we will introduce some notation first.

Image for post
Image for post

For j=2, we can write it in a binary form 10 with j1=1 and j2=0.

Image for post
Image for post

The binary form 0.10 (0. j1 j2) equals to 0.5 in decimal.

Image for post
Image for post

It can be proven here that we can perform the QFT iteratively as:

Image for post
Image for post

A controlled-R quantum gate applies a relative phase change to |1>. The matrix form of this operator is:

Image for post
Image for post

So the QFT can be implemented with a series of the controlled-R gate as below:

Image for post
Image for post

Consider multiple R2 with j2.

Image for post
Image for post

Therefore, the result for qubit j1 before the switching at the end is.

Image for post
Image for post

Let’s take out the annotation for better clarity.

Image for post
Image for post
Source

Here is an example of the circuit:

Image for post
Image for post
Quantum Fourier Transform (5-qubits) Modified from source

Difference between QFT and FFT

The general formula for QFT is:

Image for post
Image for post

In quantum computing, loading the coefficient (αj) for the computation bases is not very simple. Also, there is no effective way to retrieve the coefficient (αk) of the computation bases after the transformation. The measurement returns the computation basis, not the coefficient!

Image for post
Image for post

But don’t be disappointed. As a standalone algorithm, it may not be very powerful. Its potential will be realized later when combining with other algorithms. For example, it can measure the period of a function that is needed to crack the RSA algorithm.

Next

Next, we need to understand an abstract concept called phase estimation before we can put everything together to solve the prime factorization.

Written by

Deep Learning

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store