The Deutsch Algorithm

Here is the very first crack of daylight between quantum and classical computing — the toy problem where a quantum computer provably does something a classical one cannot. You are handed a mystery one-bit function f:\{0,1\}\to\{0,1\}, sealed inside an oracle you may query but not read. Your task is not to learn f — only to decide one yes/no fact about it: is it constant (f(0)=f(1)) or balanced (f(0)\ne f(1))? Classically you have no choice but to look up both values and compare them: two queries. Deutsch's algorithm settles it in one.

Constant vs balanced: it's really one XOR

There are exactly four one-bit functions. Two are constant and two are balanced:

\underbrace{\begin{array}{c|c} x & f(x) \\ \hline 0 & 0 \\ 1 & 0 \end{array}}_{\text{constant}} \quad \underbrace{\begin{array}{c|c} x & f(x) \\ \hline 0 & 1 \\ 1 & 1 \end{array}}_{\text{constant}} \qquad \underbrace{\begin{array}{c|c} x & f(x) \\ \hline 0 & 0 \\ 1 & 1 \end{array}}_{\text{balanced}} \quad \underbrace{\begin{array}{c|c} x & f(x) \\ \hline 0 & 1 \\ 1 & 0 \end{array}}_{\text{balanced}}

The single number that separates the two camps is the parity f(0)\oplus f(1) — the XOR of the two outputs. It is 0 exactly when the function is constant and 1 exactly when it is balanced. So the whole problem is: compute the one bit f(0)\oplus f(1). The catch is that this bit is a global property — it depends on both inputs at once — and a single classical evaluation f(0) or f(1) tells you nothing about it on its own.

The circuit

The whole algorithm is five columns of a circuit. Prepare the two qubits as |0\rangle|1\rangle, put a Hadamard on each wire, fire the oracle U_f once, Hadamard the top wire again, and measure it. That one measured bit is the answer.

Why one query is enough: the algebra

Step 1 — the Hadamards. Starting from |0\rangle|1\rangle, a Hadamard on each qubit gives the balanced pair

(H\otimes H)\,|0\rangle|1\rangle = |{+}\rangle\,|{-}\rangle = \tfrac{1}{\sqrt2}\big(|0\rangle + |1\rangle\big)\otimes|{-}\rangle.

Step 2 — the oracle, via phase kickback. The oracle acts as U_f\,|x\rangle|y\rangle = |x\rangle|y\oplus f(x)\rangle. With the target held in |{-}\rangle, this famously kicks the value of f(x) up into a phase on the first register while leaving the target untouched:

U_f\,|x\rangle|{-}\rangle = (-1)^{f(x)}\,|x\rangle|{-}\rangle.

Applied across the superposition, the first register becomes

\tfrac{1}{\sqrt2}\big[(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\big]\otimes|{-}\rangle.

Pull out the common factor (-1)^{f(0)} (a harmless global phase) and the whole thing hinges on the parity f(0)\oplus f(1):

(-1)^{f(0)}\,\tfrac{1}{\sqrt2}\big[\,|0\rangle + (-1)^{f(0)\oplus f(1)}|1\rangle\,\big]\otimes|{-}\rangle = (-1)^{f(0)}\begin{cases} |{+}\rangle\,|{-}\rangle & \text{if } f(0)\oplus f(1)=0 \ (\text{constant}),\\[2pt] |{-}\rangle\,|{-}\rangle & \text{if } f(0)\oplus f(1)=1 \ (\text{balanced}).\end{cases}

Step 3 — the final Hadamard. Because H|{+}\rangle=|0\rangle and H|{-}\rangle=|1\rangle, the last Hadamard on the top qubit turns that hidden phase pattern into a definite basis state:

\text{constant}\ \longrightarrow\ |0\rangle, \qquad \text{balanced}\ \longrightarrow\ |1\rangle.

Measuring the top qubit therefore returns f(0)\oplus f(1) with certainty — no repeats, no probability, and only one call to the oracle.

Worked example 1: a constant oracle

Take the constant function f(0)=f(1)=1. Both kickback phases are (-1)^1=-1, so after the oracle the top register is

\tfrac{1}{\sqrt2}\big[(-1)^{1}|0\rangle + (-1)^{1}|1\rangle\big] = -\tfrac{1}{\sqrt2}\big(|0\rangle+|1\rangle\big) = -\,|{+}\rangle.

The overall minus is a global phase with no observable effect. The final Hadamard sends |{+}\rangle\mapsto|0\rangle, so H(-|{+}\rangle) = -|0\rangle and the meter reads 0 every single time. Parity check: f(0)\oplus f(1) = 1\oplus 1 = 0 — constant, exactly as the measured bit announced.

Worked example 2: a balanced oracle

Now take the balanced function f(0)=0,\ f(1)=1. The two phases now disagree: (-1)^0=+1 and (-1)^1=-1, giving

\tfrac{1}{\sqrt2}\big[(+1)|0\rangle + (-1)|1\rangle\big] = \tfrac{1}{\sqrt2}\big(|0\rangle-|1\rangle\big) = |{-}\rangle.

The final Hadamard sends |{-}\rangle\mapsto|1\rangle, so the meter reads 1 with certainty. Parity check: f(0)\oplus f(1) = 0\oplus 1 = 1 — balanced. Notice what just happened: the two computational paths interfered. When the phases matched (constant) the |1\rangle amplitude was reinforced into a clean |{+}\rangle; when they clashed (balanced) that same interference produced a clean |{-}\rangle instead. The oracle wrote the answer into the relative phase, and the Hadamard read it out.

The strange, wonderful thing about Deutsch's algorithm is what you end up knowing. You walk away certain whether f is constant or balanced — a genuine fact about the function — yet you never learned f(0) or f(1) individually. The measurement hands you their XOR and nothing else. It is like being told, once and for sure, that two hidden cards are the same colour or different colours without ever being shown either card. Classically that is impossible: the only way to know a relationship between two values is to look at both. Quantum interference lets you evaluate a global combination of all the outputs in a single shot, precisely because the qubit never had to commit to one input — it explored the superposition and let the answers cancel or reinforce. This "compute a joint property, not the individual values" idea is the seed that grows into Deutsch–Jozsa and, eventually, the great quantum speedups.

Do not oversell this. Deutsch's algorithm improves the query count from 2 to 1 — a real, provable separation, but a constant-factor one, not the exponential fireworks people associate with quantum computing. (The exponential version comes with Deutsch–Jozsa, which scales the same idea to n bits.) Second, and just as important: the single measured bit is f(0)\oplus f(1) and only that. You cannot squeeze f(0) or f(1) out of it — the algorithm answers a global question and deliberately throws away the local values. Asking "so what is f(0)?" after running it is a category error: that information was never on the wire you measured. One query buys you exactly one global bit, no more.