Simple Algorithm
Quantum Computing · Rydberg State · 32 min

The Solovay–Kitaev Theorem

Efficient approximation with a finite gate set.

Density says a finite gate set gets arbitrarily close to any gate. Solovay and Kitaev showed it gets there fast: accuracy ε\varepsilon 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 ε\varepsilon to ε3/2\varepsilon^{3/2}.
  • Solve the recursion to obtain c=log⁡5/log⁡32≈3.97c=\log5/\log\tfrac32\approx3.97 and c′=log⁡3/log⁡32≈2.71c'=\log3/\log\tfrac32\approx2.71.
  • Derive the Ω(log⁡(1/ε))\Omega(\log(1/\varepsilon)) volume lower bound, and explain which gate sets and algorithms attain it.

The theorem, precisely

Fix a finite gate set G⊂SU(d)\mathcal{G}\subset SU(d). Global phases are irrelevant, so we work in SU(d)SU(d) with distance ∥U−V∥\norm{U-V}. Two hypotheses matter: G\mathcal{G} is closed under inverses (g∈G⇒g†∈Gg\in\mathcal{G}\Rightarrow g^\dagger\in\mathcal{G}), and the group ⟨G⟩\langle\mathcal{G}\rangle it generates is dense in SU(d)SU(d).

A set S⊂SU(d)S\subset SU(d) is an ε\varepsilon-net if every U∈SU(d)U\in SU(d) lies within ε\varepsilon of some element of SS.

The group-commutator trick

The engine of the proof: if VV and WW are δ\delta-close to the identity, their group commutator [V,W]gp=VWV†W†[V,W]_{\mathrm{gp}} = VWV^\dagger W^\dagger is only O(δ2)\order{\delta^2} away from it, and it barely notices small errors in VV and WW.

DerivationCommutators are second order
  1. V=e−iA,W=e−iB,A,B Hermitian,∥A∥,∥B∥≤δV = e^{-iA},\quad W = e^{-iB},\qquad A,B\ \text{Hermitian},\quad \norm{A},\norm{B}\le\delta

    Write near-identity elements through their generators.

  2. VWV†W†=exp⁡ ⁣(−[A,B]+O(δ3))VWV^\dagger W^\dagger = \exp\!\big(-[A,B] + \order{\delta^3}\big)

    Baker–Campbell–Hausdorff: the first-order terms cancel, and the leading term is the Lie bracket, of size O(δ2)\order{\delta^2}.

  3. Rx(φ) Ry(φ) Rx(φ)† Ry(φ)†≈Rz(φ2)R_x(\varphi)\,R_y(\varphi)\,R_x(\varphi)^\dagger\,R_y(\varphi)^\dagger\approx R_z(\varphi^2)

    Example: A=φ2XA = \tfrac{\varphi}{2}X and B=φ2YB=\tfrac{\varphi}{2}Y give −[A,B]=−φ24 2iZ=−iφ22Z-[A,B] = -\tfrac{\varphi^2}{4}\,2iZ = -i\tfrac{\varphi^2}{2}Z. Exactly, the commutator is a rotation by ϑ\vartheta with sin⁡ϑ2=2sin⁡2φ21−sin⁡4φ2\sin\tfrac{\vartheta}{2} = 2\sin^2\tfrac{\varphi}{2}\sqrt{1-\sin^4\tfrac{\varphi}{2}}, about an axis tilted slightly away from zz.

  4. Balanced commutator lemma. Conversely, every U∈SU(2)U\in SU(2) with ∥U−I∥≤ε\norm{U-\id}\le\varepsilon is exactly a group commutator VWV†W†VWV^\dagger W^\dagger with ∥V−I∥,∥W−I∥≤Cε\norm{V-\id},\norm{W-\id}\le C\sqrt{\varepsilon}. Choose φ\varphi so that the xx/yy commutator above has the same rotation angle as UU, then conjugate VV and WW by a rotation that carries the commutator's axis onto UU's axis.

Predict before you look

VV and WW are rotations by φ=0.1\varphi = 0.1 rad about xx and yy. About what angle, in radians, is their group commutator?

Show the answer

0.01 rad

ϑ≈φ2=0.01\vartheta\approx\varphi^2 = 0.01 rad (exactly 0.009990.00999). Four rotations by 0.10.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)\mathrm{SK}(U,n) returns a word approximating UU within εn\varepsilon_n. Level 00 is a lookup in a precomputed ε0\varepsilon_0-net, for instance all words up to some length ℓ0\ell_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 (U1U_1, V1V_1, W1W_1).

