Solovay–Kitaev theorem

Let ${\displaystyle {\mathcal {G}}}$ be a finite set of elements in SU(2) containing its own inverses (so ${\displaystyle g\in {\mathcal {G}}}$ implies ${\displaystyle g^{-1}\in {\mathcal {G}}}$) and such that the group ${\displaystyle \langle {\mathcal {G}}\rangle }$ they generate is dense in SU(2). Consider some ${\displaystyle \varepsilon >0}$. Then there is a constant ${\displaystyle c}$ such that for any ${\displaystyle U\in SU(2)}$, there is a sequence ${\displaystyle S}$ of gates from ${\displaystyle {\mathcal {G}}}$ of length ${\displaystyle O(\log ^{c}(1/\varepsilon ))}$ such that ${\displaystyle \|S-U\|\leq \varepsilon }$. That is, ${\displaystyle S}$ approximates ${\displaystyle U}$ to operator norm error.[2]

The constant ${\displaystyle c}$ can be made to be ${\displaystyle 3+\delta }$ for any fixed ${\displaystyle \delta >0}$.[4] However, there exist particular gate sets for which we can take ${\displaystyle c=1}$, which makes the length of the gate sequence tight up to a constant factor.[5]

The proof of the Solovay-Kitaev theorem proceeds by recursively constructing a gate sequence giving increasingly good approximations to ${\displaystyle U\in \operatorname {SU} (2)}$.[2] Suppose we have an approximation ${\displaystyle U_{n-1}\in \operatorname {SU} (2)}$ such that ${\displaystyle \|U-U_{n-1}\|\leq \varepsilon _{n-1}}$. Our goal is to find a sequence of gates approximating ${\displaystyle UU_{n-1}^{-1}}$ to ${\displaystyle \varepsilon _{n}}$ error, for ${\displaystyle \varepsilon _{n}<\varepsilon _{n-1}}$. By concatenating this sequence of gates with ${\displaystyle U_{n-1}}$, we get a sequence of gates ${\displaystyle U_{n}}$ such that ${\displaystyle \|U-U_{n}\|\leq \varepsilon _{n}}$.

The key idea is that commutators of elements close to the identity can be approximated "better-than-expected". Specifically, for ${\displaystyle V,W\in \operatorname {SU} (2)}$ satisfying ${\displaystyle \|V-I\|\leq \delta _{1}}$ and ${\displaystyle \|W-I\|\leq \delta _{1}}$ and approximations ${\displaystyle {\tilde {V}},{\tilde {W}}\in \operatorname {SU} (2)}$ satisfying ${\displaystyle \|V-{\tilde {V}}\|\leq \delta _{2}}$ and ${\displaystyle \|W-{\tilde {W}}\|\leq \delta _{2}}$, then

${\displaystyle \|VWV^{-1}W^{-1}-{\tilde {V}}{\tilde {W}}{\tilde {V}}^{-1}{\tilde {W}}^{-1}\|\leq O(\delta _{1}\delta _{2}),}$

where the big O notation hides higher-order terms. One can naively bound the above expression to be ${\displaystyle O(\delta _{2})}$, but the group commutator structure creates substantial error cancellation.

We use this observation by rewriting the expression we wish to approximate as a group commutator ${\displaystyle UU_{n-1}^{-1}=V_{n-1}W_{n-1}V_{n-1}^{-1}W_{n-1}^{-1}}$. This can be done such that both ${\displaystyle V_{n-1}}$ and ${\displaystyle W_{n-1}}$ are close to the identity (since ${\displaystyle \|UU_{n-1}^{-1}-I\|\leq \varepsilon _{n-1}}$). So, if we recursively compute gate sequences approximating ${\displaystyle V_{n-1}}$ and ${\displaystyle W_{n-1}}$ to ${\displaystyle \varepsilon _{n-1}}$ error, we get a gate sequence approximating ${\displaystyle UU_{n-1}^{-1}}$ to the desired better precision ${\displaystyle \varepsilon _{n}}$ with ${\displaystyle \varepsilon _{n}}$. We can get a base case approximation with constant ${\displaystyle \varepsilon _{0}}$ by brute-force computation of all sufficiently long gate sequences.