Unitary gates, circuits and universality

Between preparation and measurement a closed register evolves by the Schrödinger equation, and while the Hamiltonian is held fixed the solution is U = exp(−iĤt/ħ) with Ĥ Hermitian — a unitary, as is the time-ordered product of such factors when Ĥ varies. A gate is one such U, produced by switching a chosen Hamiltonian on for a chosen time, so whatever else it does it obeys U†U = I. Three consequences follow, and they are the rules of circuit design. Norms are preserved, so ⟨ψ|ψ⟩ = 1 stays 1 and the Born rule keeps working. The inverse exists and is U†, so every gate is reversible: a classical NAND, which maps two bits to one, cannot be a quantum gate, and its reversible replacement is the three-bit Toffoli. And U is linear, so it cannot clone an unknown state or reset a qubit; measurement, which is a projector Pₖ rather than a unitary, is not a gate either and sits outside the circuit box. The check is mechanical: np.allclose(U.conj().T @ U, np.eye(U.shape[0])) — the columns must form an orthonormal set.

Any U in U(2) is e^(iα) times an element of SU(2), and the global phase changes no probability, so what a one-qubit gate does is fixed by an SU(2) matrix. Every such matrix is Rₙ(θ) = exp(−iθ n⋅σ/2) = cos(θ/2) I − i sin(θ/2) n⋅σ, which rotates the Bloch vector by θ about the unit vector n. The half-angle is the double cover at work: θ = 2π gives −I, the same point on the sphere but a sign that a control qubit can detect. Now read the gate list. X = iRₓ(π) is a half-turn about x, swapping the poles. Z = iR_z(π) fixes the poles and flips |+⟩ to |−⟩. H = iRₘ(π) with m = (x + z)/√2 exchanges the x and z axes, which is why HXH = Z. S = e^(iπ/4)R_z(π/2) and T = e^(iπ/8)R_z(π/4) turn the equator by 90° and 45°: T takes |+⟩, Bloch vector (1, 0, 0), to (|0⟩ + e^(iπ/4)|1⟩)/√2, Bloch vector (0.707, 0.707, 0). Because H swaps axes, HTH = e^(iπ/8)Rₓ(π/4) is an eighth-turn about x — two rotation axes from two gates.

Two qubits share C² ⊗ C², a four-dimensional space with basis |00⟩, |01⟩, |10⟩, |11⟩ in that order, so a two-qubit gate is a 4 × 4 unitary. If gate A acts on the left qubit and B on the right, the combined operator is the Kronecker product A ⊗ B, whose entries are (A ⊗ B)_(ij),(kl) = Aᵢₖ Bⱼₗ — every entry of A multiplied by the whole of B. In NumPy that is np.kron(A, B), and the argument order is the qubit order. A gate on the left qubit alone is A ⊗ I; on the right alone, I ⊗ A; and H ⊗ I, written out, is (1/√2) times the block matrix [[I, I], [I, −I]]. CNOT is not built this way. It is |0⟩⟨0| ⊗ I + |1⟩⟨1| ⊗ X — do nothing if the control is |0⟩, apply X if it is |1⟩ — giving the block-diagonal matrix [[I, 0], [0, X]] that swaps the |10⟩ and |11⟩ columns. The distinction is physical. A product gate A ⊗ B maps a Schmidt-rank-1 state to a Schmidt-rank-1 state, so it can never entangle; CNOT, a sum of two products, can, and does.

A circuit is read left to right in time, but operators act on the ket nearest to them first, so the matrix is the product in reverse: gates G₁ then G₂ then G₃ give U = G₃G₂G₁. Take the Bell circuit — H on the left qubit, then CNOT with that qubit as control. U = CNOT⋅(H ⊗ I). Applied to |00⟩ = (1, 0, 0, 0)ᵀ: H ⊗ I gives (1, 0, 1, 0)ᵀ/√2, then CNOT swaps the last two entries, (1, 0, 0, 1)ᵀ/√2 = (|00⟩ + |11⟩)/√2. The input had Schmidt rank 1, the output rank 2 — the CNOT did the entangling. Gates on different qubits in the same time step are Kronecker-multiplied, so one layer of H on both qubits is H ⊗ H; the depth of a circuit is its number of layers and the size its number of gates. Two conventions bite in software: whether the left-most ket is qubit 0 (this lesson, and np.kron) or qubit n − 1 (Qiskit's little-endian ordering), and which qubit is the control — CNOT with control on the right is I ⊗ |0⟩⟨0| + X ⊗ |1⟩⟨1|, a different matrix.

Universality is proved in three steps. First, any unitary on 2ⁿ dimensions is a product of two-level unitaries, acting on only two basis states, and each of those, once controlled-NOTs along a Gray code make its two basis states differ in a single bit, is a multiply-controlled one-qubit gate, which decomposes exactly into CNOTs and single-qubit gates. Second, any single-qubit gate is e^(iα)R_z(β)R_y(γ)R_z(δ) — three Euler rotations about two axes. Third, and this is where T earns its place, R_z(π/4) = T and Rₓ(π/4) = HTH (both up to phase) compose to a single rotation Rₖ(Φ) with cos(Φ/2) = cos²(π/8) = (2 + √2)/4 = 0.8536, so Φ = 62.80°, and Φ/2π is irrational. Powers of an irrational rotation never repeat and come arbitrarily close to any angle about k; conjugating by H gives the same irrational rotation about a second, non-parallel axis, so with the Euler decomposition {H, T} generates rotations dense in SU(2), and with CNOT the products are dense in U(2ⁿ) up to a global phase. Replace T by S and the composite R_z(π/2)Rₓ(π/2) is a 120° rotation about (1, 1, 1)/√3: three applications return to the start. That is the Clifford group {H, S, CNOT}, finite up to phase and, by Gottesman–Knill, classically simulable in polynomial time. Superposition and entanglement it can make; universality it cannot.

Dense is not cheap, and two bills arrive. The first is precision. A finite set never hits a generic rotation exactly, so a target is approximated to within ε in operator norm; the Solovay–Kitaev theorem guarantees this with O(log^c(1/ε)) gates, c ≈ 3.97, and number-theoretic synthesis brings a z-rotation down to about 3 log₂(1/ε) T gates. Errors add at worst linearly: if each of m gates is within ε of its ideal, the whole circuit is within mε, because unitaries preserve norms. So a 2,000-rotation circuit that must be good to 10⁻³ needs each rotation good to 5 × 10⁻⁷, costing about 3 log₂(2 × 10⁶) ≈ 63 T gates apiece — and tightening the tolerance a thousandfold to 10⁻⁶ raises that only to about 93. The second bill is not logarithmic. A generic n-qubit unitary needs at least ⌈(4ⁿ − 3n − 1)/4⌉ CNOTs: three for n = 2, and 262,137 for n = 10. Universality says every unitary is reachable; it says nothing about reaching it in polynomial time, which is why useful quantum algorithms are the rare structured unitaries — Grover's iterate, the QFT — with polynomial-size circuits.