Case Study 1: The Fourier Speedup That Was Never There

DataField.Dev

Case Study 1: The Fourier Speedup That Was Never There

The proposal

A signal-processing group runs FFTs constantly — spectral analysis on large datasets, millions of samples per transform, and the FFT is the bottleneck.

Someone finds the complexity comparison:

$$\text{classical FFT: } \mathcal{O}(N\log N) \qquad \text{QFT: } \mathcal{O}\big((\log N)^2\big)$$

For $N = 2^{20}$ — a million samples — that is 20 million operations against 210 gates.

A hundred-thousand-fold speedup. They write a proposal.

The complexity comparison is correct. The QFT really does apply the Fourier transform to $2^n$ amplitudes in $\mathcal{O}(n^2)$ gates, and this book verified it: Qiskit's QFTGate unitary is the DFT matrix, to $10^{-10}$.

What breaks

They build a prototype. Three qubits, a pure frequency-3 signal, and it works perfectly:

   QFT output amplitudes:      [0, 0, 0, 0, 0, 1, 0, 0]
   measurement probabilities:  [0, 0, 0, 0, 0, 1, 0, 0]
   measuring gives outcome 5 with P = 1.0000

The transform is exactly right. Then they try to get the spectrum out, and there is no spectrum to get.

One measurement returns one integer. They need all $2^n$ amplitudes — that is what a spectrum is — and the quantum register hands back a single sample from a distribution.

Running it more times does not help in the way they expect. Repeated measurement gives the magnitudes $|\hat{f}_k|^2$ to sampling accuracy, and:

the phases are gone entirely,
resolving $2^{20}$ probabilities to any useful precision needs vastly more than $2^{20}$ shots,
and full reconstruction requires state tomography — measurements in exponentially many bases, at cost $\mathcal{O}(4^n)$.

$$\underbrace{\mathcal{O}(n^2)}_{\text{compute}} \;+\; \underbrace{\mathcal{O}(4^n)}_{\text{read out}} \;=\; \text{catastrophically worse than the FFT}$$

And the input was already a problem

The prototype used initialize() with a hand-written signal, which hid the second half of the failure.

Loading an arbitrary classical signal of $2^n$ samples into a quantum register costs $\mathcal{O}(2^n)$. There is no shortcut for arbitrary data — the amplitudes must be prepared, and preparing $N$ arbitrary amplitudes takes $\Omega(N)$ operations.

So the real structure of their proposal was:

   load     O(2^n)      <- reading the data they already have
   QFT      O(n^2)      <- the part they were excited about
   read     O(4^n)      <- reconstructing the answer

The transform is sandwiched between an exponential load and an exponential readout, and the $\mathcal{O}(n^2)$ in the middle is irrelevant.

The general shape, and it is worth naming: an exponentially fast subroutine wrapped in exponential I/O.

This book has now hit it twice in consecutive chapters. Chapter 21 §21.7: Grover's oracle must be a circuit, so searching real data costs $\mathcal{O}(N)$ to encode before the $\mathcal{O}(\sqrt N)$ search. Here: the QFT is fast and unreachable from both ends.

It is the most common way quantum speedup claims go wrong, and it will appear again in Chapter 32, where a large fraction of quantum machine learning proposals assume efficient state preparation from classical data.

Why the complexity comparison misled them

Because it compares the wrong two things.

$\mathcal{O}(N\log N)$ for the FFT counts operations to produce $N$ numbers you can then use.

$\mathcal{O}(n^2)$ for the QFT counts gates to produce a quantum state you cannot read.

These are not the same deliverable, and the complexity notation does not say so. A complexity class describes the cost of an operation; it does not describe what you get.

The honest comparison has to include I/O on both sides — and once it does, the QFT loses badly for any task that wants the transformed data as data.

What the QFT is actually for

The capability is real, and the criterion is sharp:

Use the QFT when you want ONE NUMBER out of the transform, not the transform.

Phase estimation (§22.4): one eigenvalue phase. Measured exact for dyadic phases, error falling as $2^{-t}$ otherwise.
Period finding (Chapter 23): one period, from which factoring follows.
Quantum counting (Chapter 21): one count $M$.
Energy estimation: one ground-state energy.

In every case the QFT's job is to concentrate a single quantity into a measurable outcome, and "measurable outcome" is exactly what the register can deliver. The exponential advantage survives because the answer is $\mathcal{O}(\log N)$ bits, not $\mathcal{O}(N)$ amplitudes.

$$\text{advantage survives when } |\text{answer}| = \mathcal{O}(\text{poly}(n)), \text{ not } \mathcal{O}(2^n)$$

Their spectral analysis wanted $2^{20}$ amplitudes. That is the disqualifying fact, and it was available before any code was written.

The check they could have run first

Ask what the output is, and how big it is.

   Do I want a number, or an array?
     a number of O(poly n) bits  ->  the QFT may help
     an array of O(2^n) values   ->  it cannot, at any speed

One question. No prototype, no proposal, no quantum hardware.

And the companion question: where does the input come from? If it is arbitrary classical data, the load is $\mathcal{O}(2^n)$ and the argument is over regardless of the output.

The lessons

A complexity class describes an operation's cost, not the deliverable. $\mathcal{O}(n^2)$ gates to produce an unreadable state and $\mathcal{O}(N\log N)$ operations to produce usable data are not comparable quantities, and writing them side by side makes them look like they are.

Count the I/O. Any quantum speedup claim must include the cost of getting data in and answers out. An exponentially fast core wrapped in exponential I/O is not a speedup — it is a slower algorithm with an interesting middle.

The size of the answer is the criterion. If what you want is $\mathcal{O}(\text{poly}(n))$ bits, a quantum advantage can survive readout. If it is $\mathcal{O}(2^n)$ values, it cannot, and no improvement to the algorithm changes that.

"The QFT is a fast Fourier transform" is false in the way that matters. It is an exact Fourier transform, computed efficiently, on data you cannot load and producing output you cannot read. What it is good for is a different thing entirely, and a genuinely important one.

And the disqualifying fact was available for free. "I need $2^{20}$ amplitudes" settles it before any of the rest — which is the recurring shape of this book's case studies: the cheap check first, and the cheap check was never run.

Reproduce it: code/example-01-qft-and-the-readout-problem.py shows the exact transform, the single-outcome measurement, and the tomography cost.