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. This study develops enhanced quantum solvers for an NP-complete Boolean satisfiability problem and reports empirical scaling advantages over leading classical solvers in large-scale simulations, with supporting validation on a superconducting quantum processor.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. This study develops enhanced quantum solvers for an NP-complete Boolean satisfiability problem and reports empirical scaling advantages over leading classical solvers in large-scale simulations, with supporting validation on a superconducting quantum processor.

arXiv:2508.08869Nature Computational ScienceJun 19, 20261 citation

Circuit Design for K-coloring Problem and its Implementation on Near-term Quantum Devices

Amit Saha, Debasri Saha, Amlan Chakrabarti

Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.Nowadays in Quantum Computing, the implementation of quantum algorithm has created a stir since Noisy Intermediate-Scale Quantum (NISQ) devices are out in the market. Researchers are mostly interested in solving NP-complete problems with the help of quantum algorithms for its speedup. As per the work on computational complexity by Karp [1], if any of the NP-complete problem can be solved then any other NP-complete problem can be reduced to that problem in polynomial time. In this Paper, K-coloring problem (NP-complete problem) has been considered to solve using Grover's search. A comparator-based approach has been used to implement K-coloring problem which enables the reduction of the qubit cost compared to the state-of-the-art. An end-to-end automated framework has been proposed to implement the K-coloring problem for any unweighted and undirected graph on any available Noisy Intermediate-Scale Quantum (NISQ) devices, which helps in generalizing our approach.

arXiv:2009.06073IEEE International Symposium on Smart Electronic Systems (iSES)Dec 1, 202012 citations

Quantum Computation and NP-Complete Problems

Tetsuro Nishino

Jul 1, 20000 citations

A Generic Variable Inputs Quantum Algorithm for 3-SAT Problem

Ping Wang, Guangqiang Liu, Liyan Liu

The Grover's algorithm can find an item satisfying certain properties in a search space of size N with circuit complexity $O\left( {\sqrt N } \right)$ , where the circuit are formed by the G operator one by one in series. The huge circuit scale is the main obstacle to the practical application of the Grover's algorithm. In this paper, we present a generic variable inputs quantum algorithm by time-space tradeoff to reduce the scale of the quantum circuit. We combine the proposed algorithm in the paper with the Schöning's algorithm to solve the 3-SAT problem which is a NP-complete problem. Compared with previous algorithms, as the input variables n of 3-SAT problem increases, the advantages of our algorithm is obvious.The Grover's algorithm can find an item satisfying certain properties in a search space of size N with circuit complexity $O\left( {\sqrt N } \right)$, where the circuit are formed by the G operator one by one in series. The huge circuit scale is the main obstacle to the practical application of the Grover's algorithm. In this paper, we present a generic variable inputs quantum algorithm by time-space tradeoff to reduce the scale of the quantum circuit. We combine the proposed algorithm in the paper with the Schöning's algorithm to solve the 3-SAT problem which is a NP-complete problem. Compared with previous algorithms, as the input variables n of 3-SAT problem increases, the advantages of our algorithm is obvious.

IEEE International Conference on Advances in Electrical Engineering and Computer Applications (AEECA)Aug 1, 20203 citations

The Grover's algorithm can find an item satisfying certain properties in a search space of size N with circuit complexity

O\left( {\sqrt N } \right)

, where the circuit are formed by the G operator one by one in series. The huge circuit scale is the main obstacle to the practical application of the Grover's algorithm. In this paper, we present a generic variable inputs quantum algorithm by time-space tradeoff to reduce the scale of the quantum circuit. We combine the proposed algorithm in the paper with the Schöning's algorithm to solve the 3-SAT problem which is a NP-complete problem. Compared with previous algorithms, as the input variables n of 3-SAT problem increases, the advantages of our algorithm is obvious.