Improved simulation of quantum circuits dominated by free fermionic operations

Abstract

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 extent, 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 $k$ controlled-Z gates, we obtain an exponential improvement $O(4.5^k)$ over the prior state-of-the-art.

Final version after peer review

References in corpus (10)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Unbiasing Fermionic Quantum Monte Carlo with a Quantum Computer
• Matchgates and classical simulation of quantum circuits
• Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer
• Matchgate Shadows for Fermionic Quantum Simulation
• Universal extensions of restricted classes of quantum operations
• Classical simulation of fermionic linear optics augmented with noisy ancillas
• How to simulate quantum measurement without computing marginals
• Lagrangian representation for fermionic linear optics
• Quantifying fermionic nonlinearity of quantum circuits

Cited by in corpus (11)

• Stabilizer Tensor Networks with Magic State Injection
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Bridging Entanglement and Magic Resources within Operator Space
• The non-stabilizerness of fermionic Gaussian states
• Fermionic Magic Resources of Quantum Many-Body Systems
• Simulation of quantum computation with magic states via Jordan-Wigner transformations
• Characterization of non-adaptive Clifford channels
• Classifying fermionic states via many-body correlation measures
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Benchmarking quantum devices beyond classical capabilities
• Efficient classical computation of the neural tangent kernel of quantum neural networks