Deutsch’s Algorithm

qc/algorithms qc/gates

The first concrete proof that a quantum computer can need fewer queries than any classical algorithm. Deutsch’s problem: given a function $f:\{0,1\}\to \{0,1\}$ as a black-box oracle, determine whether $f$ is constant ($f(0)=f(1)$) or balanced ($f(0)\ne f(1)$). Classically, this needs 2 queries to be certain (evaluate $f(0)$ and $f(1)$, compare). Deutsch’s algorithm does it in 1 query.

The oracle and phase kickback

The oracle is a unitary $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$ — reversible, since classical $f$ generally isn’t. Key insight — phase kickback: if the target qubit is prepared in $|-⟩=\frac{1}{\sqrt{2}}(|0⟩-|1⟩)$ instead of a computational basis state, applying $U_f$ leaves $|-⟩$ unchanged but writes $f(x)$ into the phase of the query register instead:

$U_f|x⟩|-⟩=(-1{)}^{f(x)}|x⟩|-⟩$

This is because $U_f$ flips the target qubit iff $f(x)=1$, and flipping $|-⟩$ just gives $-|-⟩$.

Circuit and derivation

Prepare $|0⟩|1⟩$, apply $H$ to both qubits, apply $U_f$, apply $H$ to the first qubit, measure it.

$|{\psi }_0⟩=|0⟩|1⟩\stackrel{H\otimes H}{\to }|{\psi }_1⟩=|+⟩|-⟩$

Applying $U_f$ via phase kickback on each branch of the query register’s superposition:

$|{\psi }_2⟩=\frac{1}{\sqrt{2}}[(-1{)}^{f(0)}|0⟩+(-1{)}^{f(1)}|1⟩]\otimes |-⟩=(-1{)}^{f(0)}\frac{1}{\sqrt{2}}[|0⟩+(-1{)}^{f(0)\oplus f(1)}|1⟩]\otimes |-⟩$

Applying $H$ to the first qubit: $H\frac{1}{\sqrt{2}}(|0⟩+|1⟩)=|0⟩$ if $f(0)\oplus f(1)=0$, or $H\frac{1}{\sqrt{2}}(|0⟩-|1⟩)=|1⟩$ if $f(0)\oplus f(1)=1$. So:

$|{\psi }_3⟩=(-1{)}^{f(0)}|f(0)\oplus f(1)⟩\otimes |-⟩$

Measuring the first qubit gives $f(0)\oplus f(1)$ exactly: outcome 0 means constant, outcome 1 means balanced — determined with a single call to $U_f$, using the interference set up by the two Hadamards around it.

Related

• Quantum Speedup — Ingredients and Myths
• The Deutsch-Jozsa Algorithm — the n-qubit generalization
• H Gate
• Measurement and Collapse

Self-Check

• Could you explain phase kickback — why does $U_f$ acting on $|-⟩$ change the phase instead of the state?
• Why does Deutsch’s algorithm need only 1 query when classically you need 2?
• What would happen to the final measurement outcome if you skipped the first Hadamard layer?