Quantum Fourier Transform

Quantum Fourier Transform

The Quantum Fourier Transform (QFT) is the quantum analogue of the discrete Fourier transform and one of the most consequential building blocks in quantum computing, providing the exponential speedups behind Shor's factoring algorithm, quantum phase estimation, and many quantum simulation routines. Whereas the fast Fourier transform on n bits requires on the order of n times 2^n operations classically, the QFT acts on the amplitudes of an n-qubit state using only about n^2 gates, an exponential reduction in circuit size. This Cirq example constructs and simulates the QFT on a four-qubit register, demonstrating the transform on the computational basis state. It builds the circuit from the characteristic pattern of Hadamard gates and controlled phase rotations followed by qubit-order-reversal swaps, and simulates it to show how the transform maps an input basis state into a uniform superposition with carefully structured relative phases. By working through a concrete small example, the script makes the otherwise abstract QFT tangible: you can see exactly which gates are applied and how the output amplitudes encode the Fourier-transformed input. It is an essential reference for understanding the primitive that powers the most celebrated quantum algorithms.

Run it

pip install -r requirements.txt
python quantum_fourier_transform.py

Source and license

Imported from examples/quantum_fourier_transform.py in quantumlib/Cirq at v1.6.1, under the Apache License 2.0. Original authors: The Cirq Developers. The upstream LICENSE is included alongside this example.