Efficient classical simulation of matchgate circuits with generalized inputs and measurements

Abstract

Matchgates are a restricted set of two-qubit gates known to be classically simulable under particular conditions. Specifically, if a circuit consists only of nearest-neighbour matchgates, an efficient classical simulation is possible if either (i) the input is a computational basis state and the simulation requires computing probabilities of multi-qubit outcomes (including also adaptive measurements), or (ii) if the input is an arbitrary product state, but the output of the circuit consists of a single qubit. In this paper we extend these results to show that matchgates are classically simulable even in the most general combination of these settings, namely, if the inputs are arbitrary product states, if the measurements are over arbitrarily many output qubits, and if adaptive measurements are allowed. This remains true even for arbitrary single-qubit measurements, albeit only in a weaker notion of classical simulation. These results make for an interesting contrast with other restricted models of computation, such as Clifford circuits or (bosonic) linear optics, where the complexity of simulation varies greatly under similar modifications.

11 pages, 2 figures. v2: Minor corrections

References in corpus (21)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Instantaneous non-local computation of low T-depth quantum circuits
• The Heisenberg Representation of Quantum Computers
• Efficient Classical Simulation of Continuous Variable Quantum Information Processes
• Negative Quasi-Probability as a Resource for Quantum Computation
• Classical simulation of noninteracting-fermion quantum circuits
• Negativity and contextuality are equivalent notions of nonclassicality
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Universal Quantum Computation with the nu=5/2 Fractional Quantum Hall State
• Matchgates and classical simulation of quantum circuits
• Charge detection enables free-electron quantum computation
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• Fermionic Linear Optics and Matchgates
• Bounds on the Probability of Success of Postselected Non-linear Sign Shifts Implemented with Linear Optics
• Fermionic Linear Optics Revisited
• Matchgate and space-bounded quantum computations are equivalent
• Extending matchgates into universal quantum computation
• Compressed quantum simulation of the Ising model
• Compressed Simulation of evolutions of the XY-model
• Geometries for universal quantum computation with matchgates
• Quantum matchgate computations and linear threshold gates

Cited by in corpus (33)

• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ansätze
• From estimation of quantum probabilities to simulation of quantum circuits
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Characterization of solvable spin models via graph invariants
• Compressed quantum computation using the IBM Quantum Experience
• All pure fermionic non-Gaussian states are magic states for matchgate computations
• Quantum Deep Hedging
• Character randomized benchmarking for non-multiplicity-free groups with applications to subspace, leakage, and matchgate randomized benchmarking
• Universal extensions of restricted classes of quantum operations
• Demonstration of Robust and Efficient Quantum Property Learning with Shallow Shadows
• Efficient simulation of quantum error correction under coherent error based on non-unitary free-fermionic formalism
• Computational power of matchgates with supplementary resources
• Effects of quantum resources on the statistical complexity of quantum circuits
• Error mitigation by training with fermionic linear optics
• Clifford algebras, Spin groups and qubit trees
• The principle of majorization: application to random quantum circuits
• Protocols for classically training quantum generative models on probability distributions
• Classical simulation of quantum circuits by dynamical localization: analytic results for Pauli-observable scrambling in time-dependent disorder
• Faster Born probability estimation via gate merging and frame optimisation
• Exact spectral form factors of non-interacting fermions with Dyson statistics
• Integrability of Goldilocks quantum cellular automata
• Quantum circuit dynamics via path integrals: Is there a classical action for discrete-time paths?
• Entanglement spectrum of matchgate circuits with universal and non-universal resources
• Analyzing the free states of one quantum resource theory as resource states of another
• Polynomially restricted operator growth in dynamically integrable models
• Gaining confidence on the correct realization of arbitrary quantum computations
• Explicit Pfaffian Formula for Amplitudes of Fermionic Gaussian Pure States in Arbitrary Pauli Bases
• Effective simulation of state distribution in qubit chains
• The Hilbert-space structure of free fermions in disguise
• Fermionic Machine Learning
• Sub-universal variational circuits for combinatorial optimization problems
• Efficient classical simulation of cluster state quantum circuits with alternative inputs