Deutsch's Algorithm determines whether a function f(x) is constant or balanced using only a single query. Before getting to the quantum circuit, it helps to see how the four possible single-bit functions are physically built.
The 4 Possible Functions
With one input bit, there are exactly four Boolean functions. Two are constant (the output ignores the input) and two are balanced (the output depends on the input). In each oracle the bottom input is set to 0 so the output wire carries exactly f(x).
| # | Name | Function | Type |
|---|---|---|---|
| 1 | Constant Zero | f(x) = 0 | Constant (identity, no gates) |
| 2 | Constant One | f(x) = 1 | Constant (X on the output wire) |
| 3 | Balanced ID | f(x) = x | Balanced (CNOT) |
| 4 | Balanced NOT | f(x) = ¬x | Balanced (X, CNOT, X) |
The General Oracle (U_f)
Every oracle is wrapped in the standard reversible form. It leaves the input register alone and XORs f(x) into the output register:
U_f |x⟩|y⟩ = |x⟩ |y ⊕ f(x)⟩
The Complete Circuit
To detect the function type in one shot, initialise the bottom wire to |1⟩ and use Hadamard gates to build superposition on both wires before and after the oracle:
|0⟩ ──[H]──╤═════╤──[H]──[M]
│ U_f │
|1⟩ ──[H]──╧═════╧───────────
The top wire is the control, the bottom wire is the target prepared in |−⟩. The oracle's (−1)^f(x) phase is kicked back onto the top wire, and the final Hadamard converts that phase difference into a measurable 0 or 1.
Mathematical Proof
1. Initialisation: |ψ₀⟩ = |0⟩|1⟩
2. Superposition: |ψ₁⟩ = |+⟩|−⟩ = ½(|0⟩ + |1⟩)(|0⟩ − |1⟩)
3. The kickback: U_f |x⟩|−⟩ = (−1)^f(x) |x⟩|−⟩
the function output is pushed into the phase of the top qubit.
4. Global state: |ψ₂⟩ = (1/√2) [ (−1)^f(0)|0⟩ + (−1)^f(1)|1⟩ ] ⊗ |−⟩
Final Measurement
After the last Hadamard on the top qubit, the relative phase between the two terms decides the outcome:
If f(0) = f(1) (constant) the top qubit collapses to ±|+⟩, so the final H gives measure 0.
If f(0) ≠ f(1) (balanced) it collapses to ±|−⟩, so the final H gives measure 1.
A single oracle query distinguishes constant from balanced, where any classical approach needs two. That one-query advantage is the seed of Deutsch-Jozsa, Simon's, and ultimately Shor's algorithm.
Part of the Quantum Series 2026. Originally published on Techucation, where the circuit diagrams are rendered in full.
