holant-tools 0.4.0a18

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

A Python toolkit that finds hidden structure in constraint problems — and uses it to give you exact, polynomial-time answers where general-purpose solvers struggle or run out of time.

In plain English, here are the concrete things you can do with it (no maths degree required):

• Make your CP-SAT / OR-Tools solves faster. Hand the library your cp_model.CpModel, get back either (a) a rewritten model that's structurally cheaper to solve, or (b) an explicit "we can't help here" signal so you know to just run the original. On real workloads the rewrite has reduced evaluation cost by 28 orders of magnitude (HPC2N trace, P=60 capacity-4 cell).
• Count solutions exactly, not just find one. "How many feasible schedules satisfy the constraints?" "How many rosters give every nurse at least one weekend off?" CP-SAT and Gurobi don't natively answer counting questions; this library does — exactly, in polynomial time, for problems whose structure permits it.
• Solve scheduling, rostering, network-flow and entity-dedup problems exactly and quickly. One-line APIs (min_cost_schedule, min_cost_flow, min_cost_roster, min_cost_dedup) that return exact optima in polynomial time when the structure fits — no MIP timeout, no heuristic approximation.
• Verify "no better solution exists" claims. "The optimiser picked schedule X — is any other schedule within 5% of optimal?" The counting layer answers this without enumeration. Useful in auditing, regulatory, and safety-critical contexts.
• Count perfect matchings on planar and bounded-genus graphs at scale. A 24×24 planar grid (576 vertices) goes from "infeasible with the textbook algorithm" to sub-second exact-integer output. Useful for statistical-mechanics partition functions, dimer / Ising / Potts model counts, and structured combinatorial enumeration.
• Simulate matchgate quantum circuits classically. 20-qubit Trotterised transverse-field Ising chains run in milliseconds via free-fermion (Bogoliubov) techniques — useful for benchmarking, certifying classical simulability, and designing matchgate-restricted variational ansätze.
• Decide if your CP / SAT model has a holographic shortcut. A polynomial-time check that says "yes, your problem admits an exact polynomial-time route via Cai–Lu's Simultaneous Realizability Problem solver" or "no, no matchgate shortcut on the searched charts/fields." Useful as a free pre-flight before reaching for an expensive solver.
• Bucket fleets of solver instances by structural complexity. Cloud meta-schedulers, batch optimisation services: allocate CPU budget proportional to a structural complexity number computed in milliseconds, rather than learning it from solve times.
• Screen counting CSP families for hardness candidacy. Designing a new counting problem? Run it through holant hardness to see whether the polynomial-time matchgate route is available — useful at the research-design stage.

Honest caveat. The library is a structural diagnostic layer that sits above industrial solvers (CP-SAT, Gurobi, SLURM), not a replacement for them. Most #P-hard problems do NOT have the kind of bounded-rank structure this library exploits — but for the ones that do, "exponential becomes polynomial" and "approximate becomes exact." Where the structure isn't there, the library is explicit: every API returns a programmatic signal you can branch on rather than a vague answer.

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. A worked-examples appendix cross-references every directory in examples/.

---

Install

pip install holant-tools

Requires Python ≥ 3.10 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. Some routines additionally use scipy / numpy / ortools when available; if you don't call those routines you don't need the deps.

A first taste — make a CP-SAT model solve faster

The most common entry point. Pass your existing cp_model.CpModel through the rewriter and dispatch on the explicit helped: bool signal:

from ortools.sat.python import cp_model
from holant_tools import rewrite_cpsat_model

model = cp_model.CpModel()
# ... build your model as usual ...

result = rewrite_cpsat_model(model)
solver = cp_model.CpSolver()

if result.helped:
    print(f"Rewriter found a faster encoding: {result.help_reason_text}")
    solver.Solve(result.rewritten_model)
else:
    print(f"No rewrite available ({result.help_reason_text}); solving original.")
    solver.Solve(model)

There is no ambiguity about whether the library actually helped on a given input — the helped field is a first-class signal you can branch on.

For domain-natural APIs (scheduling / network flow / rostering / dedup), see docs/programmers-guide.md §3.

When should a developer reach for this library?

A short trigger list. If any of these describe your situation, the library has a direct API for it. Each row points to the call you make — and to the longer treatment in docs/programmers-guide.md for the full workflow.

