Solovay-Kitaev Theorem

Guarantees that any discrete universal gate set fills the unitary group efficiently, with only polylogarithmic overhead.

Statement

The Solovay-Kitaev theorem says: given a finite gate set that generates a dense subgroup of SU(2) (or SU(d)) and is closed under inverses, any target unitary can be approximated to precision ε using a sequence of only O(log^c(1/ε)) gates, where the exponent c is a small constant near 3 to 4 for the standard algorithm.

Why it matters

Fault-tolerant hardware offers only a discrete set of gates — typically Clifford+T — because those are the ones that can be protected by error-correcting codes. Arbitrary rotations must be approximated. Without Solovay-Kitaev, the required gate count might grow polynomially in 1/ε, which would be ruinous; the theorem promises the far gentler polylogarithmic growth.

How the algorithm works

The construction is recursive. A base level supplies a coarse net of achievable unitaries. Each higher level uses group-commutator identities — products of the form V W V† W† — to build a finer approximation from two slightly-better approximations of related unitaries. Precision improves super-linearly at each level, giving the logarithmic depth.

def sk_recurse(U, n, base_approx, gc_decompose):
    if n == 0:
        return base_approx(U)
    Un1 = sk_recurse(U, n-1, base_approx, gc_decompose)
    V, W = gc_decompose(U @ Un1.conj().T)
    Vn1 = sk_recurse(V, n-1, base_approx, gc_decompose)
    Wn1 = sk_recurse(W, n-1, base_approx, gc_decompose)
    return Vn1 @ Wn1 @ Vn1.conj().T @ Wn1.conj().T @ Un1

Modern refinements

For the specific Clifford+T set, number-theoretic algorithms (Ross-Selinger) beat generic Solovay-Kitaev, achieving near-optimal T-counts of about 3·log2(1/ε) for single-qubit z-rotations. Solovay-Kitaev remains the general guarantee that any universal discrete set is efficient. See Clifford+T synthesis and gate synthesis.