Reference shelf

Algorithms compared

Deutsch-Jozsa, Grover, and Shor side by side: the problem each solves, the cost, the speedup, and its real status.

Written by Claude Fable 5

The three algorithms the course builds, side by side. Read each row as one sentence: this is the problem, this is what it costs classically, this is what quantum brings, and this is the trick that buys the difference. The speedups are not the same kind, and the last column is where the honesty lives.

Not all speedups are equal

Grover's quadratic speedup is real but modest: it halves the exponent. Shor's is the exponential one, and it comes only from the hidden periodic structure of factoring, not from searching many answers at once. Deutsch- Jozsa is the toy that first showed a provable separation at all. Keep those three flavors distinct.

Algorithm	Problem	Classical cost	Quantum cost	Speedup	Key mechanism	Status
Deutsch-Jozsa	Decide whether a promised oracle is constant (same output for every input) or balanced (0 on half the inputs, 1 on the other half).	Up to $2^{n - 1} + 1$ queries in the worst case, just over half the table.	A single query.	Exponential, in the number of oracle queries.	Phase kickback writes each $f (x)$ as a sign $(- 1)^{f (x)}$ on the input, then a Hadamard makes those signs interfere so one read-out reveals the global property.	A promise problem, not a practical task, but the first clean proof that interference can beat every classical strategy.
Grover	Find the one marked item in an unstructured search of $N$ possibilities, given only a checker for the answer.	About $N /2$ tries on average, up to $N$ in the worst case.	$\frac{π}{4} N$	Quadratic: the cost drops to its square root.	Amplitude amplification. Two reflections per step, an oracle sign-flip of the marked amplitude then diffusion (inversion about the mean), rotate the state toward the answer.	Broadly applicable to any brute-force search, but only quadratic, and it needs many low-error qubits to beat classical hardware in practice.
Shor	Factor a large integer $N = pq$ , the problem RSA's security rests on.	Super-polynomial in the number of digits (best known).	Polynomial in the number of digits.	Exponential (super-polynomial to polynomial).	Reduce factoring to finding the period of $a^{x} mod N$ (a cheap classical step), then let the quantum Fourier transform extract that period. A greatest-common-divisor finishes the job.	Breaks RSA, Diffie-Hellman and elliptic-curve crypto in principle. Estimated to need millions of high-quality physical qubits, far beyond today's roughly thousand-qubit noisy machines.

Where the wins do and do not come from

The pattern across the three: a speedup appears exactly when the problem hides structure a quantum circuit can turn into interference. Shor has a period; Deutsch-Jozsa has a global promise. Grover has none, which is why it can only manage a quadratic gain on raw search.

What quantum does not do

There is no known efficient quantum algorithm for the NP-complete problems, such as SAT or scheduling. Running Grover over the

2^{n}

candidate assignments of a brute force costs

2^{n} = 2^{n /2}

, which is still exponential: a quadratic speedup on an exponential cost stays exponential. The full argument, and where the exponential wins actually come from, is in What quantum cannot do.