Let n be a positive integer divisible by 8.The Clifford-cyclotomic gate set 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 G n represents a unitary matrix U, then the entries of U must lie in R n , the smallest subring of C containing 1/2 and exp(2πi/n).The converse implication, that every unitary U with entries in R n can be represented by a circuit over 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 ≥ 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 • 2 k with k ≥ 3.
Let n be a positive integer divisible by 8.The Clifford-cyclotomic gate set 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 G n represents a unitary matrix U, then the entries of U must lie in R n , the smallest subring of C containing 1/2 and exp(2πi/n).The converse implication, that every unitary U with entries in R n can be represented by a circuit over 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 ≥ 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 • 2 k with k ≥ 3.
Circuit design is an important aspect of quantum computation theory, and the question of constructing a circuit that exactly represents a given operator is prominent in the research area. 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/2 and \mathrm{exp}(2\pi i/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 thesis, 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\geq 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\geq 3.
We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov, and Mosca [Quantum Inf. Comput. 13(7,8), 607–630 (2013)]. Their algorithm takes as input an exactly synthesizable single-qubit unitary—one which can be expressed without error as a product of Clifford and T gates—and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n, we consider the “Clifford-cyclotomic” gate set consisting of the Clifford group plus a z-rotation by πn. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of πn z-rotations. For the Clifford+T case n = 4, the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[eiπn,1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100%.
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,ζk], where k is a positive integer that depends on the gate set and ζk is a primitive 2k-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 3k by extending the classical qutrit gates X, CX, and CCX with the Hadamard gate H and the Tk gate Tk=diag(1,ωk,ωk2), where ωk is a primitive 3k-th root of unity. This gate set is equivalent to the qutrit Toffoli+Hadamard gate set when k=1, and to the qutrit Clifford+Tk gate set when k>1. We then prove that a 3n×3n unitary matrix U can be represented by an n-qutrit circuit over the Clifford-cyclotomic gate set of degree 3k if and only if the entries of U lie in the ring Z[1/3,ωk].
In this paper we study single qutrit circuits consisting of words over the Clifford+D cyclotomic gate set, where D=diag(±ξa,±ξb,±ξc), ξ is a primitive 9-th root of unity and a,b,c are integers. We characterize classes of qutrit unit vectors z with entries in Z[ξ,χ1] based on the possibility of reducing their smallest denominator exponent (sde) with respect to χ:=1−ξ, by acting an appropriate gate in Clifford+D. We do this by studying the notion of `derivatives mod 3' of an arbitrary element of Z[ξ] and using it to study the smallest denominator exponent of HDz where H is the qutrit Hadamard gate and D. In addition, we reduce the problem of finding all unit vectors of a given sde to that of finding integral solutions of a positive definite quadratic form along with some additional constraints. As a consequence we prove that the Clifford+D gates naturally arise as gates with sde 0 and 3 in the group U(3,Z[ξ,χ1]) of 3×3 unitaries with entries in Z[ξ,χ1]. We illustrate the general applicability of these methods to obtain an exact synthesis algorithm for Clifford+R and recover the previous exact synthesis algorithm in \cite{kmm}. The framework developed to formulate qutrit gate synthesis for Clifford+D extends to qudits of arbitrary prime power.
Kliuchnikov, Maslov, and Mosca proved in 2012 that a 2×2 unitary matrix V can be exactly represented by a single-qubit Clifford+ T circuit if and only if the entries of V belong to the ring Z[1/2,i] . Later that year, Giles and Selinger showed that the same restriction applies to matrices that can be exactly represented by a multi-qubit Clifford+ T circuit. These number-theoretic characterizations shed new light upon the structure of Clifford+ T circuits and led to remarkable developments in the field of quantum compiling. In the present paper, we provide number-theoretic characterizations for certain restricted Clifford+ T circuits by considering unitary matrices over subrings of Z[1/2,i] . We focus on the subrings Z[1/2] , Z[1/2] , Z[1/i2] , and Z[1/2,i] , and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates {X,CX,CCX} with an analogue of the Hadamard gate and an optional phase gate.
Minimizing the number of CNOT gates required to synthesize a Clifford operator is a central problem in quantum circuit optimization. We extend the link--middle--cut (LMC) framework for linear reversible circuits to Clifford operators represented by binary symplectic tableaux. By introducing block-support connectivity graphs and determinantal invariants, we obtain efficiently computable lower bounds on ancilla-free CNOT complexity. We prove that these bounds are tight for qubit permutations: a permutation of n qubits with k cycles requires exactly 3(n−k) CNOT gates, even when arbitrary one-qubit Clifford gates are available. We also derive efficiently computable bounds for synthesis up to a permutation of the output qubits, corresponding to free qubit relabeling. Finally, we further demonstrate the utility of the bound by using it as an admissible heuristic for A∗-based Clifford synthesis and show that, on benchmark instances, the resulting search can prove optimality beyond what was possible with earlier SAT-based methods, and that it may be used in combination with earlier A∗ heuristics to improve the CNOT counts obtained through heuristic search.