holant-tools 0.2.0a6

Decision procedures for matchgate-Holant tractability: polynomial-time SRP solver, Galluccio-Loebl Holant evaluator, hardness-candidate screening, and a tropical-Holant kernel with polynomial-time optimisation (Hungarian for bipartite, Edmonds blossom for general).

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. Optional: pip install 'holant-tools[networkx]' enables polynomial-time non-bipartite tropical Pfaffian via Edmonds' blossom (v0.2.0a4); without NetworkX, the non-bipartite case falls back to enumeration.

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 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 Q, or a specific finite field F_p?
• Is this a candidate for #P-hardness? (Screening: if no realising basis exists across Q-bar + 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, tropical optimisation.

Scope (v0.2.0a6 — 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 Q-bar + 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 ~ 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³).
• 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 ⌈c/2⌉ + 1 to 1, at the cost of N · M · C variables instead of N · M.
• Empirically demonstrated 28-orders-of-magnitude reduction in evaluation cost on the HPC2N P=60 cell.

Precedence + exclusion compilation (v0.1.10)

• Per precedence edge (before, after): arity-2 NAND on every (x[before, s_a], x[after, s_b]) pair with s_b < s_a (time-slot encoding only). All NANDs are matchgate rank 1.
• Per exclusion pair (A, B): arity-2 NAND per machine (bipartite encoding) or per same-machine slot pair (time-slot encoding).
• The full set of standard HPC scheduling primitives — assignment, capacity, precedence, exclusion — is now compilable. Real PWA traces with preceding_job_number dependencies can be compiled in full.

Tropical Holant kernel + end-to-end scheduling optimisation (v0.2.0a1, a3, a4, a5, a6 — alpha)

The (δ) direction from the admissibility-geometry roadmap: optimisation as a semiring choice over the admissible set, not a category-extension of the framework. The same Holant network that counts admissible configurations under the standard (+, ×) semiring computes the cheapest admissible configuration under the tropical (min, +) semiring.

• holant_tools.semiring (v0.2.0a1) — Semiring dataclass + StandardSemiring + TropicalMinPlusSemiring.
• pfaffian(M, semiring=...) (v0.2.0a1) — polymorphic dispatch. The default StandardSemiring is the v0.1.x Parlett-Reid path (every existing call site unaffected). The TropicalMinPlusSemiring path computes min-weight perfect matching: the signed Pfaffian sum collapses (no additive inverse → no signs) to the unsigned tropical permanent.
• holant_tools.tropical (v0.2.0a3 + v0.2.0a4) — hungarian_min_cost (Hungarian / Jonker-Volgenant, O(n³), no external dependency), min_weight_perfect_matching (Edmonds via NetworkX, O(n³) for non-bipartite — optional install: pip install holant-tools[networkx]), plus the bipartite-detection helpers.
• Three-tier dispatch in pfaffian(M, semiring=TropicalMinPlusSemiring) (v0.2.0a4) — auto-detects (1) bipartite K_{n,n} → Hungarian, (2) non-bipartite + NetworkX → Edmonds, (3) non-bipartite no NetworkX → v0.2.0a1 enumeration fallback. All transparent to the caller.
• Worked examples — examples/10-tropical-optimisation/: hpc_assignment_min_makespan.py (v0.2.0a1, n=5) and hpc_assignment_polynomial.py (v0.2.0a3, n=5..30 with timing comparison).
• Polymorphic multilinear evaluator (v0.2.0a5): holant_sum_of_pfaffians(terms, semiring=...), holant_genus_g(matrices, genus, semiring=...), holant_planar(M, semiring=...) are all polymorphic over semiring. The tropical paths give polynomial-time argmin for bounded-matchgate-rank Holant networks — the v0.1.5 four-coordinate cost factorisation now applies to optimisation, not just counting.
• Kernel status (v0.2.0a5): the (δ) kernel arc is structurally complete. The polynomial-time tropical Pfaffian is available for every input (bipartite Hungarian, non-bipartite Edmonds, enumeration fallback) and the multilinear evaluator is polymorphic. A Holant network with bounded coordinates under (min, +) is exact polynomial-time evaluable for both counting and optimisation through the same API.
• End-to-end scheduling pipeline (v0.2.0a6): holant_tools.scheduling.min_cost_schedule(instance, cost_fn) takes a SchedulingInstance + cost function and returns the exact polynomial-time minimum-cost schedule. Built on compile_to_holant_time_slot_weighted (weighted variant of the v0.1.9 time-slot encoding) + Hungarian dispatch. Scope: assignment + capacity (precedence / exclusion in weighted form are v0.2.0a7+). Worked example: examples/10-tropical-optimisation/end_to_end_hpc_optimisation.py runs the full parse_swf → instance_from_window → min_cost_schedule pipeline on the bundled SWF in ~10 ms.
• Domain modules for non-scheduling areas not yet shipped. Network flow / rostering / MDM domain glue analogous to min_cost_schedule is the v0.2.x continuation. For now, callers can use the scheduling pipeline (or supply cost matrices directly to the kernel).

Not yet shipped (the v0.2+ roadmap)

• Non-symmetric arity ≥ 5.
• Multi-chart coverage of the basis manifold M (currently a single open chart u ≠ v).
• Holant* / Holant^c variants (auxiliary signatures available).
• Translation layers from SAT / CSP / MILP / SLURM / AMPL / MiniZinc.
• Tropical-Plücker / tropical-Grassmannian specialisation for planar graphs. v0.2.0a4 handles non-bipartite via Edmonds at O(n³); a planarity-aware algorithm could potentially achieve O(n^{3/2}) by exploiting planarity directly. Theoretical refinement.
• Tropical matchgate_rank — the Hankel-rank Tropical analogue (research-grade); deferred. The polymorphic sum_of_pfaffians is shipped in v0.2.0a5.
• Weighted compilation with precedence / exclusion — v0.2.0a6 covers assignment + capacity; combinatorial forbidden-pair constraints in weighted form are pending.
• Domain modules — holant_tools.network_flow, holant_tools.rostering, holant_tools.mdm — end-to-end glue from non-scheduling domain-native formats to the tropical Pfaffian primitive (scheduling is shipped in v0.2.0a6 via min_cost_schedule).
• Diagnostic-layer CP-SAT / Gurobi integration — encoding-selection presolve wrapped as a preflight pass for the standard solvers.

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 this unlocks: a class of problems that was previously uncomputable

The empirical claim: under the v0.1.9 time-slot encoding + v0.1.10 precedence/exclusion compilation, real HPC scheduling instances move from evaluation cost ~10^40 operations (no computer in the next century can do this) to ~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 M = GL_2/~, the parity-pullback construction in a chart of 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

143 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, precedence + exclusion compilation, tropical Holant kernel + polynomial-time Hungarian + Edmonds blossom + polymorphic multilinear evaluator + weighted scheduling compiler + end-to-end min-cost schedule).

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.