Which spin-constraint problems are naturally -complete?
Can a classical sequence of pairings, recouplings, or an adiabatic path certify a spin-constraint problem? Identify natural complete problems with explicit verification and promise gaps.
Discuss this questionDefine a promise problem on a polynomial-size description of bounded-locality subsystem-spin constraints and thresholds with . A classical witness describes a polynomial-length sequence of pairings or recouplings, or an efficiently implementable Hamiltonian path, from specified preparable input states. Give a uniform polynomial-time quantum verifier that accepts some such guide on every YES instance and rejects every guide on every NO instance. Seek natural problem families that are -complete under polynomial-time reductions. State exactly what the guide certifies—low energy, a constraint-satisfaction probability, or a state-generation task—and account for preparation and verification error.
Efficiently describing a path is not a proof that it prepares a useful state. Completeness needs a runtime and success bound; soundness applies to every proposed classical guide. The Q19 containment route remains a separate, stronger question.
Why this is interesting
A natural -complete spin problem would identify a verification boundary without requiring the stronger containment .
A place to start
Fix one guide language and one spin-constraint family. Prove membership by accounting for all verification resources, then ask whether the constraints can express a known classical-witness verification task with a preserved promise gap.
Related work
These works provide context and established results. They need not be the origin of this exact formulation.
Discuss this question
Reading is public. Posting requires a GitHub account. You can also write to Kunal.