# When proving the Solovay-Kitaev theorem, why do we consider a small neighborhood $S_\epsilon$ of the identity?

There are number of points I haven't understood or am confused in the proof of Solovay-Kitaev theorem. The proof I'm reading in given in the Appendix 3 of Neilson and Chuang's book, Quantum Computation and Quantum Information.

Solovay-Kitaev Theorem: Let $$G$$ be a finite set of elements in $$\mathrm{SU(2)}$$ containing its own inverses such that $$\langle G\rangle$$ is dense in $$\mathrm{SU(2)}$$. Let $$\epsilon > 0$$ be given. We define $$G_l$$ to be the set of all words of length at most l, such that each symbol is in $$G$$. Then $$G_l$$ is an $$\epsilon$$-net in $$\mathrm{SU(2)}$$ for $$l = O (\log^{4}(\frac{1}{\epsilon}))$$.

Initially, why we are considering a small neighborhood of identity, $$S_\epsilon$$? This $$S_\epsilon$$ is an $$\epsilon$$-net covering a ball around identity. The unitary we want to approximate may be bit far from identity element in $$\mathrm{SU(2)}$$. The proof seems to claim that we can only approximate unitaries which are in $$\epsilon$$-net of identity.

Any help is greatly appreciated...

• I have just edited the question restricted to only a one point about which I'm confused. Commented Nov 22, 2022 at 6:32

I don't have the book in front of me right now to recall all the details. However, the key point is that if you have a small neighbourhood around identity that you can "hit" with some sequence $$G_l$$, then you can also hit a small neighbourhood in the region of any $$G$$ with a sequence $$G_lG$$. So the aim is that you can cover the whole surface of the Bloch sphere by spreading copies of that ball all over the surface.
• So if we have set of sequences of length l which cover the small neighborhood of identity, we can then pick some suitable sequence, $w$, from the set such that if unitary $U$ is anywhere in $SU(2)$ then $wU$ would be is some small neighborhood of $U$. Did I understand the intuition correctly? Commented Nov 24, 2022 at 8:09
• Two parts of the question: (1) why a neighbourhood around the Identity, and (2) why a small neighbourhood around the identity? (1) is answered by @DaftWullie. For (2): the dependence of $\epsilon$ on $l$ that you're seeking out is an asymptotic behaviour, when $\epsilon$ gets smaller and smaller. Also, you can use many prototypical tricks for small $\epsilon$ regime, e.g: Baker-Campbell Hausdorff formula is convergent for small enough elements of the Lie algebra, or Lagrange's theorem to Taylor expand to 1st or 2nd order enables you to extract the residue to be quadratic/ cubic in $\epsilon$. Commented Mar 26, 2023 at 19:00