Synthesis of single-qutrit circuits from Clifford + R gates

This is the authors' abstract. We don't add key points for this paper.

We present two deterministic compilation algorithms for single-qutrit unitaries with O(log1/ε) gate depth. Each algorithm selects a nearby approximation to the target unitary and then exactly synthesizes the approximation over the Clifford $+$ 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 R count of 2.193(11)+8.621(7)log₁₀(1/ε), albeit with a time complexity of O(ε^-4.4). The Householder search algorithm results in a larger average R count of 3.20(13)+10.77(3)log₁₀(1/ε) at a reduced time complexity of O(ε^-0.42), greatly extending the reach in ε. 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 R gate as the nontransversal gate for qutrit-based computation.