Case Study: The Algorithm That Wasn't — Superposition Without Interference

Executive Summary

A researcher proposes a quantum algorithm for database search that is, on its face, compelling: load all $N$ records into superposition, evaluate a matching predicate on all of them at once, and measure. One query instead of $N$.

The circuit compiles. It runs. It returns a uniformly random record, every time, forever.

This case study builds that circuit, proves it cannot work, and then repairs it — turning a superposition-only algorithm into a genuine one by adding the missing ingredient. It is the most important negative result in the book, because the flawed reasoning behind it is the standard popular explanation of quantum computing.

Skills applied

• Computing the output distribution of a superposition-and-measure circuit (§11.4).
• Identifying the absence of interference as the failure mode (§11.6).
• Understanding phase kickback as the repair (§11.8).
• Quantifying the difference between marking an answer and amplifying it.

Phase 1: The proposed algorithm

Search $N = 2^n$ records for the one satisfying predicate $f$.

from qiskit import QuantumCircuit

def naive_search(n, oracle):
    qc = QuantumCircuit(n + 1, n)
    qc.h(range(n))              # superposition over all N records
    qc.compose(oracle, inplace=True)   # |x>|0> -> |x>|f(x)>
    qc.measure(range(n), range(n))     # read the record
    return qc

The pitch: "we evaluate $f$ on all $N$ records in one oracle call, so the marked record is found in one query."

Phase 2: Compute what it actually returns

After the Hadamards:

$$|\psi_1\rangle = \frac{1}{\sqrt N}\sum_{x=0}^{N-1}|x\rangle|0\rangle$$

After the oracle:

$$|\psi_2\rangle = \frac{1}{\sqrt N}\sum_x |x\rangle|f(x)\rangle$$

Now measure the first register. The Born rule gives, for every $x$:

$$P(x) = \left|\frac{1}{\sqrt N}\right|^2 = \frac{1}{N}$$

Uniform. The marked record is returned with probability $1/N$ — precisely the odds of guessing at random. The oracle call changed nothing about the distribution over $x$.

Where did the computation go?

It happened. $f$ really was evaluated on all $N$ inputs, and the results really are present in the state — in the second register, entangled with the first. But measurement returns one branch, chosen by amplitude, and every amplitude is identical.

The core error. Computing a value is not the same as making it likely to be observed. Quantum parallelism delivers the first for free and does nothing at all about the second.

Phase 3: A partial repair that still fails

"Fine," says the researcher, "measure the second register first, postselect on $f(x)=1$, then read $x$."

This works — with probability $1/N$ per attempt. Postselection succeeds when the second register collapses to 1, which happens with probability (number of matches)/$N$. On failure you must repeat. Expected attempts: $N$.

We have reproduced classical brute force exactly, with extra steps and a refrigerator.

Second lesson. Postselection converts a superposition into a classical search. Any "algorithm" whose success hinges on a lucky measurement outcome has smuggled the exponential cost into the retry count.

Phase 4: The actual repair — phase, then amplify

Two changes convert this into Grover's algorithm.

Change 1: mark with phase instead of a bit. Put the target register in $|-\rangle$ so the oracle becomes a phase oracle:

$$U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$$

The marked record now differs from the others — but only in sign, and sign is invisible to measurement. Measuring here still gives uniform $1/N$. This alone is not enough, which is worth pausing on: the oracle has done real work, and the work is still unobservable.

Change 2: convert phase into amplitude. Apply the diffusion operator $D = 2|s\rangle\langle s| - I$, which reflects all amplitudes about their mean. The marked amplitude is $-1/\sqrt N$ while the mean is $\approx +1/\sqrt N$; reflecting about the mean sends the marked amplitude to roughly $3/\sqrt N$ and slightly reduces the rest.

That is one Grover iteration. Repeat $\approx \frac{\pi}{4}\sqrt N$ times and the marked amplitude approaches 1.

def grover_iteration(n, phase_oracle):
    qc = QuantumCircuit(n)
    qc.compose(phase_oracle, inplace=True)
    qc.h(range(n)); qc.x(range(n))          # diffusion
    qc.h(n-1); qc.mcx(list(range(n-1)), n-1); qc.h(n-1)
    qc.x(range(n)); qc.h(range(n))
    return qc

Phase 5: Compare the three

For $N = 1{,}024$ ($n = 10$), one marked record:

Grover uses 25 oracle calls where classical needs ~512. The speedup is real, quadratic, and entirely attributable to the amplification step — the oracle call count differs from the naive version by a factor of 25, not by a factor of 1,024.

Third lesson. The oracle was never the bottleneck. Superposition made one oracle call cover all inputs at the outset, and that bought nothing. The 20× improvement came from the $\sqrt N$ iterations of interference.

Phase 6: Recognizing the error in the wild

The naive pattern reappears constantly in proposals. Three warning signs:

1. The algorithm has no interference step — no final Hadamard layer, no diffusion, no QFT. If nothing converts phases into amplitudes, there is no algorithm.
2. Success depends on a postselection outcome with probability that shrinks exponentially in problem size.
3. The claimed speedup is stated in oracle calls only, ignoring the number of repetitions needed to get an answer with constant probability.

The honest question to ask of any proposed quantum algorithm: what makes the right answer more likely to be measured than the wrong ones? If there is no answer, there is no algorithm.

Discussion Questions

1. The naive circuit genuinely evaluates $f$ on all $N$ inputs. In what sense is that computation "wasted," and is "wasted" the right word?
2. Marking with a phase changes the state but not the measurement distribution. Why is it nevertheless progress?
3. Postselection turns the algorithm into classical brute force. Are there settings where postselection is legitimate?
4. Grover is provably optimal for unstructured search. What does that say about the prospects for a one-query search algorithm of any design?

Your Turn: Extensions

• Implement all three circuits for $n = 4$ and compare measured distributions.
• Plot success probability against Grover iteration count and locate the peak; confirm over-rotation past it.
• Modify the phase oracle to mark two records and verify $k_{\text{opt}} = \lfloor\frac{\pi}{4}\sqrt{N/M}\rfloor$.
• Write the naive circuit's output distribution analytically for an oracle with $M$ marked items and confirm it is uniform regardless of $M$.

Key Takeaways

• Evaluating $f$ on a superposition of all inputs is free and, on its own, worth exactly nothing: measurement returns a uniformly random branch.
• Postselection recovers correctness at the cost of exponentially many retries — classical brute force in disguise.
• Phase marking is invisible to measurement until an interference step converts phase into amplitude.
• Grover's speedup lives entirely in the $\sqrt N$ amplification iterations, not in the parallel oracle evaluation.
• Test any proposed quantum algorithm by asking what makes the correct answer more likely to be measured. No mechanism, no algorithm.