Deutsch's Algorithm

Suppose someone hands you a black-box function f that takes a single bit and returns a single bit. You can call f as many times as you want, but you don't get to peek inside. There are exactly four functions it could be: one that returns 0 no matter what you give it; one that always returns 1; one that returns its input unchanged; and one that returns the input flipped. Call them f₀, f₁, f₂, f₃. Two of them — f₀ and f₁ — are constant: they ignore the input. The other two — f₂ and f₃ — are balanced: half the inputs return 0, half return 1.

The classical question: how many queries do you need to decide whether f is constant or balanced? You query f(0). Suppose it returns 0. Could the function be constant (f₀)? Yes. Could it be balanced (f₂)? Also yes. Same input, same output, two different classes. You need f(1) as well to break the tie. Same story whatever f(0) turns out to be. Two queries, every time. No clever encoding gets you out of it.

Deutsch's algorithm — the first textbook quantum routine where the math comes out strictly ahead of the classical lower bound — does it in one. The speedup is small in absolute terms (2 → 1 is not going to break RSA), but it's the first place a quantum circuit beats every possible classical circuit, and the trick behind it is the trick behind every quantum algorithm that came later. The resource Deutsch's circuit exploits isn't parallelism. It is not “the qubit tries both inputs at once and reports back.” The resource is interference: two computational paths through a superposition, set up so the answer you want stays loud and the one you don't cancels itself out.

The four oracles

There are only four single-bit functions, and the classical classification splits them cleanly into two pairs:

The quantum version of an oracle has to be reversible — every quantum gate is — so we can't just have a one-input, one-output box. The standard trick is to give the oracle two qubits: a data qubit x and an ancilla y. The oracle Uf acts as |x⟩|y⟩ ↦ |x⟩|y ⊕ f(x)⟩. It leaves the data alone and XORs f(x) into the ancilla. Setting y = 0 recovers a regular query: read the ancilla, get f(x).

Phase kickback: the actual trick

Prepare the ancilla in the state |−⟩ = (|0⟩ − |1⟩)/√2 instead of |0⟩. Now ask what Uf does to |x⟩|−⟩. The oracle XORs f(x) into the ancilla. If f(x) = 0, the ancilla is untouched. If f(x) = 1, the XOR swaps |0⟩ ↔ |1⟩, which negates |−⟩ (because its |1⟩ coefficient is the negative one). Either way, the ancilla comes out as |−⟩; the only thing that happens is a sign on the whole register:

Read that again. The output of f ended up as a phase on the data qubit. The ancilla is just a workspace we used to convert function output into a sign. This is phase kickback, and it's the whole engine. Without an ancilla in |−⟩ there's no kickback, no sign, nothing to interfere — and Deutsch's algorithm doesn't work. With it, we can prepare the data qubit in a superposition of |0⟩ and |1⟩ and the oracle stamps a sign in front of each branch in a single call.

The full circuit

Five steps. Two qubits. One oracle query.

1. Start in |0⟩|0⟩.
2. Apply X to q₁ — the register is now |0⟩|1⟩ (ancilla in |1⟩).
3. Apply H to both qubits — the register is now |+⟩|−⟩.
4. Apply the oracle Uf. Phase kickback stamps (-1)f(x) on each branch of q₀.
5. Apply H to q₀. The two branches interfere.
6. Measure q₀. If you get 0, f is constant. If you get 1, f is balanced.

Here's the circuit drawn out, specialised to f₂(x) = x (the “identity” oracle, which is just a CNOT with q₀ as control and q₁ as target):

Copy as Qiskit Remix in sandbox →

Run it yourself

Each button below resets the simulator and replays the full Deutsch circuit with one of the four oracles spliced in. Watch the probability bars and the verdict label. The bars show all four basis states |q₁ q₀⟩; q₁ ends up in a 50/50 mix because it's still in |−⟩ (the kickback target), so what matters is the q₀ marginal — sum the bars where q₀ = 0 versus where q₀ = 1. Or just read the verdict; we summed for you.

