Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Electronic colloquium on computational complexity

Some Results on Matchgates and Holographic Algorithms.

Jin‐Yi Cai, Vinay Choudhary

Published Jan 1, 2006• 1 citation
OpenAlex

Abstract

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.

Related papers

On the Theory of Matchgate Computations

Jin‐Yi Cai, Vinay Choudhary, Pinyan Lu

Valiant has proposed a new theory of algorithmic computation based on perfect matchings and Pfaffians. We study the properties of matchgates—the basic building blocks in this new theory. We give a set of algebraic identities which completely characterizes these objects for arbitrary numbers of inputs and outputs. These identities are derived from Grassmann-Plücker identities. The 4 by 4 matchgate character matrices are of particular interest. These were used in Valiant's classical simulation of a fragment of quantum computations. For these 4 by 4 matchgates, we use Jacobi's theorem on compound matrices to prove that the invertible matchgate matrices form a multiplicative group. Our results can also be expressed in the theory of Holographic Algorithms in terms of realizable standard signatures. These results are useful in establishing limitations on the ultimate capabilities of Valiant's theory of matchgate computations and Holographic Algorithms.

Theory of Computing Systems•Jun 1, 2007•64 citations

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in the statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs and can be arbitrary real-valued symmetric functions. We prove that every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

arXiv:1008.0683•SIAM Journal on Computing•Jan 1, 2017•50 citations

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

Annual Symposium on Foundations of Computer Science•Oct 1, 2010•50 citations

Matchgates Revisited

Jin‐Yi Cai, Aaron Gorenstein

We study a collection of concepts and theorems that laid the foundation of matchgate computation. This includes the signature theory of planar matchgates, and the parallel theory of characters of not necessarily planar matchgates. Our aim is to present a unified and, whenever possible, simplified account of this challenging theory. Our results include: (1) A direct proof that Matchgate Identities (MGI) are necessary and sufficient conditions for matchgate signatures. This proof is self-contained and does not go through the character theory. More importantly it rectifies a gap in the existing proof. (2) A proof that Matchgate Identities already imply the Parity Condition. (3) A simplified construction of a crossover gadget. This is used in the proof of sufficiency of MGI for matchgate signatures. This is also used to give a proof of equivalence between the signature theory and the character theory which permits omittable nodes. (4) A direct construction of matchgates realizing all matchgate-realizable symmetric signatures.

arXiv:1303.6729•Mar 27, 2013•7 citations

Holographic algorithms with unsymmetric signatures

Jin‐Yi Cai, Pinyan Lu

Holographic algorithms were introduced by Valiant as a new methodology to derive polynomial time algorithms. Here information and computation are represented by exponential sums using the so-called signatures. These signatures express superpositions of perfect matchings, and are used to achieve exponential sized cancellations, and thereby exponential speedups. Most holographic algorithms so far used symmetric signatures. In this paper we use unsymmetric signatures to give some new holographic algorithms. We also prove a characterization theorem for a class of realizable un-symmetric signatures, each of which may be used to design new holographic algorithms.

Symposium on Discrete Algorithms•Jan 20, 2008•8 citations

Geometry in Algorithms and Complexity: Holographic Algorithms and Valiant's Conjecture

Sitan Chen

The $\\P$ versus $\\NP$ problem is arguably the most important open problem in all of theoretical computer science. In recent years, geometry has arisen as one of the most promising approaches for tackling this problem, both for obtaining positive results (polynomial-time solutions to seemingly intractable computational problems) and for proving negative results (impossibility results stating that such algorithms cannot exist). This work deals with both directions. \nIn the positive direction, the theory of holographic algorithms introduced by Valiant represents a novel approach to achieving polynomial-time algorithms for seemingly intractable counting problems via a reduction to counting planar perfect matchings and a linear change of basis. The connection to geometry is that a counting problem can be solved by a holographic algorithm provided a particular system of equations associated to that problem is solvable. Two fundamental parameters in holographic algorithms are the \\emph{domain size} and the \\emph{basis size}. Roughly, the domain size is the range of colors involved in the counting problem at hand (e.g. counting graph $k$-colorings is a problem over domain size $k$), while the basis size $\\ell$ captures the dimensionality of the representation of those colors. A major open problem has been: for a given $k$, what is the smallest $\\ell$ for which any holographic algorithm for a problem over domain size $k$ ``collapses to'' (can be simulated by) a holographic algorithm with basis size $\\ell$? Cai and Lu showed in 2008 that over domain size 2, basis size 1 suffices, opening the door to an extensive line of work on the structural theory of holographic algorithms over the Boolean domain. Cai and Fu later showed for signatures of full rank that over domain sizes 3 and 4, basis sizes 1 and 2, respectively, suffice, and they conjectured that over domain size $k$ there is a collapse to basis size $\\lfloor\\log_2 k\\rfloor$. In the first half of this work, we resolve this conjecture in the affirmative for signatures of full rank for all $k$. As a simple consequence, we are able to formulate Valiant's holographic framework over all domain sizes in terms of the geometry of spinor varieties and their orbits under basis change. \nIn the negative direction, Valiant's conjecture is an algebraic analogue of $\\P$ versus $\\NP$ which states that the permanent polynomial $\\perm_m$ cannot be computed as a linear projection of the determinant polynomial $\\det_n$ for $n = \\poly(m)$. This can be formulated as an orbit containment problem; for the sake of bringing tools from algebraic geometry to bear on Valiant's conjecture, Mulmuley and Sohoni conjectured that Valiant's conjecture still holds when one passes to the Zariski closures of the relevant orbits. Essential to understanding what changes in this relaxation is understanding the geometry of the boundary of the orbit closure of $\\det_n$. In the second half of this work, we study this problem for $n = 3$ and use a combinatorial approach to give a complete classification of the irreducible components on the boundary in this case. We additionally present a new infinite family of boundary components for all even $n$. Beyond these results and a general overview of Mulmuley-Sohoni's program, we also provide exposition on known lower bounds for the determinantal complexity of the permanent in Valiant's and Mulmuley-Sohoni's settings, an exponential lower bound due to Landsberg and Ressayre under a more restricted model of determinantal representations, Kumar's result on the non-normality of the orbit closure of $\\det_n$, Harris and Eisenbud's classification of maximal linear subspaces of the determinantal hypersurface in dimensions 3 and 4, and Huttenhain-Lairez's independent proof of our boundary component classification by way of resolution of singularities.

•Jun 21, 2016•0 citations
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.
Valiant has proposed a new theory of algorithmic computation based on perfect matchings and Pfaffians. We study the properties of matchgates—the basic building blocks in this new theory. We give a set of algebraic identities which completely characterizes these objects for arbitrary numbers of inputs and outputs. These identities are derived from Grassmann-Plücker identities. The 4 by 4 matchgate character matrices are of particular interest. These were used in Valiant's classical simulation of a fragment of quantum computations. For these 4 by 4 matchgates, we use Jacobi's theorem on compound matrices to prove that the invertible matchgate matrices form a multiplicative group. Our results can also be expressed in the theory of Holographic Algorithms in terms of realizable standard signatures. These results are useful in establishing limitations on the ultimate capabilities of Valiant's theory of matchgate computations and Holographic Algorithms.
Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in the statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs and can be arbitrary real-valued symmetric functions. We prove that every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.
Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.
We study a collection of concepts and theorems that laid the foundation of matchgate computation. This includes the signature theory of planar matchgates, and the parallel theory of characters of not necessarily planar matchgates. Our aim is to present a unified and, whenever possible, simplified account of this challenging theory. Our results include: (1) A direct proof that Matchgate Identities (MGI) are necessary and sufficient conditions for matchgate signatures. This proof is self-contained and does not go through the character theory. More importantly it rectifies a gap in the existing proof. (2) A proof that Matchgate Identities already imply the Parity Condition. (3) A simplified construction of a crossover gadget. This is used in the proof of sufficiency of MGI for matchgate signatures. This is also used to give a proof of equivalence between the signature theory and the character theory which permits omittable nodes. (4) A direct construction of matchgates realizing all matchgate-realizable symmetric signatures.
Holographic algorithms were introduced by Valiant as a new methodology to derive polynomial time algorithms. Here information and computation are represented by exponential sums using the so-called signatures. These signatures express superpositions of perfect matchings, and are used to achieve exponential sized cancellations, and thereby exponential speedups. Most holographic algorithms so far used symmetric signatures. In this paper we use unsymmetric signatures to give some new holographic algorithms. We also prove a characterization theorem for a class of realizable un-symmetric signatures, each of which may be used to design new holographic algorithms.
The P\\PP versus NP\\NPNP problem is arguably the most important open problem in all of theoretical computer science. In recent years, geometry has arisen as one of the most promising approaches for tackling this problem, both for obtaining positive results (polynomial-time solutions to seemingly intractable computational problems) and for proving negative results (impossibility results stating that such algorithms cannot exist). This work deals with both directions. \nIn the positive direction, the theory of holographic algorithms introduced by Valiant represents a novel approach to achieving polynomial-time algorithms for seemingly intractable counting problems via a reduction to counting planar perfect matchings and a linear change of basis. The connection to geometry is that a counting problem can be solved by a holographic algorithm provided a particular system of equations associated to that problem is solvable. Two fundamental parameters in holographic algorithms are the \\emph{domain size} and the \\emph{basis size}. Roughly, the domain size is the range of colors involved in the counting problem at hand (e.g. counting graph kkk-colorings is a problem over domain size kkk), while the basis size ell\\ellell captures the dimensionality of the representation of those colors. A major open problem has been: for a given kkk, what is the smallest ell\\ellell for which any holographic algorithm for a problem over domain size kkk ``collapses to'' (can be simulated by) a holographic algorithm with basis size ell\\ellell? Cai and Lu showed in 2008 that over domain size 2, basis size 1 suffices, opening the door to an extensive line of work on the structural theory of holographic algorithms over the Boolean domain. Cai and Fu later showed for signatures of full rank that over domain sizes 3 and 4, basis sizes 1 and 2, respectively, suffice, and they conjectured that over domain size kkk there is a collapse to basis size lfloorlog2krfloor\\lfloor\\log_2 k\\rfloorlfloorlog2​krfloor. In the first half of this work, we resolve this conjecture in the affirmative for signatures of full rank for all kkk. As a simple consequence, we are able to formulate Valiant's holographic framework over all domain sizes in terms of the geometry of spinor varieties and their orbits under basis change. \nIn the negative direction, Valiant's conjecture is an algebraic analogue of P\\PP versus NP\\NPNP which states that the permanent polynomial permm\\perm_mpermm​ cannot be computed as a linear projection of the determinant polynomial detn\\det_ndetn​ for n=poly(m)n = \\poly(m)n=poly(m). This can be formulated as an orbit containment problem; for the sake of bringing tools from algebraic geometry to bear on Valiant's conjecture, Mulmuley and Sohoni conjectured that Valiant's conjecture still holds when one passes to the Zariski closures of the relevant orbits. Essential to understanding what changes in this relaxation is understanding the geometry of the boundary of the orbit closure of detn\\det_ndetn​. In the second half of this work, we study this problem for n=3n = 3n=3 and use a combinatorial approach to give a complete classification of the irreducible components on the boundary in this case. We additionally present a new infinite family of boundary components for all even nnn. Beyond these results and a general overview of Mulmuley-Sohoni's program, we also provide exposition on known lower bounds for the determinantal complexity of the permanent in Valiant's and Mulmuley-Sohoni's settings, an exponential lower bound due to Landsberg and Ressayre under a more restricted model of determinantal representations, Kumar's result on the non-normality of the orbit closure of detn\\det_ndetn​, Harris and Eisenbud's classification of maximal linear subspaces of the determinantal hypersurface in dimensions 3 and 4, and Huttenhain-Lairez's independent proof of our boundary component classification by way of resolution of singularities.