holant-tools 0.4.0a12

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.

Working programmer in a hurry? Skip to docs/programmers-guide.md — it answers "when do I reach for this library, what do I call, and how do I tell when it can't help me" with a cheat sheet at the end.

Citing this work / mathematician audience? docs/insights-and-techniques.md catalogues the mathematical insights and techniques original to this library: parity-pullback SRP construction, two-chart cover of M, general-arity Plücker enumeration, the closed-form augmented-Pfaffian weight-1 identity for arity ≥ 5, the four structural-fingerprint coordinates, the tropical-rank concavity theorem, the parity-split rank-≤-2 theorem for symmetric basis-aware matchgate rank, the Holant^c chart-aware infeasibility finding, the matchgate-rank analysis of the classical time-slot encoding, and four new genus-g Kasteleyn techniques (linear-system Poincaré-dual cocycle, bilinearity-vs-direction obstruction, direction-aware intersection on walks, and spin-structure base alignment via shift discovery). Each entry includes definitions, derivation sketches, and explicit citations.

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.4.0a12 — current alpha; v0.3.0 is current stable)

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 with hand-coded Grassmann–Plücker identities (both parity branches). v0.3.0a0 + v0.3.0a2 extend to arity ≥ 5 via the general Plücker enumeration (matchgate_identities_arity_n_even/_odd) plus the augmented-Pfaffian weight-1 identity at arity ≥ 5 odd parity (matchgate_identity_augmented_weight_1_arity_n_odd); reproduces the v0.1 hand-coded arity-4 identities exactly as special cases.
• 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 rotation system, all genera. kasteleyn_orient(...) for planar inputs; kasteleyn_orient_genus_g(...) returns the $2^{2g}$ spin-structure-twisted matrices for genus $\geq 1$ ready to pass to holant_genus_g. Verified end-to-end against brute-force PM counts on planar C_4 (PM=2), 4×4 torus (genus 1, PM=272), and Petersen on Σ_2 (genus 2, PM=6). Shipped in v0.4.0a3 — see docs/insights-and-techniques.md §§2.5–2.8.

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, a7, a8, a9 — 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.0a8+). 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.

• Tropical matchgate_rank (v0.2.0a7): holant_tools.tropical_matchgate_rank(values) computes the min number of tropical-line components (L(w) = alpha + beta * w) whose tropical sum (= min) equals the input sequence. For concave finite sequences this equals the number of piecewise-linear segments; for non-concave finite sequences the rank is genuinely +inf (cannot be expressed as a min of lines). Completes the four-coordinate structural-fingerprint apparatus for the weighted-signature case (alongside the polymorphic sum_of_pfaffians and the unchanged signature_coverage).

• One-call diagnostic (v0.2.0a8): holant_tools.scheduling.tropical_instance_coordinates(instance, cost_fn) bundles the polymorphic four-coordinate apparatus for a weighted instance: underlying 0/1 admissibility coordinates + cost-matrix sparsity + per-row tropical matchgate rank + tractability flags (admissibility_rank_1, all_cost_rows_concave, polynomial_time_optimisation). The "is this instance structurally well-suited for tropical optimisation?" single-call answer.

• Per-edge restrictions for min_cost_schedule (v0.2.0a9): optional kwargs allowed_machines={job → set of machines}, time_windows={job → (earliest_slot, latest_slot)}, forbidden_edges=set of (job, machine, slot). All compile to math.inf in the cost matrix; Hungarian handles them natively. Polynomial-time exact. General precedence DAGs and same-machine-exclusion pairs are explicitly deferred (they're combinatorial-on-pairs, not per-edge; the counting path in v0.1.10 handles them via NAND signatures but the analogous optimisation path is research-grade).

• Network-flow domain module (v0.2.0a10): holant_tools.network_flow — MinCostFlowInstance, min_cost_flow, max_flow_value provide source/sink/edge vocabulary for bipartite supply-demand transportation and assignment problems. Same Hungarian-backed kernel as min_cost_schedule; different domain-natural API. Worked example: 3-factory × 4-warehouse transportation in examples/11-network-flow/. v0.2.0a12 bug fix: per-edge capacities are now respected (auto-dispatches to NetworkX when binding); FlowEdge.capacity defaults to None (unlimited) rather than 1.

• Rostering domain module (v0.2.0a11): holant_tools.rostering — Employee (max_shifts, certifications, unavailable), Shift (headcount, required_certifications), RosteringInstance, min_cost_roster. Workforce-rostering vocabulary on the same kernel. Worked example: 5-nurse 6-shift weekly roster with skill mix in examples/12-rostering/.

• MDM domain module (v0.2.0a12): holant_tools.mdm — Record, EntityCandidate (with capacity), MDMInstance, min_cost_dedup. Entity resolution / dedup with regulatory cardinality caps. Worked example: 8-customer 4-entity bank dedup in examples/13-mdm/.

Non-symmetric arity ≥ 5, Holant^c, multi-chart M, planar Pfaffian API, diagnostic layer (v0.3.0)

The v0.3 line extends the realisability theory, formalises a second Holant variant, and ships a structural-diagnostic LAYER above industrial schedulers.

• General-arity Plücker matchgate identities for non-symmetric signatures (v0.3.0a0): holant_tools.non_symmetric.matchgate_identities_arity_n_even/_odd ship the full Grassmann–Plücker enumeration for arity ≥ 5 (the v0.1 hand-coded arity-4 identities now extend uniformly). realizability_subvariety_non_symmetric automatically picks up the new identities; the v0.1 arity-4 cases are reproduced exactly as special cases. v0.3.0a2 followup: added the augmented-Pfaffian weight-1 identity at arity ≥ 5 odd parity (the most-important identity from the augmented-Kasteleyn framework). Strictly tightens the realisability check over standard Plücker alone; higher-order augmented relations remain research-grade.
• Multi-chart M coverage (v0.3.0a1): srp_solve_multi_chart(signatures, modulus=None) tries the primary chart β = [[1,u],[1,v]] first and falls back to the secondary chart β = [[u,1],[v,1]]; the two charts together cover all of M except a measure-zero edge case. Closes the v0.2 known limitation about chart-1-only.
• Holant^c variant (v0.3.0a3): srp_solve_holant_c(signatures, modulus=None, chart=...) augments F with the pinning unaries {δ_0 = (1, 0), δ_1 = (0, 1)} via direct chart-aware subvariety computation and returns the SRP feasibility under the Holant^c semantics. Finding: in the current 2-chart system, Holant^c is provably infeasible for any F (δ_0 fails on chart 1 with τ ≡ (1, 1); δ_1 fails symmetrically on chart 2). This is the correct Cai-Lu-Xia dichotomy outcome at the matchgate-realisability level. The API is in place for future extension (additional charts; per-signature chart selection). Holant* is deferred — the abstract concept needs identity-basis matchgate realisability, a different framework.
• Planar tropical Pfaffian API (v0.3.0a4): planar_tropical_pfaffian(weights, rotation_system=None) ships the API surface so downstream code can adopt it today. Honest scope: currently dispatches to the same Edmonds-via-NetworkX O(n³) path that min_weight_perfect_matching uses. The rotation_system argument is recorded but not algorithmically exploited yet. The "planar" adjective is currently aspirational; the Klein 2007 / Borradaile-Klein O(n^{3/2}) algorithm is multi-month future work. The algorithm_used and complexity_class result fields let downstream code detect which path was taken.
• Encoding-selection diagnostic + CP-SAT integration (v0.3.0a5): holant_tools.diagnostic.diagnose_constraints(constraints) takes an abstract ConstraintSpec list (six recognised kinds: AT_MOST_K, EXACT_K, AT_LEAST_K, EXACT_1, SUM_EQ, ALL_DIFFERENT) and returns per-constraint matchgate-rank + monolithic/time-slot/hybrid encoding recommendation. The headline practical capability: tells you which encoding will be rank-1 (polynomial-time tractable) before the underlying solver burns hours. holant_tools.diagnostic_cpsat.diagnose_cpsat_model(model) is the optional OR-Tools wrapper (gracefully degrades if ortools not installed); recognises 7 common CP-SAT call patterns (AddExactlyOne, AddAtMostOne, AddBoolOr, AddAllDifferent, AddLessOrEqual, AddGreaterOrEqual, AddEquality).
• Pattern-rewriting transformer (v0.3.0a6): rewrite_to_time_slot(spec) and rewrite_constraints(constraints) produce structural blueprints for the time-slot rewrite of each rank-explosive constraint. AT_MOST_K(n, k) ↦ K per-slot AT_MOST_1 + n per-variable AT_MOST_1 + n linking + n·K auxiliary booleans; analogous rewrites for EXACT_K, AT_LEAST_K, ALL_DIFFERENT. All rewritten constraints are rank-1 by construction.
• CP-SAT model rewriter rewrite_cpsat_model (v0.4.0a0): materialises the v0.3.0a6 blueprint into a runnable CP-SAT model. The headline programmatic signal is result.helped: bool — True when the rewriter applied at least one rewrite, False when the library cannot improve this particular model (with help_reason_code ∈ {rewrote, empty_model, all_already_rank_1, no_recognised_patterns, rewrites_disabled} for branching). The "we can't help here" signal is wired in as a first-class field so calling code can dispatch cleanly. Worked example: examples/14-cpsat-rewrite/.
• Solution-equivalence verifier verify_cpsat_rewrite_equivalence (v0.4.0a1): sample feasible solutions on the original and rewritten CP-SAT models, marginalise auxiliaries, and verify that the rewrite preserves the feasible set (and objective values when present) on the original variables. Surfaces verdict.equivalent: bool plus a structured reason code in {equivalent, trivial, missing_solutions, spurious_solutions, objective_mismatch, enumeration_incomplete}. The verifier flagged a real AT_LEAST_K rewriter bug on its first run (v0.4.0a2 ships the fix).
• AT_LEAST_K rewriter fix (v0.4.0a2): the v0.4.0a0 _apply_at_least_k_rewrite used AddMaxEquality(x_i, m_{i,*}) (bi-directional linking, enforces sum == K), where the correct semantics is the one-way implication m_{i,j} -> x_i. v0.4.0a2 ships the fix; the verifier confirms equivalence on the canonical 11-solution test case.
• Full genus-g Kasteleyn / Galluccio–Loebl pipeline (v0.4.0a3): the genus-1 and genus-2 branches of kasteleyn_orient_genus_g are now implemented end-to-end. New module holant_tools.genus — genus_from_rotation_system, homology_generators, symplectic_basis (with direction-aware walk-intersection fallback for $g \geq 2$), poincare_dual_cocycle_linear_system, poincare_dual_cocycle_general, direction_aware_intersection_walks. The pipeline rotation_system → genus → symplectic basis → PD cocycles → base orientation + spin-structure twists → holant_genus_g reproduces the perfect-matching count exactly on the 4×4 torus (272) and the Petersen graph on Σ_2 (6). Four novel techniques documented at docs/insights-and-techniques.md §§2.5–2.8.
• Basis-aware matchgate rank (v0.4.0a4): the parity-split rank-≤-2 theorem for symmetric signatures is now in the public package. basis_aware_matchgate_rank (single signature) and configuration_basis_aware_matchgate_rank (configuration level) plus hand-buildable corruption-detection verifiers. For symmetric inputs, the basis-aware rank is provably in {0, 1, 2}; rank=2 constructions are explicit via the parity-split. Closes the §3.5 doc loop (was previously pointing at code in the private research repo). See docs/insights-and-techniques.md §3.5.
• Dart-chain intersection — degree-3-vertex blindspot fixed (v0.4.0a5): the v0.4.0a3 walks-formula intersection had a hidden blindspot at degree-3 vertices (its "Rule 2: 4-dart alternation" requires 4 distinct rotation positions). Stress-testing on 200 random rotation systems across K_5, K_{3,3}, K_7, K_8, Heawood found 167/200 (83.5%) degenerate cases. v0.4.0a5 ships dart_chain_intersection, a passage-arc cyclic-interleaving formula that handles shared darts correctly and works at all vertex degrees. Same stress test now gives 200/200 non-degenerate. symplectic_basis (g≥2) uses the dart-chain primitive internally; the genus-g Kasteleyn pipeline is now correct by construction on arbitrary rotation systems. See docs/insights-and-techniques.md §2.7.
• ALL_DIFFERENT model-level rewrite (v0.4.0a6, extended in v0.4.0a9 to single-variable affine expressions): closes the last open item in the v0.4.0a0 rewriter. rewrite_cpsat_model materialises the per-(variable, value) channelling rewrite for AddAllDifferent on plain integer variables (v0.4.0a6) or single-variable affine expressions c_i * x_i + b_i (v0.4.0a9). Verified end-to-end via the v0.4.0a1 solution-equivalence verifier on uniform domains, non-uniform domains, ALL_DIFFERENT + objective, and affine expressions with mixed positive offsets and negative/scaled coefficients. Worked example: examples/16-all-different-timetable/. Multi-variable expressions inside AddAllDifferent (e.g., x + y) are detected and passed through unchanged.
• Third chart of 𝓜 = identity-basis chart (v0.4.0a7): the 2-chart cover (primary + secondary) misses exactly the single equivalence class of the identity basis — not a 1-dim stratum as one might first expect. v0.4.0a7 adds the identity chart as a third option in srp_solve_multi_chart and srp_solve_holant_c_multi_chart. Behavioral consequence: Holant^c with F = {EQ_2}, previously infeasible in primary + secondary (the §5.1 doc finding), is now feasible at identity (EQ_2, δ_0, δ_1 each individually identity-realisable on appropriate parity branches). F not identity-realisable (e.g., OR_3) remains infeasible — correctly so. See docs/insights-and-techniques.md §5.2.

The polymorphic four-coordinate apparatus — what lifts and what doesn't

The v0.1.5 structural-fingerprint apparatus has four coordinates over the standard (+, ×) semiring. v0.2.0a5 + v0.2.0a7 lift the apparatus to the tropical (min, +) semiring:

Coordinate	Standard (counting)	Tropical (optimisation)
Matchgate rank	matchgate_rank (v0.1.5) — Hankel-rank based, exact	tropical_matchgate_rank (v0.2.0a7) — concave-piecewise-linear case
Sum-of-Pfaffians	holant_sum_of_pfaffians (v0.1.5)	holant_sum_of_pfaffians(..., semiring=...) (v0.2.0a5)
Field-extension distance	field_extension_distance (v0.1.5)	no clean tropical analogue (see below)
Sub-signature coverage	signature_coverage (v0.1.5)	works as-is (0/1 indicator, semiring-independent)

Three of the four lift cleanly; the fourth (field-extension distance) has no natural tropical analogue because tropical (min, +) is a semiring, not a field — there is no field-extension structure to take a distance over. This was the genuine technical content of the v0.2.0a7 work: the lift completes for matchgate rank in the finite-weighted case but cannot complete for field-extension distance regardless of how the analogue is formulated.

Going inner-first, this is the deepest reachable position for the kernel arc. The kernel (Pfaffian) + multilinear evaluator (sum_of_pfaffians, genus_g) + tropical matchgate rank together constitute the complete polymorphic structural-fingerprint apparatus for tropical evaluation. Further inner work — general non-concave tropical rank, a tropical analogue of field-extension distance — is research-grade and not currently in scope.

• 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.4+ roadmap)

