Extending Matchgate Simulation Methods to Universal Quantum Circuits

Matchgates are a family of parity-preserving two-qubit gates, nearest-neighbour circuits of which are known to be classically simulable in polynomial time. In this work, we present a simulation method to classically simulate an $\mathit{n}$-qubit circuit containing $\mathit{N}$ gates, $\mathit{m}$ of which are universality-enabling gates and $$ of which are matchgates, in the setting of single-qubit Pauli measurements and product state inputs. The universality-enabling gates we consider include the SWAP, CZ, and CPhase gates. For fixed $\mathit{m}$ as $\mathit{n}\to \mathbf{\infty }$, the resource cost, $\mathit{T}$, scales as $$. For $\mathit{m}$ scaling as a linear function of $\mathit{n}$, however, $\mathit{T}$ scale as $$, where $\mathit{H}(\lambda )$ is the binary entropy function.