Some Results on Matchgates and Holographic Algorithms
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    We establish a 1-1 correspondence between Valiant's character theory of match-gate/matchcircuit [13] and his signature theory of planarmatchgate/matchgrid [15], thus unifying the two theories in expressibility. In [3], we established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Plucker identities. The 1-1 correspondence established in this paper gives a corresponding set of identities which completely characterizes planar-matchgates and their signatures. Applying this characterization we prove some negative results for holographic algorithms. On the positive side, we also give a polynomial time algorithm for a simultaneous node-edge deletion problem, using holographic algorithms. Finally we give characterizations of symmetric signatures realizable in the Hadamard basis.

    Reference
    Related
    Cited by
Get Citation

Jin-Yi Cai, Vinay Choudhary. Some Results on Matchgates and Holographic Algorithms. International Journal of Software and Informatics, 2007,1(1):3~36

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 10,2007
  • Revised:October 18,2007
  • Adopted:
  • Online:
  • Published: