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:2508.14670 · Electronic Proceedings in Theoretical Computer Science

A Complete and Natural Rule Set for Multi-Qutrit Clifford Circuits

Sarah Meng Li, Michele Mosca, Neil J. Ross, John van de Wetering, Yuming Zhao

Published Aug 19, 2025• 2 citations
arXivHTMLPDF

Abstract

We present a complete set of rewrite rules for n-qutrit Clifford circuits where n is any non-negative integer.This is the first completeness result for any fragment of quantum circuits in odd prime dimensions.We first generalize Selinger's normal form for n-qubit Clifford circuits to the qutrit setting.Then, we present a rewrite system by which any Clifford circuit can be reduced to this normal form.We then simplify the rewrite rules in this procedure to a small natural set of rules, giving a clean presentation of the group of qutrit Clifford unitaries in terms of generators and relations.

DOI
10.4204/eptcs.426.2

Related papers

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

Simpler Presentations for Many Fragments of Quantum Circuits

Colin Blake

Equational reasoning is central to quantum circuit optimisation and verification: one replaces subcircuits by provably equivalent ones using a fixed set of rewrite rules viewed as equations. A finite rule set is most informative when it separates the genuine algebra of a circuit fragment from the structural treatment of wires. This paper gives six near-Clifford fragments a common PROP treatment, where wire permutations are structural: qubit Clifford, real Clifford, Clifford+T (up to two qubits), Clifford+CS (up to three qubits), CNOT-dihedral, and qutrit Clifford. Starting from prior completeness theorems, we transfer completeness into this setting and remove redundant non-structural rules, then check minimality by separating interpretations tailored to individual axioms; the resulting presentations are minimal in all arities for qubit Clifford, real Clifford, and CNOT-dihedral, minimal in bounded ranges for the remaining fragments, and comparable by one transfer-and-separation pattern.

quant-pharXiv:2602.09874•Feb 11, 2026•0 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

Nine Normal Forms: A Complete Rewrite System for the Single-Phase Three-Qubit Fragment of the Clifford Hierarchy

Ian Richard C Buckley

We prove the first completeness theorem for a multi-qubit fragment of the third Clifford level ($\mathsf{C}3$). Let $\mathcal{F}$ be the single-phase 3-qubit fragment: the 42 states of the form $T_i^{(\pm)} \cdot B_k \cdot |{+}{+}{+}\rangle$, where ${B_k}{k=0}^{6}$ are the seven CZ-type base circuits of the Origami ISA and $T_i^{(\pm)} \in {T_i, T_i^\dagger}$ applies a single T gate to qubit $i$. We define a rewrite system $\mathcal{R} = {R3, R4}$ on $\mathcal{F}$: R3 (T-absorption): $T_i \cdot B_k \cdot |{+}{+}{+}\rangle \to B_k \cdot |{+}{+}{+}\rangle$ when the T gate acts trivially on the reduced state of qubit $i$ in $B_k |{+}{+}{+}\rangle$. R4 (SWAP normalisation): reorder qubits into lexicographically smallest equivalent representative. Theorem 1 (Completeness). Two states $\psi_1, \psi_2 \in \mathcal{F}$ satisfy $\psi_1 = e^{i\theta}\psi_2$ for some $\theta \in \mathbb{R}$ if and only if $\mathcal{R}$ reduces both to the same SWAP-normal form. There are exactly 9 normal forms. The proof follows the standard term-rewriting route: (i) termination via a two-component measure (C$_3$-gate count, lexicographic qubit order); (ii) local confluence by explicit critical-pair analysis; (iii) global confluence by Newman's lemma; (iv) faithfulness by exact state-vector comparison. The 9 normal forms partition into three resource tiers — 1 stabiliser, 6 dark magic ($\mathcal{N} = 0$, $\mathrm{TV} < 1$), and 2 genuine magic ($\mathcal{N} > 0$) — where $\mathrm{TV}(\psi) = \sum_u |W_\psi(u)|$ is the total variation of the discrete Wigner function. A key corollary: the magic class of any state in $\mathcal{F}$ is decidable at compile time by a single rule application of R3, with no state tomography required. This is the first completeness result for any multi-qubit $\mathsf{C}_3$ rewrite system. Prior completeness results (Hadzihasanovic–Ng–Wang 2018; Jeandel–Perdrix–Vilmart 2018) covered single-qubit Clifford+T; this result covers the 3-qubit single-phase case. Part of the Origami ISA series. Companion papers: 466 (CZ-type bases) · 467 (magic orbits) · 468 (ISA as coloured PROP) · 470 (three-tier resource theory) Keywords: quantum resource theory, magic states, Clifford hierarchy, rewrite systems, confluence, normal forms, dark magic, Wigner function, total variation, stabiliser states, T gate, Origami ISA, categorical quantum mechanics, PROP, term rewriting

