How does a quantum computer perform a Fourier transform?

A quantum computer performs a Fourier transform using a quantum circuit called the Quantum Fourier Transform (QFT). The QFT is a linear transformation that maps quantum states representing data into a frequency-based representation, analogous to the classical Fast Fourier Transform (FFT). However, the QFT operates on quantum amplitudes instead of classical data, enabling it to process superposition states efficiently. The core mechanism involves applying a sequence of quantum gates—primarily Hadamard gates and controlled phase rotations—to entangled qubits. These operations decompose the input state into a combination of oscillatory components, revealing periodic patterns in the quantum data.

The QFT circuit is built by iterating over each qubit in the input register. For a given qubit at position j (starting from the least significant bit), a Hadamard gate is applied first, placing it into a superposition. Then, a series of controlled phase-shift gates (e.g., R_k gates, where R_k applies a phase of 2π/2^k) are applied between qubit j and every higher-index qubit k > j. These phase rotations encode frequency information into the relative phases of the qubits. For example, in a 3-qubit system, the first qubit (j=0) would undergo a Hadamard, followed by a controlled-R_2 gate (phase π/2) with qubit 1 and a controlled-R_3 gate (phase π/4) with qubit 2. This process repeats for qubits 1 and 2, with decreasing phase shifts. Finally, the qubits are reordered (e.g., via swap operations) to account for the bit-reversed output order inherent to the QFT.

The QFT’s efficiency stems from its logarithmic depth in the number of qubits. For n qubits, the circuit requires O(n²) gates—compared to the classical FFT’s O(n2ⁿ) operations—providing an exponential speedup for certain tasks. However, this advantage is context-dependent: the QFT is most powerful when used as a subroutine in algorithms like Shor’s factoring algorithm, where it identifies periodicities in quantum states. Developers should note that the QFT’s output isn’t directly readable; it must be combined with measurement or further processing to extract useful classical information. The practical implementation often involves optimizing gate sequences to minimize errors, especially on noisy quantum hardware.