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 (38)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Improved Simulation of Stabilizer Circuits
• Characterizing Quantum Supremacy in Near-Term Devices
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Hartree-Fock on a superconducting qubit quantum computer
• Exact and Approximate Unitary 2-Designs: Constructions and Applications
• Quantum Simulators: Architectures and Opportunities
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Quantum Error Correction: An Introductory Guide
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Trading classical and quantum computational resources
• Simulation of quantum circuits by low-rank stabilizer decompositions
• Universal Quantum Computation with the nu=5/2 Fractional Quantum Hall State
• Unbiasing Fermionic Quantum Monte Carlo with a Quantum Computer
• Matchgates and classical simulation of quantum circuits
• Quantum algorithms to simulate many-body physics of correlated fermions
• Fermionic partial tomography via classical shadows
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Observing ground-state properties of the Fermi-Hubbard model using a scalable algorithm on a quantum computer
• Hadamard-free circuits expose the structure of the Clifford group
• Constructing a virtual two-qubit gate by sampling single-qubit operations
• Complexity of quantum impurity problems
• Matchgate Shadows for Fermionic Quantum Simulation
• From estimation of quantum probabilities to simulation of quantum circuits
• Matchgate benchmarking: Scalable benchmarking of a continuous family of many-qubit gates
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Quantum advantage of unitary Clifford circuits with magic state inputs
• The Power of Noisy Fermionic Quantum Computation
• All pure fermionic non-Gaussian states are magic states for matchgate computations
• Fast estimation of outcome probabilities for quantum circuits
• 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
• `Classical' quantum states
• Lagrangian representation for fermionic linear optics
• On detection of quasiclassical states
• Quantifying fermionic nonlinearity of quantum circuits
• Efficient classical simulation and benchmarking of quantum processes in the Weyl basis

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