Efficient Fault-Tolerant Single Qubit Gate Approximation And Universal Quantum Computation Without Using The Solovay-Kitaev Theorem

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 ε > 0 requires O(logᶜ[1/ε]) 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 Ω(log[1/ε]) gates chosen from a finite set. Here I give a partial answer to this question by showing that this is possible using O(log[1/ε] loglog[1/ε] logloglog[1/ε] ⋯) FT gates chosen from a finite set depending on the value of ε. The key idea is to construct an approximation of any phase gate in a FT way by recursion to any given accuracy ε > 0. This method is straightforward to implement, easy to understand, and interestingly does not involve the Solovay-Kitaev theorem.