Malcolm Low | Practical AI, Computing & Quantum Research

Singapore-based practical guides, tutorials and experiments in AI, computing, modelling, simulation, optimisation and quantum computing, with research notes and hands-on workflows.

,

Deutsch’s Algorithm in Quantum Computing: The 4 Cases

Deutsch’s algorithm explained: the four one-bit Boolean functions, the reversible oracle, and the single-query circuit that beats the classical two.

·

Written by

Malcolm Low
Part of the Quantum Computing: A Complete Learning Path series.
QUANTUM SERIES 2026
The four Boolean functions, the reversible oracle, and the single-query Deutsch circuit with full derivation.

Deutsch’s Algorithm determines whether a single-bit function f(x) is constant (f(0) = f(1)) or balanced (f(0) ≠ f(1)) using only one oracle query. To understand how the algorithm works, we first need to see how each possible function is physically realised as a reversible quantum gate, and then how the complete Deutsch circuit encodes that function into a measurable phase difference.

1  ·  The 4 Possible Functions

With a single input bit x ∈ {0,1} and output bit f(x) ∈ {0,1}, there are exactly four possible Boolean functions. Two are constant (output ignores the input) and two are balanced (output depends on the input).

# Name f(0) f(1) Gate implementation Type
1 Constant Zero 0 0 Identity — no gates needed Constant
2 Constant One 1 1 X gate on output wire only Constant
3 Balanced ID 0 1 CNOT (x = control, y = target) Balanced
4 Balanced NOT 1 0 X on x, CNOT, X on x (flip, copy, restore) Balanced

The four reversible oracles, including both constant and both balanced cases:

Circuit diagrams for Deutsch’s four reversible oracles: constant zero, constant one, balanced identity, and balanced NOT.
The four reversible oracles implement the mapping (x, y) ↦ (x, y ⊕ f(x)).
Key point: both constant oracles leave the x wire untouched and act only on y. Both balanced oracles use x as a control and output y ⊕ f(x) on the target wire. All four are reversible, which is required for quantum computation.

2  ·  The General Oracle Uf

All four functions are wrapped in a single reversible gate Uf that leaves the input register unchanged and XORs the function value into the output register:

Uf |x⟩|y⟩  =  |x⟩ |y ⊕ f(x)⟩

As a two-wire circuit, Uf passes x unchanged on the top wire while the bottom wire carries y ⊕ f(x). The box spans both wires to show they are processed jointly by a single gate:

General oracle U_f: x is unchanged and the lower wire exits as y ⊕ f(x).
The oracle passes x through unchanged and maps y to y ⊕ f(x).

The reversibility of Uf is guaranteed because XOR is its own inverse: applying Uf twice returns the original state. This property allows quantum algorithms to query f without destroying the superposition.

With the target prepared in |−⟩ = (|0⟩ − |1⟩)/√2, each fixed x branch explains the factor (−1)f(x). If f(x) = 0, the target is not flipped and |−⟩ is unchanged (+1). If f(x) = 1, the oracle applies X, and X|−⟩ = (|1⟩ − |0⟩)/√2 = −|−⟩. Thus the target returns to |−⟩ while that x branch acquires a minus sign: Uf|x⟩|−⟩ = (−1)f(x)|x⟩|−⟩. When x is in superposition, this becomes a relative phase on its branches.

For the eigenstate derivation behind this sign, see Understanding Phase Kickback in Quantum Computing.

3  ·  The Complete Deutsch Circuit

The algorithm wraps Uf in Hadamard gates on both wires. Initialise q[0] = |0⟩ and q[1] = |1⟩, apply H to both, query Uf once, apply a final H to q[0], then measure q[0]:

Deutsch algorithm circuit with checkpoints φ₀ after initialization, φ₁ after Hadamards, and φ₂ after the oracle.
Circuit checkpoints: φ₀ after initialization, φ₁ after the Hadamards, and φ₂ after U_f.

The three states at each checkpoint:

State Expression Note
|φ₀⟩ |0⟩|1⟩ Initialisation
|φ₁⟩ |+⟩|−⟩ = ½(|0⟩+|1⟩)(|0⟩−|1⟩) After both H gates
|φ₂⟩ (1/√2)[(−1)^f(0)|0⟩+(−1)^f(1)|1⟩] ⊗ |−⟩ After Uf, before final H
The target qubit q[1] stays in |−⟩ throughout. Only the phase of q[0] changes, carrying the function information via kickback.

4  ·  Mathematical Proof

The full derivation follows four steps. Each is exact; no approximation is involved.

Step 1 — Initialisation:
  |φ₀⟩ = |0⟩|1⟩

