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:2609.40106

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

Xiaoning Bian, Sarah Meng Li, Neil J. Ross, John van de Wetering, Yuming Zhao

quant-phSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
v1 · Sep 30, 2026v2 · Oct 5, 2026
arXivHTMLPDF

Abstract

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}_d)$ 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 up to global phase in the Agda proof assistant.

Comments
80 pages, plus a separate supplement. This work is accompanied by a full proof of the relation reduction written without AI assistance and a machine-checked Agda formalisation, both available in public repositories linked in the paper

Related papers

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

Sarah Meng Li, Michele Mosca, Neil J. Ross +2 more

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.

arXiv:2508.14670•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•2 citations

A Normal Form for Single-Qudit Clifford+TTT Operators

Akalank Jain, Amolak Ratan Kalra, Shiroman Prakash

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.

arXiv:2011.07970•Nov 16, 2020•0 citations

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 theory of the Clifford commutant

Lennart Bittel, Jens Eisert, Lorenzo Leone +2 more

The Clifford group plays a central role in quantum information science. It is the building block for many error-correcting schemes and matches the first three moments of the Haar measure over the unitary group-a property that is essential for a broad range of quantum algorithms, with applications in pseudorandomness, learning theory, benchmarking, and entanglement distillation. At the heart of understanding many properties of the Clifford group lies the Clifford commutant: the set of operators that commute with k -fold tensor powers of Clifford unitaries. Previous understanding of this commutant has been limited to relatively small values of k , constrained by the number of qubits n . In this work, we develop a complete theory of the Clifford commutant. Our first result provides an explicit orthogonal basis for the commutant and computes its dimension for arbitrary n and k . We also introduce an alternative and easy-to-manipulate basis formed by isotropic sums of Pauli operators. We show that this basis is generated by products of permutations, which generate the unitary group commutant, and at most three other operators. Additionally, we develop a graphical calculus allowing a diagrammatic manipulation of elements of this basis. These results enable a wealth of applications: among others, we characterize all measurable magic measures and identify optimal strategies for stabilizer property testing, whose success probability also offers an operational interpretation to stabilizer entropies. Finally, we show that these results also generalize to multi-qudit systems with prime local dimension.

arXiv:2504.12263•Quantum•Jul 22, 2026•2 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

Generators And Relations for Some Classes of Quantum Circuits

Xiaoning Bian

We give three finite presentations in terms of generators and relations for three groups of operators. The operators are frequently used in quantum computation. The result can potentially be used to optimize quantum circuits. Two of the three proofs use the Reidemeister-Schreier theorem. Both the Reidemeister-Schreier theorem and the two proofs using it have been formally verified in the proof assistant Agda. First, we give a finite presentation of the group of 2-qubit Clifford+T operators. The proof applies the Reidemeister-Schreier theorem to a finite presentation of a supergroup of the 2-qubit Clifford+T group that was given by Greylyn. The process generates hundreds of relations. We then simplify them to 20 relations using a Pauli rotation representation as an almost-normal form. Second, we give a finite presentation of U_n (Z[1/2, i]), the group of unitary n × n- matrices with entries in Z[1/2, i]. Amy, Glaudell, and Ross showed that this group is generated by a certain set of two-level matrices, and they also gave an exact synthesis algorithm that converts any element of U_n (Z[1/2, i]) to a word in these generators. We say that a word is in normal form if it is an output of the exact synthesis algorithm. Using what we call semantically guided rewriting, we show that each word in the two-level generators is equivalent to a normal form under the congruence generated by finitely many relations. Third, we give a finite presentation of the group of 3-qubit Clifford+CS operators. Amy, Glaudell, and Ross proved that up to a condition on the determinant, the n-qubit Clifford+CS group is exactly U_(2^n) (Z[1/2, i]). In particular, the 3-qubit Clifford+CS group is a subgroup of U_8 (Z[1/2, i]) of index 2. Using a similar technique as in our first result, we repeatedly apply the Reidemeister-Schreier theorem to the presentation of U_8 (Z[1/2, i]) (from our second result), and then simplify thousands of relations into 17 relations. To do the simplification, we devise an almost-normal form for Clifford+CS operators. We also show that the 3-qubit Clifford+CS group, which is of course infinite, is the amalgamated product of three finite subgroups.

•Aug 24, 2023•0 citations
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,Zd)\mathrm{Sp}(2n,\mathbb{Z}_d)Sp(2n,Zd​) 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 up to global phase in the Agda proof assistant.
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 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.
The Clifford group plays a central role in quantum information science. It is the building block for many error-correcting schemes and matches the first three moments of the Haar measure over the unitary group-a property that is essential for a broad range of quantum algorithms, with applications in pseudorandomness, learning theory, benchmarking, and entanglement distillation. At the heart of understanding many properties of the Clifford group lies the Clifford commutant: the set of operators that commute with k -fold tensor powers of Clifford unitaries. Previous understanding of this commutant has been limited to relatively small values of k , constrained by the number of qubits n . In this work, we develop a complete theory of the Clifford commutant. Our first result provides an explicit orthogonal basis for the commutant and computes its dimension for arbitrary n and k . We also introduce an alternative and easy-to-manipulate basis formed by isotropic sums of Pauli operators. We show that this basis is generated by products of permutations, which generate the unitary group commutant, and at most three other operators. Additionally, we develop a graphical calculus allowing a diagrammatic manipulation of elements of this basis. These results enable a wealth of applications: among others, we characterize all measurable magic measures and identify optimal strategies for stabilizer property testing, whose success probability also offers an operational interpretation to stabilizer entropies. Finally, we show that these results also generalize to multi-qudit systems with prime local dimension.
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 give three finite presentations in terms of generators and relations for three groups of operators. The operators are frequently used in quantum computation. The result can potentially be used to optimize quantum circuits. Two of the three proofs use the Reidemeister-Schreier theorem. Both the Reidemeister-Schreier theorem and the two proofs using it have been formally verified in the proof assistant Agda. First, we give a finite presentation of the group of 2-qubit Clifford+T operators. The proof applies the Reidemeister-Schreier theorem to a finite presentation of a supergroup of the 2-qubit Clifford+T group that was given by Greylyn. The process generates hundreds of relations. We then simplify them to 20 relations using a Pauli rotation representation as an almost-normal form. Second, we give a finite presentation of U_n (Z[1/2, i]), the group of unitary n × n- matrices with entries in Z[1/2, i]. Amy, Glaudell, and Ross showed that this group is generated by a certain set of two-level matrices, and they also gave an exact synthesis algorithm that converts any element of U_n (Z[1/2, i]) to a word in these generators. We say that a word is in normal form if it is an output of the exact synthesis algorithm. Using what we call semantically guided rewriting, we show that each word in the two-level generators is equivalent to a normal form under the congruence generated by finitely many relations. Third, we give a finite presentation of the group of 3-qubit Clifford+CS operators. Amy, Glaudell, and Ross proved that up to a condition on the determinant, the n-qubit Clifford+CS group is exactly U_(2^n) (Z[1/2, i]). In particular, the 3-qubit Clifford+CS group is a subgroup of U_8 (Z[1/2, i]) of index 2. Using a similar technique as in our first result, we repeatedly apply the Reidemeister-Schreier theorem to the presentation of U_8 (Z[1/2, i]) (from our second result), and then simplify thousands of relations into 17 relations. To do the simplification, we devise an almost-normal form for Clifford+CS operators. We also show that the 3-qubit Clifford+CS group, which is of course infinite, is the amalgamated product of three finite subgroups.