quantum gate directory

Matchgates are the two-qubit gates that act separately on the even- and odd-parity subspaces, with matching determinants. Introduced by Valiant and identified physically as free-fermion evolutions, they are the fermionic counterpart of the Clifford group: rich enough to entangle, structured enough to simulate classically.

$$ G(A, B) = \begin{bmatrix} A_{11} & 0 & 0 & A_{12} \\ 0 & B_{11} & B_{12} & 0 \\ 0 & B_{21} & B_{22} & 0 \\ A_{21} & 0 & 0 & A_{22} \end{bmatrix}, \qquad A, B \in \mathsf{U}(2),\ \det A = \det B $$

Here $A$ acts on the even-parity subspace $\{|00\rangle, |11\rangle\}$ and $B$ on the odd-parity subspace $\{|01\rangle, |10\rangle\}$.

Free fermions

Under the Jordan–Wigner transformation, matchgates on neighboring qubits are exactly the evolutions generated by Hamiltonians quadratic in fermionic operators — non-interacting fermions (Terhal and DiVincenzo). Circuits of nearest-neighbor matchgates on a line are classically simulable in polynomial time — the free-fermion analog of the Gottesman–Knill theorem.

The boundary of that simulability is remarkably sharp (Jozsa and Miyake): allow the same gates between non-neighboring qubits — equivalently, add the SWAP — and the circuit family becomes universal for quantum computation.

Membership fine print

• SWAP is famously not a matchgate ($\det A = 1$ but $\det B = -1$); the fermionic SWAP exists precisely to fix this, paying a $-1$ phase on $|11\rangle$ to satisfy the determinant condition.
• FSim$(\theta, \phi)$ is a matchgate only at $\phi = 0$ (where it reduces to the XY interaction); the Sycamore gate's $\mathrm{e}^{-i\pi/6}$ phase likewise breaks the determinant condition.
• $R_{zz}$ fails too: $Z \otimes Z$ is quartic, not quadratic, in Majorana operators — interacting, not free.
• Single-qubit $z$ rotations, embedded on either qubit, are matchgates; single-qubit $x$ or $y$ rotations are not.