yohandi

A recent graduate with a strong interest in algorithms and data structures.

[Tutorial] Discrete Fourier Transform in Quantum Computing

March 09, 2024 by Yohandi

algorithm polynomial quantum-computing tutorial

Discrete Fourier Transform (DFT) is a specific kind of Fourier Transform usually used in signal processing and data analysis, though it is also used to compute polynomial multiplication in computer science. DFT is applied to discrete, sampled data, rather than a continuous signal. The discrete part of its name reflects that the algorithm is designed for sequences of values at discrete intervals.

Before proceeding to read this post, the followings are few basic variables and operations in quantum computing that will be used for this post:

A qubit is represented by vectors.
- Basic states cover $∣0 ⟩ = (10)$ and $∣1 ⟩ = (01)$ , which classically are considered as 0 and 1, respectively.
- Superposition state, $∣ ψ ⟩$ , represents a general quantum state, which is a superposition of the basis states. In a linear combination, $∣ ψ ⟩ = α ∣0 ⟩ + β ∣1 ⟩$ , where $α$ and $β$ are complex numbers that satisfy $∣ α ∣^{2} + ∣ β ∣^{2} = 1$ .
The quantum bit operations that are used include Pauli-X gate, Hadamard gate, and Controlled phase gate.
- Pauli-X gate, which is represented as $X = (0110)$ , corresponds to a NOT gate in a classical bit inversion. The gate operates as follows: $X ∣0 ⟩ = ∣1 ⟩$ and $X ∣1 ⟩ = ∣0 ⟩$ .
- Hadamard gate, which is represented as $H = \frac{1}{2} (11 1 - 1)$ . It creates superposition states from the basic states: $H ∣0 ⟩ = \frac{∣0 ⟩ + ∣1 ⟩}{2}$ and $H ∣1 ⟩ = \frac{∣0 ⟩ - ∣1 ⟩}{2}$ . If we apply hadamard to $∣ ψ ⟩$ , we get $H ∣ ψ ⟩ = \frac{α + β}{2} ∣0 ⟩ + \frac{α - β}{2} ∣1 ⟩$ .
- Controlled phase gate, which controls the phase rotation, is represented as $C R_{z} (θ) = 100001000010 000 e^{i θ}$ . The first three diagonal elements are 1, implying that when the control qubit is in the $∣0 ⟩$ state, or $∣1 ⟩$ state but targeting $∣0 ⟩$ , the gate does not change the state of the system. The last element implies a phase shift of $θ$ when the control qubit is in the $∣1 ⟩$ state.

Discrete Fourier Transform

Discrete Fourier Transform transforms a sequence of complex numbers, say

KaTeX can only parse string typed expression

a_{0}, a_{1}, \dots, a_{N - 1}

, into another sequence of complex numbers, say

A_{0}, A_{1}, \dots, A_{N - 1}

, where

A

is defined as:

A = A_{0} A_{1} A_{2} ⋮ A_{N - 1} = ω^{0} ω^{0} ω^{0} ⋮ ω^{0} ω^{0} ω^{1} ω^{2} ⋮ ω^{(N - 1)} ω^{0} ω^{2} ω^{4} ⋮ ω^{2 (N - 1)} \dots \dots \dots ⋱ \dots ω^{0} ω^{(N - 1)} ω^{2 (N - 1)} ⋮ ω^{(N - 1) (N - 1)} a_{0} a_{1} a_{2} ⋮ a_{N - 1}

, where

KaTeX can only parse string typed expression

ω = e^{- \frac{2 π}{N} i}

. This implies that the

j

-th element of

A

is:

A_{j} = k = 0 \sum N - 1 e^{- \frac{2 π}{N} i (j \cdot k)} a_{k}, \forall j \in {0, 1, \dots, N - 1}

By computing the matrix multiplication,

KaTeX can only parse string typed expression

A

can be simply obtained through an

O (N^{2})

näive implementation.

Fast Fourier Transform

Currently, Fast Fourier Transform stands as the quickest classical algorithm that converts the same sequence of

KaTeX can only parse string typed expression

a

into

A

O (N lo g N)

performance. Let

P (x)

be a polynomial function, the algorithm exploits the fact that:

$P (x) = P_{1} (x^{2}) + x P_{2} (x^{2})$
$P (- x) = P_{1} (x^{2}) - x P_{2} (x^{2})$

, where

KaTeX can only parse string typed expression

P_{1} (x)

is the polynomial containing all the terms of

P (x)

with even powers, and

P_{2} (x)

contains all the terms of

P (x)

with odd powers. As it is possible to reconstruct

P (x)

given

x_{0}, x_{1}, \dots, x_{N - 1}

such that

x_{i} \neq = x_{j}, \forall i \neq = j

and

i, j \in {0, 1, \dots, N - 1}

, the objective of the algorithm is simply to find

P (x_{0}), P (x_{1}), \dots, P (x_{N - 1})

for any configuration of

x

. Setting up

x

{1, ω, ω^{2}, \dots, ω^{(N - 1)}}

allows divide-and-conquer approach to be used (due to symmetry) for efficient evaluation of

