Transform Algorithms

Quantum Fourier Transform

The quantum analog of the discrete Fourier transform

The Quantum Fourier Transform (QFT) is the quantum analogue of the classical discrete Fourier transform (DFT), and it serves as the backbone of many of the most important quantum algorithms, including Shor's factoring algorithm and quantum phase estimation. While the classical DFT requires O(N log N) operations using the Fast Fourier Transform, the QFT achieves an exponential speedup, requiring only O((log N)^2) quantum gates. The QFT maps quantum states from the computational basis to the Fourier basis by applying a carefully structured sequence of Hadamard gates and controlled phase rotations.

Mathematical Foundation

The classical discrete Fourier transform acts on a vector of N complex numbers (x_0, ..., x_{N-1}) and produces another vector (y_0, ..., y_{N-1}) where each component is y_k = (1/sqrt(N)) * sum_{j=0}^{N-1} x_j * e^{2*pi*i*j*k/N}. The quantum Fourier transform performs an analogous operation on the amplitudes of a quantum state. Given a state |j⟩ in the computational basis, the QFT transforms it into a superposition of all basis states with phases determined by the index j.

Formally, the QFT acts on an n-qubit register (where N = 2^n) as QFT|j⟩ = (1/sqrt(N)) * sum_{k=0}^{N-1} e^{2*pi*i*j*k/N} |k⟩. Because the transform is linear and unitary, it can be applied to superposition states as well. The inverse QFT, which is essential for algorithms like phase estimation, simply applies the conjugate transpose of this operation. The exponential speedup arises because the QFT operates directly on the 2^n amplitudes encoded in n qubits, processing them in parallel through quantum interference.

\text{QFT}|j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i jk/N} |k\rangle

QFT definition

\text{QFT}|x\rangle = \frac{1}{\sqrt{2^n}} \bigotimes_{k=1}^{n} \left(|0\rangle + e^{2\pi i x / 2^k} |1\rangle\right)

Product formula

R_k = \begin{pmatrix} 1 & 0 \\ 0 & e^{2\pi i / 2^k} \end{pmatrix}

Rotation gate

•Unitarity: The QFT is a unitary transformation, meaning it preserves the norm of quantum states and is perfectly reversible via the inverse QFT.
•Product Representation: The QFT can be decomposed into a tensor product of single-qubit states, each involving conditional rotations that encode bits of the input index.
•Exponential Speedup: For N = 2^n amplitudes, the QFT uses O(n^2) gates compared to O(N log N) classical operations — an exponential improvement in gate complexity.
•Approximate QFT: By dropping small-angle rotations, the QFT can be approximated with O(n log n) gates, which is useful for near-term devices with limited coherence.

Circuit Implementation

The QFT circuit is built recursively from Hadamard gates and controlled rotation gates. For the first qubit, a Hadamard gate creates the state (|0⟩ + |1⟩)/sqrt(2). Then controlled-R_2, controlled-R_3, up to controlled-R_n are applied from each subsequent qubit to the first, encoding progressively finer phase information. This process repeats for each qubit, with the number of required controlled rotations decreasing by one at each step.

After applying all the Hadamard and rotation gates, the qubits are in the correct Fourier state but in reverse order — the most significant bit of the frequency is stored on the last qubit. Therefore, a sequence of SWAP gates is typically applied to reverse the qubit order. The total gate count is n(n+1)/2 Hadamard and rotation gates plus roughly n/2 SWAP gates, giving the overall O(n^2) complexity. On quantum hardware, SWAP operations are expensive, so algorithms that can tolerate reversed output order often omit them.

|j_1 j_2 \dots j_n\rangle \rightarrow \frac{|0\rangle + e^{2\pi i 0.j_n}|1\rangle}{\sqrt{2}} \otimes \text{QFT}_{n-1}|j_1 \dots j_{n-1}\rangle

Circuit step

•Layered Structure: The QFT circuit consists of n layers, where layer k applies a Hadamard to qubit k followed by controlled rotations from all higher-index qubits.
•Gate Count: Exactly n Hadamards and n(n-1)/2 controlled rotations are required for an exact n-qubit QFT.
•SWAP Reversal: The natural output order is bit-reversed; SWAP gates restore the expected ordering at the cost of additional operations.
•Circuit Depth: The depth can be reduced to O(n) on linear-nearest-neighbor architectures using specialized swap networks and approximate techniques.

Applications

The QFT is arguably the most widely used subroutine in quantum algorithm design. Its primary application is in quantum phase estimation, where the inverse QFT extracts phase information encoded in the amplitudes of a quantum state. This makes QFT indispensable for quantum chemistry simulations, where molecular ground-state energies are computed via phase estimation of unitary evolution operators.

Shor's algorithm for integer factorization uses the QFT to discover the period of a modular exponentiation function, which classical computers cannot do efficiently for large numbers. Beyond these flagship applications, the QFT appears in quantum signal processing, quantum walk algorithms, hidden subgroup problems, and quantum algorithms for lattice-based cryptography. Understanding the QFT deeply is therefore essential for any quantum algorithm designer.

•Phase Estimation: The inverse QFT converts phase-encoded amplitudes into measurable computational basis states.
•Shor's Algorithm: Period finding via QFT enables polynomial-time integer factorization, threatening RSA cryptography.
•Quantum Chemistry: Estimating eigenvalues of molecular Hamiltonians relies on QPE, which in turn depends on the QFT.
•Hidden Subgroup: The QFT over appropriate groups solves the hidden subgroup problem, generalizing period finding.

Code in Action

Runnable implementations you can copy and experiment with.

Quantum Fourier Transform with Qiskit

A 3-qubit QFT circuit using Qiskit's built-in QFT library component, applied to the initial state |001⟩.

qft_qiskit.py

from qiskit import QuantumCircuit
from qiskit.circuit.library import QFT

n = 3
qc = QuantumCircuit(n)

# Prepare initial state |001>
qc.x(0)

# Apply QFT
qc.append(QFT(num_qubits=n, inverse=False), range(n))

# Decompose to see individual gates
qc = qc.decompose()
print(qc.draw(output='text'))

Quantum Fourier Transform with PennyLane

A 3-qubit QFT using PennyLane's native QFT operation, returning measurement probabilities.

qft_pennylane.py

import pennylane as qml
import numpy as np

n = 3
dev = qml.device('default.qubit', wires=n)

@qml.qnode(dev)
def qft_circuit():
    # Prepare |001>
    qml.PauliX(wires=0)
    # Apply QFT
    qml.QFT(wires=range(n))
    return qml.probs(wires=range(n))

print(qft_circuit())

Explore next

Quantum Phase Estimation

Explore next

Quantum Counting

from qiskit import QuantumCircuit from qiskit.circuit.library import QFT n = 3 qc = QuantumCircuit(n) # Prepare initial state |001> qc.x(0) # Apply QFT qc.append(QFT(num_qubits=n, inverse=False), range(n)) # Decompose to see individual gates qc = qc.decompose() print(qc.draw(output='text'))

import pennylane as qml import numpy as np n = 3 dev = qml.device('default.qubit', wires=n) @qml.qnode(dev) def qft_circuit(): # Prepare |001> qml.PauliX(wires=0) # Apply QFT qml.QFT(wires=range(n)) return qml.probs(wires=range(n)) print(qft_circuit())