Computational power of matchgates with supplementary resources

Abstract

We study the classical simulation complexity in both the weak and strong senses, of matchgate (MG) computations supplemented with all combinations of settings involving inclusion of intermediate adaptive or nonadaptive computational basis measurements, product state or magic and general entangled state inputs, and single- or multi-line outputs. We find a striking parallel to known results for Clifford circuits, after some rebranding of resources. We also give bounds on the amount of classical simulation effort required in case of limited access intermediate measurements and entangled inputs. In further settings we show that adaptive MG circuits remain classically efficiently simulable if arbitrary two-qubit entangled input states on consecutive lines are allowed, but become quantum universal for three or more lines. And if adaptive measurements in non-computational bases are allowed, even with just computational basis inputs, we get quantum universal power again.

arXiv comment17 pages, 4 figures

References in corpus (15)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• On the role of entanglement in quantum computational speed-up
• Optimal Creation of Entanglement Using a Two--Qubit Gate
• Classical simulation of noninteracting-fermion quantum circuits
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Trading classical and quantum computational resources
• Universal Quantum Computation with the nu=5/2 Fractional Quantum Hall State
• Matchgates and classical simulation of quantum circuits
• Efficient classical simulation of matchgate circuits with generalized inputs and measurements
• All pure fermionic non-Gaussian states are magic states for matchgate computations
• Matchgate and space-bounded quantum computations are equivalent
• Extending matchgates into universal quantum computation
• Classical simulation of fermionic linear optics augmented with noisy ancillas
• Geometries for universal quantum computation with matchgates

Cited by in corpus (11)

• Measuring magic on a quantum processor
• Fermion Sampling: a robust quantum computational advantage scheme using fermionic linear optics and magic input states
• Character randomized benchmarking for non-multiplicity-free groups with applications to subspace, leakage, and matchgate randomized benchmarking
• LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States
• Gravitational back-reaction is magical
• Effects of quantum resources on the statistical complexity of quantum circuits
• Entanglement phase diagrams from partial transpose moments
• Faster Born probability estimation via gate merging and frame optimisation
• The Hadamard gate cannot be replaced by a resource state in universal quantum computation
• Entanglement spectrum of matchgate circuits with universal and non-universal resources
• Gaining confidence on the correct realization of arbitrary quantum computations