holant-tools 0.1.10

Decision procedures for matchgate-Holant tractability: polynomial-time SRP solver, Galluccio-Loebl Holant evaluator, hardness-candidate screening.

holant-tools

Decision procedures for matchgate-Holant tractability.

holant-tools decides, in polynomial time, whether a set of matchgate constraint functions admits a polynomial-time holographic-algorithm route — and if so, gives you the basis on which to construct it. The kernel implementation of a tractability-routing layer that could sit on top of general-purpose constraint solvers.

To the author's knowledge, this is the first published runnable implementation of Cai–Lu 2011's polynomial-time Simultaneous Realizability Problem solver — a result that has stood as paper-only since 2011.

Install

pip install holant-tools

Requires Python ≥ 3.9 and sympy.

30-second example: Cai–Lu §5.1 reproduced

The canonical published example is #_7 Pl-Rtw-Mon-3CNF — a #P-complete counting problem that is tractable mod 7. Two signatures: EQ_2 = [1, 0, 1] (recognizer, arity 2) and OR_3 = [0, 1, 1, 1] (generator, arity 3).

$ holant solve examples/01-counting-csps/cai_lu_5_1_mod7_3cnf.json --modulus 7
SRP: FEASIBLE
  Witness basis: u = 2, v = 3
  Branch combination: [even, even]
  solved over F_7 (tried 1 branch combination(s))

The same problem is infeasible over the algebraic closure of $\mathbf{Q}$ (no rational/algebraic basis works) — the mod-7 specificity is the "#_7" in the problem name, and it falls out of the algorithm.

Programmatic API:

from holant_tools import from_symmetric, srp_solve

sigs = [
    from_symmetric([1, 0, 1], name="EQ_2"),
    from_symmetric([0, 1, 1, 1], name="OR_3", kind="generator"),
]
result = srp_solve(sigs, modulus=7)
print(result.feasible)   # True
print(result.witness)    # {U: 2, V: 3}

What it does

Given a list of matchgate signatures, the tool answers:

