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

arXiv:1307.7430

Holographic Algorithms Beyond Matchgates

Jin‐Yi Cai, Heng Guo, Tyson Williams

Published Jul 29, 2013• 0 citations
arXivHTMLPDF

Abstract

Holographic algorithms introduced by Valiant are composed of two ingredients: matchgates, which are gadgets realizing local constraint functions by weighted planar perfect matchings, and holographic reductions, which show equivalences among problems with different descriptions via certain basis transformations. In this paper, we replace matchgates in the paradigm above by the affine type and the product type constraint functions, which are known to be tractable in general (not necessarily planar) graphs. More specifically, we present polynomial-time algorithms to decide if a given counting problem has a holographic reduction to another problem defined by the affine or product-type functions. Our algorithms also find a holographic transformation when one exists. We further present polynomial-time algorithms of the same decision and search problems for symmetric functions, where the complexity is measured in terms of the (exponentially more) succinct representations. The algorithm for the symmetric case also shows that the recent dichotomy theorem for Holant problems with symmetric constraints is efficiently decidable. Our proof techniques are mainly algebraic, e.g., using stabilizers and orbits of group actions.

DOI
10.48550/arxiv.1307.7430

Related papers

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.

SIAM Journal on Computing•Jan 1, 2017•16 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

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 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.

arXiv:1008.0683•Aug 4, 2010•30 citations

Holographic Algorithm with Matchgates Is Universal for Planar $\#$CSP Over Boolean Domain

Jin‐Yi Cai, Zhiguo Fu

We prove a complexity classification theorem that classifies all counting constraint satisfaction problems ($\#$CSP) over Boolean variables into exactly three categories: (1) Polynomial-time tractable; (2) $\#$P-hard for general instances, but solvable in polynomial-time over planar graphs; and (3) $\#$P-hard over planar graphs. The classification applies to all sets of local, not necessarily symmetric, constraint functions on Boolean variables that take complex values. It is shown that Valiant's holographic algorithm with matchgates is a universal strategy for all problems in category (2).

arXiv:1603.07046•Mar 23, 2016•1 citation

Dichotomy for Real Holantc Problems

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks, with counting CSP being a special case. A complexity classification for Holant problems is more difficult to prove, not only because it logically implies a classification for counting CSP, but also due to the deeper reason that there exist more intricate polynomial time tractable problems in the broader framework. We discover a new family of constraint functions ℒ which define polynomial time computable counting problems. These do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0–1 pinning functions. Previously, dichotomy for the same framework was only known for symmetric constraint functions. The set ℒ supplies the last piece of tractability. We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.

Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•12 citations

Computational Complexity of Holant Problems

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free ($\mathrm{Holant}^*$ problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free ($\mathrm{Holant}^c$ problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations.

SIAM Journal on Computing•Jan 1, 2011•64 citations
Holographic algorithms introduced by Valiant are composed of two ingredients: matchgates, which are gadgets realizing local constraint functions by weighted planar perfect matchings, and holographic reductions, which show equivalences among problems with different descriptions via certain basis transformations. In this paper, we replace matchgates in the paradigm above by the affine type and the product type constraint functions, which are known to be tractable in general (not necessarily planar) graphs. More specifically, we present polynomial-time algorithms to decide if a given counting problem has a holographic reduction to another problem defined by the affine or product-type functions. Our algorithms also find a holographic transformation when one exists. We further present polynomial-time algorithms of the same decision and search problems for symmetric functions, where the complexity is measured in terms of the (exponentially more) succinct representations. The algorithm for the symmetric case also shows that the recent dichotomy theorem for Holant problems with symmetric constraints is efficiently decidable. Our proof techniques are mainly algebraic, e.g., using stabilizers and orbits of group actions.
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.
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 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.
Holographic Algorithm with Matchgates Is Universal for Planar #\##CSP Over Boolean Domain
We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (#\##CSP) over Boolean variables into exactly three categories: (1) Polynomial-time tractable; (2) #\##P-hard for general instances, but solvable in polynomial-time over planar graphs; and (3) #\##P-hard over planar graphs. The classification applies to all sets of local, not necessarily symmetric, constraint functions on Boolean variables that take complex values. It is shown that Valiant's holographic algorithm with matchgates is a universal strategy for all problems in category (2).
Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks, with counting CSP being a special case. A complexity classification for Holant problems is more difficult to prove, not only because it logically implies a classification for counting CSP, but also due to the deeper reason that there exist more intricate polynomial time tractable problems in the broader framework. We discover a new family of constraint functions ℒ which define polynomial time computable counting problems. These do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0–1 pinning functions. Previously, dichotomy for the same framework was only known for symmetric constraint functions. The set ℒ supplies the last piece of tractability. We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.
We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant problems. Compared to counting constraint satisfaction problems (#CSP), it is a refinement with a more explicit role for the constraint functions. Both graph homomorphism and #CSP can be viewed as special cases of Holant problems. We prove complexity dichotomy theorems in this framework. Our dichotomy theorems apply to local constraint functions, which are symmetric functions on Boolean input variables and evaluate to arbitrary real or complex values. We discover surprising tractable subclasses of counting problems, which could not easily be specified in the #CSP framework. When all unary functions are assumed to be free (Holant∗\mathrm{Holant}^*Holant∗ problems), the tractable ones consist of functions that are degenerate, or of arity at most two, or holographic transformations of Fibonacci gates. When only two special unary functions, the constant zero and constant one functions, are assumed to be free (Holantc\mathrm{Holant}^cHolantc problems), we further identify three special families of tractable cases. Then we prove that all other cases are #P-hard. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations.