Matchgates and Holographic Algorithms

Jin‐Yi Cai, Heng Guo, Tyson Williams

Jin‐Yi Cai, Heng Guo, Tyson Williams

Jin‐Yi Cai, Vinay Choudhary

Leslie Gabriel Valiant

Jin‐Yi Cai, Vinay Choudhary

We establish a 1-1 correspondence between Valiant's character theory of matchgate/matchcircuit [14] and his signature theory of planar-matchgate/matchgrid [16], thus unifying the two theories in expressibility. In [5], we had established a complete characterization of general matchgates, in terms of a set of useful Grassmann-Pl"ucker identities. With this correspondence, we give 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.

Mingji Xia

A holographic algorithm solves a problem in a domain of size n, by reducing it to counting perfect matchings in planar graphs. It may simulate a n-value variable by a bunch of t matchgate bits, which has 2t values. The transformation in the simulation can be expressed as a n × 2t matrix M, called the base of the holographic algorithm. We wonder whether more matchgate bits bring us more powerful holographic algorithms. In another word, whether we can solve the same original problem, with a collapsed base of size n × 2r, where r<t.