• Is this set of constraints jointly realizable on some basis? (Cai–Lu's Simultaneous Realizability Problem; polynomial-time decidable per their 2011 Theorem 4.1.)
• If yes, what is the basis? (Provides the witness.)
• Over which field — algebraic closure of $\mathbf{Q}$, or a specific finite field $\mathbf{F}_p$?
• Is this a candidate for #P-hardness? (Screening: if no realising basis exists across $\overline{\mathbf{Q}}$ + multiple small primes, the matchgate / holographic-algorithm route is unavailable — a necessary condition for hardness in the Cai–Lu–Xia dichotomy framework.)

CLI

holant signature "[1, 0, 1]"             # Individual realizability (Cai–Lu Thm 2.5)
holant check    sigs.json                 # Necessary-condition SRP check
holant solve    sigs.json [--modulus p]   # Full SRP (intersection on M)
holant hardness sigs.json [--primes ...]  # Hardness-candidate screening

JSON input format (sigs.json):

[
  {"values": [1, 0, 1],    "kind": "recognizer", "name": "EQ_2"},
  {"values": [0, 1, 1, 1], "kind": "generator",  "name": "OR_3"}
]

• values: signature entries by Hamming weight, length = arity + 1.
• kind: "recognizer" or "generator".
• name: optional display string.

See examples/ for worked walkthroughs organised by application area: counting CSPs, hardness screening, perfect matchings, matchgate quantum circuits, portfolio routing, scheduling, structural fingerprint, scheduling adapter, SWF parser + empirical scan.

Scope (v0.1.9 — current)

Decision procedures (the v0.1.x baseline)

• Symmetric matchgate signatures, any arity. Cai–Lu Theorem 2.5 (necessary) + Theorem 4.1 (sufficient, polynomial-time SRP).
• Non-symmetric matchgate signatures, arity ≤ 4, both parity branches, with the full Grassmann–Plücker matchgate identities.
• Galluccio–Loebl Holant evaluator for genus-$g$ matchgate networks (signed Pfaffian sum over $2^{2g}$ spin structures).
• Hardness-candidate screening across $\overline{\mathbf{Q}}$ + small finite fields.
• Automatic Kasteleyn-orientation construction from a planar embedding (rotation system) — kasteleyn_orient().

Quantum simulation (v0.1.2–4)

• FreeFermionCircuit — polynomial-time matchgate quantum-circuit simulator via covariance matrices. Verified against state-vector simulation; exponential speedup begins at $n \sim 10$ qubits.
• Non-adjacent matchgate gates, Pauli-string observables (X / Y / Z mixed), O(n³) Pfaffian via Parlett–Reid skew-LDLT.

Structural-fingerprint coordinates (v0.1.5)

Four coordinates that quantify how-far-from-matchgate any Holant signature is:

• Matchgate rank — matchgate_rank(sig). Hankel-rank-based; $O(n^3)$.
• Sum-of-Pfaffians evaluator — holant_sum_of_pfaffians, holant_sum_of_genus_g. Multilinear in per-vertex signatures.
• Field-extension distance — field_extension_distance(sigs). Promotes Cai–Lu's mod-$p$ phenomenon from solver parameter to output coordinate.
• Sub-signature coverage — signature_coverage, configuration_coverage. Quantifies "matchgate almost everywhere with structured exceptions."

Scheduling adapter + SWF parser (v0.1.6–8)

• SchedulingInstance + compile_to_holant — turn (jobs, machines, capacities) into Holant configurations.
• instance_coordinates — lift the four coordinates to instance level.
• SWF parser — parse_swf handles Parallel Workloads Archive .swf / .swf.gz files transparently.
• Empirical scan tooling — examples/09-swf-parser/scan_archive.py runs systematic (window × partition) sweeps on real archives. Verified on KTH-SP2 (28k jobs) and HPC2N (203k jobs).

Time-slot encoding (v0.1.9)

• compile_to_holant_time_slot — refinement encoding for capacity-bounded scheduling. Collapses matchgate rank from $\lceil c/2 \rceil + 1$ to 1, at the cost of $N \cdot M \cdot C$ variables instead of $N \cdot M$.
• Empirically demonstrated 28-orders-of-magnitude reduction in evaluation cost on the HPC2N P=60 cell.

Not yet shipped (the v0.2+ roadmap)

• Non-symmetric arity ≥ 5.
• Multi-chart coverage of the basis manifold $\mathcal{M}$ (currently a single open chart $u \ne v$).
• Holant$^*$ / Holant$^c$ variants (auxiliary signatures available).
• Translation layers from SAT / CSP / MILP / SLURM / AMPL / MiniZinc.
• Tropical Holant — counting → optimisation via $(\min, +)$ semiring. Promotes the framework from exact-count to exact-optimise on bounded-coordinate problems.
• Precedence-DAG and exclusion-pair compilation in the scheduling adapter.

Why is this useful?

Where Holant-tractable structure shows up in practice:

• Counting #SAT instances with planar matchgate structure — preprocessing layer that detects when a problem admits Valiant's holographic-algorithm route.
• Classical simulation of matchgate quantum circuits — Valiant 2002; classical simulability of free-fermion quantum dynamics.
• Statistical mechanics on planar / bounded-genus lattices — dimer counting, Ising and Potts models, free-fermion lattice models.
• Counting perfect matchings on planar and bounded-genus graphs — the FKT theorem and its Galluccio–Loebl extension are the canonical algorithms.
• Designing tractable counting CSP variants — the framework lets you check, ahead of time, whether your designed problem class lies in the polynomial-time matchgate corner.

See docs/holant-tools-applications.md for the full discussion of where matchgate tractability genuinely applies, where it could apply with further development, and where it honestly doesn't.

What v0.1.9 unlocks: a class of problems that was previously uncomputable

The empirical claim: under the v0.1.9 time-slot encoding, real HPC scheduling instances move from evaluation cost $\sim 10^{40}$ operations (no computer in the next century can do this) to $\sim 10^{13}$ operations (minutes on a workstation). A 28-orders-of-magnitude reduction in evaluation cost — verified on the HPC2N archive from the Parallel Workloads Archive.

This is exact counting, not optimisation. So the class of currently-uncomputable problems unlocked is #P-hard counting / verification / reliability / partition-function problems with bounded-coordinate structure under some encoding. Eight concrete application domains:

1. Network reliability of critical infrastructure under correlated failures (power grid, telecom, supply chain). Where "we sampled 10⁶ failure scenarios" is not a substitute for "the exact failure probability is X" — safety-critical contexts demand exact answers. Bounded-treewidth + bounded-capacity grids (typical of real infrastructure) now admit polynomial-time exact reliability calculation.

2. Probabilistic logic programming with constraint structure (ProbLog, PRISM, ProbCog). Currently use weighted #SAT, exponential. Bounded-coordinate sub-classes — where the constraint hypergraph has bounded structure — become polynomial. Exact Bayesian inference in larger graphical models than current methods reach.

3. Industrial schedule counting / shift verification (hospital rostering, transit dispatch, factory line-staffing). "How many feasible rosters? How many satisfy fairness X? How many are robust to one absentee?" Current: CP-SAT model counting times out past ~50 employees; sampling gives error bars only. New: exact counting in polynomial time for bounded-coordinate rostering instances.

4. Exact partition functions of statistical mechanics models on real lattices (Ising, Potts, q-state on planar / bounded-genus / bounded-treewidth lattices). Currently polynomial for planar Ising (FKT) only; bounded-genus + sum-of-Pfaffians + time-slot refinements push this to genuinely larger systems.

5. Quantum supremacy verification. "Did our quantum processor really produce the claimed distribution?" Currently: 53-qubit Sycamore-era verification took weeks on supercomputers; 70+ qubits "uncomputable." Matchgate / free-fermion-decomposable circuits + rank-bounded extensions become tractable for larger N. Already implemented in our FreeFermionCircuit from v0.1.2-alpha.

6. Formal-methods exact model counting. "Exactly how many states of this protocol satisfy the invariant?" Currently: SAT-based bounded model checking; exact counting is exponential in the state-space encoding. Protocols with bounded constraint structure become exact-countable.

7. Computational biology exact sequence/tree counting. Phylogenetic trees compatible with character data, under structural constraints. Currently MCMC; exact intractable past ~30 taxa. Bounded-coordinate cases (treewidth-bounded character matrices) become polynomial-time exact.

8. Reliability / risk in finance / insurance. Joint default probabilities under correlated structures. Currently copula models with Monte Carlo; exact intractable. When correlation structure has bounded matchgate-rank, exact joint probabilities in polynomial time.

The honest precondition

Bounded-coordinate structure is the requirement — and not every #P-hard problem has it. The empirical pattern from the SWF / KTH-SP2 / HPC2N scans:

• Encoding 1 (naive): rank explodes with problem size → no benefit.
• Encoding 2 (refined, like time-slot): rank stays at 1 → 28-orders-of-magnitude benefit.

The diagnostic layer's job is to find Encoding 2 for a given problem. When it exists, the benefit is the kind of number we just observed empirically.

One-line summary

The class unlocked: #P-hard problems with bounded-rank structure under some encoding — particularly counting / verification / reliability / partition-function problems on bounded-treewidth, bounded-genus, or bounded-capacity-per-resource constraint structures. The framework's job is identifying the right encoding; once found, exact-polynomial replaces exact-exponential or polynomial-approximate.

For the empirical demonstration on real Parallel Workloads Archive traces, see examples/09-swf-parser/. For the structural rationale, see docs/holant-tools-applications.md.

Math

docs/holant-tools-theory.md contains the theory: matchgate signatures, the Cai–Lu basis manifold $\mathcal{M} = \mathrm{GL}_2/!\sim$, the parity-pullback construction in a chart of $\mathcal{M}$, the Grassmann–Plücker matchgate identities for arity 4 (both parity branches, the latter via augmented-Pfaffian), and the Galluccio–Loebl Holant formula for genus-$g$ networks.

Tests

git clone https://github.com/pcoz/holant-tools.git
cd holant-tools
pip install -e .
python tests/test_holant_tools.py

101 tests across all subsystems (signatures, realizability, intersection, SRP solver, Pfaffian + Galluccio–Loebl Holant evaluator, non-symmetric arity-4 identities, hardness screening, Kasteleyn orientation, free-fermion simulator, structural-fingerprint coordinates, scheduling adapter, SWF parser, time-slot encoding).

License

LICENSE — modeled on the MIT License with an explicit attribution clause. Use is free; attribution to Edward Chalk (sapientronic.ai) is required for publications, presentations, derivative works, and products that build on this software.

References

• [CL11] J.-Y. Cai, P. Lu. Holographic Algorithms: From Art to Science. J. Comput. Syst. Sci. 77 (1) (2011) 41–61.
• [Val08] L. G. Valiant. Holographic Algorithms. SIAM J. Comput. 37 (5) (2008) 1565–1594.
• [GL99] A. Galluccio, M. Loebl. On the theory of Pfaffian orientations. J. Algebraic Combin. 9 (1999).
• [Tes00] G. Tesler. Matchings in graphs on non-orientable surfaces. J. Combin. Theory B 78 (2000).
• [Nor08] S. Norine. Matching structure and Pfaffian orientations of graphs. PhD thesis, Georgia Tech, 2005.