Matchgate and space-bounded quantum computations are equivalent

Abstract

Matchgates are an especially multiflorous class of two-qubit nearest neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions, and one-dimensional spin chains. We show that the computational power of circuits of matchgates is equivalent to that of space-bounded quantum computation with unitary gates, with space restricted to being logarithmic in the width of the matchgate circuit. In particular, for the conventional setting of polynomial-sized (logarithmic-space generated) families of matchgate circuits, known to be classically simulatable, we characterise their power as coinciding with polynomial-time and logarithmic-space bounded universal unitary quantum computation.

22 pages

References in corpus (6)

• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Matchgates and classical simulation of quantum circuits
• Charge detection enables free-electron quantum computation
• Quantum circuits for strongly correlated quantum systems
• Both Toffoli and Controlled-NOT need little help to do universal quantum computation
• Simulating quantum systems using real Hilbert spaces

Cited by in corpus (26)

• 14-qubit entanglement: creation and coherence
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• Quantum Commuting Circuits and Complexity of Ising Partition Functions
• Compressed quantum computation using the IBM Quantum Experience
• All pure fermionic non-Gaussian states are magic states for matchgate computations
• Extending matchgates into universal quantum computation
• Compressed quantum simulation of the Ising model
• Computational power of matchgates with supplementary resources
• The Bethe Ansatz as a Quantum Circuit
• Compressed Simulation of evolutions of the XY-model
• Quantum matchgate computations and linear threshold gates
• Compressed quantum metrology for the Ising Hamiltonian
• Generalised state spaces and non-locality in fault tolerant quantum computing schemes
• Compressed simulation of thermal and excited states of the 1-D XY-model
• Two-party LOCC convertibility of quadpartite states and Kraus-Cirac number of two-qubit unitaries
• Eliminating Intermediate Measurements in Space-Bounded Quantum Computation
• Maximally entangled gapped ground state of lattice fermions
• Solving Free Fermion Problems on a Quantum Computer
• Entanglement spectrum of matchgate circuits with universal and non-universal resources
• Gaining confidence on the correct realization of arbitrary quantum computations
• Permanents, Bosons and Linear Optics
• Fermionic anyons: entanglement and quantum computation from a resource-theoretic perspective
• Effective simulation of state distribution in qubit chains
• Cloud-Assisted Contracted Simulation of Quantum Chains