DerivationSolving the recursion
  1. ∥V1W1V1†W1† U1−U∥=∥V1W1V1†W1†−Δ∥≤C εn−13/2=:εn\norm{V_1W_1V_1^\dagger W_1^\dagger\,U_1 - U} = \norm{V_1W_1V_1^\dagger W_1^\dagger - \Delta}\le C\,\varepsilon_{n-1}^{3/2} =: \varepsilon_n

    Unitary invariance of the norm (U=ΔU1U = \Delta U_1), then error contraction. The error of U1U_1 does not accumulate, because Δ\Delta is computed from U1U_1 exactly.

  2. an:=C2εn=an−13/2=a0(3/2)na_n := C^2\varepsilon_n = a_{n-1}^{3/2} = a_0^{(3/2)^n}

    The accuracy improves doubly exponentially in nn, provided the base net is fine enough: ε0<1/C2\varepsilon_0 < 1/C^2.

  3. (32)n≥log⁡(1/(C2ε))log⁡(1/a0)⟹n=O(log⁡log⁡(1/ε))\Big(\tfrac{3}{2}\Big)^{n}\ge\frac{\log\big(1/(C^2\varepsilon)\big)}{\log(1/a_0)}\quad\Longrightarrow\quad n = \order{\log\log(1/\varepsilon)}

    Levels needed for accuracy ε\varepsilon.

  4. Ln=5 Ln−1=5nℓ0=O((log⁡1ε)log⁡5/log⁡(3/2))L_n = 5\,L_{n-1} = 5^n\ell_0 = \order{\Big(\log\tfrac{1}{\varepsilon}\Big)^{\log 5/\log(3/2)}}

    Because 5n=((3/2)n)log⁡5/log⁡(3/2)5^n = \big((3/2)^n\big)^{\log5/\log(3/2)} and (3/2)n=Θ(log⁡(1/ε))(3/2)^n = \Theta(\log(1/\varepsilon)).

  5. Tn=3 Tn−1+O(1)=O((log⁡1ε)log⁡3/log⁡(3/2))T_n = 3\,T_{n-1} + \order{1} = \order{\Big(\log\tfrac{1}{\varepsilon}\Big)^{\log 3/\log(3/2)}}

    Three recursive calls per level, and O(1)\order{1} matrix work for fixed dd; the word is returned as this recursive description (writing it out in full takes time proportional to its length). Numerically, log⁡5/log⁡1.5≈3.97\log5/\log1.5\approx3.97 and log⁡3/log⁡1.5≈2.71\log3/\log1.5\approx2.71.

Check your understanding

Where exactly does this proof use that G\mathcal{G} is closed under inverses?

  1. In building the base ε0\varepsilon_0-net
  2. In writing V1†V_1^\dagger and W1†W_1^\dagger as words over G\mathcal{G}
  3. In the Baker–Campbell–Hausdorff expansion
  4. Nowhere; it is only a convenience
Show the answer

B. In writing V1†V_1^\dagger and W1†W_1^\dagger as words over G\mathcal{G}

The output V1W1V1†W1†U1V_1W_1V_1^\dagger W_1^\dagger U_1 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
  1. #{words of length≤L}≤∑ℓ=0Lgℓ≤2gL\#\{\text{words of length}\le L\}\le\sum_{\ell=0}^{L}g^\ell\le2g^L

    With g=∣G∣≥2g=\abs{\mathcal{G}}\ge2.

  2. vol(Bε(V))≈κ εD,D=dim⁡SU(d)=d2−1\mathrm{vol}\big(B_\varepsilon(V)\big)\approx\kappa\,\varepsilon^{D},\qquad D = \dim SU(d) = d^2-1

    Small balls in a DD-dimensional manifold, with Haar measure normalized to total volume 11.

  3. 2gL⋅κ εD≥1⟹L≥Dlog⁡(1/ε)−log⁡(2κ)log⁡g2g^L\cdot\kappa\,\varepsilon^{D}\ge1\quad\Longrightarrow\quad L\ge\frac{D\log(1/\varepsilon)-\log(2\kappa)}{\log g}

    The balls around all words must cover the group. For SU(2)SU(2): L≥3log⁡(1/ε)/log⁡g−O(1)L\ge3\log(1/\varepsilon)/\log g-\order{1}.

  4. For nn-qubit circuits, D=4n−1D=4^n-1 and each gate is one of O(g n2)\order{g\,n^2} placements, so generic nn-qubit unitaries need Ω(4nlog⁡(1/ε)/log⁡n)\Omega\big(4^n\log(1/\varepsilon)/\log n\big) gates.

