Why do Grover's and Shor's algorithms actually work?

One mechanism, applied four times, is the actual engine behind Deutsch-Jozsa, Grover's search, and Shor's factoring. It has a name, phase kickback, and this site never said it out loud until now.

You'll be able to say why one mechanism, phase kickback, runs Deutsch-Jozsa, Simon and Shor.

The trick: aim at something that can't move, and watch the recoil

Picture a locked door with a combination dial, and a rule: turning the dial to the right number does nothing visible to the door: it was already unlocked, so "unlocking" it again just leaves it exactly as unlocked as before. But the person turning the dial isn't left unaffected. Their hand picks up a small, specific twist depending on whether the combination they tried was right or wrong: a twist you can't see by looking at the door, only by looking at the hand.

Now do this in superposition: instead of trying combinations one at a time, hold every combination in your hand at once, and touch the dial once. The door, silent throughout, never changing, has left a different twist onto each of your simultaneously-held combinations. Nothing about the door tells you which twist went where. But if you now let all those twisted possibilities interfere with each other, the twisted-right combination reinforcing itself and the twisted-wrong ones cancelling out, the answer falls out.

That is phase kickback, stated without a single equation. The "door" is a target qubit prepared so that touching it can never change it. The "twist" is a phase. And "letting them interfere" is exactly what a Hadamard gate, or the more elaborate Fourier transform used in Shor's algorithm, is for. The mechanism, with the equation: Working: keep going ↓

The mechanism: eigenstates don't move, so the phase has nowhere else to go

An eigenstate of a gate U is a state that U leaves pointing the same direction: U only ever multiplies it by a number, U|u⟩ = λ|u⟩, called the eigenvalue. For any gate used in quantum computing, λ is a pure phase, λ = e^iφ, since gates preserve length.

The cleanest possible case: the gate Z flips the sign of |1⟩ and leaves |0⟩ alone, so |1⟩ is an eigenstate of Z with eigenvalue −1. Take the controlled version, CZ, wired so a control qubit decides whether Z is applied to a target held fixed at |1⟩, and put the control in an equal superposition |+⟩ = (|0⟩+|1⟩)/√2:

Read that literally: the target started at |1⟩ and ends at |1⟩, untouched every single time, because |1⟩ is exactly what Z can't change. But the control started at |+⟩ and ended at |−⟩ = (|0⟩−|1⟩)/√2, a real, measurable flip, purely from being wired to a gate that, by every other measure, "did nothing."

Try it below with a general phase, not just Z's −1.

Watch the phase kick back

The target (left) is fixed at |1⟩ throughout, an eigenstate of every phase gate below, so it is mathematically incapable of moving. Set how much phase each application carries, then apply it a few times and watch the control (right) accumulate it instead.

Where this mechanism runs, and where the proofs already live

This page does not re-derive what The Machinery has already proven and independently referee-verified. It exists to name the mechanism plainly and point at exactly where each proof lives.

Deutsch's algorithm and Deutsch-Jozsa are the smallest complete instance: an oracle U_f|x⟩|y⟩ = |x⟩|y⊕f(x)⟩, with the answer register prepared in |−⟩, kicks back (−1)^f(x) onto the query register instead of ever writing to the answer register, proven on topic f08 and f09 (Deutsch, Proc. R. Soc. Lond. A 400, 97 (1985); Deutsch & Jozsa, Proc. R. Soc. Lond. A 439, 553 (1992); the exact one-query version: Cleve, Ekert, Macchiavello & Mosca, Proc. R. Soc. Lond. A 454, 339 (1998)), and numerically checked two different ways: exhaustively at f08's n=1 (all four possible one-bit functions), and by sampling at f09's n=4 (both constant functions, plus 20 of the 12,870 possible balanced ones); worth knowing which is which before quoting either as a full proof by enumeration.

Grover's algorithm uses the identical trick in its phase-oracle form: instead of writing "is this the answer?" to a separate register, the oracle multiplies the marked state by −1 directly, exactly the kickback pattern above with the marked state playing the role of the fixed eigenstate. Grover, arXiv quant-ph/9605043 (Proc. 28th STOC, 212 (1996)), proved the O(√N) query bound this buys; play the mechanism yourself at Grover's Escape, where over-rotating past the answer is a failure mode this site's games are built to show rather than hide.

Quantum phase estimation generalises the widget above from a fixed ±1 to an arbitrary eigenvalue e^2πiθ of any unitary U, using repeated controlled applications of increasing powers of U to read θ out bit by bit, proven (with its "sharply peaked, not exact" limit stated plainly) on topic f12. Shor's algorithm is one specific choice of U, modular multiplication, that turns phase estimation's output into the period behind factoring, worked through with a 2,000-trial numerical verification on topic f13. It is the mechanism the Bitcoin page's qubit counts run on, though not the counts themselves: those come from separate resource-estimation papers cited there, since bitcoin.html is upfront that it asserts those numbers rather than deriving them.

References

Go deeper