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

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

Chenghua Liu, Boning Meng

Published Sep 6, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2610.00079

Related papers

Base collapse of holographic algorithms

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.

arXiv:1511.01230•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2016•6 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

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 classes: (1) polynomial-time solvable; (2) \#P-hard for general instances but solvable in polynomial time over planar structures; and (3) \#P-hard over planar structures. The classification applies to all finite sets of local, not necessarily symmetric, constraint functions on Boolean variables that take algebraic complex values. It is shown that Valiant's holographic algorithm with matchgates is a universal strategy for all problems in class (2).

arXiv:1603.07046•SIAM Journal on Computing•Nov 5, 2019•23 citations

Exact Diamond Balls, Antipodal Widths, and Query-Uniform Compression Bounds for Quantum Channels

Amin Abaee

Quantum channels with fixed finite-dimensional input and output form a compact convexbody. We ask how many continuous latent parameters are needed to encode an arbitrarychannel and reconstruct it with uniformly small diamond-norm error, when the encoder iscontinuous and the decoder is unrestricted. This is a continuous analogue of nonlinear width,distinct from tomography, which counts channel uses, and from programmable processors,which fix a decoding device. For a compact source the optimal error equals the minimalworst-case radius of the encoder’s fibers. Lower bounds follow from antipodal pairs in thesource and from latent collision topology via Borsuk–Ulam and the deleted-product coindex.Even input-independent output preparation forces error one below the output-state dimen-sion, with a Clifford analogue inside the unitary channels. We determine the largest diamondball contained in the channel body: it is centred at the completely depolarizing channel, isoptimal among all centres, and, together with a full-direction section, certifies the interme-diate lower envelope; the same channel is the optimal constant decoder, with exact coveringradius, so the two envelopes meet at the exact width at zero latent dimension. Constructiveupper bounds from convex projection and balanced pinching bracket the intermediate widths,and meet the lower envelope in the degenerate collapse case and from the affine dimensionon. Every finite-query adaptive network induces a continuous final code containing all sideinformation, so the same bottlenecks hold uniformly in the number of queries, for uniformlysuccessful postselection, and for sampled transcripts; a one-query informationally completemeasurement achieves the injective threshold, and repetition gives an O(N −1/2) expected-error bound. In the input-independent case the widths are governed by the companion’sflatness dichotomy: the flat value one fails for every output dimension at least three at thebottom two latent dimensions, the qutrit sitting exactly at 4/3 there, through a flag-quotientcohomology computation.

•Sep 13, 2026•0 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 classes: (1) Polynomial-time solvable; (2) #P-hard for general instances, but solvable in polynomial-time over planar structures; and (3) #P-hard over planar structures. The classification applies to all finite sets of complex-valued, not necessarily symmetric, constraint functions on Boolean variables. It is shown that Valiant's holographic algorithm with matchgates is universal strategy for all problems in class (2).

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2017•12 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 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.
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.
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.
We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (\#CSP) over Boolean variables into exactly three classes: (1) polynomial-time solvable; (2) \#P-hard for general instances but solvable in polynomial time over planar structures; and (3) \#P-hard over planar structures. The classification applies to all finite sets of local, not necessarily symmetric, constraint functions on Boolean variables that take algebraic complex values. It is shown that Valiant's holographic algorithm with matchgates is a universal strategy for all problems in class (2).
Quantum channels with fixed finite-dimensional input and output form a compact convexbody. We ask how many continuous latent parameters are needed to encode an arbitrarychannel and reconstruct it with uniformly small diamond-norm error, when the encoder iscontinuous and the decoder is unrestricted. This is a continuous analogue of nonlinear width,distinct from tomography, which counts channel uses, and from programmable processors,which fix a decoding device. For a compact source the optimal error equals the minimalworst-case radius of the encoder’s fibers. Lower bounds follow from antipodal pairs in thesource and from latent collision topology via Borsuk–Ulam and the deleted-product coindex.Even input-independent output preparation forces error one below the output-state dimen-sion, with a Clifford analogue inside the unitary channels. We determine the largest diamondball contained in the channel body: it is centred at the completely depolarizing channel, isoptimal among all centres, and, together with a full-direction section, certifies the interme-diate lower envelope; the same channel is the optimal constant decoder, with exact coveringradius, so the two envelopes meet at the exact width at zero latent dimension. Constructiveupper bounds from convex projection and balanced pinching bracket the intermediate widths,and meet the lower envelope in the degenerate collapse case and from the affine dimensionon. Every finite-query adaptive network induces a continuous final code containing all sideinformation, so the same bottlenecks hold uniformly in the number of queries, for uniformlysuccessful postselection, and for sampled transcripts; a one-query informationally completemeasurement achieves the injective threshold, and repetition gives an O(N −1/2) expected-error bound. In the input-independent case the widths are governed by the companion’sflatness dichotomy: the flat value one fails for every output dimension at least three at thebottom two latent dimensions, the qutrit sitting exactly at 4/3 there, through a flag-quotientcohomology computation.
We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (#CSP) over Boolean variables into exactly three classes: (1) Polynomial-time solvable; (2) #P-hard for general instances, but solvable in polynomial-time over planar structures; and (3) #P-hard over planar structures. The classification applies to all finite sets of complex-valued, not necessarily symmetric, constraint functions on Boolean variables. It is shown that Valiant's holographic algorithm with matchgates is universal strategy for all problems in class (2).
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.