Synthesis of Single Qutrit Circuits from Clifford+R

We present two deterministic algorithms to approximate single-qutrit gates. These algorithms utilize the Clifford + $\mathbf{R}$ group to find the best approximation of diagonal rotations. The first algorithm exhaustively searches over the group; while the second algorithm searches only for Householder reflections. The exhaustive search algorithm yields an average $\mathbf{R}$ count of $2.193(11)+8.621(7){\log }_{10}(1\mathrm{/}\epsilon )$, albeit with a time complexity of $\mathcal{O}({\epsilon }^{-4.4})$. The Householder search algorithm results in a larger average $\mathbf{R}$ count of $3.20(13)+10.77(3){\log }_{10}(1\mathrm{/}\epsilon )$ at a reduced time complexity of $\mathcal{O}({\epsilon }^{-0.42})$, greatly extending the reach in $\epsilon$. These costs correspond asymptotically to 35% and 69% more non-Clifford gates compared to synthesizing the same unitary with two qubits. Such initial results are encouraging for using the $\mathbf{R}$ gate as the non-transversal gate for qutrit-based computation.