Extending matchgates into universal quantum computation

Abstract

Matchgates are a family of two-qubit gates associated with noninteracting fermions. They are classically simulatable if acting only on nearest neighbors, but become universal for quantum computation if we relax this restriction or use SWAP gates [Jozsa and Miyake, Proc. R. Soc. A 464, 3089 (2008)]. We generalize this result by proving that any nonmatchgate parity-preserving unitary is capable of extending the computational power of matchgates into universal quantum computation. We identify the single local invariant of parity-preserving unitaries responsible for this, and discuss related results in the context of fermionic systems.

9 pages, 2 figures

References in corpus (6)

• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Matchgates and classical simulation of quantum circuits
• Charge detection enables free-electron quantum computation
• Matchgate and space-bounded quantum computations are equivalent
• Quantum matchgate computations and linear threshold gates
• Matchgate quantum computing and non-local process analysis

Cited by in corpus (20)

• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• Free fermions behind the disguise
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Characterization of solvable spin models via graph invariants
• All pure fermionic non-Gaussian states are magic states for matchgate computations
• Character randomized benchmarking for non-multiplicity-free groups with applications to subspace, leakage, and matchgate randomized benchmarking
• Computational power of matchgates with supplementary resources
• Geometries for universal quantum computation with matchgates
• Efficient learning of quantum states prepared with few fermionic non-Gaussian gates
• Quantum computation from fermionic anyons on a 1D lattice
• The computational power of matchgates and the XY interaction on arbitrary graphs
• Entanglement spectrum of matchgate circuits with universal and non-universal resources
• Geometric representations of braid and Yang-Baxter gates
• Fermionic anyons: entanglement and quantum computation from a resource-theoretic perspective
• Gaining confidence on the correct realization of arbitrary quantum computations
• Analyzing the free states of one quantum resource theory as resource states of another
• GHZ transform (I): Bell transform and quantum teleportation
• Polynomially restricted operator growth in dynamically integrable models
• Fermionic Machine Learning
• The Computational Power of Non-interacting Particles