Complexity classification of cubic bipartite holant problems with fixed weights
A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic Weights
Computational Complexity
Summary
This paper studies a special kind of computational problem involving networks with two types of nodes and fixed rules at each node. The authors completely classify which problems can be solved easily and which ones are computationally very hard based on the fixed rules, called signatures. They handle complex number weights and provide exact mathematical conditions separating the easy from the hard cases. Their work reveals deep structural properties and uses advanced mathematical tools to prove the classification.
What this means in practice
- •For algorithm designers: Determine which Holant problems with specific constraints can be solved efficiently or are intractable when designing algorithms for network computations.
- •For quantum computing engineers: Use the complexity boundaries of cubic bipartite Holant problems as a guide to identify feasible computational tasks in quantum simulations involving tensor networks.
A theory result. No direct application yet.
Authors
Yin, Liu
Abstract
We classify the exact evaluation of $\operatorname{Holant}(f\mid=_3)$ for every fixed complex algebraic symmetric Boolean ternary signature $f$. An input is a cubic bipartite multigraph: every vertex on one side carries $f$, every vertex on the other side carries ternary equality, and no auxiliary signatures are freely available. The tractable signatures are precisely rank-one tensors, generalized equalities, and equality-preserving cube-root diagonal transformations of six affine signatures, together with nonzero scalings and reversal. Every other signature gives a $\#\mathrm{P}$-hard problem under polynomial-time Turing reductions. We also identify the exact real intersection: it consists of the same tractable families as in the rational classification, with real algebraic parameters. The proof preserves degree exactly three on both sides of every oracle instance. A rank-one matrix extracted by interpolation supplies one unary signature only after its unused factor has been absorbed in triples. Over the complex numbers this absorption has three exceptional projective directions. We combine this constraint with projective matrix-group orbits, explicit ternary replacements, and an exhaustive treatment of finite projective orders. The cases of orders three and five include exact polynomial certificates; the certificate identities and a rational-arithmetic verifier are supplied as supplementary material.