Q35: Quantum spin-SAT: which subsystem spins can be forbidden?

Working mathematical formulation

Fix a constant locality $k$ and permitted subset-spin projectors $\Pi_{S,j}$ , $\lvert S\rvert\le k$ . A forbidden-spin constraint requires $\Pi_{S,j}\lvert\psi\rangle=0.$ Classify local Hamiltonians with force terms $I-\Pi_{S,j}$ , forbid terms $\Pi_{S,j}$ , or forbidden joint patterns formed from commuting projectors on nested or disjoint subsets, with the UNION of subsets in each clause also of size at most $k$ . State the allowed interaction graph and weights. Separate exact zero-energy versus inverse-polynomial frustration promises from general energy thresholds, and arbitrary quantum witnesses from product or multiple-unentangled witnesses.

Scope & assumptions

A forbid-only family that never excludes a subsystem’s maximal spin is satisfied by the fully polarized product state. A nontrivial hardness claim must specify a constraint language that avoids such automatic solutions.

Why this is interesting

Subsystem-spin constraints offer a natural quantum constraint-satisfaction language. Crossing subsets introduce noncommuting conditions; labels on a single laminar coupling tree behave differently.

Explicit variants

Promises on total spin and Young shape
For a specified family of spin constraints, ask for $\mathsf{QMA}$ membership and hardness of satisfiability or approximate satisfiability. Repeat with the witness restricted to a declared total-spin sector, equivalently a two-row Young shape for qubits, or with a promise that a satisfying witness exists in that sector. Specify how the verifier enforces the restriction and retain an inverse-polynomial promise gap.

A place to start

Classify small fixed constraint sets on three and four qubits. Compare laminar instances with crossing subsets and test proposed gadgets in both YES and NO cases.

Related work

These works provide context and established results. They need not be the origin of this exact formulation.

Discuss this question

Continue on GitHub Propose a research question

Reading is public. Posting requires a GitHub account. You can also write to Kunal.