Improved simulation of quantum circuits dominated by free fermionic operations

We present a classical algorithm for simulating universal quantum circuits composed of "free" nearest-neighbour matchgates or equivalently fermionic-linear-optical (FLO) gates, and "resourceful" non-Gaussian gates. We achieve the promotion of the efficiently simulable FLO subtheory to universal quantum computation by gadgetizing controlled phase gates with arbitrary phases employing non-Gaussian resource states. Our key contribution is the development of a novel phase-sensitive algorithm for simulating FLO circuits. This allows us to decompose the resource states arising from gadgetization into free states at the level of statevectors rather than density matrices. The runtime cost of our algorithm for estimating the Born-rule probability of a given quantum circuit scales polynomially in all circuit parameters, except for a linear dependence on the newly introduced FLO <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>e</mml:mi><mml:mi>x</mml:mi><mml:mi>t</mml:mi><mml:mi>e</mml:mi><mml:mi>n</mml:mi><mml:mi>t</mml:mi></mml:math>, which scales exponentially with the number of controlled-phase gates. More precisely, as a result of finding optimal decompositions of relevant resource states, the runtime doubles for every maximally resourceful (e.g., swap or CZ) gate added. Crucially, this cost compares very favourably with the best known prior algorithm, where each swap gate increases the simulation cost by a factor of approximately 9. For a quantum circuit containing arbitrary FLO unitaries and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math> controlled-Z gates, we obtain an exponential improvement <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mn>4.5</mml:mn><mml:mi>k</mml:mi></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math> over the prior state-of-the-art.