Shorter quantum circuits via single-qubit gate approximation

Quantum 7, 1208 (2023).

https://doi.org/10.22331/q-2023-12-18-1208

We give a novel procedure for approximating general single-qubit unitaries from a finite universal gate set by reducing the problem to a novel magnitude approximation problem, achieving an immediate improvement in sequence length by a factor of 7/9. Extending the works [28] and [15], we show that taking probabilistic mixtures of channels to solve fallback [13] and magnitude approximation problems saves factor of two in approximation costs. In particular, over the Clifford+$sqrt{mathrm{T}}$ gate set we achieve an average non-Clifford gate count of $0.23log_2(1/varepsilon)+2.13$ and T-count $0.56log_2(1/varepsilon)+5.3$ with mixed fallback approximations for diamond norm accuracy $varepsilon$.
This paper provides a holistic overview of gate approximation, in addition to these new insights. We give an end-to-end procedure for gate approximation for general gate sets related to some quaternion algebras, providing pedagogical examples using common fault-tolerant gate sets (V, Clifford+T and Clifford+$sqrt{mathrm{T}}$). We also provide detailed numerical results for Clifford+T and Clifford+$sqrt{mathrm{T}}$ gate sets. In an effort to keep the paper self-contained, we include an overview of the relevant algorithms for integer point enumeration and relative norm equation solving. We provide a number of further applications of the magnitude approximation problems, as well as improved algorithms for exact synthesis, in the Appendices.