Your situation	What to call	Where to read more
"My CP-SAT / OR-Tools model takes hours to solve and I suspect an encoding issue"	rewrite_cpsat_model(model) then branch on result.helped	programmers-guide §3.1, examples/14-cpsat-rewrite/
"I need to count valid solutions, not just find one — 'how many feasible rosters exist?'"	srp_solve_multi_chart + Pfaffian-based evaluation	§3.2, examples/01-counting-csps/
"I'm building a scheduler / roster / flow / dedup solver and the MIP times out at scale"	min_cost_schedule, min_cost_flow, min_cost_roster, min_cost_dedup	§3.3, examples 10–13
"I want to verify 'no schedule is within 5% of optimal' without enumerating alternatives"	holant_sum_of_pfaffians over the cost-capped configuration set	§2.7
"I need exact partition functions / dimer counts / matching counts on a planar or bounded-genus lattice"	kasteleyn_orient[_genus_g] + holant_planar / holant_genus_g (auto-fast for size ≥ 16)	§3.7, examples/15-toroidal-dimer-counting/, examples/19-transparent-fast-holant/
"I have two candidate encodings for my CSP and want to know which one will solve faster"	diagnose_constraints([ConstraintSpec(...), ...]) before implementing either	§3.5
"I'm running a fleet of solver instances and want to budget CPU proportional to expected difficulty"	tropical_instance_coordinates(instance, cost_fn) then bucket	§3.6, examples/09-swf-parser/
"I'm designing a new counting CSP / hardness candidate and need to know if it has a holographic shortcut"	holant hardness sigs.json --primes ...	examples/02-hardness-screening/
"I'm classically simulating matchgate quantum circuits or free-fermion dynamics"	FreeFermionCircuit(...) plus the Majorana-rotation helpers	§A.4, examples/04-matchgate-quantum-circuits/
"I need to classify a Boolean function's matchgate structure (rank, basis, Cai–Lu Form)"	basis_aware_matchgate_rank(sigma) + matchgate_form_decomposition(sigma)	§3.8
"My problem needs free pinning (δ_0 / δ_1) — i.e. Holant^c style #SAT or weighted model counting"	srp_solve_holant_c_multi_chart(F, modulus=...) (identity chart in v0.4.0a7+)	§3.9, examples/17-pinning-and-identity-chart/

