holant-tools 0.1.9

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 $#\mathsf{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 $#\mathsf{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.

Scope (v0.1)

Shipped:

• 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 at arity 4.
• 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().
• FreeFermionCircuit — polynomial-time matchgate quantum-circuit simulator via covariance matrices. Verified against state-vector simulation; exponential speedup begins at $n \sim 10$ qubits.

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 common formats.
• Automatic Kasteleyn-orientation construction from rotation-system input.

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.

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
# All v0.1 + v0.2 + v0.3-alpha + v0.3-beta + v0.3-beta-followon + hardness tests pass.

47 tests across all subsystems.

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.