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.
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.
This paper introduces an observation-respecting computational principle that forbids the existence of pre-solution “cheat sheets” for canonical SAT instances. Classical complexity theory implicitly allows auxiliary information that encodes solution-relevant structure prior to solving, erasing any notion of causal or observational order. In contrast, physically grounded models of computation—motivated by quantum mechanics—permit classical information only as the irreversible outcome of explicit measurement. We formalize this distinction by introducing non-resolving preprocessing procedures, defined as polynomial-time processes that avoid satisfiability-correlated measurement. For a canonical non-uniform family of satisfiable SAT instances, we define a hierarchy of solution structures and show that no such preprocessing can significantly compress these structures prior to observation. The obstruction arises from a fundamental mismatch between distribution-level information available before measurement and realization-dependent information that emerges only after satisfiability is resolved. Rather than claiming a resolution of P versus NP in the classical Turing model, this work isolates a precise conceptual barrier: realization-dependent solution information cannot be generated in advance without violating observation-respecting constraints. The result provides a physically motivated explanation for persistent pre-solution information asymmetry in NP-complete problems and suggests new directions for examining computational hardness through the lens of information generation.
We approach the 3-SAT satisfiability problem with the quantum-inspired method of imaginary time propagation (ITP) applied to matrix product states (MPS) on a classical computer. This ansatz is fundamentally limited by a quantum entanglement barrier that emerges in imaginary time, reflecting the exponential hardness expected for this NP-complete problem. Strikingly, we argue based on careful analysis of the structure imprinted onto the MPS by the 3-SAT instances that this barrier arises from classical computational complexity. To reveal this connection, we elucidate with stochastic models the specific relationship between the classical hardness of the ♯P ⊇ NP-complete counting problem $\sharp$3-SAT and the entanglement properties of the quantum state. Our findings illuminate the limitations of this quantum-inspired approach and demonstrate how purely classical computational complexity can manifest in quantum entanglement. Furthermore, we present estimates of the non-stabilizerness required by the protocol, finding a similar resource barrier. Specifically, the necessary amount of non-Clifford operations scales superlinearly in system size, thus implying extensive resource requirements of ITP on different architectures such as Clifford circuits or gate-based quantum computers.
Abstract Estimating ground state energies of local Hamiltonian models is a central problem in quantum physics. The question of whether a given local Hamiltonian is frustration-free, meaning the ground state is the simultaneous ground state of all local interaction terms, is known as the Quantum k-SAT (k-QSAT) problem. In analogy to its classical Boolean constraint satisfaction counterpart, the NP-complete problem k-SAT, Quantum k-SAT is QMA1 QMA 1 -complete (for k≥3 k ≥ 3 , and where QMA1 QMA 1 is a quantum generalization of NP with one-sided error), and thus likely intractable. But whereas k-SAT has been well-studied for special tractable cases, as well as from a “parameterized complexity” perspective, much less is known in similar settings for k-QSAT. Here, we study the open problem of computing satisfying assignments to k-QSAT instances which have a “dimer covering” or “matching”; such systems are known to be frustration-free, but it remains open whether one can efficiently compute a ground state. Our results fall into three directions, all of which relate to the “dimer covering” setting: (1) We give a polynomial-time classical algorithm for k-QSAT when all qubits occur in at most two interaction terms or clauses. (2) We give a “parameterized algorithm” for k-QSAT instances from a certain non-trivial class, which allows us to obtain exponential speedups over brute force methods in some cases. This is achieved by reducing the problem to solving for a single root of a single univariate polynomial. An explicit family of hypergraphs, denoted Crash, for which such a speedup is obtained is introduced. (3) We conduct a structural graph theoretic study of 3-QSAT interaction graphs which have a “dimer covering”. We remark that the results of (2), in particular, introduce a number of new tools to the study of Quantum SAT, including graph theoretic concepts such as transfer filtrations and blow-ups from algebraic geometry.
The Boolean satisfiability problem (SAT) is of central importance in both theory and practice. Yet, most provable guarantees for quantum algorithms rely exclusively on Grover-type methods that cap the possible advantage at only quadratic speed-ups, making the search for approaches that surpass this quadratic barrier a key challenge. In this light, this work presents a rigorous worst-case runtime analysis of a recently introduced measurement-driven quantum SAT solver. Importantly, this quantum algorithm does not exclusively rely on Grover-type methods and shows promising numerical performance. Our analysis establishes that the algorithm's runtime depends on an exponential trade-off between two key properties: the spectral gap of the associated Hamiltonian and the success probability of the driving measurements. We show that this trade-off can be systematically controlled by a tunable rotation angle. Beyond establishing a worst-case runtime expression, this work contributes significant algorithmic improvements. First, we develop a new readout routine that efficiently finds a solution even for instances with multiple satisfying assignments. Second, a measurement parallelization scheme, based on perfect hash families, is introduced. Third, we establish an amplitude-amplified version of the measurement-driven algorithm. Finally, we demonstrate the practical utility of our framework: By suitably scheduling the algorithm's parameters, we show that its runtime collapses from exponential to polynomial on a special class of SAT instances, consistent with their known classical tractability. A problem we leave open is to establish a non-trivial lower bound on the spectral gap as a function of the rotation angle. Resolving this directly translates into an improved worst-case runtime, potentially realizing a super-quadratic quantum advantage.
The k-SAT problem is a canonical NP-complete problem for which no efficient algorithm is known. This paper proposes a hybrid quantum–classical search algorithm that employs Grover’s algorithm as the inner local search of a randomized outer loop. Each outer iteration measures a random assignment, prepares a problem-dependent superposition over the Hamming ball of radius r around it, and applies amplitude amplification to locate a satisfying assignment; it returns an assignment rather than a yes/no answer and cannot certify unsatisfiability. Because the ball center is measured, the outer loop remains a classical repetition over independently sampled balls and contributes the inverse success probability rather than its square root; balancing this against the inner quadratic speedup shifts the optimal radius from n/(k+1) to n/(1+k) and yields the running time (2−2/(1+k))n, up to polynomial factors—1.268n for k = 3, below the best known classical 1.307n. The contribution is not an asymptotic record—the best known quantum exponents for k-SAT, obtained by amplifying stronger classical solvers as black boxes, remain smaller—but a fully explicit, gate-level construction: the problem-dependent state over the Hamming ball and the k-SAT oracle are decomposed into elementary quantum gates, and the polynomial gate and qubit overheads are accounted for in full.
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.