Density says a finite gate set gets arbitrarily close to any gate. Solovay and Kitaev showed it gets there fast: accuracy ε costs only polylogarithmically many gates, thanks to one algebraic trick, the group commutator.
What you’ll learn
State the Solovay–Kitaev theorem precisely, including its hypotheses (inverse-closure, density) and the exponents for length and runtime.
Prove that group commutators of near-identity elements are second order and contract approximation errors from ε to ε3/2.
Solve the recursion to obtain c=log5/log23≈3.97 and c′=log3/log23≈2.71.
Derive the Ω(log(1/ε)) volume lower bound, and explain which gate sets and algorithms attain it.
The theorem, precisely
Fix a finite gate set G⊂SU(d). Global phases are irrelevant, so we work in SU(d) with distance ∥U−V∥. Two hypotheses matter: G is closed under inverses (g∈G⇒g†∈G), and the group ⟨G⟩ it generates is dense in SU(d).
A set S⊂SU(d) is an ε-net if every U∈SU(d) lies within ε of some element of S.
The group-commutator trick
The engine of the proof: if V and W are δ-close to the identity, their group commutator[V,W]gp=VWV†W† is only O(δ2) away from it, and it barely notices small errors in V and W.
DerivationCommutators are second order
V=e−iA,W=e−iB,A,BHermitian,∥A∥,∥B∥≤δ
Write near-identity elements through their generators.
VWV†W†=exp(−[A,B]+O(δ3))
Baker–Campbell–Hausdorff: the first-order terms cancel, and the leading term is the Lie bracket, of size O(δ2).
Rx(φ)Ry(φ)Rx(φ)†Ry(φ)†≈Rz(φ2)
Example: A=2φX and B=2φY give −[A,B]=−4φ22iZ=−i2φ2Z. Exactly, the commutator is a rotation by ϑ with sin2ϑ=2sin22φ1−sin42φ, about an axis tilted slightly away from z.
Balanced commutator lemma. Conversely, every U∈SU(2) with ∥U−I∥≤ε is exactly a group commutator VWV†W† with ∥V−I∥,∥W−I∥≤Cε. Choose φ so that the x/y commutator above has the same rotation angle as U, then conjugate V and W by a rotation that carries the commutator's axis onto U's axis.
Predict before you look
V and W are rotations by φ=0.1 rad about x and y. About what angle, in radians, is their group commutator?
Show the answer
0.01 rad
ϑ≈φ2=0.01 rad (exactly 0.00999). Four rotations by 0.1 rad nearly cancel, leaving a rotation ten times smaller. The recursion exploits exactly this quadratic shrinkage.
The recursion and its exponents
The algorithm SK(U,n) returns a word approximating U within εn. Level 0 is a lookup in a precomputed ε0-net, for instance all words up to some length ℓ0, found once by brute force.
text
SK(U, n):
if n == 0:
return the word in the base ε0-net closest to U
U1 = SK(U, n-1) # ‖U − U1‖ ≤ ε(n−1)
Δ = U · U1† # ‖Δ − I‖ ≤ ε(n−1)
V, W = balanced_commutator(Δ) # Δ = V W V† W†, ‖V − I‖, ‖W − I‖ = O(√ε(n−1))
V1 = SK(V, n-1)
W1 = SK(W, n-1)
return V1 · W1 · V1† · W1† · U1 # inverse of a word = reversed word of inverses
Five sub-words per level, but only three recursive calls (U1, V1, W1).
Unitary invariance of the norm (U=ΔU1), then error contraction. The error of U1 does not accumulate, because Δ is computed from U1 exactly.
an:=C2εn=an−13/2=a0(3/2)n
The accuracy improves doubly exponentially in n, provided the base net is fine enough: ε0<1/C2.
(23)n≥log(1/a0)log(1/(C2ε))⟹n=O(loglog(1/ε))
Levels needed for accuracy ε.
Ln=5Ln−1=5nℓ0=O((logε1)log5/log(3/2))
Because 5n=((3/2)n)log5/log(3/2) and (3/2)n=Θ(log(1/ε)).
Tn=3Tn−1+O(1)=O((logε1)log3/log(3/2))
Three recursive calls per level, and O(1) matrix work for fixed d; the word is returned as this recursive description (writing it out in full takes time proportional to its length). Numerically, log5/log1.5≈3.97 and log3/log1.5≈2.71.
Check your understanding
Where exactly does this proof use that G is closed under inverses?
In building the base ε0-net
In writing V1† and W1† as words over G
In the Baker–Campbell–Hausdorff expansion
Nowhere; it is only a convenience
Show the answer
B. In writing V1† and W1† as words over G
The output V1W1V1†W1†U1 needs inverses of words, hence inverses of generators. Without inverse-closure they must be approximated separately; Bouland and Giurgica-Tiron (2021) gave an inverse-free Solovay–Kitaev algorithm that still achieves polylogarithmic length, with a larger exponent.
Lower bounds, optimal sets and the frontier
DerivationThe volume lower bound
#{words of length≤L}≤ℓ=0∑Lgℓ≤2gL
With g=∣G∣≥2.
vol(Bε(V))≈κεD,D=dimSU(d)=d2−1
Small balls in a D-dimensional manifold, with Haar measure normalized to total volume 1.
2gL⋅κεD≥1⟹L≥loggDlog(1/ε)−log(2κ)
The balls around all words must cover the group. For SU(2): L≥3log(1/ε)/logg−O(1).
For n-qubit circuits, D=4n−1 and each gate is one of O(gn2) placements, so generic n-qubit unitaries need Ω(4nlog(1/ε)/logn) gates.
So Solovay–Kitaev is optimal up to the exponent: log(1/ε) is necessary and log3.97(1/ε) suffices. Can a gate set reach the lower bound? Harrow, Recht and Chuang (2002) showed that sets with a spectral gap (for the random walk they generate on SU(2)) admit O(log(1/ε))-length approximations, building on Lubotzky, Phillips and Sarnak's arithmetic constructions; their argument is not an efficient algorithm. Bourgain and Gamburd (2008) proved such a gap for every dense set with algebraic entries.
For Clifford+T, number theory even makes the optimum computable: Ross and Selinger's algorithm reaches T-count 3log2(1/ε)+O(loglog(1/ε)) (see the synthesis deep dive).
Key takeaways
Solovay–Kitaev: for any finite, inverse-closed, dense G⊂SU(d), accuracy ε costs O(logc(1/ε)) gates, found in time O(logc′(1/ε)).
The engine is the group commutator: near the identity it is second order, so approximating the factors within ε gives the commutator within ε3/2.
Five sub-words and three recursive calls per level give c=log5/log23≈3.97 and c′=log3/log23≈2.71.
Volume counting forces Ω(log(1/ε)); spectral-gap gate sets and number-theoretic Clifford+T synthesis attain it up to constants.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Question 1
Which hypothesis is not needed for the standard Solovay–Kitaev theorem?
The gate set is finite
The gate set is closed under inverses
The generated group is dense in SU(d)
The gate entries are algebraic numbers
Show the answer
D. The gate entries are algebraic numbers
Solovay–Kitaev needs a finite, inverse-closed set generating a dense subgroup; arithmetic properties of the entries play no role. They matter for the optimalO(log(1/ε)) results via spectral gaps (Bourgain–Gamburd).
Question 2
In the recursion, the error contracts as εn∝εn−13/2 and the length grows as Ln=5Ln−1. If a cleverer step gave εn∝εn−12 with still Ln=5Ln−1, what length exponent c would result?
log5/log2≈2.32
log5/log1.5≈3.97
5/2
1
Show the answer
A.log5/log2≈2.32
Now εn∼ε02n, so n≈log2log(1/ε) levels suffice and L=5n=loglog25(1/ε). In general c=log(branching)/log(contraction exponent).
Question 3
For a gate set of g elements in SU(2), the counting argument shows that a typical target needs length at least about
log(1/ε)/logg
3log(1/ε)/logg
log3.97(1/ε)
1/ε3
Show the answer
B.3log(1/ε)/logg
SU(2) is three-dimensional, so an ε-net needs ∼ε−3 points, while only ∼gL words exist: L≳3log(1/ε)/logg.
Question 4
Why does the group commutator of two near-identity unitaries drive the recursion?
It is always exactly the identity
It commutes with every element of G
Its distance from I is second order, and errors in its factors enter only at order δη
It turns SU(2) into a finite group
Show the answer
C. Its distance from I is second order, and errors in its factors enter only at order δη
For ∥V−I∥,∥W−I∥≤δ, the commutator is O(δ2) from I, and replacing V,W by η-approximations changes it by only O(δη+η2). That turns accuracy ε into ε3/2 at each level.
Further reading
A. Yu. Kitaev, "Quantum computations: algorithms and error correction", Russian Math. Surveys 52, 1191 (1997).
A. Yu. Kitaev, A. H. Shen & M. N. Vyalyi, Classical and Quantum Computation (AMS, 2002).
C. M. Dawson & M. A. Nielsen, "The Solovay–Kitaev algorithm", Quantum Inf. Comput. 6, 81 (2006), arXiv:quant-ph/0505030.
A. W. Harrow, B. Recht & I. L. Chuang, "Efficient discrete approximations of quantum gates", J. Math. Phys. 43, 4445 (2002).
G. Kuperberg, "Breaking the cubic barrier in the Solovay–Kitaev algorithm" (2023).