Extending Matchgate Simulation Methods to Universal Quantum Circuits

Abstract

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 $\mathbf{n}$-qubit circuit containing $\mathbf{N}$ gates, $\mathbf{m}$ of which are universality-enabling gates and $\mathbf{N}-\mathbf{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 $\mathbf{m}$ as $\mathbf{n}\to \infty$, the resource cost, $\mathbf{T}$, scales as $\mathcal{O}\left({\left(\frac{\mathbf{en}}{\mathbf{m}+1}\right)}^{2\mathbf{m}+2}\right)$. For $\mathbf{m}$ scaling as a linear function of $\mathbf{n}$, however, $\mathbf{T}$ scale as $\mathcal{O}\left(2^{2\mathbf{nH}\left(\frac{\mathbf{m}+1}{\mathbf{n}}\right)}\right)$, where $\mathbf{H}(\hat{I}»)$ is the binary entropy function.