Deutsch’s Algorithm

Deutsch's algorithm, published by David Deutsch in 1985, was the first quantum algorithm to outperform every classical algorithm on a well-defined problem. The problem is tiny — determining a single property of a one-bit function — but the solution captures the central idea behind almost every quantum speedup: quantum interference allows the computer to learn a global property of a function in fewer queries than any classical procedure.

The problem

You are given a black-box function $f : \{0,1\} \to \{0,1\}$ (an oracle) and you are allowed to evaluate it. There are four possible functions, split into two families:

Constant: $f(0) = f(1)$ . Either $f \equiv 0$ or $f \equiv 1$ .
Balanced: $f(0) \ne f(1)$ . Either $f(0)=0,f(1)=1$ or $f(0)=1,f(1)=0$ .

The goal is to decide which family $f$ belongs to. Classically, you must query $f$ at least twice (once with input $0$ and once with input $1$ ) — knowing only $f(0)$ leaves the answer ambiguous. Deutsch's algorithm does it in exactly one query.

The quantum oracle

The quantum oracle $U_f$ acts on two qubits: an input register $|x\rangle$ and an output register $|y\rangle$ :

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

where $\oplus$ is addition modulo 2 (XOR). This unitary encoding is reversible by design — applying $U_f$ twice returns the original state, since $(y \oplus f(x)) \oplus f(x) = y$ .

The algorithm step by step

Initialise. Start with $|00\rangle$ . Flip qubit 1 to get $|01\rangle$ , so the output register begins in $|1\rangle$ .

Superpose. Apply a Hadamard to both qubits:

= \tfrac{1}{2}\bigl(|0\rangle + |1\rangle\bigr)\bigl(|0\rangle - |1\rangle\bigr).$$ The output register $|-\rangle = \tfrac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$ is the **phase kickback ancilla**; any $f(x)$ evaluated against it imprints a $(-1)^{f(x)}$ phase on the input. **Query.** Apply $U_f$ once. Using the phase kickback identity $U_f|x\rangle|-\rangle = (-1)^{f(x)}|x\rangle|-\rangle$, the joint state becomes $$\tfrac{1}{\sqrt{2}}\bigl((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle\bigr) \otimes |-\rangle.$$ **Interfere.** Apply $H$ to the input register. Using $H|0\rangle = (|0\rangle+|1\rangle)/\sqrt{2}$ and $H|1\rangle = (|0\rangle-|1\rangle)/\sqrt{2}$, the input register (including its $1/\sqrt{2}$ prefactor) becomes $$\tfrac{1}{2}\bigl(\bigl((-1)^{f(0)}+(-1)^{f(1)}\bigr)|0\rangle + \bigl((-1)^{f(0)}-(-1)^{f(1)}\bigr)|1\rangle\bigr).$$ Working it out case by case: if $f$ is **constant** ($f(0) = f(1)$), the amplitude on $|1\rangle$ vanishes and the input qubit is $|0\rangle$ with probability 1. If $f$ is **balanced** ($f(0) \ne f(1)$), the amplitude on $|0\rangle$ vanishes and the input qubit is $|1\rangle$ with probability 1. **Measure.** Read qubit 0. Outcome $0$ means constant; outcome $1$ means balanced. <Callout type="tip"> The single query suffices because quantum mechanics lets both inputs be probed simultaneously. The Hadamard gates convert the problem into a question about the *parity* $f(0) \oplus f(1)$, which is encoded globally in the relative phase — invisible to classical sampling but revealed by interference. </Callout> ## Try it The exercise uses the balanced oracle $f(0)=0, f(1)=1$, implemented as a CNOT with qubit 0 as control and qubit 1 as target. Complete the circuit by adding the oracle gate and the final Hadamard, then measure qubit 0. A result of $1$ confirms the function is balanced. <RunnableExample />