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

Abstract

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 $\text{O}({\log }^c[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 $\Omega (\log [1/ϵ])$ 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/ϵ]\log \log [1/ϵ]\log \log \log [1/ϵ]\cdots )$ 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.