Exact Synthesis of Multiqubit Clifford-Cyclotomic Circuits

Let \(n\ge 8\) be divisible by 4. The Clifford-cyclotomic gate set \(\mathcal {G}_n\) is the universal gate set obtained by extending the Clifford gates with the z-rotation \(T_n = \textrm{diag}(1,\zeta _n)\) , where \(\zeta _n\) is a primitive n-th root of unity. In this note, we show that, when n is a power of 2, a multiqubit unitary matrix U can be exactly represented by a circuit over \(\mathcal {G}_n\) if and only if the entries of U belong to the ring \(\mathbb {Z}[1/2,\zeta _n]\) . We moreover show that \(\log (n)-2\) ancillas are always sufficient to construct a circuit for U. Our results generalize prior work to an infinite family of gate sets and show that the limitations that apply to single-qubit unitaries, for which the correspondence between Clifford-cyclotomic operators and matrices over \(\mathbb {Z}[1/2,\zeta _n]\) fails for all but finitely many values of n, can be overcome through the use of ancillas.