• Non-symmetric arity ≥ 5 — shipped in v0.3.0a0 + v0.3.0a2 via general Plücker enumeration plus the augmented-Pfaffian weight-1 identity. Remaining: higher-order augmented-Pfaffian relations (research-grade).
• Multi-chart coverage of the basis manifold M — shipped in v0.3.0a1 via srp_solve_multi_chart. Primary chart [[1,u],[1,v]] + secondary chart [[u,1],[v,1]] together cover all of M except a measure-zero edge case.
• Holant^c variant — shipped in v0.3.0a3 via srp_solve_holant_c. In the current 2-chart system Holant^c is provably infeasible for any F (a correct Cai-Lu-Xia finding); future chart-system extension will give positive feasibility cases. Holant* remains deferred — its abstract concept requires identity-basis matchgate realisability, a different framework.
• Translation layers from SAT / CSP / MILP / SLURM / AMPL / MiniZinc / DIMACS. Would open the diagnostic layer to a broader audience (SAT community / OR community). Each ~1 session of mechanical extraction work.
• Tropical-Plücker / tropical-Grassmannian specialisation for planar graphs — API shipped in v0.3.0a4 as planar_tropical_pfaffian (signpost only). Currently dispatches to Edmonds O(n³); the actual Klein 2007 / Borradaile-Klein O(n^{3/2}) algorithm is multi-month future engineering work. The API is stable so downstream code can adopt it today.
• Tropical matchgate_rank for non-concave / +inf-bearing sequences — v0.2.0a7 ships the concave-piecewise-linear case (the natural tropical-Form-1 representable family); the general case is a research-grade open problem.
• Weighted compilation with precedence / exclusion — v0.2.0a6 covers assignment + capacity; combinatorial forbidden-pair constraints in weighted form are pending.
• Additional domain modules — beyond the four currently shipped (scheduling v0.2.0a6, network_flow v0.2.0a10, rostering v0.2.0a11, MDM v0.2.0a12), other application domains (combinatorial auctions, supply-chain routing, sensor allocation, etc.) can be added as needed — same kernel, different vocabulary.
• Diagnostic-layer CP-SAT / Gurobi integration — CP-SAT diagnostic shipped in v0.3.0a5, abstract rewriter shipped in v0.3.0a6, rewrite_cpsat_model materialises the rewrite into a runnable CP-SAT model in v0.4.0a0 with an explicit helped: bool signal, solution-equivalence verifier shipped in v0.4.0a1 (verify_cpsat_rewrite_equivalence), AT_LEAST_K rewriter bug discovered by the verifier and fixed in v0.4.0a2. Remaining: Gurobi / Z3 / MiniZinc / DIMACS wrappers; ALL_DIFFERENT model-level rewrite.
• Automatic Kasteleyn-orientation construction from rotation-system + surface-embedding input — shipped in v0.4.0a3 as kasteleyn_orient_genus_g(vertices, edges, rotation, genus). Full pipeline verified end-to-end against brute-force PM counts.

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.

New to the library? docs/programmers-guide.md is a working-programmer's tour: when to reach for the library, what to call for what kinds of problems, and how to tell when it can't help. Includes a cheat sheet.

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

280 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 + tropical matchgate rank + polymorphic instance coordinates + per-edge restrictions + network_flow + rostering + MDM domain modules + CP-SAT rewriter + solution-equivalence verifier + AT_LEAST_K fix + full genus-g Kasteleyn pipeline + basis-aware matchgate rank + dart-chain intersection + ALL_DIFFERENT CP-SAT rewrite (plain + affine) + identity-basis chart + augmented Plücker vacuousness correction).

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.