Matchgates and classical simulation of quantum circuits

Understand

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.