Erik Gustafson

We present two deterministic compilation algorithms for single-qutrit unitaries with $\mathcal{O}(\log \frac{1}{\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 $\yintm + \slopem \log_{10}(1 / \varepsilon)$, albeit with a time complexity of $\mathcal{O}(\varepsilon^{\pgfmathprintnumber[fixed,precision=2]{\fullcomplexity}})$. The Householder search algorithm results in a larger average $\mathbf{R}$ count of $\yint + \slope \log_{10}(1 / \varepsilon)$ at a reduced time complexity of $\mathcal{O}(\varepsilon^{\pgfmathprintnumber[fixed,precision=2]{\householdercomplexity}})$, greatly extending the reach in $\varepsilon$. 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.