The quantum Fourier transform (QFT) writes a number into phases. On n qubits it takes the basis state |x⟩ to

Σᵧ e^{2πi·xy/2ⁿ} |y⟩ / √2ⁿ:

every outcome equally likely, the information all in the relative phases. The circuit needs only n(n+1)/2 gates: a Hadamard on each qubit, controlled phase rotations `cp(π/2ᵏ)` between pairs, and swaps that reverse the order of the qubits at the end.

The QFT is the step that turns phases into a readable number in phase estimation, and so in factoring. Phase estimation uses it backwards: the *inverse* QFT.

This exercise's intent is *equivalent*: your whole program must be the same circuit as the identity, up to a global phase. The engine decides it on every one of the 8 basis states, by proof. The angles π/2 and π/4 are dyadic, so the program also runs bit-exact.