Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2011.07970

A Normal Form for Single-Qudit Clifford+TTT Operators

Akalank Jain, Amolak Ratan Kalra, Shiroman Prakash

Published Nov 16, 2020• 0 citations
arXivHTMLPDF

Abstract

We propose a normal form for single-qudit gates composed of Clifford and $T$-gates for qudits of odd prime dimension $p\geq 5$. We prove that any single-qudit Clifford+$T$ operator can be re-expressed in this normal form in polynomial time. We also provide strong numerical evidence that this normal form is unique. Assuming uniqueness, we are able to use this normal form to provide an algorithm for exact synthesis of any single-qudit Clifford+$T$ operator with minimal $T$-count.

DOI
10.48550/arxiv.2011.07970

Related papers

A Normal Form for Single-Qutrit Clifford+T Operators

Shiroman Prakash, Akalank Jain, Bhakti Kapur +1 more

We propose a normal form for single-qudit gates composed of Clifford and $T$-gates for qudits of odd prime dimension $p\geq 5$. We prove that any single-qudit Clifford+$T$ operator can be re-expressed in this normal form in polynomial time. We also provide strong numerical evidence that this normal form is unique. Assuming uniqueness, we are able to use this normal form to provide an algorithm for exact synthesis of any single-qudit Clifford+$T$ operator with minimal $T$-count.

•Mar 8, 2018•0 citations

A Complete and Natural Rule Set for Multi-Qudit Clifford Circuits in All Odd Prime Dimensions

Xiaoning Bian, Sarah Meng Li, Neil J. Ross +2 more

We present a complete set of $16$ rewrite rules for multi-qudit Clifford circuits in all odd prime dimensions. Completeness means that any two Clifford circuits representing the same linear map can be rewritten into each other using these rules. Each rule involves at most three qudits and admits an intuitive interpretation. To establish completeness, we first work at the symplectic level, using the isomorphism between the symplectic group $\mathrm{Sp}(2n,\mathbb{Z}_p)$ and the quotient of the Clifford group by the Pauli group. We construct a circuit normal form that captures the stabiliser tableau of a Clifford operator and is unique up to Pauli correction. Using this normal form, we derive a complete set of symplectic relations, which we then lift to Clifford relations by incorporating Pauli corrections. We also formally verify completeness in the Agda proof assistant.

quant-pharXiv:2609.40106•Oct 1, 2026•0 citations

Normal form for single-qutrit Clifford+ T operators and synthesis of single-qutrit gates

Shiroman Prakash, Akalank Jain, Bhakti Kapur +1 more

We study single-qutrit gates composed of Clifford and $T$ gates, using the qutrit version of the $T$ gate proposed by Howard and Vala [M. Howard and J. Vala, Phys. Rev. A 86, 022316 (2012)]. We propose a normal form for single-qutrit gates analogous to the Matsumoto-Amano normal form for qubits. We prove that the normal form is optimal with respect to the number of $T$ gates used and that any string of qutrit Clifford+$T$ operators can be put into this normal form in polynomial time. We also prove that this form is unique and provide an algorithm for exact synthesis of any single-qutrit Clifford+$T$ operator.

arXiv:1803.03228•Physical Review A•Sep 5, 2018•40 citations

Remarks on Matsumoto and Amano's normal form for single-qubit Clifford+T operators

Brett Gordon Giles, Peter Selinger

Matsumoto and Amano (2008) showed that every single-qubit Clifford+T operator can be uniquely written of a particular form, which we call the Matsumoto-Amano normal form. In this mostly expository paper, we give a detailed and streamlined presentation of Matsumoto and Amano's results, simplifying some proofs along the way. We also point out some corollaries to Matsumoto and Amano's work, including an intrinsic characterization of the Clifford+T subgroup of SO(3), which also yields an efficient T-optimal exact single-qubit synthesis algorithm. Interestingly, this also gives an alternative proof of Kliuchnikov, Maslov, and Mosca's exact synthesis result for the Clifford+T subgroup of U(2).

arXiv:1312.6584•Dec 23, 2013•19 citations

Generators and relations for n-qubit Clifford operators

Peter Selinger

We define a normal form for Clifford circuits, and we prove that every Clifford operator has a unique normal form. Moreover, we present a rewrite system by which any Clifford circuit can be reduced to normal form. This yields a presentation of Clifford operators in terms of generators and relations.

arXiv:1310.6813•Logical Methods in Computer Science•Jun 19, 2015•46 citations

Quantum Compiling Methods for Fault-Tolerant Gate Sets of Dimension Greater than Two

Andrew N. Glaudell

Fault-tolerant gate sets whose generators belong to the Clifford hierarchy form the basis of many protocols for scalable quantum computing architectures. At the beginning of the decade, number-theoretic techniques were employed to analyze circuits over these gate sets on single qubits, providing the basis for a number of state-of-the-art quantum compiling algorithms. In this dissertation, I further this program by employing number-theoretic techniques for higher-dimensional gate sets on both qudit and multi-qubit circuits. First, I introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. I show that these canonical forms are T-optimal and describe an algorithm which takes as input a Clifford+T circuit and outputs the canonical form for that operator. The algorithm runs in time linear in the number of gates of the circuit. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. Finally, we show that a similar extension of these normal forms to higher dimensions exists, but do not establish uniqueness. Moving to multi-qubit circuits, I 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/√−2], 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. I then establish the existence and uniqueness of a normal form for one of these gate sets, the two-qubit gate set of Clifford+Controlled Phase gate CS. This normal form is optimal in the number of CS gates, making it the first normal form that is non-Clifford optimal for a fault tolerant universal multi-qubit gate set. We provide a synthesis algorithm that runs in a time linear in the gate count and outputs the equivalent normal form. In proving the existence and uniqueness of the normal form, we likewise establish the generators and relations for the two-qubit Clifford+CS group. Finally, we demonstrate that a lower bound of 5 log2 (1/ε) + O(1) CS gates are required to ε-approximate any 4 × 4 unitary matrix. Lastly, using the characterization of circuits over the Clifford+CS gate set and the existence of an optimal normal form, I provide an ancilla-free inexact synthesis algorithm for two-qubit unitaries using the Clifford+SC gate set for Pauli-rotations. These operators require 6 log2 (1/ε) + O(1) CS gates to synthesize in the typical case and 8 log2 (1/ε) + O(1) in the worst case.

•Jan 1, 2019•2 citations
We propose a normal form for single-qudit gates composed of Clifford and TTT-gates for qudits of odd prime dimension p≥5p\geq 5p≥5. We prove that any single-qudit Clifford+TTT operator can be re-expressed in this normal form in polynomial time. We also provide strong numerical evidence that this normal form is unique. Assuming uniqueness, we are able to use this normal form to provide an algorithm for exact synthesis of any single-qudit Clifford+TTT operator with minimal TTT-count.
We propose a normal form for single-qudit gates composed of Clifford and TTT-gates for qudits of odd prime dimension p≥5p\geq 5p≥5. We prove that any single-qudit Clifford+TTT operator can be re-expressed in this normal form in polynomial time. We also provide strong numerical evidence that this normal form is unique. Assuming uniqueness, we are able to use this normal form to provide an algorithm for exact synthesis of any single-qudit Clifford+TTT operator with minimal TTT-count.
We present a complete set of 161616 rewrite rules for multi-qudit Clifford circuits in all odd prime dimensions. Completeness means that any two Clifford circuits representing the same linear map can be rewritten into each other using these rules. Each rule involves at most three qudits and admits an intuitive interpretation. To establish completeness, we first work at the symplectic level, using the isomorphism between the symplectic group Sp(2n,Zp)\mathrm{Sp}(2n,\mathbb{Z}_p)Sp(2n,Zp​) and the quotient of the Clifford group by the Pauli group. We construct a circuit normal form that captures the stabiliser tableau of a Clifford operator and is unique up to Pauli correction. Using this normal form, we derive a complete set of symplectic relations, which we then lift to Clifford relations by incorporating Pauli corrections. We also formally verify completeness in the Agda proof assistant.
We study single-qutrit gates composed of Clifford and TTT gates, using the qutrit version of the TTT gate proposed by Howard and Vala [M. Howard and J. Vala, Phys. Rev. A 86, 022316 (2012)]. We propose a normal form for single-qutrit gates analogous to the Matsumoto-Amano normal form for qubits. We prove that the normal form is optimal with respect to the number of TTT gates used and that any string of qutrit Clifford+TTT operators can be put into this normal form in polynomial time. We also prove that this form is unique and provide an algorithm for exact synthesis of any single-qutrit Clifford+TTT operator.
Matsumoto and Amano (2008) showed that every single-qubit Clifford+T operator can be uniquely written of a particular form, which we call the Matsumoto-Amano normal form. In this mostly expository paper, we give a detailed and streamlined presentation of Matsumoto and Amano's results, simplifying some proofs along the way. We also point out some corollaries to Matsumoto and Amano's work, including an intrinsic characterization of the Clifford+T subgroup of SO(3), which also yields an efficient T-optimal exact single-qubit synthesis algorithm. Interestingly, this also gives an alternative proof of Kliuchnikov, Maslov, and Mosca's exact synthesis result for the Clifford+T subgroup of U(2).
Fault-tolerant gate sets whose generators belong to the Clifford hierarchy form the basis of many protocols for scalable quantum computing architectures. At the beginning of the decade, number-theoretic techniques were employed to analyze circuits over these gate sets on single qubits, providing the basis for a number of state-of-the-art quantum compiling algorithms. In this dissertation, I further this program by employing number-theoretic techniques for higher-dimensional gate sets on both qudit and multi-qubit circuits. First, I introduce canonical forms for single qutrit Clifford+T circuits and prove that every single-qutrit Clifford+T operator admits a unique such canonical form. I show that these canonical forms are T-optimal and describe an algorithm which takes as input a Clifford+T circuit and outputs the canonical form for that operator. The algorithm runs in time linear in the number of gates of the circuit. Our results provide a higher-dimensional generalization of prior work by Matsumoto and Amano who introduced similar canonical forms for single-qubit Clifford+T circuits. Finally, we show that a similar extension of these normal forms to higher dimensions exists, but do not establish uniqueness. Moving to multi-qubit circuits, I 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/√−2], 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. I then establish the existence and uniqueness of a normal form for one of these gate sets, the two-qubit gate set of Clifford+Controlled Phase gate CS. This normal form is optimal in the number of CS gates, making it the first normal form that is non-Clifford optimal for a fault tolerant universal multi-qubit gate set. We provide a synthesis algorithm that runs in a time linear in the gate count and outputs the equivalent normal form. In proving the existence and uniqueness of the normal form, we likewise establish the generators and relations for the two-qubit Clifford+CS group. Finally, we demonstrate that a lower bound of 5 log2 (1/ε) + O(1) CS gates are required to ε-approximate any 4 × 4 unitary matrix. Lastly, using the characterization of circuits over the Clifford+CS gate set and the existence of an optimal normal form, I provide an ancilla-free inexact synthesis algorithm for two-qubit unitaries using the Clifford+SC gate set for Pauli-rotations. These operators require 6 log2 (1/ε) + O(1) CS gates to synthesize in the typical case and 8 log2 (1/ε) + O(1) in the worst case.