OE-4.4 Quantum Algorithms

What this is and why it exists

These four algorithms are the reason this field is funded. But their speed-ups differ in kind, and conflating them is the commonest error people make when talking about quantum computing.

Shor's is exponential and would break widely used public-key cryptography. Grover's is only quadratic and merely accelerates search. Those are not the same statement, and the difference decides what is actually at risk.

Deutsch's and Deutsch–Jozsa are teaching algorithms — contrived problems whose purpose is to show interference doing computational work.

The vocabulary

• Quantum Fourier transform — the quantum version of the discrete Fourier transform.
• Phase estimation — recovering a phase, which underlies several algorithms.
• Oracle — a black box the algorithm may query.
• Interference — amplitudes adding and cancelling, which is where the advantage comes from.
• Exponential speed-up — the classical cost grows exponentially where the quantum one does not.
• Quadratic speed-up — the quantum cost is roughly the square root of the classical one.
• Period finding — the structure Shor's algorithm actually exploits.

The mental model

Start with what makes any of this work. It is not that a superposition tries every input and reports the best. Measurement gives one outcome, chosen by the probabilities. The trick is interference: arranging the amplitudes so that wrong answers cancel and the right one is left with high probability. Every algorithm here is an exercise in that arrangement.

Deutsch's algorithm and its generalisation are the teaching cases. The problem is contrived — determine a global property of a black-box function with fewer queries than classical logic allows. Nobody needs the answer. The point is that you can watch interference do computational work in a case small enough to follow completely.

The quantum Fourier transform and phase estimation are the machinery. They are what several serious algorithms are built from, and it is worth knowing them as components rather than as results.

Grover's algorithm searches an unsorted collection. Classically you check items one at a time. Grover's does it in roughly the square root of that number of steps. That is a real improvement and it is quadratic, not exponential. A quadratic gain on a large search is worth having and does not break anything.

Shor's algorithm factors large numbers. Its speed-up is exponential over the best known classical methods. Widely used public-key cryptography rests on factoring being hard, so that matters a great deal. The structure it exploits is period finding — the quantum part finds a period, and classical number theory turns that period into factors. That is why the previous unit taught greatest common divisor.

Hold the distinction. Exponential for factoring. Quadratic for search. Saying that quantum computers break all encryption collapses those two, and it is wrong.

What you should now be able to explain or do

Say why interference rather than parallel trial is the source of the advantage. Explain what Deutsch and Deutsch–Jozsa demonstrate and why the problems are contrived. Describe the quantum Fourier transform and phase estimation as components. State Grover's speed-up as quadratic and say what that is worth. State Shor's as exponential, name the structure it exploits, and say which classical machinery finishes the job.

Check yourself