Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers

Achieving quantum advantage remains a milestone in the noisy intermediate-scale quantum era. Without complexity proofs, scaling advantage-where quantum resource requirements grow more slowly than their classical counterparts-is the primary indicator. However, direct applications of quantum optimization algorithms to classically intractable problems have yet to demonstrate this advantage. Here we develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem. We propose a restricting space reduction algorithm that achieves optimal search-space dimensionality under mod-2 arithmetic, thereby reducing qubit requirements and time complexity. Numerical studies on instances with up to 70 variables demonstrate that our enhanced quantum approximate optimization algorithm- and quantum adiabatic algorithm-based solvers outperform state-of-the-art classical solvers; the quantum adiabatic algorithm-based solver serves as a lower-bound reference while retaining scaling advantage. Furthermore, experiments on a 13-qubit superconducting processor confirm the predicted improvements. Collectively, our results provide empirical evidence of quantum speedup for an NP-complete problem.