Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

The matchgate even/odd split, kernel-checked: amplitudes are even-dimensional Pfaffians (2×2, 4×4, 6×6, and the recursive general object)

Rob Mitchell

Published Nov 8, 2026• 0 citations
Publisher

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, 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.

DOI
10.5281/zenodo.24062178

Related papers

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

Rob Mitchell

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.

•Nov 8, 2026•0 citations

Pfaffian Circuits

Jason Morton

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 \leq ω_p \leq 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 \times 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.

arXiv:1101.0129•Dec 30, 2010•9 citations

Matrix Elements of Fermionic Gaussian Operators in Arbitrary Pauli Bases: A Pfaffian Formula

M. A. Rajabpour, M. A. Seifi Mirjafarlou, Reyhaneh Khasseh

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 $\mathfrak{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.

arXiv:2506.02809•Jun 3, 2025•1 citation

The Sign Is the Boundary

The Institute for Applied Ontological Mathematics

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.

•Oct 11, 2026•0 citations

Matchgate synthesis via Clifford matchgates and TTT gates

Berta Casas, Paolo Braccia, Élie Gouzien +2 more

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 $\overline{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 $\mathbb{SO}(2n)$, which reduces the compilation from $2^n\times 2^n$ unitaries to $2n\times2n$ ones, thus reducing exponentially the size of the target matrix. Moreover, we rigorously show that this scheme is efficient, as an approximation error $\varepsilon_{\mathbb{SO}(2n)}$ incurred in this smaller-dimensional representation translates at most into an $O(n \,\varepsilon_{\mathbb{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\otimes U^*$ has entries in the ring $\mathbb{Z}\big[1/\sqrt 2,i\big]$ can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford$+\overline{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.

quant-pharXiv:2602.05425•Feb 6, 2026•7 citations

Henstock-Kurzweil Path Integrals for Open Quantum Systems: Bosonic and Fermionic Reservoirs — A Machine-Verified Approach

Yuri N. Berdinsky, Alexander S. Ushakov

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.

•Sep 13, 2026•1 citation
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)O(n^{ω_p})O(nωp​) time algorithms, where ωpω_pωp​ is the order of Pfaffian evaluation in the ring of interest (with 1.19≤ωp≤31.19 \leq ω_p \leq 31.19≤ωp​≤3 depending on the ring) and nnn is the number of inclusions of variables into clauses. Our approach often requires just the evaluation of an n×nn \times nn×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)O(n^{ω_p})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)\mathfrak{so}(2L)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+T+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‾\overline{T}T gate (a TTT unitary up to a phase) is universal for the matchgate group. Our approach leverages the connection between nnn-qubit matchgate circuits and the standard representation of SO(2n)\mathbb{SO}(2n)SO(2n), which reduces the compilation from 2n×2n2^n\times 2^n2n×2n unitaries to 2n×2n2n\times2n2n×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)\varepsilon_{\mathbb{SO}(2n)}εSO(2n)​ incurred in this smaller-dimensional representation translates at most into an O(n εSO(2n))O(n \,\varepsilon_{\mathbb{SO}(2n)})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 UUU such that U⊗U∗U\otimes U^*U⊗U∗ has entries in the ring Z[1/2,i]\mathbb{Z}\big[1/\sqrt 2,i\big]Z[1/2​,i] can be exactly synthesized by a finite sequence of gates from the matchgate-Clifford+T‾+\overline{T}+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 XXXXXX Hamiltonian on n=4, 8n=4,\,8n=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.