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.
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.
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.
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.
Let G(A, B) denote the 2-qubit gate which acts as the 1-qubit SU(2) gates A and B in the even and odd parity subspaces respectively, of two qubits. Using a Clifford algebra formalism we show that arbitrary uniform families of circuits of these gates, restricted to act only on nearest neighbour (n.n.) qubit lines, can be classically efficiently simulated. This reproduces a result originally proved by Valiant using his matchgate formalism, and subsequently related by others to free fermionic physics. We further show that if the n.n. condition is slightly relaxed, to allowing the same gates to act only on n.n. and next-n.n. qubit lines, then the resulting circuits can efficiently perform universal quantum computation. From this point of view, the gap between efficient classical and quantum computational power is bridged by a very modest use of a seemingly innocuous resource (qubit swapping). We also extend the simulation result above in various ways. In particular, by exploiting properties of Clifford operations in conjunction with the Jordan-Wigner representation of a Clifford algebra, we show how one may generalise the simulation result above to provide further classes of classically efficiently simulatable quantum circuits, which we call Gaussian quantum circuits. 1
In quantum information theory and statistical physics, symmetries of multiple copies, or replicas, of a system play a pivotal role. For unitary ensembles, these symmetries are encoded in the replicated commutant: the algebra of operators commuting with the ensemble across k replicas. Determining the commutant is straightforward for the full unitary group, but remains a major obstacle for structured, computationally relevant circuit families. We solve this problem for matchgate circuits, which prepare fermionic Gaussian states on n qubits. Using a Majorana fermion representation, we show that operators coupling different system copies generate the orthogonal Lie algebra so(k), endowing the space of invariants with rich and tractable structure. This underlying symmetry decomposes the matchgate commutant into irreducible sectors, which we completely resolve via a Gelfand--Tsetlin construction. We provide an explicit orthonormal basis of the matchgate commutant for all k and n, together with a formula for its dimension that grows polynomially in n. Furthermore, we characterize the commutant of the Clifford--matchgate subgroup, showing that restricting to signed permutations of Majorana modes yields a commutant that qualitatively diverges from the matchgate case for k≥4 replicas. Ultimately, our orthonormal basis turns algebraic classification into a working toolbox. Using it, we derive closed-form expressions for matchgate twirling channels and a fermionic analogue of Weingarten calculus, the projector encoding all moments of the Gaussian state orbit, state and unitary frame potentials, the average nonstabilizerness of fermionic Gaussian states, a systematic hierarchy of non-Gaussianity measures, and a fermionic de Finetti theorem.
Clifford and matchgate circuits are canonical families of classically simulable quantum circuits. Their intersection, the matchgate-Clifford group, plays an important role in randomized fermionic protocols and in matchgate synthesis. Its adjoint action is isomorphic to the group of unit-determinant signed permutations of 2n Majorana modes, and we study optimal exact synthesis in this group. That is, given a target unitary and a gate set, output an n-qubit circuit implementing the target using the fewest operations. We show that the complexity of this problem strongly depends on the gate set. In particular, we study gate sets consisting of Majorana braids with different connectivity graphs. For path and complete graphs, we prove that the problem is classically solvable in O(n2) time, and we provide explicit gate-optimal compilers. In addition, we prove that when the connectivity graph is a tree, the decision version of the optimal synthesis problem becomes NP-complete. Finally, we benchmark our optimal compiler on chains of up to n=80 qubits against those of \texttt{Qiskit} and \texttt{Tket}, obtaining circuits with constant factor improvements ×2.57 and ×2.28 in the total number of gates, respectively.
Matchgates are a family of two-qubit gates associated with noninteracting fermions. They are classically simulatable if acting only on nearest neighbors but become universal for quantum computation if we relax this restriction or use swap gates [Jozsa and Miyake, Proc. R. Soc. A 464, 3089 (2008)]. We generalize this result by proving that any nonmatchgate parity-preserving unitary is capable of extending the computational power of matchgates into universal quantum computation. We identify the single local invariant of parity-preserving unitaries responsible for this, and discuss related results in the context of fermionic systems.