Quantum Fourier Transform

Definition

The Quantum Fourier Transform on qubits transforms:

In matrix form, is a unitary matrix with entries:

QFT Circuit

The QFT circuit for qubits uses gates:

Apply Hadamard to qubit
Apply controlled- gates from qubits
Swap qubits to reverse the order

The controlled- gate applies phase :

QFT vs FFT

Aspect	FFT	QFT
Input	N classical numbers	n qubits (N = 2^n states)
Output	N classical numbers	n qubits
Complexity	O(Nlog N) gates	O(n^2) gates
Parallelism	Sequential	Exponential

The QFT is exponentially faster than the FFT, but the input/output are in quantum states.

Applications

QFT is a subroutine for:

Shor's algorithm: period finding
Quantum phase estimation: eigenvalue extraction
Quantum signal processing: filtering and analysis
Hidden subgroup problems: finding hidden structure

Approximate QFT

For some applications, an approximate QFT with truncated controlled- gates provides near-optimal performance with fewer gates:

Remove gates with small phase angles
Approximation error: for removing
Useful for algorithms where exact QFT is not required

Python: QFT Implementation

import numpy as np

def qft_matrix(n):
    # Compute the QFT matrix for n qubits.
    N = 2**n
    Q = np.zeros((N, N), dtype=complex)
    for j in range(N):
        for k in range(N):
            Q[k, j] = np.exp(2j * np.pi * j * k / N) / np.sqrt(N)
    return Q

def qft_circuit_demo(n=3):
    Q = qft_matrix(n)
    print(f"QFT matrix ({2**n}x{2**n}):")
    print(np.round(Q, 3))
    print(f"Is unitary: {np.allclose(Q @ Q.conj().T, np.eye(2**n))}")

qft_circuit_demo()

QFT Implementation Details

The QFT circuit for qubits:

Circuit elements:

Hadamard gates
controlled- gates
SWAP gates (for bit ordering)

Gate count: gates total. Depth: with parallel controlled rotations.

QFT vs FFT Comparison

Aspect	FFT	QFT
Input	Classical vector	Quantum state
Output	Classical vector	Quantum state
Complexity	O(Nlog N)	O(n^2) where N=2^n
Parallelism	Sequential	Inherent
Data loading	O(N)	Exponential (challenge)

The QFT is exponentially faster but operates on quantum states, not classical data.

Summary

This topic covers the fundamental concepts and applications in quantum computing. Understanding these concepts is essential for advancing in the field and applying quantum techniques to real-world problems. The mathematical framework provides the foundation for analyzing quantum algorithms and hardware implementations.

Key takeaways include the importance of quantum coherence, the role of entanglement as a resource, and the tradeoffs between different quantum computing architectures. As the field progresses from NISQ to fault-tolerant devices, these foundational concepts will continue to underpin new developments and applications.

Further study should include hands-on implementation using quantum programming frameworks, analysis of recent research papers, and exploration of the connections between quantum computing and other fields such as machine learning, optimization, and simulation.

QFT Approximation

For applications where exact QFT is not required, approximate QFT with truncated controlled rotations provides near-optimal performance:

Remove controlled- gates for
Approximation error:
Gate count: instead of

The approximate QFT is useful for algorithms where the QFT is a subroutine and exact phase estimation is not required.