On the theory of matchgate computations

DOI10.1007/s00224-007-9092-8zbMath1178.68254OpenAlexW2084341218MaRDI QIDQ841626

Pinyan Lu, Vinay Choudhary, Jin-Yi Cai

Publication date: 18 September 2009

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

Full work available at URL: https://doi.org/10.1007/s00224-007-9092-8

zbMATH Keywords

holographic algorithmsGrassmann-Plücker identitiesmatchgates

Mathematics Subject Classification ID

General topics in the theory of algorithms (68W01)

Related Items

Some observations on holographic algorithms, Erratum to: ``Signature theory in holographic algorithms, Valiant's holant theorem and matchgate tensors, Holographic algorithms: from art to science, Holographic algorithms on domains of general size, Holographic algorithms beyond matchgates, Holographic algorithms on bases of rank 2, The complexity of planar Boolean \#CSP with complex weights, Holographic algorithms: the power of dimensionality resolved, FKT is not universal -- a planar holant dichotomy for symmetric constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Expressiveness of matchgates.
• The statistics of dimers on a lattice
• Quantum Circuits That Can Be Simulated Classically in Polynomial Time
• On Symmetric Signatures in Holographic Algorithms
• Some Results on Matchgates and Holographic Algorithms
• Dimer problem in statistical mechanics-an exact result
• Holographic Algorithms: The Power of Dimensionality Resolved
• Matrices and matroids for systems analysis