Step 2 — Apply H to both wires:
  |φ₁⟩ = |+⟩|−⟩
       = (1/√2)(|0⟩ + |1⟩) ⊗ (1/√2)(|0⟩ − |1⟩)

Step 3 — Apply U_f (phase kickback on |−⟩ target):
  U_f |x⟩|−⟩ = (−1)^f(x) |x⟩|−⟩

  |φ₂⟩ = (1/√2)[ (−1)^f(0)|0⟩ + (−1)^f(1)|1⟩ ] ⊗ |−⟩

Step 4 — Apply H to q[0] and inspect cases:

  Constant  f(0) = f(1) = c:
    |φ₂⟩ = (−1)^c (1/√2)(|0⟩ + |1⟩) ⊗ |−⟩
    After H: (−1)^c |0⟩ ⊗ |−⟩  →  Measure 0

  Balanced case 1: f(0) = 0, f(1) = 1:
    |φ₂⟩ = (1/√2)(|0⟩ − |1⟩) ⊗ |−⟩ = |−⟩ ⊗ |−⟩
    After H on q[0]: |1⟩ ⊗ |−⟩  →  Measure 1

  Balanced case 2: f(0) = 1, f(1) = 0:
    |φ₂⟩ = (1/√2)(−|0⟩ + |1⟩) ⊗ |−⟩ = −|−⟩ ⊗ |−⟩
    After H on q[0]: −|1⟩ ⊗ |−⟩  →  Measure 1

  In the second case the leading minus is a global phase, so it does not change the measurement result.
The global phase (−1)^c in the constant case is unobservable. All that matters is whether the amplitudes on |0⟩ and |1⟩ are in phase (constant) or out of phase (balanced), which the final H converts to a deterministic measurement.

5  ·  Final Measurement

The measurement of q[0] after the final Hadamard gives a deterministic result in both cases:

Measure q[0] Function type Why
0 Constant f(0) ⊕ f(1) = 0; amplitudes add constructively on |0⟩
1 Balanced f(0) ⊕ f(1) = 1; amplitudes cancel on |0⟩, survive on |1⟩

A classical algorithm must evaluate f(0) and f(1) separately, requiring two queries. Deutsch’s algorithm queries Uf exactly once, using superposition to probe both inputs simultaneously and interference to extract a global property of the function. This is the first demonstrated quantum computational advantage over any classical approach.

The technique introduced here — query in superposition, encode information as phase, extract via interference — is the blueprint for Deutsch-Jozsa, Simon’s algorithm, and ultimately Shor’s factoring algorithm.
About the author

Malcolm Low is an Associate Professor at the Singapore Institute of Technology, writing on quantum computing, programming, and applied computing from Singapore.

Website: malcolmlow.com  ·  Singapore

Quantum Series 2026  ·  Built with Qiskit 1.x

✦ This article was generated with the assistance of Claude by Anthropic ✦

Frequently Asked Questions

What is Deutsch’s algorithm?

Deutsch’s algorithm was the first quantum algorithm shown to outperform any classical algorithm. It determines whether a one-bit Boolean function is constant or balanced using a single query, versus the two queries a classical approach requires.

Why does Deutsch’s algorithm only need one query?

It uses phase kickback and superposition to evaluate the function on both possible inputs simultaneously, then uses interference to extract the answer from a single measurement.

What are the four cases in Deutsch’s algorithm?

The four possible one-bit Boolean functions are: always return 0, always return 1, return the input unchanged, and return the input’s negation. The first two are “constant,” the last two are “balanced.”

Is Deutsch’s algorithm useful in practice?

Not directly — it solves a toy problem — but it demonstrates the core quantum principles (superposition, interference, phase kickback) that underlie every practical quantum algorithm, including Grover’s and Shor’s. For the multi-qubit generalization that turns this principle into an exponential speedup, see our guide to The Deutsch-Jozsa Algorithm.

Continue the Quantum Series
← Previous: Phase kickback
Multi-Qubit Scaling: The Deutsch-Jozsa Algorithm →

Comments

One response to “Deutsch’s Algorithm in Quantum Computing: The 4 Cases”

  1. Draw Quantum Diagrams with Matplotlib on Termux Avatar
    Draw Quantum Diagrams with Matplotlib on Termux

    […] same Matplotlib-first workflow was later used for the three reviewed figures in Deutsch’s Algorithm in Quantum Computing: The 4 Cases. Those circuit diagrams were drawn directly with Matplotlib—not Qiskit’s circuit drawer—after […]

    Like

    Reply

Leave a comment

More posts