Quantum Fourier Transform

A journey from Fourier Series to QFT

13 min readJul 25, 2021

In this article we discuss about the Real Fourier Series(periodic function using sine and cosine), Complex Fourier Series(periodic function using exponential), Continuous Fourier Transform, Discrete Fourier Transform, Fast Fourier Transform and finally Quantum Fourier Transform. At the end we design the Unitary gates with Quantum Fourier Transform using Qiskit and Cirq Modules.

Fourier Series:

Fourier Series apply to functions that are either periodic or are only defined on a bounded interval.

A function f whose domain is all the real numbers, R, is said to be periodic if there is a unique smallest positive real number T, such that

The number, T, is called the period of f (here f is function).

A function which is defined only over a bounded interval of the real numbers is said to have bounded domain, example as shown in below fig.

The Real Fourier Series:

The real Fourier series of a periodic function with period 2π is the sum

The Fourier coefficients (or their graph) is called the spectrum of f. It is a possibly infinite list (or graph) of the weights of the various frequencies contained in f. Viewed in this way, the coefficients, themselves, represent a new function, F(n).

The Fourier mechanism is a kind of operator, FS, applied to f(x) to get a new function, F(n), which is also called the spectrum.

Fourier “operator” takes one function, f(x), domain R, and produces another function, its spectrum F(n), domain Z (greater than or equal to 0).

The way to produce the Fourier coefficients, of a function, f, is through the following easy formulas

They work for functions which have period 2π or bounded domain [−π, π).

The Complex Fourier series:

We continue to study real functions of a real variable, f(x), which are either periodic or have a bounded domain. We still want to express them as a weighted sum of special “pure” frequency functions.

To convert from sines and cosines to complex numbers, one formula should come to mind:

Euler’s formula,

Solving this for cosine and sine, we find:

we can apply these equivalences to the real Fourier expression for f to get an equivalent expression as shown below

The Complex Fourier series of a periodic function with period 2π is the sum

The complex Fourier series is a cleaner sum than the real Fourier expansion which uses sinusoids, and it allows us to deal with all the coefficients at once when doing computations. The coefficients, are generally complex. However, even when they are all complex, the sum is still real.

Well, the complex Fourier coefficients independent of real Fourier coefficients can be achieved. The formula for computing the complex spectrum is as shown below,

the complex Fourier expansion of our periodic f and its coefficients

Ordinary Frequency:

We know what the period, T, of a periodic f(x) means. The frequency, f, of a periodic f(x) is just the reciprocal of the period, f = 1/T

Angular Frequency:

When we ask the question “How many periods fit an interval of length l?” there’s nothing forcing us to choose l = 1. That’s a common choice in physics only because it produces answers per second, per unit or per radian of some cyclic phenomenon. If, instead, we wanted to express things per cycle or per revolution we would choose l = 2π.

Angular frequency, usually denoted by the letter ω, is therefore defined to be ω = 2π/T

The relationship between angular frequency and ordinary frequency from the above is ω = 2πf

The relationship between period and angular frequency ω · T = 2π

Continuous Fourier Transform:

Fourier series assumed and required that a function, f, was either periodic or a bounded domain.

A natural question to ask is whether we can find expansions for non-periodic functions defined over all R?

The answer to this question is the Fourier Transform (FT ).

In order to express non-periodic functions as a weighted sum of frequencies is that the Fourier basis will no longer be a discrete set of functions and neither their corresponding weights.

The above formulas have to be modified in the following ways:

The integer n must become a real number s.
The sum will have to turn into an integral.
The limits of integration have to be changed from ±π to ±∞.
we make the formulas symmetric by replacing the normalization constant, 1/(2π) by √(1/(2π)).

These considerations suggest that if we want to express a non-periodic but function f as a “sum” of frequencies, we would do so using

Since the sum is really an integral, the weights become a function over R, c(s), where each real s represents a frequency, and c(s) is “how much” of that frequency the function f requires.

This weighting function, c(s), is computable from f(x) using the companion formula,

It is this above function of s that we say the Fourier Transform, or FT , of the function f(x), and it is usually denoted by the capital letter of the function we are transforming, in this case F(s),

We also consider the inverse of the Fourier transform, which allows us to recover f from F

shift-property:

One aspect of the FT we will find useful is its shift-property. For real g(the only kind of number that makes sense when f happens to be a function of R).

where in the last version we do need to state that h is real, since FT generally is a function of C (complex).

Discrete Fourier Transform:

Sometimes Continuous Domains Don’t Work, instead of functions, f : R → C, we turn to functions which are only defined on the finite set of integers Z = {0, 1, 2, . . . , N − 1}.

Why Continuous domains don’t need?

Computers, having a finite capacity, can’t store data for continuous functions. Instead, such functions must be sampled at discrete points, producing arrays of numbers that only approximate the original function. We are bound to process these arrays, not the original functions.
Most of the data we analyze don’t have a function or formula behind them. They originate as discrete arrays of numbers, making a function of a continuous variable inapplicable.

To define the DFT , we start with the FT and make the following adjustments.

The integrals will become sums from 0 to N − 1.
The factor of 1/ √ 2π will be replaced by a normalizing factor 1/ √ N. In quantum computing the choice is driven by our need for all vectors to live on the projective sphere in Hilbert space and therefore be normalized.
We will use Nth roots of unity, in place of the general exponential, as shown below.

An Nth order DFT is a function of an N-component vector f = (fk) that produces a new N-component vector F = (Fj ) described by the formula giving the output vector’s N coordinates

Inverse DFT:

shift-property:

the shift property holds in the discrete case in the form of

We can see, it’s the same idea: a spatial or time translation in one domain corresponds to a phase shift in the other domain.

Fast Fourier Transform:

Recursive Equation:

Splitting f into even and odd parts: Given a vector f of dimension N, divide it into two vectors of size N/2 as shown below

from the above conditions we can rewrite as following,

ω is Nth root of unity, so ω^2 is an (N/2)th root of unity. If we rewrite the final sum using ω’ for ω^2 , N’ for N/2 and labeling the ω outside the odd sum as an Nth root as shown below

reducing further for simplicity as shown below

Bit Reversal Mapping for 3-bit Integers

We have to compute N output coordinates, and the above tells us that we can get each one using, what appears to be log N operations, so it seems like we have an O(N log N) algorithm.

Take away:

It improves the DFT ’s O(N^2 ) to O(N log N), a speed up that changes the computational time of some large arrays from over an hour to a fraction of a second.
The recursive nature of the solution sets the stage for studying the quantum Fourier transform (QFT ) circuit.

Quantum Fourier Transform:

consider a basis state |ψ⟩^n and its preferred basis amplitudes.

We can really feel the Fourier transform concept when we view the states as complex vectors, which we subject the standard DFT

The yth coordinate of the output QFT is produced using

It’s more common in quantum computing to take the Computational Basis State route, and in that case the definition of the QFT would be

Shift Property:

The shift property of the DFT,

when plugged into the definition of QFT results in a quantum translation invariance

We lose the minus exponent of ω because the QFT uses a positive exponent in its forward direction.

A Comparison between QFT and H:

It is interesting to see some similarities and differences between the Hadamard operator and the QFT.

How do these two operators compare on the Computational Basis State?

nth Order Hadamard:

where x ⊙ y is the mod-2 dot product based on the individual binary digits in the base-2 representation of x and y.

N-Dimensional QFT:

The definition of the Nth order QFT is

The exponent of the root-of-unity is an ordinary integer product for QFT

QFT Equals H for N = 2:

when N = 2 (n = 1) both operators are the same. Look

The QFT Circuit from the Math:

The Computational Basis State kets in an N-dimensional Hilbert space are officially tensor products of the individual Computational Basis States of the 2-dimensional qubit spaces,

We index in decreasing order because we want the right-most bit to correspond to the least significant bit of the binary number.

the encoded decimal integer x,

its binary representation,

general notation,

After applying the Recursion Relation using Fast Fourier Transform similar to the DFT as shown above in the case of Discrete Fourier Transform.

In the case of n = 3(N = 8), the factored QFT is

by applying the above conditions

The First (Most-Significant) Output Factor:

Here, ω is an 8th root of unity (N = 8 or n = 3), so the coefficient of |1⟩ in the numerator can be derived from above x -general notation as shown below

But substitution gives as,

The output state’s most-significant factor, is derived from the input state’s least significant ket. Make a note that this will necessitate a reversal of the kets once we have the output of the circuit.