The QFT on n qubits uses O(n^2) gates. The classical FFT uses O(n * 2^n) operations. Does this mean the QFT provides an exponential speedup for computing Fourier transforms?
AYes — the QFT is always exponentially faster than the classical FFT
BNo — the QFT transforms quantum amplitudes, which cannot be directly read out; the speedup applies only when the QFT is used as a subroutine within a larger quantum algorithm
CYes — but only for real-valued input data, not complex
DNo — the QFT and FFT compute different transforms
The QFT operates on the amplitudes of a quantum state, not on classical data. You cannot efficiently load arbitrary classical data into quantum amplitudes (the 'state preparation' problem), and you cannot read out all amplitudes after the QFT (measurement collapses to one basis state). The QFT's power lies in being a subroutine: when the input state naturally arises from a quantum computation (as in phase estimation or Shor's algorithm), the QFT efficiently extracts period or phase information that can then be measured.
Question 2 True / False
The QFT circuit for 3 qubits consists of only Hadamard gates — no controlled rotations are needed for small registers.
TTrue
FFalse
Answer: False
Even for 3 qubits, the QFT circuit requires Hadamard gates and controlled phase rotation gates. The circuit applies H to the first qubit, then controlled-R2 and controlled-R3 (where Rk applies a phase of e^(2*pi*i/2^k)), then H to the second qubit, then controlled-R2 from the third qubit, then H to the third qubit, plus SWAP gates to reverse the bit order. Only for 1 qubit is the QFT a single Hadamard.
Question 3 Short Answer
Why is the QFT useful for finding the period of a function, even though measuring the QFT output gives only one random value?
Think about your answer, then reveal below.
Model answer: When applied to a periodic state with period r, the QFT concentrates amplitude on multiples of 2^n/r — the peaks of the Fourier transform of a periodic function. Measuring gives a random multiple of approximately 2^n/r. From this, the period r can be extracted via continued fractions. Multiple measurements (O(1) repetitions) provide enough information to determine r with high probability.
The QFT converts periodicity in the computational basis into sharp peaks in the Fourier basis. A state with period r has nonzero amplitudes only at positions that are multiples of r; after the QFT, these become peaks at multiples of 2^n/r. This is the discrete version of the fact that the Fourier transform of a periodic signal has peaks at the signal's frequency. Shor's algorithm exploits exactly this: it creates a periodic state via modular exponentiation, applies the QFT, and reads off the period.