A Hybrid Quantum–Classical Algorithm for k-SAT via Grover-Enhanced Local Search

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.