•Jul 6, 2026•0 citations

Nine Normal Forms: A Complete Rewrite System for the Single-Phase Three-Qubit Fragment of the Clifford Hierarchy

Ian Richard C Buckley

We prove the first completeness theorem for a multi-qubit fragment of the third Clifford level ($\mathsf{C}3$). Let $\mathcal{F}$ be the single-phase 3-qubit fragment: the 42 states of the form $T_i^{(\pm)} \cdot B_k \cdot |{+}{+}{+}\rangle$, where ${B_k}{k=0}^{6}$ are the seven CZ-type base circuits of the Origami ISA and $T_i^{(\pm)} \in {T_i, T_i^\dagger}$ applies a single T gate to qubit $i$. We define a rewrite system $\mathcal{R} = {R3, R4}$ on $\mathcal{F}$: R3 (T-absorption): $T_i \cdot B_k \cdot |{+}{+}{+}\rangle \to B_k \cdot |{+}{+}{+}\rangle$ when the T gate acts trivially on the reduced state of qubit $i$ in $B_k |{+}{+}{+}\rangle$. R4 (SWAP normalisation): reorder qubits into lexicographically smallest equivalent representative. Theorem 1 (Completeness). Two states $\psi_1, \psi_2 \in \mathcal{F}$ satisfy $\psi_1 = e^{i\theta}\psi_2$ for some $\theta \in \mathbb{R}$ if and only if $\mathcal{R}$ reduces both to the same SWAP-normal form. There are exactly 9 normal forms. The proof follows the standard term-rewriting route: (i) termination via a two-component measure (C$_3$-gate count, lexicographic qubit order); (ii) local confluence by explicit critical-pair analysis; (iii) global confluence by Newman's lemma; (iv) faithfulness by exact state-vector comparison. The 9 normal forms partition into three resource tiers — 1 stabiliser, 6 dark magic ($\mathcal{N} = 0$, $\mathrm{TV} < 1$), and 2 genuine magic ($\mathcal{N} > 0$) — where $\mathrm{TV}(\psi) = \sum_u |W_\psi(u)|$ is the total variation of the discrete Wigner function. A key corollary: the magic class of any state in $\mathcal{F}$ is decidable at compile time by a single rule application of R3, with no state tomography required. This is the first completeness result for any multi-qubit $\mathsf{C}_3$ rewrite system. Prior completeness results (Hadzihasanovic–Ng–Wang 2018; Jeandel–Perdrix–Vilmart 2018) covered single-qubit Clifford+T; this result covers the 3-qubit single-phase case. Part of the Origami ISA series. Companion papers: 466 (CZ-type bases) · 467 (magic orbits) · 468 (ISA as coloured PROP) · 470 (three-tier resource theory) Keywords: quantum resource theory, magic states, Clifford hierarchy, rewrite systems, confluence, normal forms, dark magic, Wigner function, total variation, stabiliser states, T gate, Origami ISA, categorical quantum mechanics, PROP, term rewriting

