Deutsch's Algorithm

This is the smallest possible quantum algorithm — one qubit, one oracle query — and it's the first one in history. Every piece of machinery from Ch. 22–23 (superposition, parallelism, phase oracles) gets used here for the very first time, on the simplest problem that can show a genuine quantum advantage at all.

The problem

You're given a black-box function f: {0,1}→{0,1}. There are exactly 4 possible such functions — 2 are constant (f(0)=f(1)) and 2 are balanced (f(0)≠f(1)). Question: which kind is it? Classically, this needs 2 queries in the worst case (check f(0), then f(1) to compare). Deutsch's algorithm needs exactly 1.

Working the math by hand

Start at |0⟩, apply H: (|0⟩+|1⟩)/√2. Apply the phase oracle: (−1)^f(0)|0⟩+(−1)^f(1)|1⟩, all over √2. Apply H again — this is exactly the Hadamard transform from Ch. 22, run backward. If f is constant, both terms share the same sign, and H constructively reconstructs |0⟩ exactly. If f is balanced, the terms have opposite signs, and H instead reconstructs |1⟩ exactly. Either way, the final measurement is 100% certain — no probability, no repeated trials needed.

Why this counts as "faster," carefully

The honest statement of Deutsch's advantage is subtler than "twice as fast," and worth getting right: for this 1-bit problem, 1 query versus a classical worst-case of 2 is a real but modest speedup — the actual significance is historical and structural, not the size of the number. This was the first proof that quantum query complexity can be strictly less than classical query complexity for any problem at all, and the H–oracle–H pattern it introduced is exactly the template Ch. 26's Deutsch–Jozsa algorithm scales up to an exponential gap (1 query versus up to 2ⁿ⁻¹+1 classically) by simply running the same circuit on n qubits instead of one.