Quantum Fourier Transform

The QFT maps the computational basis to the Fourier basis and underlies phase estimation, Shor's algorithm, and more. It re-expresses the amplitude distribution of the computational basis in the Fourier basis, making periodic and phase structure easier to extract through interference.

The problem it solves

The classical discrete Fourier transform turns a length-N sequence into its frequency content; it is everywhere, but it is also expensive — O(N²) operations done directly, O(N log N) with the fast Fourier transform (FFT). The QFT is its quantum counterpart: it transforms the quantum state of N = 2ⁿ numbers encoded as amplitudes into the Fourier basis.

The point is not that the transform is somehow "fast", but how it folds global information into phases. The QFT does not hand you the transformed values one by one (no quantum measurement can do that), but it arranges periodicity and phase information into a form that later interference can exploit — which is exactly what phase estimation and Shor's algorithm rely on.

What it does — from amplitudes to phases

On a basis state |x⟩, the QFT sends it to a uniform superposition in which every basis state carries a phase proportional to x:

|x⟩ → (1/√N) Σ_y e^(2πi·xy/N) |y⟩

In other words, the input label x is "written into" the rate at which the relative phase rotates across the components of the output superposition. A slowly varying phase corresponds to a low frequency; a fast-winding phase to a high frequency. The QFT thus translates "which number is this basis state" into "how fast do these phases wind".

Why the circuit needs only O(n²) gates

The QFT circuit has an elegant recursive structure. For each qubit, apply one Hadamard — which alone performs the single-qubit Fourier transform on that qubit — followed by a ladder of controlled phase rotations that fold in contributions from the lower-order qubits at ever-finer angles. Qubit i receives a rotation of π / 2^(j−i) from qubit j.

The controlled-phase gates number n(n−1)/2; together with n Hadamards and up to ⌊n/2⌋ swaps, the exact QFT therefore uses O(n²) gates. By comparison, a classical FFT on N = 2ⁿ amplitudes needs O(N log N) = O(2ⁿ·n) operations — the QFT manipulates an exponentially large amplitude space with a polynomial number of gates in the qubit count. It is worth stressing that this does not speed up the Fourier transform of classical data (you cannot cheaply load data into amplitudes, nor read all the results out); its power appears only as a subroutine inside a larger algorithm. More precisely, the QFT acts on an already-prepared quantum state Σx ax|x⟩ and outputs a quantum state Σy ãy|y⟩; unless the surrounding algorithm only needs some global property, you cannot read out all the ãy at once by measurement — so the QFT's power is as a subroutine inside phase estimation and Shor's algorithm, not a drop-in replacement for the classical FFT.

Implementation

import qalgora, numpy as np

# Convention: r1(theta) = diag(1, exp(i*theta)), and q[0] is the most significant qubit.
# Under this convention positive angles give the forward (+2 pi i x y / N) QFT; a backend
# with the opposite phase sign would realise the inverse instead.
@qalgora.kernel
def qft(q: qalgora.qview):
    n = q.size()
    for i in range(n):
        h(q[i])
        for j in range(i + 1, n):
            angle = np.pi / (2 ** (j - i))
            r1.ctrl(angle, q[j], q[i])
    # reverse qubit order
    for i in range(n // 2):
        swap(q[i], q[n - 1 - i])

Seeing it in code

Read the kernel against the theory above. The outer loop walks over each qubit: h(q[i]) is the single-qubit Fourier transform on that qubit; inside the inner loop, r1.ctrl(angle, q[j], q[i]) applies a controlled phase rotation whose angle angle = π / 2^(j−i) is exactly the fine contribution coming from qubit j. The final swap loop reverses the qubit order — this bit-by-bit construction produces its output in reversed bit order, so the swaps restore the standard convention.

The output bit order depends on the implementation convention; this page restores the standard order with the final swaps. On a backend that omits the swaps or uses a different measurement endianness, the output bit string may need to be read in reverse.

Inverse QFT

The inverse simply runs the adjoint — qalgora-Q generates it for you:

@qalgora.kernel
def iqft(q: qalgora.qview):
    qalgora.adjoint(qft, q)