Neil J. Ross

We present a complete set of rewrite rules for multi-qudit Clifford circuits, where \emph{qudit} denotes a d-level quantum system with d an odd prime. Completeness means that any two Clifford circuits representing the same linear map can be transformed into each other using these rules. In total, there are 19 \emph{Clifford relations}, each involving at most three qudits and admitting an intuitive interpretation. Our approach leverages the isomorphism between the symplectic group $\mathrm{Sp}(2n, \mathbb{Z}_d)$ and the quotient of the Clifford group by the Pauli group. We first derive a complete set of \emph{symplectic relations} for $\mathrm{Sp}(2n, \mathbb{Z}_d)$, and then lift them to Clifford relations by incorporating Pauli corrections. To do this, we introduce a \emph{symplectic normal form} that captures the stabiliser tableau of a Clifford operator and is unique up to Pauli correction. This simplification enables a streamlined derivation of a complete set of 66 relations, which we further compress to 18 symplectic relations. Our computations in $\mathrm{Sp}(2n, \mathbb{Z}_d)$ are formalised in the Agda proof assistant, providing a machine-verified proof of correctness.