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:1511.01230 · ACM Symposium on Theory of Computing (STOC)

Base collapse of holographic algorithms

Mingji Xia

Published Jun 10, 2016• 6 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1145/2897518.2897560

Related papers

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

Bases Collapse in Holographic Algorithms.

Jin‐Yi Cai, Pinyan Lu

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This problem without modulo 7 is #P-complete, and counting mod 2 is NP-hard. We give a general collapse theorem for bases of dimension 4 to dimension 2 in the holographic algorithms framework. We also define an extension of holographic algorithms to allow more general support vectors. Finally we give a bases folding theorem showing that in a natural setting the support vectors can be simulated by basis of dimension 2. 1

Electronic colloquium on computational complexity•Jan 1, 2007•0 citations

Holographic algorithms

J.-Y. Cai

Leslie Valiant recently proposed a theory of holographic algorithms.These novel algorithms achieve exponential speed-ups for certain computational problems compared to naive algorithms for the same problems.The methodology uses Pfaffians and (planar) perfect matchings as basic computational primitives, and attempts to create exponential cancellations in computation.In this article we survey this new theory of matchgate computations and holographic algorithms.

Current Developments in Mathematics•Jan 1, 2005•3 citations

When Matchgate Base Collapse Fails: A Qutrit Trichotomy and Unbounded Exact Width

Chenghua Liu, Boning Meng

Holographic algorithms solve planar counting problems by encoding each value of a finite domain into several Boolean matchgate wires. Base collapse asks whether every exact representation can be compressed to a number of wires per edge bounded only by the domain size. Chen (STOC 2016) and Xia (STOC 2016) established broad positive collapse theorems under full-rank and related structural hypotheses. Together, these works left open whether a domain-only collapse bound survives when several locally deficient signatures must share one encoding. We resolve this open problem negatively, already on a three-state (qutrit) domain. For every $a\ge4$, we construct a five-label integer-valued qutrit language of maximum arity $a$ with an exact rational matchgate presentation, yet every exactly equivalent label-preserving presentation requires common width $Ω(2^{a/2}/a)$, even if its domain, base, tensors, and complex weights may all change. The construction avoids the usual local degeneracies, so the obstruction is genuinely simultaneous. Algebraic geometry then drives an exhaustive trichotomy explaining the boundary of collapse: the gadget closure either separates into rays, is Gaussian-mobile and collapses to width at most three, or is confined to a rigid plane-plus-ray flag containing our unbounded family. Pure-spinor geometry forces compression in the mobile case, while dimension bounds for matchgate varieties and Zariski avoidance place exact integer data outside every low-width algebraic image. Thus one geometric framework explains both why collapse occurs and why it can fail without bound.

arXiv:2610.00079•Sep 6, 2026•0 citations

Bases Collapse in Holographic Algorithms

Jin‐Yi Cai, Pinyan Lu

Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This problem without modulo 7 is #P-complete, and counting mod 2 is NP-hard. We give a general collapse theorem for bases of dimension 4 to dimension 2 in the holographic algorithms framework. We also define an extension of holographic algorithms to allow more general support vectors. Finally we give a Basis Folding Theorem showing that in a natural setting the support vectors can be simulated by bases of dimension 2.

IEEE Conference on Computational Complexity (CCC)•Jun 1, 2007•21 citations
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.
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 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.
Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This problem without modulo 7 is #P-complete, and counting mod 2 is NP-hard. We give a general collapse theorem for bases of dimension 4 to dimension 2 in the holographic algorithms framework. We also define an extension of holographic algorithms to allow more general support vectors. Finally we give a bases folding theorem showing that in a natural setting the support vectors can be simulated by basis of dimension 2. 1
Holographic algorithms solve planar counting problems by encoding each value of a finite domain into several Boolean matchgate wires. Base collapse asks whether every exact representation can be compressed to a number of wires per edge bounded only by the domain size. Chen (STOC 2016) and Xia (STOC 2016) established broad positive collapse theorems under full-rank and related structural hypotheses. Together, these works left open whether a domain-only collapse bound survives when several locally deficient signatures must share one encoding. We resolve this open problem negatively, already on a three-state (qutrit) domain. For every a≥4a\ge4a≥4, we construct a five-label integer-valued qutrit language of maximum arity aaa with an exact rational matchgate presentation, yet every exactly equivalent label-preserving presentation requires common width Ω(2a/2/a)Ω(2^{a/2}/a)Ω(2a/2/a), even if its domain, base, tensors, and complex weights may all change. The construction avoids the usual local degeneracies, so the obstruction is genuinely simultaneous. Algebraic geometry then drives an exhaustive trichotomy explaining the boundary of collapse: the gadget closure either separates into rays, is Gaussian-mobile and collapses to width at most three, or is confined to a rigid plane-plus-ray flag containing our unbounded family. Pure-spinor geometry forces compression in the mobile case, while dimension bounds for matchgate varieties and Zariski avoidance place exact integer data outside every low-width algebraic image. Thus one geometric framework explains both why collapse occurs and why it can fail without bound.
Holographic algorithms are a novel approach to design polynomial time computations using linear superpositions. Most holographic algorithms are designed with basis vectors of dimension 2. Recently Valiant showed that a basis of dimension 4 can be used to solve in P an interesting (restrictive SAT) counting problem mod 7. This problem without modulo 7 is #P-complete, and counting mod 2 is NP-hard. We give a general collapse theorem for bases of dimension 4 to dimension 2 in the holographic algorithms framework. We also define an extension of holographic algorithms to allow more general support vectors. Finally we give a Basis Folding Theorem showing that in a natural setting the support vectors can be simulated by bases of dimension 2.