Self-Assessment Quiz: The Quantum Fourier Transform

Twenty questions on the QFT, its circuit, its cost, and the crucial distinction between transforming a state and reading a spectrum. Aim for 16+.

Question 1

The QFT on $n$ qubits acts on basis states as:

A) $|j\rangle \mapsto \frac{1}{\sqrt{2^n}}\sum_k e^{2\pi ijk/2^n}|k\rangle$ B) $|j\rangle \mapsto |2^n - j\rangle$ C) $|j\rangle \mapsto |j\rangle$ D) $|j\rangle \mapsto \sum_k |k\rangle$

Question 2

The classical FFT on $2^n$ amplitudes costs:

A) $O(n)$ B) $O(n^2)$ C) $O(2^n n)$ D) $O(2^{2n})$

Question 3

The QFT circuit uses approximately:

A) $O(n)$ gates B) $O(n^2)$ gates C) $O(2^n)$ gates D) $O(n\log n)$ gates

Question 4

That comparison ($n^2$ vs. $2^n n$) means the QFT is:

A) Exponentially faster at transforming, though the result is not directly readable B) Slower C) Equivalent D) Only useful classically

Question 5

The QFT circuit is built from:

A) Hadamards and controlled phase rotations B) CNOTs only C) Toffolis D) Measurements

Question 6

The smallest controlled rotation in an exact $n$-qubit QFT is:

A) $\pi/2$ B) $\pi/4$ C) $\pi/2^{n-1}$ D) $\pi$

Question 7

The approximate QFT drops rotations smaller than a threshold, reducing cost to:

A) $O(n)$ B) $O(n\log n)$ C) $O(n^2)$ D) $O(2^n)$

Question 8

Dropping those small rotations is acceptable because:

A) They are exactly zero B) Their cumulative error is bounded and small relative to other error sources C) The QFT is not needed D) They cancel exactly

Question 9

The QFT circuit ends with:

A) A measurement B) A sequence of SWAPs (or relabelling) to reverse qubit order C) A Hadamard on all qubits D) Nothing

Question 10

Measuring immediately after a QFT gives:

A) The full spectrum B) One frequency sampled from the spectrum's probability distribution C) All amplitudes D) The input state

Question 11

Therefore the QFT does not give exponential speedup for:

A) Period finding B) General signal processing where you need the whole spectrum C) Phase estimation D) Shor's algorithm

Question 12

In Shor's algorithm the QFT is applied to:

A) The output register B) The input/counting register, to extract periodicity C) An ancilla only D) Classical data

Question 13

The inverse QFT differs from the QFT by:

A) Conjugating the phase rotations (negating angles) B) Removing the Hadamards C) Adding measurements D) Nothing

Question 14

Loading $2^n$ classical values into a quantum state to be transformed costs:

A) $O(1)$ B) Generally $O(2^n)$ — the data-loading bottleneck C) $O(n)$ always D) Nothing

Question 15

The QFT's power in algorithms comes from:

A) Producing a readable spectrum B) Converting periodicity in phase into concentrated amplitude at frequency values C) Compressing data D) Reducing qubit count

Question 16

True or false: The QFT can replace the FFT in classical signal processing for exponential speedup.

Question 17

True or false: The QFT is unitary.

Question 18

True or false: The approximate QFT changes the algorithm's asymptotic success probability significantly.

Question 19

Short answer. Explain why "the QFT is exponentially faster than the FFT" is true and misleading at once.

Question 20

Short answer. In Shor's algorithm, what does a measured QFT output actually tell you, and what classical post-processing is required?

Answer Key

Q Ans Note
1 A The discrete Fourier transform acting on amplitudes.
2 C FFT is $O(N\log N)$ with $N = 2^n$.
3 B $n$ Hadamards plus $O(n^2)$ controlled rotations.
4 A The caveat in the answer is the whole point — see Q19.
5 A $H$ followed by controlled-$R_k$ rotations, per qubit.
6 C The rotations halve each level down, reaching $\pi/2^{n-1}$.
7 B Truncating at $O(\log n)$ levels gives $O(n\log n)$ gates.
8 B Coppersmith showed the error is bounded and negligible compared to hardware error — and the tiny rotations are the hardest to implement accurately anyway.
9 B The standard circuit produces qubits in reversed order; SWAPs fix it, or you relabel in classical post-processing for free.
10 B One sample, not the spectrum. This is the crux.
11 B You would need exponentially many samples to reconstruct a full spectrum.
12 B The counting register holds the periodic phase structure.
13 A Negate the rotation angles and reverse the gate order.
14 B The QRAM/data-loading problem, which invalidates many proposed quantum speedups on classical data.
15 B Periodic phases interfere constructively at multiples of the frequency, concentrating amplitude where the answer is — making it likely to be measured, not merely present.
16 False It transforms exponentially faster but you cannot read the result out, and loading the data costs $O(2^n)$ anyway. Both ends of the pipeline defeat it.
17 True It is a change of basis, implemented by unitary gates.
18 False The success probability degrades negligibly, which is why the approximate QFT is standard in resource estimates.
19 — True: the circuit performs the transform in $O(n^2)$ operations versus $O(2^n n)$ classically. Misleading: the output is a quantum state whose amplitudes are the spectrum, and measurement yields one sample rather than the spectrum. Extracting all $2^n$ amplitudes needs exponentially many repetitions, and loading $2^n$ classical inputs costs exponential time to begin with. The QFT is useful only when the answer is a single property of the spectrum — a period, a phase — that one or a few samples reveal.
20 — A measurement returns an integer $y$ close to $j \cdot 2^t/r$ for some integer $j$, where $r$ is the period. Post-processing applies the continued-fraction expansion to $y/2^t$ to find a rational approximation with denominator $< N$; that denominator is a candidate for $r$. You then verify classically whether $a^r \equiv 1 \pmod N$, and repeat the quantum step if the candidate fails — typically a small constant number of repetitions suffices.