Completeness for Prime-Dimensional Phase-Affine Circuits

Equational reasoning about circuits underpins quantum-circuit optimisation and verification.In the qubit CNOT-dihedral fragment, phase polynomials and layered normal forms support 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 F d 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, and cubic calculi.Their binomial-basis identities expose the mixed diagonal gates forced by affine transport.These calculi have unique phase-affine normal forms, and the resulting equational theories are complete: semantic equality coincides with derivable equality.