  Arbitrarily accurate fault-tolerant (FT) universal quantum computation can be
carried out using the Clifford gates Z, S, CNOT plus the non-Clifford T gate.
Moreover, a recent improvement of the Solovay-Kitaev theorem by Kuperberg
implies that to approximate any single-qubit gate to an accuracy of $\epsilon >
0$ requires $\text{O}(\log^c[1/\epsilon])$ quantum gates with $c > 1.44042$.
Can one do better? That was the question asked by Nielsen and Chuang in their
quantum computation textbook. Specifically, they posted a challenge to
efficiently approximate single-qubit gate, fault-tolerantly or otherwise, using
$\Omega(\log[1/\epsilon])$ gates chosen from a finite set. Here I give a
partial answer to this question by showing that this is possible using
$\text{O}(\log[1/\epsilon] \log\log[1/\epsilon] \log\log\log[1/\epsilon]
\cdots)$ FT gates chosen from a finite set depending on the value of
$\epsilon$. The key idea is to construct an approximation of any phase gate in
a FT way by recursion to any given accuracy $\epsilon > 0$. This method is
straightforward to implement, easy to understand, and interestingly does not
involve the Solovay-Kitaev theorem.
