PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Chenghua Liu, Boning Meng

arXiv:2610.00079v1cs.CC

TL;DR

The paper asks whether exact matchgate presentations admit a common-width bound depending only on domain size, despite the representation size needed to coordinate several signatures. It uses algebraic geometry to analyze when support geometry permits collapse and when exact common width can grow without bound, showing that the latter already occurs for qutrits.

  • Problem

    For qutrits, minimum exact common width is unbounded, challenging the question of whether every matchgate-realizable labelled language has a width bound depending only on domain size.

    Source: §1 · p. 2

  • Method

    The paper uses pure-spinor incidence for collapse and star-table varieties with Zariski avoidance for lower bounds robust to exact re-presentation.

    Source: §1.4 · p. 5

  • Results

    For q=3, minimum exact common width is unbounded across integer-valued, positive-arity, non-full-rank signature families under exact labelled equivalence.

    Source: §1 · p. 2, §3.1 · p. 8

  • Takeaways & Limitations

    Local domain and port rank do not control labelled information coordinated across ports; support mobility yields a small common Gaussian cover, while a fixed plane-plus-ray flag can leave width-growing residual data.

    Source: §11 · p. 43

    The result does not establish computational hardness: the high-arity right label grows with k, and equivalence is stricter than gadget or polynomial-time equivalence.

    Source: §1.1 · p. 3

Abstract

