Case Study: The QFT Is Not a Faster FFT

Executive Summary

A signal-processing group proposes replacing their FFT pipeline with a QFT. Their reasoning is arithmetically sound: transforming $2^{30}$ samples costs the FFT about $3\times10^{10}$ operations and the QFT about 900 gates. Thirty million times fewer operations.

They are correct about the transform and wrong about everything surrounding it. This case study works through the two bottlenecks that bracket the QFT — getting classical data in and getting the spectrum out — and shows that both are exponentially expensive, which is why no quantum signal-processing product exists despite the QFT being twenty-five years old.

Skills applied

• Distinguishing the transform's cost from end-to-end cost (§14.11).
• Analyzing the state-preparation / data-loading bottleneck (§14.13).
• Analyzing the readout bottleneck via the Born rule (§14.12).
• Identifying the narrow conditions under which the QFT does deliver.

Phase 1: The proposal

Input: $2^{30}$ real samples from a sensor array. Output: the power spectrum.

Phase 2: Bottleneck one — loading the data

The QFT acts on a state whose amplitudes are the signal:

$$|\psi\rangle = \frac{1}{\|x\|}\sum_{j=0}^{2^{30}-1} x_j\,|j\rangle$$

Preparing an arbitrary such state requires, in general, $O(2^n)$ gates. There is no shortcut: the state has $2^{30} \approx 10^9$ independent amplitudes, and each must be specified by the circuit. Information-theoretically, a circuit that can produce any of $2^{30}$ arbitrary amplitudes must have at least that many parameters.

So loading costs $\sim10^{9}$ operations — already comparable to the entire classical FFT, before the QFT runs at all.

What about QRAM? Proposals for quantum random-access memory promise $O(\log N)$ access time to a superposition over $N$ stored values. Three caveats: no QRAM has been built at meaningful scale; the hardware requires $O(N)$ physical components, so the $O(N)$ cost has moved into the device rather than vanishing; and the error-correction requirements for a QRAM large enough to matter are formidable. Every quantum algorithm claiming a speedup on classical data inherits this problem — it is not specific to signal processing.

Finding 1. Loading $2^n$ classical values costs $O(2^n)$. The QFT's $O(n^2)$ is dwarfed by its own input stage.

Phase 3: Bottleneck two — reading the spectrum

Suppose the state is loaded for free. Apply the QFT:

$$|\tilde\psi\rangle = \sum_k \tilde{x}_k|k\rangle$$

The amplitudes now are the Fourier coefficients — the transform genuinely happened, exponentially fast.

Now measure. The Born rule returns one value of $k$, with probability $|\tilde x_k|^2$. You have obtained a single sample from the power spectrum, normalized, with no phase information.

To estimate all $2^{30}$ coefficients to modest precision you need at least $O(2^{30})$ samples — and each sample requires re-preparing the input state and re-running the transform. The exponential returns, with the reload cost multiplied on top.

Finding 2. The spectrum exists in the amplitudes and is not accessible. Reading $2^n$ numbers out of a quantum state requires $\Omega(2^n)$ measurements, by Holevo's bound.

Phase 4: End to end

The quantum pipeline is roughly eight orders of magnitude worse, and that is before error correction.

Phase 5: When the QFT does pay

The QFT is not useless — it is the engine of the field's flagship algorithm. What distinguishes Shor from this proposal is that Shor satisfies three conditions that the signal-processing pipeline violates.

1. The input is computed, not loaded. Shor's input state is produced by modular exponentiation — a circuit of $O(n^3)$ gates. Nothing is loaded from classical memory. The state is generated by a compact circuit, which is the only affordable way to fill $2^n$ amplitudes.

2. The answer is one number, not the whole spectrum. Shor needs the period $r$, extracted from a few samples via continued fractions. One or a handful of measurements suffice.

3. The spectrum is sharply peaked. Periodic structure concentrates amplitude on multiples of $2^t/r$, so a single measurement lands on useful information with high probability. A generic signal's spectrum is spread out, so single samples are nearly uninformative.

The rule. The QFT pays when the input is generated by an efficient circuit, the output is a single property of the spectrum, and that property produces a concentrated distribution. Fail any of the three and the exponential advantage evaporates.

Phase 6: The recommendation

Do not pursue. No reformulation of a general spectral-analysis pipeline satisfies the three conditions, because the data is inherently classical and the required output is the full spectrum.

Test any similar proposal with three questions: 1. Where does the input state come from — a circuit, or classical memory? 2. How many numbers must come out — one, or exponentially many? 3. Is the output distribution concentrated or spread?

These three questions dispose of a large fraction of proposed quantum speedups on classical data, and they take five minutes rather than a research program.

Discussion Questions

1. The QFT genuinely transforms exponentially faster. Why is that not the operative fact?
2. Holevo's bound caps extraction at $n$ bits from $n$ qubits. Connect that to the readout bottleneck.
3. QRAM claims $O(\log N)$ access using $O(N)$ hardware. Has the exponential cost disappeared or moved?
4. Apply the three questions to a quantum machine-learning proposal that classifies classical images.

Your Turn: Extensions

• Implement a 3-qubit QFT and verify it against numpy.fft on the amplitude vector.
• Prepare a non-trivial 4-qubit state with initialize and count the gates the transpiler emits; observe the scaling with qubit count.
• Estimate the shots needed to reconstruct an 8-qubit spectrum to 5% accuracy per coefficient.
• Take Shor's counting register and confirm its spectrum is sharply peaked for a small period.

Key Takeaways

• The QFT transforms in $O(n^2)$ but is bracketed by two exponential bottlenecks: loading $2^n$ classical amplitudes and reading $2^n$ coefficients out.
• Measurement returns one sample from the spectrum, not the spectrum — the Born rule, not an engineering limitation.
• QRAM relocates the exponential cost into hardware; it does not remove it, and it does not exist at scale.
• The QFT pays only when the input is circuit-generated, the output is a single property, and the distribution is concentrated. Shor meets all three.
• Three questions — where does the input come from, how many numbers come out, how concentrated is the distribution — dispose of most classical-data quantum speedup claims.