19. Deutsch's Algorithm

19.1The problem

You are given a one-bit function f: {0,1} → {0,1} as a black box. The function is promised to be either constant (f(0) = f(1)) or balanced (f(0) ≠ f(1)). Question: which is it? The problem looks trivial and is — that is the point. It is the smallest setting in which "a global property of f" can be separated from "the values of f", so it is the cleanest place to watch interference perform a query-computational feat. Deutsch posed it and solved it in 1985, in the first quantum algorithm ever written down; everything in this part is a descendant.

19.2Classical solution

Deterministically you must query f twice: f(0) alone is consistent with both cases, and so is f(1) alone. Two queries always decide it — if the answers agree, constant; else balanced. Randomization cannot help: with one query you see f(x) for one x, and that single bit is compatible with both a constant and a balanced function, so no strategy beats a coin flip. Classical query complexity: exactly 2. The quantum algorithm, we will see, needs exactly 1. A factor of 2 — the smallest possible separation — but a separation with a mechanism, not an accident.

19.3Quantum circuit

q0: |0> ──H──■──H──M        outcome 0 → constant
            │               outcome 1 → balanced
q1: |1> ──H──Uf──            Uf: |x>|y> ↦ |x>|y ⊕ f(x)>

Two qubits. The input register q0 starts in |0⟩; the ancilla q1 starts in |1⟩. Apply H to both, apply the oracle once (control q0, target q1), apply H to q0 again, and measure q0 only. The ancilla is never measured — its job, explained next, is to be in |−⟩ so the oracle acts as a phase. One oracle query, one measurement, a deterministic answer.

19.4Interference

After the Hadamards the state is (|0⟩+|1⟩)/√2 ⊗ |−⟩. Since |−⟩ is an eigenstate of every X-flip, the oracle kicks f back as phase: Uf(|x⟩|−⟩) = (−1)^{f(x)}|x⟩|−⟩. The input register now holds ((−1)^{f(0)}|0⟩ + (−1)^{f(1)}|1⟩)/√2. The final H maps that to amplitudes — for |0⟩: ((−1)^{f(0)}+(−1)^{f(1)})/2, and for |1⟩: ((−1)^{f(0)}−(−1)^{f(1)})/2. If f is constant the two terms add to ±1: you measure 0 with certainty. If f is balanced they cancel to exactly 0: you measure 1 with certainty. Destructive interference between the two queries is the entire computation; the ancilla made it possible by converting values into phases.

19.5Implementation

Build the state vector of two qubits as a length-4 numpy array (index = 2·x + y), the oracle as a permutation matrix, and Hadamards as the 2×2 matrix you already know. The whole algorithm:

import numpy as np

H = np.array([[1, 1], [1, -1]]) / np.sqrt(2)

def deutsch(f):
    psi = np.array([0, 1, 0, 0], dtype=complex)      # |0>|1>
    psi = np.kron(H, H) @ psi                        # H on both qubits
    U = np.zeros((4, 4))                             # oracle permutation
    for x in (0, 1):
        for y in (0, 1):
            U[(x << 1) | (y ^ f(x)), (x << 1) | y] = 1
    psi = U @ psi
    psi = np.kron(H, np.eye(2)) @ psi                # final H on q0
    p0 = abs(psi[0]) ** 2 + abs(psi[1]) ** 2         # P(q0 = 0)
    return "constant" if p0 > 0.5 else "balanced"

The permutation matrix is symmetric because y ↦ y ⊕ f(x) is its own inverse — a small mercy you will not get with general oracles.

19.6Experimental verification

oracles = {"f=0": lambda x: 0, "f=1": lambda x: 1,
           "f=x": lambda x: x, "f=1-x": lambda x: 1 - x}
for name, f in oracles.items():
    answer = deutsch(f)                    # from 19.5
    truth = "constant" if name in ("f=0", "f=1") else "balanced"
    print(name, "->", answer, "| expected:", truth)