Extending Matchgate Simulation Methods to Universal Quantum Circuits

Understand

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 $\boldsymbol{n}$-qubit circuit containing $\boldsymbol{N}$ gates, $\boldsymbol{m}$ of which are universality-enabling gates and $\boldsymbol{N-m}$ 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 $\boldsymbol{m}$ as $\boldsymbol{n} \rightarrow \boldsymbol{\infty}$, the resource cost, $\boldsymbol{T}$, scales as $\boldsymbol{\mathcal{O}\left(\left(\frac{en}{m+1}\right)^{2m+2}\right)}$.