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 n-qubit circuit containing N gates, m of which are universality-enabling gates and 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 m as n → ∞, the resource cost, T, scales as O((en/m+1)^2m+2). For m scaling as a linear function of n, however, T scale as O(2^2nH(m+1/n)), where H(λ) is the binary entropy function.