Quantum matchgate computations and linear threshold gates

DOI10.1098/RSPA.2010.0332zbMATH Open1207.81016arXiv1005.1143OpenAlexW3106511654MaRDI QIDQ3076715FDOQ3076715

Maarten Van den Nest

Publication date: 23 February 2011

Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Abstract: The theory of matchgates is of interest in various areas in physics and computer science. Matchgates occur in e.g. the study of fermions and spin chains, in the theory of holographic algorithms and in several recent works in quantum computation. In this paper we completely characterize the class of boolean functions computable by unitary two-qubit matchgate circuits with some probability of success. We show that this class precisely coincides with that of the linear threshold gates. The latter is a fundamental family which appears in several fields, such as the study of neural networks. Using the above characterization, we further show that the power of matchgate circuits is surprisingly trivial in those cases where the computation is to succeed with high probability. In particular, the only functions that are matchgate-computable with success probability greater than 3/4 are functions depending on only a single bit of the input.

Full work available at URL: https://arxiv.org/abs/1005.1143

zbMATH Keywords

threshold gatesmatchgatesclassical simulations

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Cites Work

• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
• Universal Quantum Simulators
• Dimer problem in statistical mechanics-an exact result
• Quantum computational networks
• Quantum Complexity Theory
• On the role of entanglement in quantum-computational speed-up
• Majority gates vs. general weighted threshold gates
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• Threshold circuits of bounded depth
• On the Size of Weights for Threshold Gates
• Agnostically Learning Halfspaces
• Theory of majority decision elements
• Halfspace matrices
• Simulating Threshold Circuits by Majority Circuits
• Matchgates and classical simulation of quantum circuits
• The Perceptron: A Model for Brain Functioning. I
• Matchgate and space-bounded quantum computations are equivalent

Cited In (4)

• Clifford gates in the Holant framework
• Title not available (Why is that?)
• Bounds on Threshold Gate Realizability
• Matchgates and classical simulation of quantum circuits

This page was built for publication: Quantum matchgate computations and linear threshold gates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3076715)