This paper studies a no-go barrier for physically inspired SAT solvers built from local, non-oracular dissipative dynamics. It formalizes a Local Repair GKSL family in which the generator is polynomial-time constructible from the formula, local in the witness encoding, and triggered only by local inconsistency or repair signals. The paper argues that such dynamics inherits the same bottleneck obstruction already visible in washout-style classical SAT dynamics: there exist SAT instance families for which any local repair process has exponentially small effective conductance or dissipative gap, preventing inverse-polynomial time-bounded discrimination between satisfiable and unsatisfiable instances. The paper is intentionally narrow. It does not claim that all physical solvers are weak, and it leaves open separator-based and global-but-non-oracular escape routes. Its contribution is to turn the “physics route” barrier into a precise transport obstruction.
There is growing interest in extensions of the standard model of gate-based quantum computation to include auxiliary degrees of freedom evolving according to a nonlinear Schrödinger equation. By reducing the
Boolean satisfiability problem SAT to quantum state discrimination, Abrams and Lloyd argued that the right type of nonlinearity can be used to solve NP and #P problems in polynomial time, at least in an
idealized noise-free limit. For practical implementation, however, we are restricted to simulated and emergent nonlinearities, such as that appearing in mean field models for ultracold atoms and similar
ensembles. A prominent example is the torsion model, which arises in two-component Bose-Einstein condensates and spin models with all-to-all Ising interaction. But torsion-based state discrimination appears to
fall short of solving SAT. Here we close this gap by constructing the filtered oracle of the Valiant-Vazirani theorem, providing a randomized polynomial-time reduction from SAT to UNIQUE SAT, a promise problem
where there is at most 1 satisfying assignment. In the noise-free limit, the UNIQUE SAT problem can be solved in polynomial time using torsion nonlinearity. Quantum Valiant-Vazirani reduction is no faster than
the efficient classical version, but a fault-tolerant implementation coupled to a nonlinear quantum coprocessor simulating torsion would enable polynomial time solution to NP (but not #P) problems.
We give a classical polynomial-time algorithm that strongly refutes random quantum 3-SAT at sufficiently large constant constraint density, thereby disproving the quantum analogue of Feige's random 3-SAT hypothesis. This stands in sharp contrast to classical random 3-SAT, for which polynomial-time strong refutation is known only at constraint density Δ≳n1/2. Although quantum 3-SAT shares the pairwise-independence barrier of its classical counterpart, our SDP-based refutation overcomes this barrier by exploiting the noncommutativity of quantum constraints.