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

Completeness for Prime-Dimensional Phase-Affine Circuits

Colin Blake

quant-phcs.LOSubmitted Mar 6, 2026• Announced Mar 9, 2026• 0 citations• Revised Jun 28, 2026 (v2)
v1 · Mar 6, 2026v2 · Jun 28, 2026v3 · Jul 6, 2026
arXivHTMLPDF

Abstract

Equational reasoning about circuits underpins quantum-circuit optimisation and verification. The qubit CNOT-dihedral fragment achieves this through phase polynomials, layered normal forms, and a complete equational theory; we develop the corresponding theory for prime-dimensional qudits, where basis labels, value controls, and phase exponents share prime-field arithmetic. We first describe reversible affine circuits over Fd as transformations x->Ax+b, with an affine normal form extending Lafont's linear normal form by translations. Adjoining finite-angle diagonal phases by polynomial degree yields linear, quadratic (odd prime), and cubic (prime greater than 3) calculi whose binomial-basis identities expose the mixed diagonal gates forced by affine transport. These calculi have unique phase-affine normal forms and are complete: semantic equality coincides with derivable equality, giving a prime-dimensional phase-polynomial analogue of the CNOT-dihedral equational theory.

Related papers

A Finite Presentation of CNOT-Dihedral Operators

Matthew Amy, Jianxin Chen, Neil J. Ross

We give a finite presentation by generators and relations of the unitary operators expressible over the {CNOT, T, X} gate set, also known as CNOT-dihedral operators. To this end, we introduce a notion of normal form for CNOT-dihedral circuits and prove that every CNOT-dihedral operator admits a unique normal form. Moreover, we show that in the presence of certain structural rules only finitely many circuit identities are required to reduce an arbitrary CNOT-dihedral circuit to its normal form. By appropriately restricting our relations, we obtain a finite presentation of unitary operators expressible over the {CNOT, T} gate set as a corollary.

arXiv:1701.00140•Electronic Proceedings in Theoretical Computer Science•Feb 27, 2018•33 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

Complete ZX-Calculi for the Stabiliser Fragment in Odd Prime Dimensions

Robert I. Booth, Titouan Carette

We introduce a family of ZX-calculi which axiomatise the stabiliser fragment of quantum theory in odd prime dimensions. These calculi recover many of the nice features of the qubit ZX-calculus which were lost in previous proposals for higher-dimensional systems. We then prove that these calculi are complete, i.e. provide a set of rewrite rules which can be used to prove any equality of stabiliser quantum operations. Adding a discard construction, we obtain a calculus complete for mixed state stabiliser quantum mechanics in odd prime dimensions, and this furthermore gives a complete axiomatisation for the related diagrammatic language for affine co-isotropic relations.

arXiv:2204.12531•Leibniz international proceedings in informatics•Jan 1, 2022•27 citations

The Qupit Stabiliser ZX-travaganza: Simplified Axioms, Normal Forms and Graph-Theoretic Simplification

Boldizsár Poór, Robert I. Booth, Titouan Carette +2 more

We present a smorgasbord of results on the stabiliser ZX-calculus for odd prime-dimensional qudits (i.e.qupits).We derive a simplified rule set that closely resembles the original rules of qubit ZX-calculus.Using these rules, we demonstrate analogues of the spider-removing local complementation and pivoting rules.This allows for efficient reduction of diagrams to the affine with phases normal form.We also demonstrate a reduction to a unique form, providing an alternative and simpler proof of completeness.Furthermore, we introduce a different reduction to the graph state with local Cliffords normal form, which leads to a novel layered decomposition for qupit Clifford unitaries.Additionally, we propose a new approach to handle scalars formally, closely reflecting their practical usage.Finally, we have implemented many of these findings in DiZX, a new open-source Python library for qudit ZX-diagrammatic reasoning.

arXiv:2306.05204•Electronic Proceedings in Theoretical Computer Science•Aug 23, 2023•19 citations

A Complete Equational Presentation of Qudit Circuits via Polycontrolled PROPs

Colin Blake

