Matchgates revisited

DOI10.4086/TOC.2014.V010A007MaRDI QIDQ3191606zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Aaron Gorenstein

Publication date 6 October 2014

Published in Theory of Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

complexity theorymatchgatesPfaffian orientation

Mathematics Subject Classification ID

Applications of graph theory (05C90) Quantum algorithms and complexity in the theory of computing (68Q12) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the theory of matchgate computations
• Some Results on Matchgates and Holographic Algorithms
• A theory for Valiant's matchcircuits (Extended abstract)
• Quantum matchgate computations and linear threshold gates
• Matchgate and space-bounded quantum computations are equivalent

Cites work

• A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
• Dimer problem in statistical mechanics-an exact result
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Signature theory in holographic algorithms

Cited in

(17)

• Some observations on holographic algorithms
• On blockwise symmetric matchgate signatures and higher domain \#CSP
• Expressiveness of matchgates.
• FKT is not universal -- a planar holant dichotomy for symmetric constraints
• Functional clones and expressibility of partition functions
• Quantum matchgate computations and linear threshold gates
• A collapse theorem for holographic algorithms with matchgates on domain size at most 4
• A theory for Valiant's matchcircuits (Extended abstract)
• Matchgate and space-bounded quantum computations are equivalent
• A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Holographic algorithms on domains of general size
• A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory
• Undirected determinant and its complexity
• A complexity trichotomy for k-regular asymmetric spin systems with complex edge functions
• On the theory of matchgate computations

This page was built for publication: Matchgates revisited

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