Deutsch Gate

A three-qubit controlled rotation that was the first single gate proven universal for quantum computation.

Definition

The Deutsch gate D(θ) is a three-qubit gate: it applies i·RX(θ), a rotation about X, to the third qubit if and only if the first two qubits are both |1⟩. It generalizes the Toffoli, which is the special case θ = π. David Deutsch introduced it in 1989 as the first gate proven to be universal by itself.

Matrix (active 2×2 block)

The full 8×8 matrix is the identity on the six basis states where the first two qubits are not both |1⟩, and equals the block above on the {|110⟩, |111⟩} pair. When θ = π the block becomes the pure NOT of the Toffoli up to phase.

Universality

Deutsch showed that if θ is an irrational multiple of π, repeated applications of D(θ) generate a dense subgroup of the unitary group, so the single gate approximates any quantum operation to arbitrary accuracy. This was the foundational proof that a finite gate set — even a single gate — suffices for universal quantum computation.

import numpy as np
def deutsch(theta):
    m = np.eye(8, dtype=complex)
    c, s = 1j*np.cos(theta/2), np.sin(theta/2)
    m[6,6]=c; m[7,7]=c; m[6,7]=s; m[7,6]=s
    return m

Legacy

Later work moved to two-qubit universal sets that are easier to build, but the Deutsch gate remains the historical milestone. Its irrational-angle argument foreshadows the Solovay-Kitaev theorem, which quantifies how efficiently a discrete gate set can fill the unitary group. See Solovay-Kitaev and Barenco gate.