The quantum Fourier transform on n qubits (N = 2^n) sends a state with amplitudes a_j to the state with amplitudes b_k = \frac{1}{\sqrt N}\sum_j a_j\,e^{2\pi i\,jk/N}. Its standard circuit works through the qubits in order, q = 0, 1, \dots, n-1: for qubit q it applies the Hadamard gate H=\tfrac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix} to q, then a controlled phase between q and each later qubit m = q+1, \dots, n-1 with angle \pi/2^{\,m-q}. (The controlled phase CP(\lambda) multiplies the amplitude of every basis state where both of its qubits read 1 by e^{i\lambda}.) At the end it swaps qubits q and n-1-q for every q < n-1-q, which reverses the bit string of every index. In total that is n Hadamards, n(n-1)/2 controlled phases and \lfloor n/2\rfloor swaps.
On a large register most controlled phases have tiny angles, and a chip lab saves time by leaving them out. The approximate QFT with threshold min_angle is the same circuit without every controlled phase whose angle is smaller than min_angle (an angle equal to min_angle is kept); the Hadamards and swaps all stay.
Write approx_qft(state, min_angle) that runs the approximate QFT on state (a normalised list of 2^n amplitudes) and returns a tuple (kept, dropped, fidelity): the numbers of controlled phases kept and dropped, and the fidelity F = |\langle \mathrm{QFT}\,\psi \,|\, \mathrm{AQFT}\,\psi\rangle|^2 = \left|\sum_k \overline{b_k}\,c_k\right|^2, where b is the exact QFT of the state and c the approximate result. F = 1 means no loss.
Bit order: basis state |b_0 b_1 \dots b_{n-1}\rangle has index int("b0b1...", 2), so qubit 0 is the leftmost bit, the most significant. In 3 qubits, |011\rangle is index 3. Press Run with plot(range(1, 9), [approx_qft([0] * 255 + [1], math.pi / 2 ** t)[2] for t in range(1, 9)]) to see the fidelity climb as fewer gates are dropped.
Examples
Input: state = [0, 1, 0, 0, 0, 0, 0, 0], min_angle = math.pi / 2
Output: (2, 1, 0.8535533905932735)
Explanation: the angles are pi/2 (qubits 0-1), pi/4 (qubits 0-2), pi/2 (qubits 1-2); pi/4 is dropped.
Input: state = [0, 1, 0, 0, 0, 0, 0, 0], min_angle = math.pi / 4
Output: (3, 0, 1.0)
Explanation: pi/4 equals the threshold, so it is kept: this is the exact QFT.
Input: state = [0, 0, 0, 1, 0, 0, 0, 0], min_angle = 4
Output: (0, 3, 0.07322330470336309)
Constraints
1 <= n <= 8;0 <= min_angle <= 4- the fidelity is compared with a tolerance of
1e-6
Goals
- Run the QFT circuit gate by gate on a state
- Drop the controlled phases whose angle is below a threshold and count what is kept
- Measure how close the approximate result stays to the exact QFT