P(|0⟩) = …, P(|1⟩) = …

Try this: run f₀ then f₂ back to back. Both end with q₀ in a definite state (probability 1), but a different one. f₀ sends q₀ to |0⟩ — constant. f₂ sends q₀ to |1⟩ — balanced. The simulator never “tried both inputs at once.” It evaluated the oracle exactly once, on a superposition, and the second Hadamard turned the resulting phase pattern into a deterministic measurement.

Why it works

After step 3 the register sits in |+⟩|−⟩, which we can rewrite as (|0⟩ + |1⟩)/√2 ⊗ |−⟩. The oracle multiplies each |x⟩ branch by (-1)f(x). The data qubit is now in the state (-1)f(0)|0⟩ + (-1)f(1)|1⟩, up to normalisation. Two cases:

• If f is constant, both signs agree. The data qubit is ±|+⟩ — an equal superposition. Apply H and you get |0⟩. Measurement: 0.
• If f is balanced, the signs disagree. The data qubit is ±|−⟩. Apply H and you get |1⟩. Measurement: 1.

The final Hadamard is the interferometer. The |+⟩ and |−⟩ branches that the oracle prepared interfere constructively or destructively at |0⟩ and |1⟩, and the answer falls out as a bit. We queried the oracle exactly once. We learned a global property of the function — its parity — that no single classical query can distinguish. The catch, of course, is that we learn only the parity; we don't get to ask “what is f(0)?” on the side. The single quantum query buys us one global question, not two local ones. That trade-off — global properties cheap, individual values still expensive — is the shape of every quantum speedup that came after.

Self-test

1. Without running the simulator: if Uf is literally the identity (no oracle gates at all), what state does the data qubit end in after the final Hadamard, and why does that measurement outcome correctly say “constant”? (Check yourself by clicking Run f₀.)
2. The four oracle buttons all leave q₁ in a 50/50 mix between |0⟩ and |1⟩. Why isn't that a problem for reading the verdict — and what would happen if we'd prepared the ancilla in |0⟩ instead of |−⟩? (Hint: no kickback.)

Open the Deutsch circuit (f₂) in the sandbox →

Phase kickback, formally, and the Deutsch-Jozsa generalisation

Start from the oracle's defining action on the computational basis:

$$U_f\,|x\rangle|y\rangle \;=\; |x\rangle\,|y \oplus f(x)\rangle$$

Apply it to $|x\rangle\,|-\rangle$ with $|-\rangle = (|0\rangle - |1\rangle)/\sqrt{2}$:

$$U_f\,|x\rangle\tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle) \;=\; \tfrac{1}{\sqrt{2}}\bigl(|x\rangle|f(x)\rangle - |x\rangle|1 \oplus f(x)\rangle\bigr)$$

If $f(x)=0$ the two terms are $|x\rangle|0\rangle - |x\rangle|1\rangle = |x\rangle|-\rangle$. If $f(x)=1$ they are $|x\rangle|1\rangle - |x\rangle|0\rangle = -|x\rangle|-\rangle$. In both cases:

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

That's the kickback identity. The data qubit picks up a sign that depends on a value of f; the ancilla goes along for the ride.

Plugging it into the Deutsch circuit, after the oracle the data qubit is $\tfrac{1}{\sqrt{2}}\bigl((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\bigr)$. Pull out a global sign and you're looking at $\pm|+\rangle$ when f is constant and $\pm|-\rangle$ when f is balanced. A final Hadamard sends those to $\pm|0\rangle$ and $\pm|1\rangle$ respectively — and measurement is invariant under the global sign.

Deutsch-Jozsa generalises this to an n-bit input. Promised that f from n bits to one is either constant or balanced (exactly half the inputs map to 0, half to 1), the quantum routine — same pattern, with n data qubits in $|+\rangle^{\otimes n}$ — decides in a single oracle query. The classical worst case requires $2^{n-1}+1$ queries (you might get unlucky and see the same output for the first $2^{n-1}$ inputs). That's where exponential separations first show up in the textbook.