A collapse theorem for holographic algorithms with matchgates on domain size at most 4

DOI10.1016/J.IC.2014.10.002MaRDI QIDQ476175zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Zhiguo Fu

Publication date 28 November 2014

Published in Information and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Abstract: Holographic algorithms with matchgates are a novel approach to design polynomial time computation. It uses Kasteleyn's algorithm for perfect matchings, and more importantly a holographic reduction . The two fundamental parameters of a holographic reduction are the domain size $k$ of the underlying problem, and the basis size $ell$. A holographic reduction transforms the computation to matchgates by a linear transformation that maps to (a tensor product space of) a linear space of dimension $2^{ell}$. We prove a sharp basis collapse theorem, that shows that for domain size 3 and 4, all non-trivial holographic reductions have basis size $ell$ collapse to 1 and 2 respectively. The main proof techniques are Matchgates Identities, and a Group Property of matchgates signatures.

Recommendations

• Basis collapse for holographic algorithms over all domain sizes
• Base collapse of holographic algorithms
• Basis collapse in holographic algorithms
• Holographic algorithms on domain size \(k > 2\)

Cites work

• scientific article; zbMATH DE number 3856167 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• A complete dichotomy rises from the capture of vanishing signatures (extended abstract)
• An effective dichotomy for the counting constraint satisfaction problem
• Complexity of counting CSP with complex weights
• Dimer problem in statistical mechanics-an exact result
• Gadgets and anti-gadgets leading to a complexity dichotomy
• Graph homomorphisms with complex values: a dichotomy theorem
• Holographic Algorithms: The Power of Dimensionality Resolved
• Holographic algorithms on bases of rank 2
• Holographic algorithms with matchgates capture precisely tractable planar \#CSP
• Holographic algorithms: from art to science
• Matchgates revisited
• Quantum computers that can be simulated classically in polynomial time
• Some observations on holographic algorithms
• Spin systems on k-regular graphs with complex edge functions
• The Complexity of Weighted Boolean #CSP
• The Complexity of the Counting Constraint Satisfaction Problem
• The completeness of the first-order functional calculus
• The complexity of symmetric Boolean parity Holant problems (extended abstract)
• The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice

Cited in

(9)

• Some Results on Matchgates and Holographic Algorithms
• Holographic algorithms on bases of rank 2
• On blockwise symmetric matchgate signatures and higher domain \#CSP
• Holographic algorithms on domains of general size
• Basis collapse in holographic algorithms
• Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain
• Nearly-linear size holographic proofs
• Basis collapse for holographic algorithms over all domain sizes
• Base collapse of holographic algorithms

This page was built for publication: A collapse theorem for holographic algorithms with matchgates on domain size at most 4

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