Synthesis of single-qutrit circuits from Clifford <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>+</mml:mo> <mml:mi>R</mml:mi> </mml:math> gates

We present two deterministic compilation algorithms for single-qutrit unitaries with $O(log1/\ensuremath{\varepsilon})$ gate depth. Each algorithm selects a nearby approximation to the target unitary and then exactly synthesizes the approximation over the Clifford $+$ $\mathbf{R}$ basis. 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/\ensuremath{\varepsilon})$, albeit with a time complexity of $O({\ensuremath{\varepsilon}}^{\ensuremath{-}4.4})$. The Householder search algorithm results in a larger average $\mathbf{R}$ count of $3.20(13)+10.77(3){log}_{10}(1/\ensuremath{\varepsilon})$ at a reduced time complexity of $O({\ensuremath{\varepsilon}}^{\ensuremath{-}0.42})$, greatly extending the reach in $\ensuremath{\varepsilon}$. These costs correspond asymptotically to 35% and 69% more non-Clifford gates compared with synthesizing the same unitary with two qubits. Such initial results are encouraging for using the $\mathbf{R}$ gate as the nontransversal gate for qutrit-based computation.