So Solovay–Kitaev is optimal up to the exponent: log⁡(1/ε)\log(1/\varepsilon) is necessary and log⁡3.97(1/ε)\log^{3.97}(1/\varepsilon) 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)SU(2)) admit O(log⁡(1/ε))\order{\log(1/\varepsilon)}-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 3log⁡2(1/ε)+O(log⁡log⁡(1/ε))3\log_2(1/\varepsilon)+\order{\log\log(1/\varepsilon)} (see the synthesis deep dive).

Key takeaways

  • Solovay–Kitaev: for any finite, inverse-closed, dense G⊂SU(d)\mathcal{G}\subset SU(d), accuracy ε\varepsilon costs O(log⁡c(1/ε))\order{\log^{c}(1/\varepsilon)} gates, found in time O(log⁡c′(1/ε))\order{\log^{c'}(1/\varepsilon)}.
  • The engine is the group commutator: near the identity it is second order, so approximating the factors within ε\varepsilon gives the commutator within ε3/2\varepsilon^{3/2}.
  • Five sub-words and three recursive calls per level give c=log⁡5/log⁡32≈3.97c=\log5/\log\frac32\approx3.97 and c′=log⁡3/log⁡32≈2.71c'=\log3/\log\frac32\approx2.71.
  • Volume counting forces Ω(log⁡(1/ε))\Omega(\log(1/\varepsilon)); 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?

  1. The gate set is finite
  2. The gate set is closed under inverses
  3. The generated group is dense in SU(d)SU(d)
  4. 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 optimal O(log⁡(1/ε))\order{\log(1/\varepsilon)} results via spectral gaps (Bourgain–Gamburd).

Question 2

In the recursion, the error contracts as εn∝εn−13/2\varepsilon_n\propto\varepsilon_{n-1}^{3/2} and the length grows as Ln=5Ln−1L_n = 5L_{n-1}. If a cleverer step gave εn∝εn−12\varepsilon_n\propto\varepsilon_{n-1}^{2} with still Ln=5Ln−1L_n = 5L_{n-1}, what length exponent cc would result?

  1. log⁡5/log⁡2≈2.32\log5/\log2\approx2.32
  2. log⁡5/log⁡1.5≈3.97\log5/\log1.5\approx3.97
  3. 5/25/2
  4. 11
Show the answer

A. log⁡5/log⁡2≈2.32\log5/\log2\approx2.32

Now εn∼ε02n\varepsilon_n\sim\varepsilon_0^{2^n}, so n≈log⁡2log⁡(1/ε)n\approx\log_2\log(1/\varepsilon) levels suffice and L=5n=log⁡log⁡25(1/ε)L = 5^n = \log^{\log_2 5}(1/\varepsilon). In general c=log⁡(branching)/log⁡(contraction exponent)c = \log(\text{branching})/\log(\text{contraction exponent}).

Question 3

For a gate set of gg elements in SU(2)SU(2), the counting argument shows that a typical target needs length at least about

  1. log⁡(1/ε)/log⁡g\log(1/\varepsilon)/\log g
  2. 3log⁡(1/ε)/log⁡g3\log(1/\varepsilon)/\log g
  3. log⁡3.97(1/ε)\log^{3.97}(1/\varepsilon)
  4. 1/ε31/\varepsilon^3
Show the answer

B. 3log⁡(1/ε)/log⁡g3\log(1/\varepsilon)/\log g

SU(2)SU(2) is three-dimensional, so an ε\varepsilon-net needs ∼ε−3\sim\varepsilon^{-3} points, while only ∼gL\sim g^L words exist: L≳3log⁡(1/ε)/log⁡gL\gtrsim3\log(1/\varepsilon)/\log g.

Question 4

Why does the group commutator of two near-identity unitaries drive the recursion?

  1. It is always exactly the identity
  2. It commutes with every element of G\mathcal{G}
  3. Its distance from I\id is second order, and errors in its factors enter only at order δη\delta\eta
  4. It turns SU(2)SU(2) into a finite group
Show the answer

C. Its distance from I\id is second order, and errors in its factors enter only at order δη\delta\eta

For ∥V−I∥,∥W−I∥≤δ\norm{V-\id},\norm{W-\id}\le\delta, the commutator is O(δ2)\order{\delta^2} from I\id, and replacing V,WV,W by η\eta-approximations changes it by only O(δη+η2)\order{\delta\eta+\eta^2}. That turns accuracy ε\varepsilon into ε3/2\varepsilon^{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).