Circuit Synthesis for Early Fault-Tolerant Quantum Computers

Error correction is an indispensable component toward realizing practical quantum computing, in which an essential task is to approximate quantum circuits with fault-tolerant (FT) operations. Clifford+T is a widely adopted universal gate set for FT quantum computing, where the number of T gates (T count) is an important resource measure of an FT circuit. Gridsynth is the state-of-the-art Clifford+T synthesis algorithm for Rz rotations, which yields optimal or near-optimal (in T count) Clifford+T decompositions for any level of approximation error. However, when given a general single-qubit unitary, gridsynth needs to perform at most three Rz syntheses, which can lead to three times the optimal T count. In this work, we present an FT synthesis algorithm that finds the optimal decomposition of arbitrary single-qubit unitaries with high probability. We show that compared to Rz synthesis, arbitrary unitary synthesis enables additional circuit optimizations, which lead to reductions in T count and approximation error. We present numerical evidence demonstrating the effectiveness of our algorithm and these optimizations at the early FT scale. Our algorithm is naturally scalable in the circuit size and can be applied to other FT gate sets.