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, computable in polynomial time. This note kernel-checks in Lean 4 + Mathlib the complete even/odd split of that correspondence over the complex numbers: the 2x2, 4x4 and 6x6 Pfaffians square to the determinant (the exact two-, four- and six-qubit amplitudes), the recursive Pfaffian defines the general even-2m object by Laplace expansion along the first row, and any odd-dimensional antisymmetric matrix has determinant 0 (det A = (-1)^n det A, proved structurally). The infrastructure det_fin_four / det_fin_five supplies the general 4x4 and 5x5 determinants Mathlib was missing. The general even-n identity det = Pf^2 (Cayley) and the full matchgate<->free-fermion correspondence remain the open rung, not claimed here. lake build green (9104 jobs), no sorry/axiom/admit.
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, computable in polynomial time. This note kernel-checks in Lean 4 + Mathlib the complete even/odd split of that correspondence over the complex numbers: the 2x2, 4x4 and 6x6 Pfaffians square to the determinant (the exact two-, four- and six-qubit amplitudes), the recursive Pfaffian defines the general even-2m object by Laplace expansion along the first row, and any odd-dimensional antisymmetric matrix has determinant 0 (det A = (-1)^n det A, proved structurally). The infrastructure det_fin_four / det_fin_five supplies the general 4x4 and 5x5 determinants Mathlib was missing. The general even-n identity det = Pf^2 (Cayley) and the full matchgate<->free-fermion correspondence remain the open rung, not claimed here. lake build green (9104 jobs), no sorry/axiom/admit.
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.
It remains an open question whether the apparent additional power of quantum computation derives inherently from quantum mechanics, or merely from the flexibility obtained by "lifting" Boolean functions to linear operators and evaluating their composition cleverly. Holographic algorithms provide a useful avenue for exploring this question. We describe a new, simplified construction of holographic algorithms in terms of Pfaffian circuits. Novel proofs of some key results are provided, and we extend the approach of [34] to nonsymmetric, odd, and homogenized signatures, circuits, and various models of execution flow. This shows our approach is as powerful as the matchgate approach. Holographic algorithms provide in general O(nωp) time algorithms, where ωp is the order of Pfaffian evaluation in the ring of interest (with 1.19≤ωp≤3 depending on the ring) and n is the number of inclusions of variables into clauses. Our approach often requires just the evaluation of an n×n Pfaffian, and at most needs an additional two rows per gate, whereas the matchgate approach is quartic in the arity of the largest gate. We give examples (even before any change of basis) including efficient algorithms for certain lattice path problems and an O(nωp) algorithm for evaluation of Tutte polynomials of lattice path matroids. Finally we comment on some of the geometric considerations in analyzing Pfaffian circuits under arbitrary basis change. Connections are made to the sum-product algorithm, classical simulation of quantum computation, and SLOCC equivalent entangled states.
Fermionic Gaussian operators are foundational tools in quantum many-body theory, numerical simulation of fermionic dynamics, and fermionic linear optics. While their structure is fully determined by two-point correlations, evaluating their matrix elements in arbitrary local spin bases remains a nontrivial task, especially in applications involving quantum measurements, tomography, and basis-rotated simulations. In this work, we derive a fully explicit and general Pfaffian formula for the matrix elements of fermionic Gaussian operators between arbitrary Pauli product states. Our approach introduces a pair of sign-encoding matrices whose classification leads to a Lie algebra isomorphic to so(2L). This algebraic structure not only guarantees consistency of the Pfaffian signs but also reveals deep connections to Clifford algebras. The resulting framework enables scalable computations across diverse fields -- from quantum tomography and entanglement dynamics to algebraic structure in fermionic circuits and matchgate computation. Beyond its practical utility, our construction sheds light on the internal symmetries of Gaussian operators and offers a new lens through which to explore their role in quantum information and computational models.
Two islands of exact tractability are usually told as separate stories. On one, a discrete sum over an exponential configuration space collapses because the interaction graph is thin: variable elimination contracts it in time governed by treewidth, and a frustrated but narrow spin glass is summed exactly. On the other, a fermionic amplitude that looks exponential collapses because the system is free: a Gaussian (matchgate) circuit is a Pfaffian, computable in polynomial time. We show these are not two algorithms but one, run in two rings, and that the entire structural difference between them — the difference that separates the classical island from the quantum one — is a single sign. Exact elimination in a commutative ring is the classical sum-product engine; the same elimination in a graded-commutative ring, where transposing two generators costs a factor of −1, is the free-fermion Pfaffian. We prove the order-independence of elimination in a formal kernel; we build the graded product and prove that its four-mode Gaussian contraction equals the Pfaffian, as a polynomial identity over any commutative ring; we prove Pf 2 = det, lowering the amplitude to bare linear algebra and carrying a non-interacting molecular Hamiltonian through it. Crucially, we show the boundary is load-bearing and decidable: deleting the Koszul sign is a one-line mutation, and a kernel-checked substitution-body probe certifies that it changes a worked value from −15 to +15 — the sign is not decoration, it is the whole difference. Pushing the abstraction one turn further, we free the sign itself to a phase: the same contraction becomes a one-parameter family Pf ζ over the circle of braidings, and a kernel proof shows that bosons (ζ = +1) and fermions (ζ = −1) are its only two symmetric points — the solution set of ζ 2 = 1 — while √ every other root of unity is an anyon, the −1 quarter-turn already yielding an amplitude no sign can produce. The classical–quantum boundary is, in full, a point on a circle, and the sign is its fermionic antipode. Around this we build a measured-capability router: a functor that never routes an instance above a measured envelope, whose order-preservation law is proved with an empty axiom footprint, and whose decision is an exact integer comparison of table sizes. The result is a single certified contraction platform that computes classical inference, frustrated-magnet thermodynamics, and non-interacting electronic structure through one engine, lowered to an operator-native reduction net and closed with a replayable receipt. The honesty boundary is stated up front: both islands are special tractable classes, not all of computation; what changes at their border is exactly the sign, and nothing we build claims otherwise. Published by The Institute for Applied Ontological Mathematics.
Matchgate unitaries are ubiquitous in quantum computation due to their relation to non-interacting fermions and because they can be used to benchmark quantum computers. Implementing such unitaries on fault-tolerant devices requires first compiling them into a discrete universal gate set, typically Clifford+T. Here, we propose a different approach for their synthesis: compile matchgate unitaries using only matchgate gates. To this end, we first show that the matchgate-Clifford group (the intersection of the matchgate and Clifford groups) plus the T gate (a T unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between n-qubit matchgate circuits and the standard representation of SO(2n), which reduces the compilation from 2n×2n unitaries to 2n×2n ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error εSO(2n) incurred in this smaller-dimensional representation translates at most into an O(nεSO(2n)) error in the exponentially large unitary. In addition, we study the exact version of the matchgate synthesis problem, and we prove that all matchgate unitaries U such that U⊗U∗ has entries in the ring Z[1/2,i] can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford+T set, without ancillas. We then use this insight to map optimal exact matchgate synthesis to Boolean satisfiability, and compile the circuits that diagonalize the free-fermionic XX Hamiltonian on n=4,8 qubits.
We unify the Henstock-Kurzweil treatment of open quantum systems with bosonic Gaussian reservoirs and fermionic Grassmann reservoirs. Finite cylindrical gauge integrals yield determinant and covariance identities for bosons, while Berezin integration yields Pfaffian identities for fermions. In both sectors the reservoir is eliminated into an influence functional and the reduced dynamics is organised by Chernoff splitting. The accompanying Lean 4 developments verify the finite-dimensional Gaussian, operator, exterior-algebra, and Pfaffian steps. This upload contains the paper and the accompanying Lean 4 formalisation. The Lean development is free of sorry, admit, and newly introduced axioms. Kernel axiom inspection of the headline results reports only propext, Classical.choice, and Quot.sound. The finite-mode formulas are exact and machine-checked; continuum and unbounded-generator qualifications are kept explicit in the paper.