P (x)

P_{1} (x^{2})

and

P_{2} (x^{2})

. This method yields the FFT's hallmark performance:

T (N) = 2 T (\frac{N}{2}) + O (N) = O (N lo g N) (by Master’s Theorem)

is obtained.

Discrete Fourier Transform in Quantum Computing

With the same objective, the Quantum Fourier Transform (QFT) converts

KaTeX can only parse string typed expression

∣ a ⟩ = \sum_{j = 0}^{n - 1} a_{j} ∣ j ⟩

into

∣ A ⟩ = \sum_{j = 0}^{n - 1} A_{j} ∣ j ⟩

, where:

A_{j} = \frac{1}{n} k = 0 \sum n - 1 e^{\frac{2 π}{n} i (j \cdot k)} a_{k}, \forall j = {0, 1, \dots, n - 1}

Notice that the

KaTeX can only parse string typed expression

∣ A ⟩

is expressed and rewrittable as:

∣ A ⟩ = \frac{1}{n} k = 0 \sum n - 1 e^{\frac{2 π}{n} ik \sum_{j = 0}^{n - 1} 2^{j} a_{j}} ∣ k ⟩ = \frac{1}{n} (∣0 ⟩ + e^{\frac{2 πi}{n} a} ∣1 ⟩ + e^{\frac{4 πi}{n} a} ∣2 ⟩ + \dots + e^{\frac{2 ( n - 1 ) πi}{n} a} ∣ (n - 1)⟩) = \frac{1}{n} k = 0 ⨂ n - 1 (∣0 ⟩ + e^{\frac{2 π}{n} i (a 2^{n - k - 1})} ∣1 ⟩) = \frac{1}{n} k = 0 ⨂ n - 1 (∣0 ⟩ + e^{2 πi [0. a_{n - k - 1} \dots a_{n - 1}]} ∣1 ⟩)

, where

KaTeX can only parse string typed expression

[0. a_{n - k - 1} \dots a_{n - 1}]

is a binary fraction representation. This expression showcases the algorithm's potential to encode phase information across a superposition of all computational basis states.

The action of the Hadamard gate produces superpositions necessity for the algorithm's operation:

H ∣ a_{j} ⟩ = \frac{1}{2} (∣0 ⟩ + e^{2 πi a_{j}} ∣1 ⟩),

. Each step in the algorithm, reliant on superposition and entanglement, achieves the quantum analogue of the classical Discrete Fourier Transform efficiently.

from qiskit import QuantumCircuit, Aer, execute, transpile
from qiskit.visualization import plot_histogram

import math
import matplotlib.pyplot as plt
import numpy as np

def dft(N, arr):
    n = math.ceil(math.log2(N))

    qc = QuantumCircuit(n, n)
    
    norm_arr = np.array(arr) / np.linalg.norm(arr)
    for i, amp in enumerate(norm_arr):
        if amp > 0:
            qc.x(i % n)

    def apply_qft(circuit, n):
        for j in range(n):
            circuit.h(j)
            
            for k in range(j + 1, n):
                circuit.cp(np.pi / 2 ** (k - j), j, k)

        for k in range(n // 2):
            circuit.swap(j, n - k - 1)

    apply_qft(qc, n)

    for i in range(n):
        qc.measure(i, i)

    simulator = Aer.get_backend('aer_simulator')
    counts = simulator.run(transpile(qc, simulator)).result().get_counts()

    print("Quantum Circuit:")
    print(qc.draw())

    print("Measurement Results:")
    plot_histogram(counts)
    plt.show()

The apply_qft function runs in

KaTeX can only parse string typed expression

O (n^{2})

, where

n

is the number of qubits. To represent an array of

N

elements in a quantum computer,

lo g_{2} (N)

number of qubits are needed. As a result, the overall performance of apply_qft is

O (lo g^{2} (N))

. This highlights a significant reduction in computational resources compared to classical methods. Currently, the fastest known quantum algorithm for Discrete Fourier Transform achieves about

O (lo g (N) lo g (lo g (N)))

performance.

Importance of Discrete Fourier Transform in Quantum Computing

The QFT algorithm exemplifies the leap between classical computing to quantum computing. One of the most notable applications of QFT include Shor's algorithm, which is an algorithm that finds the prime factors of an integer. Compared to the most efficient classical factoring algorithm that runs in

KaTeX can only parse string typed expression

O (e^{1.9 l o g^{1/3} (N) l o g^{2/3} (l o g (N))})

, Shor's algorithm runs in

O (lo g^{2} (N) lo g (lo g (N)) lo g (lo g (lo g (N))))

. That is significantly faster!

Beyond the acceleration, QFT highlights the unique capabilities of quantum systems to encode and manipulate information in ways that classical systems cannot replicate. This opens up avenues for complex system optimizations!

References

Nielsen, M., "Quantum Computation and Quantum Information," Cambridge University Press. https://www.worldcat.org/oclc/174527496.

← Natural Parallelism: Advancing Machine Learning with OpenACC Multiple Dispatch Micro-Kernels for IREE →