Optimal ancilla-free Clifford+T synthesis for general single-qubit unitaries

Abstract

We propose two Clifford+$T$ synthesis algorithms that are optimal with respect to $T$-count. The first algorithm, called deterministic synthesis, approximates any single-qubit unitary by a single-qubit Clifford+$T$ circuit with the minimum $T$-count. The second algorithm, called probabilistic synthesis, approximates any single-qubit unitary by a probabilistic mixture of single-qubit Clifford+$T$ circuits with the minimum $T$-count. For most of single-qubit unitaries, the runtimes of deterministic synthesis and probabilistic synthesis are ${\epsilon }^{-1/2-o(1)}$ and ${\epsilon }^{-1/4-o(1)}$, respectively, for an approximation error $\epsilon$. Although this complexity is exponential in the input size, we demonstrate that our algorithms run in practical time at $\epsilon \approx 10^{-15}$ and $\epsilon \approx 10^{-22}$, respectively. Furthermore, we show that, for most single-qubit unitaries, the deterministic synthesis algorithm requires at most $3{\log }_2(1/\epsilon )+o({\log }_2(1/\epsilon ))$ $T$-gates, and the probabilistic synthesis algorithm requires at most $1.5{\log }_2(1/\epsilon )+o({\log }_2(1/\epsilon ))$ $T$-gates. Remarkably, complexity analyses in this work do not rely on any numerical or number-theoretic conjectures.

arXiv comment31 pages, 5 figures