Exact Synthesis of Multiqutrit Clifford-Cyclotomic Circuits

It is known that the matrices that can be exactly represented by a multiqubit circuit over the Toffoli+Hadamard, Clifford+T, or, more generally, Clifford-cyclotomic gate set are precisely the unitary matrices with entries in the ring Z[1/2,ζₖ], where k is a positive integer that depends on the gate set and ζₖ is a primitive 2ᵏ-th root of unity. In the present paper, we establish an analogous correspondence for qutrits. We define the multiqutrit Clifford-cyclotomic gate set of degree 3ᵏ by extending the classical qutrit gates X, $CX$, and $CCX$ with the Hadamard gate H and the Tₖ gate Tₖ=diag(1,ωₖ, ωₖ²), where ωₖ is a primitive 3ᵏ-th root of unity. This gate set is equivalent to the qutrit Toffoli+Hadamard gate set when $k=1$, and to the qutrit Clifford+Tₖ gate set when $k>1$. We then prove that a 3ⁿ× 3ⁿ unitary matrix U can be represented by an n-qutrit circuit over the Clifford-cyclotomic gate set of degree 3ᵏ if and only if the entries of U lie in the ring Z[1/3,ωₖ].