2024/06/07 by H. F. Chau, Chau, H. F.
Computer Science · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2406.04846
openalex publication_date 2024/06/07 · openalex created_date 2024/06/11 · openalex updated_date 2026/07/28
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(logc[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.