Efficient Clifford+T approximation of single-qubit operators

Abstract

We give an efficient randomized algorithm for approximating an arbitrary element of $SU(2)$ by a product of Clifford+$T$ operators, up to any given error threshold $\epsilon >0$. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in $\log (1/\epsilon )$. If the operator to be approximated is a $z$-rotation, the resulting gate sequence has $T$-count $K+4{\log }_2(1/\epsilon )$, where $K$ is approximately equal to $10$. We also prove a worst-case lower bound of $K+4{\log }_2(1/\epsilon )$, where $K=-9$, so that our algorithm is within an additive constant of optimal for certain $z$-rotations. For an arbitrary member of $SU(2)$, we achieve approximations with $T$-count $K+12{\log }_2(1/\epsilon )$. By contrast, the Solovay-Kitaev algorithm achieves $T$-count $O({\log }^c(1/\epsilon ))$, where $c$ is approximately $3.97$.

References in corpus (6)

• A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
• Methodology for quantum logic gate constructions
• Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits
• Asymptotically Optimal Topological Quantum Compiling
• A State Distillation Protocol to Implement Arbitrary Single-qubit Rotations
• Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators

Cited by in corpus (6)

• Majorana Zero Modes and Topological Quantum Computation
• Efficient synthesis of universal Repeat-Until-Success circuits
• Efficient synthesis of probabilistic quantum circuits with fallback
• Solovay-Kitaev Decomposition Strategy for Single-Qubit Channels
• Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators
• Distributed Quantum Computing Utilizing Multiple Codes on Imperfect Hardware