  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.
