Boolean Holant problems with complex signatures show clear complexity divide
A Dichotomy for Boolean Complex Holant Problems with Conjugate-Closed Signature Sets
Computational Complexity
Summary
This paper studies a type of mathematical puzzle called Boolean Holant problems, where answers come from complex numbers with a special symmetry. The authors found a clear rule that tells which of these puzzles can be solved easily and which are hard. Their work uses tools from quantum information theory and group theory. This helps understand the complexity of problems that show up when simulating quantum circuits.
What this means in practice
- •For quantum circuit simulators: Determine when simulating a quantum circuit classically can be done efficiently based on the structure of its signature sets.
- •For computational complexity engineers: Use the tractability criteria to design or avoid certain problem instances within Holant frameworks to manage computational resources.
A theory result. No direct application yet.
Authors
Jincheng Guan, Shuai Shao, Zhuxiao Tang
Abstract
We study Boolean Holant problems with complex-valued signature sets closed under conjugation. Such sets arise naturally in tensor-network expressions for classical strong simulation of quantum circuits. We prove a complexity dichotomy for such problems with an explicit tractability criterion. This extends the dichotomy for real-valued Holant problems, with the same four tractability conditions. Our proofs use Xia's projective binary group framework and quantum entanglement theory. The conjugate closure assumption precisely makes $k$-uniformity, directly applicable to the classification of Holant problems, by realizing reduced density matrices via Holant gadgets. We also use the classification of absolutely maximally entangled states to resolve a particular $6$-ary obstruction in our inductive proof of the \#P-hardness.