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

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.

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

arXiv:2609.40106 [quant-ph]

(or arXiv:2609.40106v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.40106 arXiv-issued DOI via DataCite (pending registration)