If your situation isn't in this list and you're unsure whether the library fits: start with diagnose_cpsat_model(model) (if you have a CP-SAT model) or diagnose_constraints(specs) (if you don't). Both take milliseconds and either point you to the workflow or tell you the library can't help with this particular shape of problem. See docs/programmers-guide.md §§4–5 for the "when the library can't help" signals and how to dispatch on them.

---

What's in the library

Going one level deeper, the library is a set of building blocks each aimed at a particular kind of structured problem. Plain practitioner perspective; the deep math is later.

• CP-SAT preflight, rewriter and verifier. diagnose_cpsat_model reads your cp_model.CpModel and tells you which constraints are structurally rank-explosive; rewrite_cpsat_model produces a runnable rewritten model (with the explicit helped: bool signal); verify_cpsat_rewrite_equivalence confirms the rewrite preserves the feasible set. Recognises AT_MOST_K, EXACT_K, AT_LEAST_K, EXACT_1, SUM_EQ, and ALL_DIFFERENT (including single-variable affine expressions like slot[i] + offset[i]).

• Domain modules with one-line APIs. min_cost_schedule (jobs / machines / time-slots with capacity, certifications, time-windows), min_cost_flow (transportation / supply-demand), min_cost_roster (workforce rostering with certifications and unavailability), min_cost_dedup (entity resolution with cardinality caps). All four share the same polynomial-time kernel under domain-natural vocabulary.

• Exact counting / Holant evaluator. pfaffian, holant_planar, holant_genus_g, holant_sum_of_pfaffians give exact counts of solutions / configurations / partition functions for problems with matchgate structure on planar or bounded-genus graphs. The same kernel handles statistical-mechanics partition functions, perfect-matching counts, and structured #SAT preprocessing.

• Tropical (min, +) optimisation kernel. Counting and optimisation are the same machine in different arithmetic. pfaffian(M, semiring=TropicalMinPlusSemiring) returns the minimum-weight perfect matching; hungarian_min_cost and min_weight_perfect_matching (via Edmonds' blossom in NetworkX) are the polynomial-time tropical Pfaffians for bipartite and general graphs.

• Kasteleyn-orientation pipeline. kasteleyn_orient (planar) and kasteleyn_orient_genus_g (closed orientable surface of genus g) turn a graph plus rotation system into the matrix you Pfaffian over, automatically constructing the 2^(2g) spin-structure twists. Verified end-to-end against brute-force perfect-matching counts on the 4×4 torus (272 dimer tilings) and the Petersen graph on Σ₂ (6 matchings).

• Fast planar Pfaffian (Klein arc). fast_planar_pfaffian_sparse and exact_planar_pfaffian deliver a fast modular-arithmetic exact-integer Pfaffian via scipy sparse LU plus Chinese Remainder Theorem. holant_planar and holant_genus_g auto-route integer Kasteleyn matrices of size ≥ 16 through this path — same API, 7–19× faster, exact integer output. Transparent on upgrade.

• Free-fermion / matchgate quantum simulator. FreeFermionCircuit is a classical simulator for matchgate quantum circuits via covariance matrices: Pauli-string observables (X / Y / Z mixed), polynomial-time per gate, verified against state-vector simulation. Exponential speedup begins around n ~ 10 qubits.

• Structural fingerprint coordinates. Milliseconds-cheap diagnostics that quantify how tractable an instance is before you spend solver time on it. matchgate_rank (Hankel-based, exact for symmetric), basis_aware_matchgate_rank (parity-split rank ≤ 2 theorem), nonsymmetric_matchgate_rank (Hankel-tensor flattening lower bound), field_extension_distance, signature_coverage, tropical_instance_coordinates. Useful for fleet bucketing, encoding selection, and tractable-CSP design.

• SRP decision procedure. srp_solve / srp_solve_multi_chart / srp_solve_holant_c_multi_chart answer "does this set of matchgate signatures admit a holographic-algorithm route, and if so, on which basis?" Searches the primary and secondary charts of M, plus a third (identity) chart for Holant^c with pinning. Polynomial-time decision per Cai–Lu 2011 Theorem 4.1.

• CLI. holant signature (individual realisability), holant check (necessary-condition SRP), holant solve (full SRP with optional --modulus p), holant hardness (multi-prime hardness-candidate screen). Useful from shell scripts and CI pipelines.

Application domains (where this structure actually shows up)

The catalogue of domains where the matchgate-Holant structure naturally appears. Useful if you're trying to figure out whether your specific problem fits.

• 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 — 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.

Where the framework moves a previously-intractable problem into reach

The headline empirical result: under the v0.1.9 time-slot encoding + v0.1.10 precedence/exclusion compilation, real HPC scheduling instances move from evaluation cost ~10⁴⁰ operations (no computer in the next century can do this) to ~10¹³ operations (minutes on a workstation). A 28-orders-of-magnitude reduction — verified on the HPC2N archive from the Parallel Workloads Archive.

Today's v0.4 additions stack on top of that. The CP-SAT rewriter (v0.4.0a0) materialises the time-slot rewrite into a runnable model with an explicit helped: bool signal, so the structural diagnosis becomes a one-call drop-in for existing OR-Tools users. The Klein-arc fast Pfaffian (v0.4.0a13–a17) takes integer-Kasteleyn perfect-matching counts on planar and bounded-genus graphs of size ≥ 16 through a modular-arithmetic exact-integer path, automatically — a 24×24 planar grid (576 vertices, dimer count ≈ 10⁷⁰) now runs sub-second where it was minutes-to-impractical before. The identity chart (v0.4.0a7) makes Holant^c with free pinning actually feasible for the positive sub-family, which is the standard reduction shape for #SAT preprocessing and weighted model counting. The non-symmetric matchgate rank (v0.4.0a12) gives the first quantitative handle on matchgate quantum circuits whose gates carry non-symmetric arity-n signatures.

The class of previously-uncomputable problems that becomes reachable is #P-hard counting / verification / reliability / partition-function problems with bounded-coordinate structure under some encoding. Eight concrete 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. Holant^c with pinning (v0.4.0a7 identity chart) is the reduction shape for embedding "specific component failed" as a literal.

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. The identity chart again is the practical mechanism for the pinning step.

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: rewrite_cpsat_model (v0.4.0a0) takes the existing CP-SAT model, returns a structurally-cheaper rewrite with an explicit helped: bool signal; verify_cpsat_rewrite_equivalence (v0.4.0a1) confirms the rewrite preserves the feasible set. 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). Previously polynomial for planar Ising (FKT) but limited by sympy Pfaffian speed beyond ~10×10 lattices. The Klein arc (v0.4.0a13–a17) now makes 16×16, 20×20, 24×24 planar grids and genus-1 / genus-2 surfaces sub-second-feasible with exact integer output — same API, transparent on upgrade. See examples/15-toroidal-dimer-counting/ and examples/19-transparent-fast-holant/.

5. Quantum supremacy verification. "Did our quantum processor really produce the claimed distribution?" 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. The FreeFermionCircuit simulator (v0.1.2-alpha) covers the symmetric / Pauli-string case; nonsymmetric_matchgate_rank (v0.4.0a12) gives the lower-bound quantitative handle for circuits whose gates carry non-symmetric arity-n signatures.

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 — and rewrite_cpsat_model is again the practical bridge when the protocol is expressed in CP-SAT.

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. Trees-on-surfaces problems where the genus is bounded also benefit from the v0.4 genus-g pipeline.

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 basis-aware rank diagnostic (v0.4.0a4) plus the Form-1/2/3 decomposition (v0.4.0a11) are the structural-classification handles for "does my correlation structure fit?"

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 is #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.

---

The mathematical core (for the curious)

Under the hood, holant-tools implements decision procedures for matchgate-Holant tractability. Given a set of matchgate constraint functions, it decides in polynomial time whether they admit a polynomial-time holographic-algorithm route — and if so, returns the basis on which to construct it. 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.

Mathematician audience / citing this work? docs/insights-and-techniques.md catalogues the mathematical insights and techniques original to this library: parity-pullback SRP construction, two-chart cover of M plus a third (identity) chart for Holant^c, 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 matchgate-rank analysis of the classical time-slot encoding, the dart-chain intersection primitive that handles degree-3-vertex blindspots, and a Klein-style fast Pfaffian arc combining scipy sparse LU, modular Parlett–Reid, and Chinese Remainder Theorem reconstruction. Each entry includes definitions, derivation sketches, and explicit citations.

A worked example for the mathematically inclined: 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 the SRP solver actually decides

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 reference

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, CP-SAT rewriter, toroidal dimer counting, ALL_DIFFERENT timetable, pinning + identity chart, fast planar Pfaffian, transparent Klein integration.

---

What's shipped, by version (the wall of detail)

Skim this section if you want to know exactly which release introduced which capability. Most readers can skip to Tests below.

Scope as of v0.4.0a17 (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 – v0.2.0a12)

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.
• 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 → enumeration fallback.
• Polymorphic multilinear evaluator (v0.2.0a5): holant_sum_of_pfaffians, holant_genus_g, holant_planar are all polymorphic over semiring.
• End-to-end scheduling pipeline (v0.2.0a6): min_cost_schedule(instance, cost_fn) returns the exact polynomial-time minimum-cost schedule.
• Tropical matchgate_rank (v0.2.0a7): completes the four-coordinate apparatus for the weighted-signature case.
• One-call diagnostic (v0.2.0a8): tropical_instance_coordinates(instance, cost_fn) — the "is this instance structurally well-suited for tropical optimisation?" single-call answer.
• Per-edge restrictions for min_cost_schedule (v0.2.0a9): allowed_machines, time_windows, forbidden_edges.
• Network-flow domain module (v0.2.0a10): MinCostFlowInstance, min_cost_flow, max_flow_value.
• Rostering domain module (v0.2.0a11): Employee, Shift, RosteringInstance, min_cost_roster.
• MDM domain module (v0.2.0a12): Record, EntityCandidate, MDMInstance, min_cost_dedup.

Non-symmetric arity ≥ 5, Holant^c, multi-chart M, 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 (v0.3.0a0 + v0.3.0a2).
• Multi-chart M coverage (v0.3.0a1). srp_solve_multi_chart tries primary + secondary; the two together cover all of M except a measure-zero edge case.
• Holant^c variant (v0.3.0a3). srp_solve_holant_c for free-pinning Holant.
• Planar tropical Pfaffian API (v0.3.0a4). API surface in place; currently dispatches to Edmonds O(n³). A native Klein-style tropical algorithm is future work.
• Encoding-selection diagnostic + CP-SAT integration (v0.3.0a5). diagnose_constraints for abstract specs, diagnose_cpsat_model for CP-SAT models.
• Pattern-rewriting transformer (v0.3.0a6). rewrite_to_time_slot, rewrite_constraints produce structural blueprints.

CP-SAT rewriter, full genus-g pipeline, Klein arc, basis-aware rank (v0.4)

The v0.4 line materialises the rewriter for real CP-SAT models, adds the full genus-g Kasteleyn pipeline end-to-end, and integrates a fast exact-integer Pfaffian at scale.

• CP-SAT model rewriter rewrite_cpsat_model (v0.4.0a0). Materialises the rewrite blueprint into a runnable model with the explicit helped: bool signal.
• Solution-equivalence verifier verify_cpsat_rewrite_equivalence (v0.4.0a1).
• AT_LEAST_K rewriter fix (v0.4.0a2). The verifier found a real rewriter bug on first run; v0.4.0a2 ships the fix.
• Full genus-g Kasteleyn / Galluccio–Loebl pipeline (v0.4.0a3). New holant_tools.genus module: genus_from_rotation_system, homology_generators, symplectic_basis, poincare_dual_cocycle_general. Verified on the 4×4 torus (PM=272) and Petersen graph on Σ_2 (PM=6). See docs/insights-and-techniques.md §§2.5–2.8.
• Basis-aware matchgate rank (v0.4.0a4). Parity-split rank-≤-2 theorem; basis_aware_matchgate_rank and configuration_basis_aware_matchgate_rank plus hand-buildable corruption-detection verifiers.
• Dart-chain intersection (v0.4.0a5). Fixes a degree-3-vertex blindspot in the v0.4.0a3 walks formula; 200/200 stress-test cases now non-degenerate.
• 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.
• Third chart of 𝓜 = identity-basis chart (v0.4.0a7). Holant^c with F = {EQ_2}, previously infeasible in primary + secondary, is now feasible at identity. See docs/insights-and-techniques.md §5.2.
• Augmented Plücker vacuousness correction (v0.4.0a8, v0.4.0a10). Empirical Jacobian-rank check showed the v0.3.0a2 augmented identity is redundant at arity ≥ 6 over standard Plücker; documentation corrected.
• Cai-Lu Form 1/2/3 decomposition (v0.4.0a11). matchgate_form_decomposition extracts the explicit (root, polynomial-in-k) atoms from the Hankel recurrence. Closes the v0.1.5 deferred gap.
• Non-symmetric matchgate rank (v0.4.0a12). nonsymmetric_matchgate_rank returns a lower bound on the matchgate rank via Hankel-tensor flattenings (Bravyi 2008).
• Fast planar Pfaffian — Klein arc, v0.4.0a13–a17. Five-release programme: Schur complement primitive (a13) → recursive structure (a14) → scipy.sparse + float64 (a15) → modular arithmetic + CRT (a16) → transparent integration (a17). Net effect: holant_planar(K) and holant_genus_g(matrices, g) on integer Kasteleyn matrices of size ≥ 16 automatically run 7–19× faster with exact integer output. No code changes required downstream.

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
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.

Not yet shipped (the roadmap)

• Translation layers from SAT / CSP / MILP / SLURM / AMPL / MiniZinc / DIMACS. Would open the diagnostic layer to a broader audience.
• Tropical-Plücker / tropical-Grassmannian specialisation for planar graphs — the planar_tropical_pfaffian API is in place (v0.3.0a4); the Klein 2007 / Borradaile-Klein O(n^{3/2}) tropical algorithm is multi-month future engineering work.
• Tropical matchgate_rank for non-concave / +inf-bearing sequences — research-grade open problem.
• Weighted compilation with precedence / exclusion — assignment + capacity covered (v0.2.0a6); combinatorial forbidden-pair constraints in weighted form are pending.
• Additional domain modules — beyond the four currently shipped (scheduling, network_flow, rostering, MDM), other application domains (combinatorial auctions, supply-chain routing, sensor allocation, etc.) can be added as needed — same kernel, different vocabulary.
• Gurobi / Z3 / MiniZinc / DIMACS wrappers — the CP-SAT rewriter and verifier are shipped (v0.4.0a0–a2); analogous wrappers for other solvers are mechanical extraction work.
• Higher-order augmented-Pfaffian relations for non-symmetric signatures — research-grade.

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 .
pytest tests/

331 tests across all subsystems: signatures, realizability, intersection, SRP solver (primary + secondary + identity charts), Pfaffian + Galluccio–Loebl Holant evaluator, non-symmetric arity-n identities, hardness screening, Kasteleyn orientation (planar + genus-g), free-fermion simulator, structural-fingerprint coordinates, scheduling adapter, SWF parser, time-slot encoding, precedence + exclusion compilation, tropical Holant kernel (Hungarian + Edmonds + polymorphic multilinear evaluator + weighted scheduling compiler + tropical matchgate rank + polymorphic instance coordinates + per-edge restrictions), domain modules (network_flow + rostering + MDM), 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, non-symmetric matchgate rank, Cai-Lu Form 1/2/3 decomposition, Klein fast planar Pfaffian (a13–a17 arc, including transparent integration into holant_planar and holant_genus_g).

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.
• [Bra08] S. Bravyi. Contraction of matchgate tensor networks on non-planar graphs. Contemporary Mathematics, vol. 482 (2008).
• [Kle07] P. Klein. A subset spanner for planar graphs, with application to subset TSP. STOC 2006 / SICOMP (2007).