Quiz: The Quantum Fourier Transform

Answers with explanations at the end.

1. Write the QFT's action on a basis state $|j\rangle$.

2. What gates make up the QFT circuit, and how many of each for $n$ qubits?

3. Four plausible reconstructions of the QFT circuit give fidelities of 0.265, 1.000, 0.250, and 0.250 against QFTGate. Which convention is correct, and why is this trap worse than an ordinary 50/50 convention choice?

4. What should you verify a hand-built QFT against, and why is that stronger than comparing it to QFTGate?

5. Give the QFT's gate count and the classical FFT's operation count for $n = 16$.

6. State the asymptotic comparison between the QFT and the FFT.

7. You apply the QFT to a pure frequency-3 signal on 3 qubits. What do the output amplitudes look like, and what does one measurement give you?

8. Why can't you use the QFT to speed up spectral analysis? Give both halves of the argument.

9. Write the three-term cost expression for "use the QFT to transform classical data."

10. State the criterion determining whether a quantum advantage survives readout.

11. Name the three stages of phase estimation and say which chapter's pattern it instantiates.

12. What replaces the final Hadamard layer in phase estimation, and why is that the natural generalization?

13. Phase estimation of $\varphi = 0.25$ with 3 counting qubits gives error 0.000000 and probability 1.0. Phase estimation of $\varphi = 1/3$ with 3 qubits gives error 0.041667. Explain the difference.

14. How does the phase-estimation error scale with the number of counting qubits? Give the measured values for $\varphi = 1/3$ at $t = 3, 5, 8$.

15. Write the formula for the number of counting qubits needed for $m$ bits of precision at confidence $1-\epsilon$. What do the extra qubits buy?

16. Why can the small controlled-phase rotations in a large QFT be dropped?

17. At $n = 8$, what fidelity and gate saving does a cutoff of 3 give? A cutoff of 4?

18. State the standard AQFT cutoff rule and the gate saving it gives at $n = 64$.

19. What dominates a QFT's fault-tolerant cost, and why is it not T gates?

20. Sweeping rotationCount in Chapter 15's estimator, 120 rotations reports fewer physical qubits than 90. What is happening, and what is the fix?

Answers

1. $\displaystyle \text{QFT}\,|j\rangle = \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2\pi i jk/N}|k\rangle$ with $N = 2^n$. It is exactly the discrete Fourier transform — verified against the DFT matrix to $10^{-10}$.

2. $n$ Hadamards, $n(n-1)/2$ controlled phase rotations, and $\lfloor n/2\rfloor$ swaps. The rotation angles halve at each step: $\pi/2, \pi/4, \pi/8, \dots$

3. Descending qubit order with the final swap layer. It is worse than a binary convention because there are four options, so you cannot stumble into the right one — and because the three wrong answers cluster near 0.25, which looks like a subtle problem (a phase convention, a normalization) rather than a fundamentally wrong circuit. That sends debugging in the wrong direction.

4. The DFT matrix, built directly from the definition. Comparing against QFTGate proves you agree with Qiskit; comparing against the mathematics proves you are correct. They come apart when porting to a framework with a different convention — and Chapter 18 §18.2 measured that Qiskit is the endianness outlier among three frameworks.

5. QFT: 136 gates. Classical FFT: 1,048,576 operations ($N\log_2 N$ with $N = 65{,}536$).

6. $\mathcal{O}(n^2) = \mathcal{O}\big((\log N)^2\big)$ for the QFT against $\mathcal{O}(N\log N)$ for the FFT — exponentially fewer operations.

7. The amplitudes are $[0,0,0,0,0,1,0,0]$ — exactly what the DFT gives. One measurement returns one integer (here, 5), not eight amplitudes.

8. Readout: extracting the $2^n$ output amplitudes requires state tomography at $\mathcal{O}(4^n)$ measurements, which annihilates the $\mathcal{O}(n^2)$ saved. Loading: getting an arbitrary classical signal of $2^n$ samples into a quantum register costs $\mathcal{O}(2^n)$ state preparation. The transform is sandwiched between an exponential load and an exponential readout.

9. $\underbrace{\mathcal{O}(2^n)}{\text{load}} + \underbrace{\mathcal{O}(n^2)} + \underbrace{\mathcal{O}(4^n)}_{\text{read out}}$ — and the middle term is irrelevant.}

10. The size of the answer. A quantum advantage can survive readout when the answer is $\mathcal{O}(\text{poly}(n))$ bits — a period, a phase, an eigenvalue, a count. It cannot when the answer is $\mathcal{O}(2^n)$ values, and no improvement to the algorithm changes that.

11. Superpose ($H$ on $t$ counting qubits), kick back (controlled-$U^{2^j}$ from counting qubit $j$), interfere (inverse QFT on the counting register). It instantiates Chapter 20 §20.1's three-step pattern.

12. The inverse QFT replaces the final Hadamard layer. It is the natural generalization because the Hadamard layer is the QFT over $(\mathbb{Z}_2)^n$ — phase estimation simply needs the version over $\mathbb{Z}_{2^t}$, where the phase can take more than two values.

13. $0.25$ is a dyadic rational — exactly representable in 3 bits ($010$) — so phase estimation returns it with zero error and probability 1. $1/3$ is not dyadic, so the register holds the best 3-bit approximation ($011 = 0.375$), and the residual is the representation error.

14. It halves with each additional counting qubit — error $\sim 2^{-t}$. Measured for $\varphi = 1/3$: 0.041667 at $t=3$, 0.010417 at $t=5$, 0.001302 at $t=8$.

15. $t = m + \left\lceil \log_2\!\left(2 + \frac{1}{2\epsilon}\right)\right\rceil$. The extra qubits buy confidence, not precision — roughly 6 extra for 99%, and the overhead is a constant independent of $m$, which is why the scaling stays clean.

16. Because the angles halve at each step, down to $2\pi/2^n$. At $n = 16$ the smallest is $2\pi/65536$ — smaller than any hardware can reliably apply and smaller than the noise floor — so applying it exactly is spending gates on something the device cannot represent anyway.

17. Cutoff 3: fidelity 0.9709, 35.7% fewer gates. Cutoff 4: fidelity 0.9951, 21.4% fewer gates.

18. $c = \mathcal{O}(\log n)$, in practice $\lceil\log_2 n\rceil$. At $n = 64$ that gives 363 gates instead of 2,016 — an 82% saving, and the AQFT uses 18% of the gates. For Shor at cryptographic sizes it is what makes the circuit expressible at all.

19. Arbitrary-angle rotations. Every controlled phase is a rotation, and under error correction rotations are not primitives — each must be synthesized into a Clifford+T sequence whose length depends on the precision demanded. Chapter 15's estimator takes rotationCount as a separate input from tCount for exactly this reason, and a QFT contains no explicit T gates at all.

20. rotationDepth was left at 0, telling the estimator every rotation happens in parallel. It has switched to a different space–time tradeoff point — note the runtime nearly tripling as the qubit count drops, which is Chapter 15 §15.8's T-factory saturation in a new guise. The fix: a QFT's rotations are largely sequential, so set rotationDepth ≈ rotationCount, and the cost becomes monotonic in both columns.