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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The matchgate even/odd split, kernel-checked: amplitudes are even-dimensional Pfaffians

Rob Mitchell
3 links
Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
preprint

The matchgate even/odd split, kernel-checked: amplitudes are even-dimensional Pfaffians

Rob Mitchell
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Quantum Computing Algorithms and Architecture
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon