Deutsch's algorithm

The question

You're handed a black-box function f that maps one bit to one bit. It is either constant (f(0) = f(1)) or balanced (f(0) ≠ f(1)). How many times must you call f to know which? Classically, two — one call tells you f(0) but nothing about f(1).

David Deutsch showed in 1985 that a quantum computer needs just one call. Not because it calls f on 0 and 1 'in parallel' and reads both answers — measurement would only ever reveal one — but because interference can extract a global property of f (constant vs balanced) without learning either individual value. You trade the answers to both sub-questions for the answer to the one question you actually asked.

How the circuit works

Qubit 1 is prepared in |−⟩ = (|0⟩−|1⟩)/√2 by the X and H. Now comes the key trick, phase kickback: the oracle flips qubit 1 whenever f of qubit 0's value is 1 — but flipping |−⟩ just multiplies it by −1. The flip meant for qubit 1 lands as a sign on qubit 0's amplitude instead. The oracle silently stamps (−1)^f(x) onto each branch x of qubit 0's superposition.

If f is constant, both branches get the same sign — an invisible global phase, and the final H returns qubit 0 to |0⟩. If f is balanced, the branches get opposite signs — turning |+⟩ into |−⟩, which the final H rotates to |1⟩. Measure qubit 0 once: 0 means constant, 1 means balanced, with certainty.

In the preset, the oracle is a CNOT — the balanced function f(x) = x — so qubit 0 reads 1. Delete the CNOT to make f constant and watch the answer flip to 0.

From toy to tidal wave

One saved query hardly threatens supercomputers. But the pattern — superpose, kick phases with an oracle, interfere, measure a global property — scales. The Deutsch-Jozsa algorithm answers the same question for n-bit functions in one query where classical algorithms may need over 2ⁿ⁻¹. Simon's algorithm turned that into an exponential speedup that directly inspired Shor's factoring algorithm.

Every one of those descendants is this circuit with more wires. If you follow the phase-kickback story here, you understand the mechanism behind quantum computing's most famous results.