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...

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

1 Answer 1


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.

  • $\begingroup$ The following essay give some details of the proof as presented in Appendix 3 of the book: link $\endgroup$
    – madeel
    Commented Nov 24, 2022 at 8:03
  • $\begingroup$ 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? $\endgroup$
    – madeel
    Commented Nov 24, 2022 at 8:09
  • $\begingroup$ 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$. $\endgroup$ Commented Mar 26, 2023 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.