Pith. sign in

REVIEW 1 major objections 5 minor 31 references

Prime-dimensional phase-affine circuits have unique layered normal forms and complete equational theories, matching the qubit CNOT-dihedral case.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-15 13:48 UTC pith:7IZEL2D2

load-bearing objection Solid, usable completeness theorems for prime-dimensional phase-affine fragments; the binomial-transport calculus is the real contribution. the 1 major comments →

arxiv 2603.06466 v3 pith:7IZEL2D2 submitted 2026-03-06 quant-ph cs.LO

Completeness for Prime-Dimensional Phase-Affine Circuits

Colin Blake This is my paper
classification quant-ph cs.LO
keywords phase-affine circuitsprime-dimensional quditscomplete equational theoryphase polynomialsaffine normal formsPROPCNOT-dihedral generalisation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper supplies complete rewrite systems for three families of qudit circuits built from reversible affine maps over a prime field together with finite-angle diagonal phases of total degree at most one, two or three. The qubit CNOT-dihedral fragment already enjoys phase-polynomial semantics, layered normal forms and a finite equational theory that underpins optimisation and verification; the work lifts that picture to prime dimension d by treating basis labels, controls and phase exponents uniformly in F_d. Affine circuits are axiomatised by a compact PROP whose normal form extends Lafont’s linear form by translations; adjoining Z, S (odd d) and T (d>3) generators produces linear, quadratic and cubic calculi. Transport rules derived from binomial identities collect every diagonal gate into a single layer, after which uniqueness of the binomial expansion of the phase function forces uniqueness of the normal form. Completeness follows: two circuits are semantically equal if and only if their equality is derivable from the finite axiom set. The result therefore gives a diagrammatic, phase-polynomial interface for multiqudit compilation that mirrors the qubit theory already used in practice.

Core claim

For each of the three fragments LinPhase_d, QuadPhase_d (odd prime d) and CubicPhase_d (prime d>3), every circuit rewrites to a unique composite of an affine normal form and a diagonal normal form; consequently semantic equality of circuits coincides with derivable equality from the corresponding finite axiom set.

What carries the argument

Phase-affine normal forms: every circuit factors as A ◦ D, where A is the unique Lafont-style affine normal form of the underlying map x ↦ Ax+b and D is the unique diagonal layer whose exponents are the coefficients of the phase function in the degree-bounded binomial basis over F_d.

Load-bearing premise

The uniqueness argument treats the binomial polynomials of degree at most three as automatically linearly independent over every prime field of characteristic larger than the degree, without an explicit independence proof inside the text.

What would settle it

Exhibit two distinct diagonal normal-form circuits (different exponent tuples) that induce the identical phase function of total degree ≤3 on F_d^n for some prime d>3, or produce a circuit that cannot be rewritten into the claimed layered shape using only the stated axioms.

Watch this falsifier — get emailed when new claim-graph text bears on it.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 5 minor

Summary. The paper constructs complete equational theories for prime-dimensional phase-affine circuits. It first presents the PROP Aff_d of reversible affine maps x ↦ Ax + b over F_d, with generators for translations, shears and scalings, a Lafont-style affine normal form, and completeness for GA_n(F_d). It then adjoins finite-angle diagonal generators Z, S (odd prime d) and T (d > 3) organised by polynomial degree, yielding the PROPs LinPhase_d, QuadPhase_d and CubicPhase_d. Semantic models are strict symmetric monoidal groupoids of pairs (g, q) with semidirect-product composition. Completeness (Theorem 2) is obtained by rewriting every circuit to a unique layered normal form A ◦ D (affine normal form followed by a binomial-basis diagonal normal form) via transport and commutation identities, so that semantic equality coincides with derivable equality.

Significance. If the results hold, the work supplies the natural prime-dimensional counterpart of the CNOT-dihedral equational theory that underpins qubit phase-polynomial optimisation, T-count reduction and parity-network synthesis. The calculi are aligned with the Clifford hierarchy and with existing multiqudit compilation techniques, and therefore constitute a usable diagrammatic interface for verification and rewriting of affine-plus-diagonal fragments over F_d. Explicit strengths include the fully expanded appendix derivations of all transport and commutation tables, the alternative group-theoretic presentations of SL_n, GL_n and GA_n in Appendix B, and the clean degree stratification that isolates precisely when new controlled-diagonal primitives appear. The normal-form uniqueness arguments rest on standard binomial bases once the characteristic hypotheses are met, making the completeness theorems robust.