from arXiv · show

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 $\Omega(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.

1 Introduction

The paper asks whether a shared exact matchgate encoding can always have width bounded by domain size, and answers no for qutrits. It also classifies when port-deficient qutrit presentations collapse and identifies a rigid flag branch containing languages of unbounded width.

1 Introduction

  • Holographic algorithms encode finite-domain planar counting problems as Boolean matchgate networks, so one common base must coordinate every occurrence of every label.Matchgates evaluate the global sum through Pfaffians and weighted perfect matchings; extra wires may be redundant or carry compatibility information shared across labels.Source: §1 · pp. 1–2

1.1 The collapse question and our answer

  • For qutrits, minimum exact common width is unbounded despite a five-label integer-valued language with an exact rational presentation.The lower bound survives arbitrary exact re-presentation, including changes to the domain, base, coordinate tensors, and complex weights; the high-arity right label grows with the construction parameter.Source: §1 · p. 2, §1.1 · pp. 2–3

1.2 Where can non-collapse occur?

  • The trichotomy’s ray-separable branch forces all-left boundary tensors to factor, while its Gaussian-mobile branch collapses to width at most three, or two when two distinct planes occur.The mobile case has a realized plane but is not confined to one flag.Source: §1.2 · p. 3
  • The one-plane flag branch contains an unbounded-width family whose all-left boundary tensors have a Boolean matchgate core times pure-ray factors.In this branch, the flag leaves residual right-side data uncontrolled; the construction uses a 2k-entry table outside every relevant low-width image.Source: §1.2 · p. 3

1.3 Proof architecture and technical ideas

  • The proof combines composable-support geometry and pure-spinor common-cover certificates with flag normal forms, block-Pfaffian interpolation, and star-table dimension bounds.Zariski avoidance selects integer data outside lower-width star-table images, establishing the obstruction under arbitrary exact re-presentation.Source: §1.3 · p. 4

1.4 Relation to previous work

  • The result answers the uniform-width aspect of Xia’s compatibility question, while the paper’s algebraic-geometric method uses incidence for collapse and star-table varieties for non-collapse.Earlier results covered full-rank or other structural regimes; prior negative results excluded specified realizations rather than bounding the size of every exact common realization.Source: §1.4 · p. 5

2 Statement-Level Preliminaries

This section establishes the signature, common-presentation, equivalence, and realized-support notions used to state the paper’s results.

2.1 Signatures, planar instances, and local rank

  • A signature is a port-ordered tensor; mode supports and ranks identify deficient ports, while support-essential families collectively span the domain.A nonzero tensor is pure when it factors into unary vectors, and Schmidt rank is defined by a port partition.Source: §2.1 · p. 6

2.2 Common matchgate presentations

  • A common presentation uses one base to lift every left label to exact matchgates and gives each right label an exact matchgate preimage.Common matchgate covers can be decoded to presentations of smaller width.Source: §2.2 · p. 6

2.3 Exact labelled equivalence and minimum width

  • Exact labelled equivalence preserves arities, label families, port orders, and every planar-instance value, while minimum exact common width ranges over equivalent presentations on any finite nonempty domain.The minimum imposes no rank condition on an alternative base; a uniform bound controls a whole class of languages.Source: §2.3 · pp. 6–7

2.4 Realized supports and monomial flags

  • Realized supports are rays or planes; each realized plane yields parity-defined distinguished rays, and a flagged core encodes plane-supported ports through those endpoints with unary factors on remaining ports.The endpoint basis is fixed for the plane-supported ports.Source: §2.4 · p. 7

3 Main Results

The paper constructs integer-valued qutrit languages whose minimum exact common width has no uniform bound, despite exact rational presentations. It also classifies the relevant support geometries into three branches, including a mobile branch that collapses to bounded width and a flag branch containing unbounded-width languages.

3.1 Unbounded exact width

  • For every integer k ≥ 2, there is a finite integer-valued domain-three language with an exact rational matchgate presentation whose base has full row rank and dimensions 3-by-(22k+3).Its maximum arity is k + 2.Source: §3.1 · pp. 7–8
  • Every port of X01 and Bk has flattening rank exactly two, while the pins have rank one; Bk is support-essential by itself.Its two link-port supports span(e0, e1), and its k hard-port supports span(e0, e2).Source: §3.1 · p. 8
  • Under exact labelled equivalence, no domain-only bound exists for the minimum exact common width of the specified integer-valued, positive-arity, non-full-rank languages.The result still holds when the displayed presentation is over Q, although equivalent presentations may use arbitrary exact complex weights.Source: §3.1 · p. 8

3.2 Support-geometric trichotomy

  • The trichotomy applies to valid rank-three qutrit presentations that are bi-essential and have port flattenings of rank at most two.It classifies the closure using supports realized at distinguished ports of connected all-left planar gadgets.Source: §3.2 · p. 8
  • The three alternatives are ray-separable closure, Gaussian-mobile closure without a monomial flag, and one-plane flag closure.In the ray-separable case, nonzero positive-arity all-left boundary tensors are completely decomposable; in the flag case, they have a Boolean-core-times-rays form using one fixed endpoint-basis isomorphism.Source: §3.2 · pp. 8–9
  • Gaussian-mobile closure yields an equivalent common presentation of width at most three, or at most two when at least two distinct planes occur.The common matchgate cover has rank at most eight, or rank four when at least two distinct planes occur.Source: §3.2 · p. 8
  • The alternatives are presentation-relative, and a flag is necessary but not sufficient for large width; the ray-separable branch has no width classification here.Every individual finite language has finite width, and a pointwise characterization would require a language invariant independent of a chosen flag presentation.Source: §3.2 · p. 9

5 Matchgate Parameter Bounds and Star-Table Varieties

The section turns the width question into parameter counting for sampled matchgate star tables, then into algebraic bounds on the tables low-width representations can produce. These Q-defined loci provide a way to identify integer obstruction tables even though integer coordinates have transcendence degree zero.

5 Matchgate Parameter Bounds and Star-Table Varieties

  • Coordinate transcendence and matchgate-variety dimension bounds quantify the parameter information available to a width-r star representation.The argument uses pivoted Pfaffian charts to bound matchgate coordinates.Source: §5 · pp. 22, 24
  • Sampled star tables arise by contracting a central matchgate with a sampler signature on each consecutive block, and each output coordinate is polynomial in the source coordinates.This packages labelled closed-star instances for the parameter count.Source: §5 · p. 23
  • The algebraic formulation permits integer obstruction tables despite their coordinates having transcendence degree zero.The resulting low-width algebraic loci are the sets later avoided in the negative construction.Source: §5 · pp. 22–23
  • When the star-table dimension bound Dk,r is below 2^k, its Q-defined Zariski closure is a proper subset of the ambient table space.The closure is obtained from the polynomial star-table map and its defining equations over Q.Source: §5 · pp. 24–25

6 Two Obstruction Tables

Section 6 constructs two nowhere-zero Boolean tables whose one-versus-rest flattenings all have rank two and whose exact matchgate-star representations are obstructed at low width. One witness is closed-form and transcendental; the other is positive-integer-valued and selected by finite algebraic avoidance.

6 Two Obstruction Tables

  • Both obstruction tables have rank-two one-versus-rest flattenings and resist matchgate-star representations at every width below the stated parameter threshold.The integer witness drives the rational qutrit construction; the transcendental witness is an explicit companion.Source: §6 · p. 25, §6.1 · p. 26, §6.2 · p. 26

6.1 A closed-form transcendental table

  • The closed-form transcendental table is everywhere positive, has algebraically independent entries, and has rank-two flattenings across every port.Its algebraic independence follows from the prime-indexed exponential construction; the resulting nonzero flattening minors establish rank two.Source: §6.1 · pp. 25–26
  • The transcendental witness cannot be represented by a matchgate star table below the parameter bound, even when the representing matchgates have arbitrary complex weights.The proposition also states that every one-versus-rest flattening has rank two.Source: §6.1 · p. 26

6.2 A positive-integer table

  • For each k ≥2, finite Zariski avoidance selects a positive-integer table outside every relevant low-width star-table closure, with every one-versus-rest flattening of rank two.The positive integer grid is used to choose an entry vector avoiding the finite collection of proper algebraic sets.Source: §6.2 · pp. 26–27
  • The integer witness is existential but effective in principle; the proof gives no useful running-time, height, or bit-length bound, unlike the transcendental witness’s simple closed formula.The two witnesses separate the tradeoffs between integer entries and closed-form specification.Source: §6.1 · p. 26, §6.2 · p. 27

7 Pfaffian Interpolation on Two Block Codewords

Section 7 gives an exact, field-preserving matchgate interpolation of any nowhere-zero Boolean table on two repetition-code words per block. A block-ordered Pfaffian construction realizes the table through independent subset components.

7 Pfaffian Interpolation on Two Block Codewords

  • Every nowhere-zero Boolean table f:{0,1}^k→K× has an exact matchgate signature over K that agrees with f on the two repetition-code words in each block.The construction uses k consecutive blocks of t=2^k bits and preserves their external linear order.Source: §7 · pp. 27–28
  • The interpolation builds one independent Pfaffian component for each nonempty subset S, contributing its multiplier when all blocks in S are selected and 1 otherwise.The subset multipliers are recursively chosen so their product recovers the target table.Source: §7 · p. 28
  • Each subset component uses baseline and alternate noncrossing matchings to produce its desired multiplier when fully selected; partial selection leaves contribution 1.Disjoint components factor without a global sign, and a final scalar restores f(0^k).Source: §7 · p. 29
  • The exact planar realization uses edge weights in K, but the theorem makes no claim of polynomial-size encoding or polynomial-time construction.The parameter matrix need not itself be planar; the planar realization is supplied for its Pfaffian tensor.Source: §7 · pp. 28–29

8 The Controlled Domain-Three Presentation

Section 8 packages the positive-integer obstruction into an exact rational qutrit presentation with deficient but essential local supports. Added link controls form a genuinely coupled two-center gadget, while a transcendental companion retains the same structural conclusions.

8 The Controlled Domain-Three Presentation

  • The right Boolean preimage uses k hard blocks and two link blocks; marker and control modes restrict its surviving coordinates to the intended link and hard states.The designated hard block uses control weights α=1 and β=2, making the two control outcomes distinct.Source: §8 · pp. 30–31
  • The integer construction gives a valid width-T_k exact matchgate presentation over Q whose right tensor is integer-valued and contains the obstruction table as an exact restriction.Its left family consists of three pins and a marker signature, and its base has full row rank.Source: §8 · p. 31
  • The Pfaffian control block yields values α and β for the two selected link configurations, and the global scale restores the obstruction table’s values.The other hard blocks contribute isolated control pairs; selecting a hard marker or exactly one link marker gives zero.Source: §8 · p. 31
  • Every port of each nonunary primitive has rank exactly two, while the pins have rank one; the language is support-essential on both sides.The right tensor’s link-port support is span(e0,e1), and its hard-port support is span(e0,e2).Source: §8 · pp. 31–32
  • The two-center gadget has Schmidt rank exactly two, so its boundary tensor does not factor into one tensor for each center.The link constraints leave exactly the state pairs (0,1) and (1,0).Source: §8 · p. 32
  • Replacing the integer table with the closed-form transcendental table gives a presentation over its coefficient field with the same rank, essentiality, and two-center properties.The proof uses nonvanishing and rank-two flattening minors, together with α≠β.Source: §8 · p. 33

9 The Lower Bound against Arbitrary Equivalent Presentations

Section 9 recovers the obstruction table from closed labelled stars in any exactly equivalent presentation, regardless of changes to its domain, base, tensors, or complex weights. The obstruction then forces the stated lower bound on every such presentation’s common width.

9 The Lower Bound against Arbitrary Equivalent Presentations

  • A fixed family of closed labelled stars recovers the same obstruction table from every exactly equivalent presentation, even when its domain, base, tensors, and weights change.The argument uses preservation of exact labelled planar-instance values and ordered planar contraction.Source: §9 · pp. 33–34
  • The recovered table becomes a matchgate-star representation with sampler pair (g0,g2), so the Section 6 obstruction applies to the competing width.The derivation assumes no rank or inverse condition on the new base or its domain signatures.Source: §9 · p. 34
  • Taking the minimum over all equivalent presentations yields the quantitative lower bound on minimum exact common width.The proof combines the forced width inequality with the constructed presentation’s upper bound.Source: §9 · p. 34
  • The transcendental companion also has unbounded width against arbitrary-complex-weight presentations, at the cost of using transcendental constants.Its explicit witness complements the integer construction.Source: §9 · p. 34
  • No domain-only width bound can hold: applying any such bound to the constructed presentations would contradict their minimum widths tending to infinity.This consequence follows from the integer construction’s presentations and the lower bound.Source: §9 · pp. 34–35

10 The Positive Boundary: Support Geometry and Collapse

This section characterizes the positive boundary of qutrit width collapse through support geometry and gadget-closure structure. It gives an exhaustive trichotomy, including low-rank common covers under stated hypotheses, an all-arity normal form for the plane-bearing case, and a width-at-most-three conclusion in the binary-context setting when a context is not partial monomial.

10 The Positive Boundary: Support Geometry and Collapse

  • Support monotonicity propagates primitive port deficiency through all-left gadgets, while full row rank preserves realized support dimensions in matchgate block row spaces.The transformed block support and the original mode support have the same dimension.Source: §10 · p. 35
  • Distinct intersecting rank-two exact matchgate row spaces lie in a rank-four exact matchgate row space containing their sum.This Gaussian hull supplies a common cover when the two planes in the theorem’s support geometry are distinct.Source: §10 · p. 36
  • Any exact matchgate cover of rank 2r compresses a valid presentation to width r while preserving its domain tensors, labels, arities, and port orders.The decoder-based argument performs the compression separately for every label without label-dependent scalars or port permutations [24, Theorem 5.2].Source: §10 · p. 38
  • Every isotropic subspace of dimension t − r defines an exact rank-2r matchgate whose row space is the joint kernel of its Clifford annihilators.This realizes the common-annihilator cover used to contain row(M) in the rank-eight case.Source: §10 · p. 38
  • The remaining plane-bearing configuration is a one-plane monomial flag with an all-arity normal form; rank-two blocks admit a fixed decoder yielding an exact Boolean matchgate signature under the stated block condition.The decoder transformation depends only on the rank-two row space and maps its parity lines to coordinate lines.Source: §10 · pp. 39, 41
  • Under the stated qutrit hypotheses, connection-prime closure yields a rank-at-most-eight common cover and width at most three; two distinct realized planes improve these bounds to rank four and width two.The theorem assumes rank M = 3, support-essentiality of the induced right family, and deficiency at every port of every domain tensor.Source: §10 · p. 40

Support decomposition

  • Rank-one modes factor off as product vectors, while stripping ports outside a plane-supported core leaves an exact matchgate whose retained modes all have rank two.The stripped factors and the plane's parity endpoints map to exact pure matchgate vectors.Source: §10 · pp. 41–42

Trichotomy

  • The closure falls into alternative (I) when every mode support is a line, alternative (II) when rank-two supports occur without a monomial flag, and alternative (III) when a monomial flag exists.These cases are mutually exclusive and exhaustive; the no-flag case is connection-prime, while the flag case satisfies alternative (III)'s support inclusions.Source: §10 · p. 42

Flag placement

  • The displayed presentation lies in alternative (III), and its parameter μk tends to infinity.The cited propositions supply the remaining operational properties and establish the final flag-placement assertion.Source: §10 · p. 42

Binary-context alternative

  • A non-partial-monomial binary context forces width at most three under the stated qutrit plane-and-line hypotheses.Otherwise, the alternatives are a rank-four common matchgate cover, a rank-eight common cover, or every binary context being partial monomial in the adapted ray basis.Source: §10 · pp. 42–43

11 Discussion and Future Directions

The discussion distinguishes local rank and port rank from the coordination of labelled information across many ports: support mobility forces compression, while a fixed plane-plus-ray flag can preserve unbounded exact width. It identifies open questions about intrinsic width characterizations, bounded-arity bounds, broader equivalence notions, explicit obstructions, and extensions beyond qutrits.

11 Discussion and Future Directions

  • Support mobility produces a small common Gaussian cover, whereas a fixed plane-plus-ray flag can preserve labelled information of arbitrarily large exact cost.The discussion separates local domain and port rank from the amount of information coordinated across many ports.Source: §11 · p. 43

11.1 From a support trichotomy to a language-level width theory

  • A presentation-independent invariant is needed to certify bounded-width realizations or quantitative lower bounds across changes to the flag, domain, or table.The labelled star-table obstruction certifies lower bounds for the constructed family but is not a general characterization; the discussion also asks whether alternative (I) languages have bounded width and whether failures of confinement have small context witnesses.Source: §11.1 · pp. 43–44

11.2 Bounded arity and the source of unbounded information

  • It remains open whether bounded arity alone, or bounded arity plus a fixed label count, bounds minimum exact width for q-element languages.The constructed family stores its growing table in the increasing arity of Bk; for rational or integer languages, the discussion also asks for effective bounds incorporating coefficient bit length.Source: §11.2 · p. 44

11.3 Robustness under broader equivalence notions

  • The lower bound is established for exact labelwise equivalence, not bounded-gadget equivalence or polynomial-time interreducibility.A broader width measure would need to account for gadget substitution size and uniformity; polynomial-time interreducibility also requires a specified uniform input model.Source: §11.3 · p. 44

11.4 Explicit and quantitative obstructions

  • The integer obstruction has neither a simple formula nor a useful height bound, and the current width lower bound leaves a large quantitative gap.A target is a uniformly generated positive-integer or rational family with polynomial per-entry bit length and construction time polynomial in total output length; it remains unclear whether the gap reflects intrinsic table cost or interpolation overhead.Source: §11.4 · pp. 44–45

11.5 Beyond qutrits and intrinsic compression

  • Beyond qutrits, intermediate-dimensional supports create richer incidence patterns, motivating a search for finite support stratifications and domain-controlled common covers.The same question has a free-fermionic formulation as simultaneous exact Gaussian mode compression, not physical qubit compression; the discussion says the challenge is recognizing residual information intrinsically from the language.Source: §11.5 · p. 45
Loading 2610.00079v1…