The matchgate even/odd split, kernel-checked: amplitudes are even-dimensional Pfaffians
Matchgates are classically simulable because their amplitudes are Pfaffians (signed sums over perfect matchings, equivalently square roots of determinants), and a determinant is a polynomial in its entries, computable in polynomial time. We kernel-check in Lean 4 + Mathlib the seed of that correspondence, over the complex numbers: (1) pfaffian2_sq_eq_det, the 2x2 Pfaffian (the single perfect-matching weight) squares to the determinant, so a matchgate amplitude is a Pfaffian, hence a polynomial, hence classically simulable; and (2) det_three_antisymm_eq_zero, a 3x3 antisymmetric matrix has determinant 0, so odd dimension kills the determinant and the Pfaffian (hence matchgates) is an even-dimensional object. Together these are the even/odd split behind matchgate simulability. We state honestly what is not proved: the 4x4 exact four-qubit amplitude is the next rung and is not claimed, and the full matchgate/free-fermion correspondence is the known Valiant / Jozsa-Miyake theorem, formalized here only in its seed.
Authors
- Rob Mitchell
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-08
- DOI
- https://doi.org/10.5281/zenodo.24047502
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- preprint