# clarifying a step in the proof of Solovay-Kitaev theorem

There is a step in the proof of the proof of Solovay-Kitaev theorem about the existence of a set containing words of at most length length $$l_0$$ that cover $$SU(2)$$ . 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}))$$.

The proof says that  Since $$\langle G \rangle$$ is dense in $$SU(2)$$ we can find an $$l_0$$ such that $$G_{l_{0}}$$ is an $$\epsilon$$-net for $$SU(2)$$ , and thus also for $$S_{\epsilon}$$ . '' Here $$S_{\epsilon}$$ is $$\epsilon$$-net around identity in $$SU(2)$$.

I couldn't fully understand why there must exist $$G_{l_{0}}$$ which is an $$\epsilon$$-net for $$SU(2)$$ ? Moreover, does this imply every$$G_{l_{k}}$$ where $$l_k \ge l_0$$ covers $$SU(2)$$ ?

Here is my reasoning to support this existence of $$G_{l_{0}}$$. Please let me know where my reasoning went wrong. I am not completely satisfied by my argument.

Since $$\langle G \rangle$$ is dense in $$SU(2)$$, therefore it is $$\epsilon_{0}^{2}$$-net for $$SU(2)$$. This $$\epsilon_{0}^{2}$$-neighborhood of all elements of $$\langle G \rangle$$ forms an open covering $$C$$ for $$SU(2)$$. Since $$SU(2)$$ is compact, we can choose finitely many elements of $$C$$ that cover $$SU(2)$$, hence an open subcover $$C^{'}$$ of $$SU(2)$$. Since every elements of covering $$C$$ is $$\epsilon_{0}^{2}$$-neighborhood of elements of $$\langle G \rangle$$, therefore each element in subcover $$C^{'}$$ is also an $$\epsilon_{0}^{2}$$-neighborhood of some elements in $$\langle G \rangle$$. That is $$C^{'} = \bigcup_{i=1}^{k}B_i$$ where $$B_i$$ is $$\epsilon_{0}^{2}$$-neighborhood of some $$F_i$$ in $$\langle G \rangle$$. We now take maximum of $$d(F_i, F_j) \le l_0$$ (rounded above to nearest integer). Thus, $$C^{'}\subset G_{l_0}$$.

In the final step, I thought to pick one unitary from each elements of the subcover and find the distance between every two unitary. Take the maximum of the distance computed to be the minimum length $$l_0$$ , as it may not be integer, it should be rounded to nearest integer. In this way each element of the subcover $$C^{'}$$ would be contained in some word of at most length $$l_0$$, that is in $$G_{l_{0}}$$.

A pedagogical review of the proof of Solovay-kitaev theoem co-authored by Nielson is available here: (https://arxiv.org/abs/quant-ph/0505030).

Any help is greatly appreciated...

• I had the same question, but your reasoning satisfies me. I don't understand why your reasoning doesn't satisfy you. Commented Mar 25, 2023 at 21:38

There is no need to use open covers for showing existance of $$G_{l_0}$$.
The simplest argument for existence of $$G_{l_0}$$ is giving a trivial example of such a generating set.
Note that according to N&C, without loss of generality we may assume that $$C \epsilon_0 < 1$$ for some constant $$C$$. This gives a lot of freedom on how we can define $$G_{l_0}$$ and what $$\epsilon_0$$ we choose.
Choose $$\epsilon_0=2$$. Then $$G_{l_0} = \{U\}$$ where $$U \in SU(2)$$. This set is $$\epsilon_0$$-net of $$SU(2)$$. You can choose $$U=I$$ if you want to make it really trivial.
The choice of $$\epsilon_0=2$$ can be motivated by the norm-2 distance between any two elements in $$SU(2)$$ given that all kets are normalized.