High-dimensional quantum computation needs a native circuit-level equational theory for qudits. We give the first finite schematic equational theory that is sound and complete for exact unitary qudit circuits in every finite dimension at least two. Circuits are built from local gates, sequential and parallel composition, and value-controls; equality is derivable exactly when the standard unitary denotations agree. For each dimension, a finite list of local bounded-arity axiom schemata presents the theory, and the diagrammatic shapes do not depend on d. Primitive value-control makes control on a chosen basis value part of the language, so local rules generate the internal algebra of controlled operations within the circuit PROP. This gives a finite, dimension-uniform basis for exact equational reasoning about qudit circuits.

quant-pharXiv:2602.09873•Leibniz international proceedings in informatics•Feb 11, 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•Leibniz international proceedings in informatics•Feb 11, 2026•3 citations
Equational reasoning about circuits underpins quantum-circuit optimisation and verification. The qubit CNOT-dihedral fragment achieves this through phase polynomials, layered normal forms, and a complete equational theory; we develop the corresponding theory for prime-dimensional qudits, where basis labels, value controls, and phase exponents share prime-field arithmetic. We first describe reversible affine circuits over Fd as transformations x->Ax+b, with an affine normal form extending Lafont's linear normal form by translations. Adjoining finite-angle diagonal phases by polynomial degree yields linear, quadratic (odd prime), and cubic (prime greater than 3) calculi whose binomial-basis identities expose the mixed diagonal gates forced by affine transport. These calculi have unique phase-affine normal forms and are complete: semantic equality coincides with derivable equality, giving a prime-dimensional phase-polynomial analogue of the CNOT-dihedral equational theory.
We give a finite presentation by generators and relations of the unitary operators expressible over the {CNOT, T, X} gate set, also known as CNOT-dihedral operators. To this end, we introduce a notion of normal form for CNOT-dihedral circuits and prove that every CNOT-dihedral operator admits a unique normal form. Moreover, we show that in the presence of certain structural rules only finitely many circuit identities are required to reduce an arbitrary CNOT-dihedral circuit to its normal form. By appropriately restricting our relations, we obtain a finite presentation of unitary operators expressible over the {CNOT, T} gate set as a corollary.
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 introduce a family of ZX-calculi which axiomatise the stabiliser fragment of quantum theory in odd prime dimensions. These calculi recover many of the nice features of the qubit ZX-calculus which were lost in previous proposals for higher-dimensional systems. We then prove that these calculi are complete, i.e. provide a set of rewrite rules which can be used to prove any equality of stabiliser quantum operations. Adding a discard construction, we obtain a calculus complete for mixed state stabiliser quantum mechanics in odd prime dimensions, and this furthermore gives a complete axiomatisation for the related diagrammatic language for affine co-isotropic relations.
We present a smorgasbord of results on the stabiliser ZX-calculus for odd prime-dimensional qudits (i.e.qupits).We derive a simplified rule set that closely resembles the original rules of qubit ZX-calculus.Using these rules, we demonstrate analogues of the spider-removing local complementation and pivoting rules.This allows for efficient reduction of diagrams to the affine with phases normal form.We also demonstrate a reduction to a unique form, providing an alternative and simpler proof of completeness.Furthermore, we introduce a different reduction to the graph state with local Cliffords normal form, which leads to a novel layered decomposition for qupit Clifford unitaries.Additionally, we propose a new approach to handle scalars formally, closely reflecting their practical usage.Finally, we have implemented many of these findings in DiZX, a new open-source Python library for qudit ZX-diagrammatic reasoning.
High-dimensional quantum computation needs a native circuit-level equational theory for qudits. We give the first finite schematic equational theory that is sound and complete for exact unitary qudit circuits in every finite dimension at least two. Circuits are built from local gates, sequential and parallel composition, and value-controls; equality is derivable exactly when the standard unitary denotations agree. For each dimension, a finite list of local bounded-arity axiom schemata presents the theory, and the diagrammatic shapes do not depend on d. Primitive value-control makes control on a chosen basis value part of the language, so local rules generate the internal algebra of controlled operations within the circuit PROP. This gives a finite, dimension-uniform basis for exact equational reasoning about qudit circuits.
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.