•Jun 27, 2026•0 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 present a complete set of rewrite rules for n-qutrit Clifford circuits where n is any non-negative integer.This is the first completeness result for any fragment of quantum circuits in odd prime dimensions.We first generalize Selinger's normal form for n-qubit Clifford circuits to the qutrit setting.Then, we present a rewrite system by which any Clifford circuit can be reduced to this normal form.We then simplify the rewrite rules in this procedure to a small natural set of rules, giving a clean presentation of the group of qutrit Clifford unitaries in terms of generators and relations.
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.
Equational reasoning is central to quantum circuit optimisation and verification: one replaces subcircuits by provably equivalent ones using a fixed set of rewrite rules viewed as equations. A finite rule set is most informative when it separates the genuine algebra of a circuit fragment from the structural treatment of wires. This paper gives six near-Clifford fragments a common PROP treatment, where wire permutations are structural: qubit Clifford, real Clifford, Clifford+T (up to two qubits), Clifford+CS (up to three qubits), CNOT-dihedral, and qutrit Clifford. Starting from prior completeness theorems, we transfer completeness into this setting and remove redundant non-structural rules, then check minimality by separating interpretations tailored to individual axioms; the resulting presentations are minimal in all arities for qubit Clifford, real Clifford, and CNOT-dihedral, minimal in bounded ranges for the remaining fragments, and comparable by one transfer-and-separation pattern.
We prove the first completeness theorem for a multi-qubit fragment of the third Clifford level (C3\mathsf{C}3C3). Let F\mathcal{F}F be the single-phase 3-qubit fragment: the 42 states of the form Ti(±)⋅Bk⋅∣+++⟩T_i^{(\pm)} \cdot B_k \cdot |{+}{+}{+}\rangleTi(±)​⋅Bk​⋅∣+++⟩, where Bkk=06{B_k}{k=0}^{6}Bk​k=06 are the seven CZ-type base circuits of the Origami ISA and Ti(±)∈Ti,Ti†T_i^{(\pm)} \in {T_i, T_i^\dagger}Ti(±)​∈Ti​,Ti†​ applies a single T gate to qubit iii. We define a rewrite system R=R3,R4\mathcal{R} = {R3, R4}R=R3,R4 on F\mathcal{F}F: R3 (T-absorption): Ti⋅Bk⋅∣+++⟩→Bk⋅∣+++⟩T_i \cdot B_k \cdot |{+}{+}{+}\rangle \to B_k \cdot |{+}{+}{+}\rangleTi​⋅Bk​⋅∣+++⟩→Bk​⋅∣+++⟩ when the T gate acts trivially on the reduced state of qubit iii in Bk∣+++⟩B_k |{+}{+}{+}\rangleBk​∣+++⟩. R4 (SWAP normalisation): reorder qubits into lexicographically smallest equivalent representative. Theorem 1 (Completeness). Two states ψ1,ψ2∈F\psi_1, \psi_2 \in \mathcal{F}ψ1​,ψ2​∈F satisfy ψ1=eiθψ2\psi_1 = e^{i\theta}\psi_2ψ1​=eiθψ2​ for some θ∈R\theta \in \mathbb{R}θ∈R if and only if R\mathcal{R}R reduces both to the same SWAP-normal form. There are exactly 9 normal forms. The proof follows the standard term-rewriting route: (i) termination via a two-component measure (C3_33​-gate count, lexicographic qubit order); (ii) local confluence by explicit critical-pair analysis; (iii) global confluence by Newman's lemma; (iv) faithfulness by exact state-vector comparison. The 9 normal forms partition into three resource tiers — 1 stabiliser, 6 dark magic (N=0\mathcal{N} = 0N=0, TV<1\mathrm{TV} < 1TV<1), and 2 genuine magic (N>0\mathcal{N} > 0N>0) — where TV(ψ)=∑u∣Wψ(u)∣\mathrm{TV}(\psi) = \sum_u |W_\psi(u)|TV(ψ)=∑u​∣Wψ​(u)∣ is the total variation of the discrete Wigner function. A key corollary: the magic class of any state in F\mathcal{F}F is decidable at compile time by a single rule application of R3, with no state tomography required. This is the first completeness result for any multi-qubit C3\mathsf{C}_3C3​ rewrite system. Prior completeness results (Hadzihasanovic–Ng–Wang 2018; Jeandel–Perdrix–Vilmart 2018) covered single-qubit Clifford+T; this result covers the 3-qubit single-phase case. Part of the Origami ISA series. Companion papers: 466 (CZ-type bases) · 467 (magic orbits) · 468 (ISA as coloured PROP) · 470 (three-tier resource theory) Keywords: quantum resource theory, magic states, Clifford hierarchy, rewrite systems, confluence, normal forms, dark magic, Wigner function, total variation, stabiliser states, T gate, Origami ISA, categorical quantum mechanics, PROP, term rewriting
We prove the first completeness theorem for a multi-qubit fragment of the third Clifford level (C3\mathsf{C}3C3). Let F\mathcal{F}F be the single-phase 3-qubit fragment: the 42 states of the form Ti(±)⋅Bk⋅∣+++⟩T_i^{(\pm)} \cdot B_k \cdot |{+}{+}{+}\rangleTi(±)​⋅Bk​⋅∣+++⟩, where Bkk=06{B_k}{k=0}^{6}Bk​k=06 are the seven CZ-type base circuits of the Origami ISA and Ti(±)∈Ti,Ti†T_i^{(\pm)} \in {T_i, T_i^\dagger}Ti(±)​∈Ti​,Ti†​ applies a single T gate to qubit iii. We define a rewrite system R=R3,R4\mathcal{R} = {R3, R4}R=R3,R4 on F\mathcal{F}F: R3 (T-absorption): Ti⋅Bk⋅∣+++⟩→Bk⋅∣+++⟩T_i \cdot B_k \cdot |{+}{+}{+}\rangle \to B_k \cdot |{+}{+}{+}\rangleTi​⋅Bk​⋅∣+++⟩→Bk​⋅∣+++⟩ when the T gate acts trivially on the reduced state of qubit iii in Bk∣+++⟩B_k |{+}{+}{+}\rangleBk​∣+++⟩. R4 (SWAP normalisation): reorder qubits into lexicographically smallest equivalent representative. Theorem 1 (Completeness). Two states ψ1,ψ2∈F\psi_1, \psi_2 \in \mathcal{F}ψ1​,ψ2​∈F satisfy ψ1=eiθψ2\psi_1 = e^{i\theta}\psi_2ψ1​=eiθψ2​ for some θ∈R\theta \in \mathbb{R}θ∈R if and only if R\mathcal{R}R reduces both to the same SWAP-normal form. There are exactly 9 normal forms. The proof follows the standard term-rewriting route: (i) termination via a two-component measure (C3_33​-gate count, lexicographic qubit order); (ii) local confluence by explicit critical-pair analysis; (iii) global confluence by Newman's lemma; (iv) faithfulness by exact state-vector comparison. The 9 normal forms partition into three resource tiers — 1 stabiliser, 6 dark magic (N=0\mathcal{N} = 0N=0, TV<1\mathrm{TV} < 1TV<1), and 2 genuine magic (N>0\mathcal{N} > 0N>0) — where TV(ψ)=∑u∣Wψ(u)∣\mathrm{TV}(\psi) = \sum_u |W_\psi(u)|TV(ψ)=∑u​∣Wψ​(u)∣ is the total variation of the discrete Wigner function. A key corollary: the magic class of any state in F\mathcal{F}F is decidable at compile time by a single rule application of R3, with no state tomography required. This is the first completeness result for any multi-qubit C3\mathsf{C}_3C3​ rewrite system. Prior completeness results (Hadzihasanovic–Ng–Wang 2018; Jeandel–Perdrix–Vilmart 2018) covered single-qubit Clifford+T; this result covers the 3-qubit single-phase case. Part of the Origami ISA series. Companion papers: 466 (CZ-type bases) · 467 (magic orbits) · 468 (ISA as coloured PROP) · 470 (three-tier resource theory) Keywords: quantum resource theory, magic states, Clifford hierarchy, rewrite systems, confluence, normal forms, dark magic, Wigner function, total variation, stabiliser states, T gate, Origami ISA, categorical quantum mechanics, PROP, term rewriting
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.