Interference Does the Work

Deutsch's algorithm solves its problem in one oracle query rather than two. The reason is not magic — it is quantum interference. Understanding exactly how interference converts a phase difference into a measurable bit is the key insight that carries forward to every query algorithm you will see.

What the algorithm produces

After the oracle call, the register qubit (qubit 0) is in one of two states:

|\psi\rangle = \begin{cases} \pm\,|{+}\rangle & \text{if } f \text{ is constant,} \\ \pm\,|{-}\rangle & \text{if } f \text{ is balanced.} \end{cases}

Here $|{+}\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$ and $|{-}\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ .

The global sign $\pm$ is unobservable, but the relative sign between the two amplitudes is not: $|{+}\rangle$ has a $+$ relative sign; $|{-}\rangle$ has a $-$ relative sign. These are orthogonal states, and the final Hadamard maps them back onto the computational basis so a measurement can distinguish them.

Phase kickback plants the relative sign

Before the oracle, the ancilla qubit is prepared in $|{-}\rangle$ . When the oracle applies $|x\rangle|y\rangle \mapsto |x\rangle|y \oplus f(x)\rangle$ , the XOR with the $|{-}\rangle$ ancilla does not change the ancilla's state — instead it kicks back a phase factor to the input qubit (a global phase on each |x⟩ component, which becomes a relative phase once x is in superposition):

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

So for the superposition $|{+}\rangle|{-}\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)|{-}\rangle$ , the oracle produces

\frac{(-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle}{\sqrt{2}} \otimes |{-}\rangle.

If $f$ is constant, both signs are the same, so the register qubit is $\pm|{+}\rangle$ . If $f$ is balanced ( $f(0) \ne f(1)$ ), the signs differ by exactly $-1$ , giving $\pm|{-}\rangle$ .

Constructive vs destructive interference closes the case

The final Hadamard on the register qubit transforms:

H|{+}\rangle = |0\rangle, \qquad H|{-}\rangle = |1\rangle.

This is interference in action. For a constant function, the two amplitudes entering the Hadamard have the same sign, so they add constructively toward $|0\rangle$ and destructively away from $|1\rangle$ . For a balanced function, the opposite signs cause constructive interference toward $|1\rangle$ and complete cancellation at $|0\rangle$ .

A single measurement then yields 0 (constant) or 1 (balanced) with certainty — revealing a global property of the function from a single query.

Why classical methods need two queries

Classically, evaluating $f$ at one point tells you only $f(0)$ or $f(1)$ in isolation. To compare them you must call the oracle twice. There is no way to simultaneously probe both inputs without superposition, and there is no mechanism to cancel one outcome against another without interference. The quantum algorithm does both at once: superposition evaluates $f(0)$ and $f(1)$ in a single call, and interference translates the phase difference into a distinguishable measurement outcome.