Contributions to the Theory of Clifford-Cyclotomic Circuits

Let $n$ be a positive integer divisible by 8. The Clifford-cyclotomic gate set ${\mathcal{G}}_n$ consists of the Clifford gates, together with a $z$-rotation of order $n$. It is easy to show that, if a circuit over ${\mathcal{G}}_n$ represents a unitary matrix $U$, then the entries of $U$ must lie in ${\mathcal{R}}_n$, the smallest subring of $\mathbb{C}$ containing $1\mathrm{/}2$ and $\mathrm{e}\mathrm{x}\mathrm{p}(2\pi i\mathrm{/}n)$. The converse implication, that every unitary $U$ with entries in ${\mathcal{R}}_n$ can be represented by a circuit over ${\mathcal{G}}_n$, is harder to show, but it was recently proved to be true when $n=2^k$. In that case, $k-2$ ancillas suffice to synthesize a circuit for $U$, which is known to be minimal for $k=3$, but not for larger values of $k$. In the present paper, we make two contributions to the theory of Clifford-cyclotomic circuits. Firstly, we improve the existing synthesis algorithm by showing that, when $n=2^k$ and $k\ge 4$, only $k-3$ ancillas are needed to synthesize a circuit for $U$, which is minimal for $k=4$. Secondly, we extend the existing synthesis algorithm to the case of $n=3\cdot 2^k$ with $k\ge 3$.