Completeness for Prime-Dimensional Phase-Affine Circuits
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
Equational reasoning about circuits is central in quantum software for validation, optimisation, and verification. For qubits, the CNOT-dihedral fragment supports efficient rewriting via phase polynomials and layered normal forms, yielding a complete and practically effective equational theory. In this work we generalise that CNOT-dihedral picture from qubits to prime-dimensional qudits. We present a compact PROP for reversible affine circuits over a prime field, with a strict symmetric monoidal semantics into the affine group and a Lafont-style affine normal form. We then adjoin finite-angle diagonal phase generators and organise them by polynomial degree, obtaining linear, quadratic (odd prime), and cubic (prime greater than 3) calculi. Using binomial-basis identities we derive uniform transport rules, establish unique phase-affine normal forms, and prove completeness: semantic equality coincides with derivable equality. This yields a prime-dimensional, phase-polynomial-aligned generalisation of the CNOT-dihedral equational theory.