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

DOI10.1016/J.IC.2014.10.002zbMATH Open1309.68085arXiv1305.1409OpenAlexW2123157085MaRDI QIDQ476175FDOQ476175

Authors: Jin-Yi Cai, Zhiguo Fu 

Publication date: 28 November 2014

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

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.

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

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\)

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• 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
• Some Results on Matchgates and 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)