major comments (1)
  1. [Lemma 11 / §3.5] Lemma 11 asserts uniqueness of the diagonal normal forms by unique expansion of degree-≤1/2/3 functions in the binomial basis over F_d. Under the standing hypotheses (d odd, respectively d>3) this is standard, and the finite-difference identities of Lemmas 5–7 already give the change-of-basis maps; nevertheless the linear independence is treated as immediate rather than given a short self-contained argument or a precise citation. Because uniqueness of the diagonal layer is load-bearing for Theorem 2, a one-paragraph derivation (via successive finite differences or evaluation on a sufficiently large grid) should be inserted in the main text.
minor comments (5)
  1. [Definition 21] Definition 21 is empty in the manuscript; either supply the missing content or remove the placeholder.
  2. [§3.5 / Tables 1–2] Tables 1 and 2 are referenced throughout §3.5 and the appendix but appear only at the end of the appendix; a forward pointer or a compact main-text summary of the key cubic transport identities would improve readability.
  3. [Figures 1–4 and Appendix A] Several diagrammatic equations in Figures 1–4 and the long appendix derivations use very dense multi-line rewrites; a few intermediate steps or colour-coding of generators would help the reader track the rewrites.
  4. [Remark 2] The comparison with the qubit CNOT-dihedral count in Remark 2 is useful; a brief sentence relating the exponent d^{binom(n+3,3)} to the dimension of the space of degree-≤3 polynomials would make the counting transparent.
  5. [§4] Open problems listed in the conclusion (reducing the scaling generators, extension beyond primes, higher-degree phases) are well-chosen; a short remark on whether the present axiom sets remain complete when the global phase generator ω is omitted would be a natural addition.

Circularity Check

0 steps flagged

No significant circularity: completeness is ordinary PROP equational reasoning with independently defined semantics and external Lafont import.

full rationale

The derivation chain is self-contained and non-circular. Aff_d is presented by explicit generators and equations (Figure 1); its semantics J·K_Aff into GA_n(F_d) is defined independently (Definition 7); soundness of axioms is checked (Lemma 1); affine normal forms and completeness (Theorem 1 / Lemmas 3–4) import Lafont’s linear theory [13] via Lemma 2 and Appendix A.1, which is an external classical reference, not a self-citation. Phase fragments adjoin Z/S/T with listed axioms (Figures 2–4); semantic PROPs Qupit are defined independently as pairs (g,q) with the semidirect-product law (Definition 11); soundness is re-checked (Lemma 9). Completeness (Theorem 2) is the standard layered-normal-form argument: existence by transport/commutation rewrites (Lemma 10, Tables 1–2, Appendix A.2) plus uniqueness of the diagonal layer from unique binomial expansions of degree-≤3 phase functions over F_d (Lemma 11) and uniqueness of the affine layer (Lemma 12). The binomial uniqueness is ordinary field arithmetic under the standing assumptions (d odd / d>3), supported by the paper’s own finite-difference identities (Lemmas 5–7), not by a fitted parameter or a self-authored uniqueness theorem. No quantity is fitted to data; no prediction is forced by construction from its own inputs; the single self-citation [5] is not load-bearing for Theorem 2. Score 0 is therefore the correct outcome.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 1 invented entities

The paper is pure equational algebra over finite fields. No numerical parameters are fitted. The load-bearing background is standard field arithmetic, the existence of unique binomial expansions of low degree, and Lafont’s completeness theorem for linear circuits; all three are classical. The generators and axioms of the three PROPs are definitions of the calculi themselves, not free postulates.

axioms (3)
  • standard math Every function F_d^n o F_d of total degree ≤ k (k=1,2,3) admits a unique expansion in the binomial monomials of degree ≤ k (used in Lemma 11).
    Classical fact for fields of characteristic >k; invoked without internal proof.
  • standard math Lafont’s presentation of linear circuits over F_d is complete for GL_n(F_d) (imported via Lemma 2 and Theorem 1).
    External published theorem; the paper only extends it by translations.
  • domain assumption d is prime (and odd for quadratic, >3 for cubic) so that 2 and 6 are invertible in F_d.
    Necessary for the binomial coefficients binom(x,2) and binom(x,3) to be well-defined polynomials; stated explicitly in Sections 3.1–3.3.
invented entities (1)
  • PROPs LinPhase_d, QuadPhase_d, CubicPhase_d no independent evidence
    purpose: Diagrammatic presentations of the three phase-affine fragments together with their finite axiom sets.
    Defined by generators and equations; they are the objects whose completeness is proved, not extra physical postulates.

pith-pipeline@v1.1.0-grok45 · 43545 in / 2389 out tokens · 29905 ms · 2026-07-15T13:48:58.825850+00:00 · methodology

0 comments
read the original 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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 8 canonical work pages · 1 internal anchor

  1. [1]

    015002, doi:https://doi.org/ 10.1088/2058-9565/aad8ca

    Matthew Amy, Parsiad Azimzadeh & Michele Mosca (2018):On the controlled-NOT complexity of controlled-NOT–phase circuits.Quantum Science and Technology4(1), p. 015002, doi:https://doi.org/ 10.1088/2058-9565/aad8ca. Available athttp://dx.doi.org/10.1088/2058-9565/aad8ca

    doi:10.1088/2058-9565/aad8ca 2018

  2. [2]

    Ross (2018):A Finite Presentation of CNOT-Dihedral Operators

    Matthew Amy, Jianxin Chen & Neil J. Ross (2018):A Finite Presentation of CNOT-Dihedral Operators. Electronic Proceedings in Theoretical Computer Science266, p. 84–97, doi:https://doi.org/10.4204/ eptcs.266.5. Available athttp://dx.doi.org/10.4204/EPTCS.266.5

    work page doi:10.4204/eptcs.266.5 2018

  3. [3]

    1476–1489, doi:https://doi.org/10.1109/tcad.2014.2341953

    Matthew Amy, Dmitri Maslov & Michele Mosca (2014):Polynomial-Time T-Depth Optimization of Clif- ford+T Circuits Via Matroid Partitioning.IEEE Transactions on Computer-Aided Design of Integrated Cir- cuits and Systems33(10), p. 1476–1489, doi:https://doi.org/10.1109/tcad.2014.2341953. Avail- able athttp://dx.doi.org/10.1109/TCAD.2014.2341953

    doi:10.1109/tcad.2014.2341953 2014

  4. [4]

    4771–4784, doi:https://doi.org/10.1109/tit.2019.2906374

    Matthew Amy & Michele Mosca (2019):T-Count Optimization and Reed–Muller Codes.IEEE Transac- tions on Information Theory65(8), p. 4771–4784, doi:https://doi.org/10.1109/tit.2019.2906374. Available athttp://dx.doi.org/10.1109/TIT.2019.2906374

    doi:10.1109/tit.2019.2906374 2019

  5. [5]

    Available athttps: //arxiv.org/abs/2602.09874

    Colin Blake (2026):Simpler Presentations for Many Fragments of Quantum Circuits. Available athttps: //arxiv.org/abs/2602.09874

    Pith/arXiv arXiv 2026

  6. [6]

    Booth & Titouan Carette (2022):Complete ZX-calculi for the stabiliser fragment in odd prime dimensions.LIPIcs, V olume 241, MFCS 2022241, pp

    Robert I. Booth & Titouan Carette (2022):Complete ZX-calculi for the stabiliser fragment in odd prime dimensions.LIPIcs, V olume 241, MFCS 2022241, pp. 24:1–24:15, doi:https://doi.org/10.4230/ LIPIcs.MFCS.2022.24. Available athttp://arxiv.org/abs/2204.12531. ArXiv:2204.12531 [quant- ph]

    Pith/arXiv arXiv 2022

  7. [7]

    Campbell, Hussain Anwar & Dan E

    Earl T. Campbell, Hussain Anwar & Dan E. Browne (2012):Magic-State Distillation in All Prime Di- mensions Using Quantum Reed-Muller Codes.Physical Review X2(4), doi:https://doi.org/10.1103/ physrevx.2.041021. Available athttp://dx.doi.org/10.1103/PhysRevX.2.041021

    doi:10.1103/physrevx.2.041021 2012

  8. [8]

    Available athttp://arxiv.org/abs/2506.12504

    Even Chiari, Wafa Makhlouf, Lucie Pepe, Emiel Koridon, Johanna Klein, Bruno Senjean, Benjamin Lasorne & Saad Yalouz (2025):Ab Initio Polaritonic Chemistry on Diverse Quantum Computing Platforms: Qubit, Qudit, and Hybrid Qubit-Qumode Architectures, doi:https://doi.org/10.48550/arXiv.2506.12504. Available athttp://arxiv.org/abs/2506.12504. ArXiv:2506.12504 ...

    doi:10.48550/arxiv.2506.12504 2025

  9. [9]

    Marston D. E. Conder, Edmund Robertson & Peter Williams (1992):Presentations for 3-dimensional special linear groups over integer rings.Proceedings of the American Mathematical Society115(1), pp. 19–26, doi:https://doi.org/10.1090/S0002-9939-1992-1079696-5

    work page doi:10.1090/s0002-9939-1992-1079696-5 1992

  10. [10]

    116–140, doi:https: //doi.org/10.4204/eptcs.394.8

    Arianne Meijer-van de Griend & Ross Duncan (2023):Architecture-Aware Synthesis of Phase Polynomials for NISQ Devices.Electronic Proceedings in Theoretical Computer Science394, p. 116–140, doi:https: //doi.org/10.4204/eptcs.394.8. Available athttp://dx.doi.org/10.4204/EPTCS.394.8

    work page doi:10.4204/eptcs.394.8 2023

  11. [11]

    Heyfron & Earl Campbell (2019):A quantum compiler for qudits of prime dimension greater than

    Luke E. Heyfron & Earl Campbell (2019):A quantum compiler for qudits of prime dimension greater than

    2019

  12. [12]

    Available athttps://arxiv.org/abs/1902.05634

    Pith/arXiv arXiv 1902

  13. [13]

    14Completeness for Prime-Dimensional Phase-Affine Circuits

    Korbinian Kottmann (2025):Phase Polynomial Intermediate Representation.https://pennylane.ai/ compilation/phase-polynomial-intermediate-representation. 14Completeness for Prime-Dimensional Phase-Affine Circuits

    2025

  14. [14]

    257–310, doi:https://doi.org/https://doi.org/10.1016/S0022-4049(03)00069-0

    Yves Lafont (2003):Towards an algebraic theory of Boolean circuits.Journal of Pure and Applied Algebra 184(2), pp. 257–310, doi:https://doi.org/https://doi.org/10.1016/S0022-4049(03)00069-0. Available athttps://www.sciencedirect.com/science/article/pii/S0022404903000690

    work page doi:10.1016/s0022-4049(03)00069-0 2003

  15. [15]

    Ross, John van de Wetering & Yuming Zhao (2025):A Complete and Natural Rule Set for Multi-Qutrit Clifford Circuits.Electronic Proceedings in Theoretical Computer Science 426, p

    Sarah Meng Li, Michele Mosca, Neil J. Ross, John van de Wetering & Yuming Zhao (2025):A Complete and Natural Rule Set for Multi-Qutrit Clifford Circuits.Electronic Proceedings in Theoretical Computer Science 426, p. 23–78, doi:https://doi.org/10.4204/eptcs.426.2. Available athttp://dx.doi.org/10. 4204/EPTCS.426.2

    work page doi:10.4204/eptcs.426.2 2025

  16. [16]

    1–62, doi:https://doi.org/10.24033/ asens.1174

    Hideya Matsumoto (1969):Sur les sous-groupes arithm ´etiques des groupes semi-simples d´eploy´es.Annales scientifiques de l’ ´Ecole Normale Sup ´erieure4e s ´erie, 2(1), pp. 1–62, doi:https://doi.org/10.24033/ asens.1174. Available athttps://www.numdam.org/articles/10.24033/asens.1174/

    work page doi:10.24033/asens.1174/ 1969

  17. [17]

    Boldizs ´ar Po ´or, Robert I. Booth, Titouan Carette, John van de Wetering & Lia Yeh (2023):The Qupit Sta- biliser ZX-travaganza: Simplified Axioms, Normal Forms and Graph-Theoretic Simplification, doi:https: //doi.org/10.4204/eptcs.384.13. Available athttp://dx.doi.org/10.4204/EPTCS.384.13

    doi:10.4204/eptcs.384.13 2023

  18. [18]

    Annals of Mathematics96(3), pp

    Daniel Quillen (1972):On the Cohomology and K-Theory of the General Linear Groups Over a Finite Field. Annals of Mathematics96(3), pp. 552–586. Available athttp://www.jstor.org/stable/1970825

    arXiv 1972

  19. [19]

    (Formerly: Mimeographed notes, Depart- ment of Math., Yale University, 1967/68.)

    Robert Steinberg & Robert Steinberg (2016):Lectures on Chevalley groups.University lecture seriesvolume 66, American Mathematical Society, Providence, Rhode Island. (Formerly: Mimeographed notes, Depart- ment of Math., Yale University, 1967/68.)

    2016

  20. [20]

    045027, doi:https: //doi.org/10.1088/2058-9565/ac5a0e

    Vivien Vandaele, Simon Martiel & Timoth ´ee Goubault de Brugi`ere (2022):Phase polynomials synthesis al- gorithms for NISQ architectures and beyond.Quantum Science and Technology7(4), p. 045027, doi:https: //doi.org/10.1088/2058-9565/ac5a0e. Available athttp://dx.doi.org/10.1088/2058-9565/ ac5a0e

    work page doi:10.1088/2058-9565/ac5a0e 2022

  21. [21]

    Qutrit ZX-calculus is Complete for Stabilizer Quantum Mechanics

    Quanlong Wang (2018):Qutrit ZX-calculus is Complete for Stabilizer Quantum Mechanics.Electronic Proceedings in Theoretical Computer Science266, pp. 58–70, doi:https://doi.org/10.4204/EPTCS. 266.3. Available athttp://arxiv.org/abs/1803.00696. ArXiv:1803.00696 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.4204/eptcs 2018

  22. [22]

    Sanders & Sabre Kais (2020):Qudits and High-Dimensional Quantum Computing.Frontiers in Physics8, doi:https://doi.org/10.3389/fphy.2020.589504

    Yuchen Wang, Zixuan Hu, Barry C. Sanders & Sabre Kais (2020):Qudits and High-Dimensional Quantum Computing.Frontiers in Physics8, doi:https://doi.org/10.3389/fphy.2020.589504. Available at http://dx.doi.org/10.3389/fphy.2020.589504

    doi:10.3389/fphy.2020.589504 2020

  23. [23]

    Charles A. Weibel (2013):The K-book: An Introduction to Algebraic K-Theory.Graduate Studies in Math- ematics145, American Mathematical Society, Providence, RI, doi:https://doi.org/10.1090/gsm/145. Appendix content A Derivations 15 A.1 Derivations for the Affine fragment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 A.2 Derivations for the P...

    doi:10.1090/gsm/145 2013

  24. [24]

    For Equations (42) and (43), the statement is immediate: these equations appear verbatim among the axioms of Affd, namely Equations (1) and (2)

  25. [25]

    Equation Equation (46) is obtained from Equation (4) by closure of derivability under tensoring with identities, composition, and symmetries in a PROP

  26. [26]

    Equation Equation (47) is derived in the same way from Lemma 17

  27. [27]

    Equation Equation (44) is an instance of the symmetric monoidal axioms, sinceσ 1,1 ◦σ 1,1 =id 2

  28. [28]

    Equation Equation (48) holds by expanding the abbreviation k from Definition 5 and using associativity of composition

  29. [29]

    Equation Equation (49) is proved using Lemma 22 and Lemma 16

  30. [30]

    Equation Equation (50) follows from Lemma 19 together with the PROP laws

  31. [31]

    This covers all equations in Figure 5, hence every ruleC=C ′ in Lafont’s presentation is derivable in Affd

    Equation Equation (45) is proved in Lemma 16. This covers all equations in Figure 5, hence every ruleC=C ′ in Lafont’s presentation is derivable in Affd. Lemma 14.Aff d ⊢ d = Proof. d = −1 (1) = −1 1 (3) = 1 (1) = 16Completeness for Prime-Dimensional Phase-Affine Circuits Lemma 15.∀x∈F × d ,Affd ⊢ xx = x Proof. xx (14) = xxd = xx−1 (3) = x Lemma 16.Aff d ...