Asymptotic Gate Count Bounds for Ancilla-Free Single-Qubit Synthesis with Arithmetic Gates

Abstract

We study ancilla-free approximation of single-qubit unitaries $U\in \mathrm{SU}(2)$ by gate sequences over Clifford+$G$, where $G\in \{T,V\}$ or their generalization. Let $p$ denote the characteristic factor of the gate set (e.g., $p=2$ for $G=T$ and $p=5$ for $G=V$). We prove three asymptotic bounds on the minimum $G$-count required to achieve approximation error at most $\epsilon$. First, for Haar-almost every $U$, we show that $3{\log }_p(1/\epsilon )$ $G$-count is both necessary and sufficient; moreover, probabilistic synthesis improves the leading constant to $3/2$. Second, for unitaries whose ratio of matrix elements lies in a specified number field, $4{\log }_p(1/\epsilon )$ $G$-count is necessary. Again, the leading constant can be improved to $2$ by probabilistic synthesis. Third, there exist unitaries for which the $G$-count per ${\log }_p(1/\epsilon )$ fails to converge as $\epsilon \to 0^{+}$. These results partially resolve a generalized form of the Ross--Selinger conjecture.

arXiv comment18 pages, 1 figure