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.
The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.
One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts. Published by the American Physical Society 2024
Present-day, noisy, small or intermediate-scale quantum processors---although far from fault tolerant---support the execution of heuristic quantum algorithms, which might enable a quantum advantage, for example, when applied to combinatorial optimization problems. On small-scale quantum processors, validations of such algorithms serve as important technology demonstrators. We implement the quantum approximate optimization algorithm on our hardware platform, consisting of two superconducting transmon qubits and one parametrically modulated coupler. We solve small instances of the NP (nondeterministic polynomial time)-complete exact-cover problem, with 96.6% success probability, by iterating the algorithm up to level two.
Quantum algorithms can deliver asymptotic speedups over their classical counterparts. However, there are few cases where a substantial quantum speedup has been worked out in detail for reasonably-sized problems, when compared with the best classical algorithms and taking into account realistic hardware parameters and overheads for fault-tolerance. All known examples of such speedups correspond to problems related to simulation of quantum systems and cryptography. Here we apply general-purpose quantum algorithms for solving constraint satisfaction problems to two families of prototypical NP-complete problems: boolean satisfiability and graph colouring. We consider two quantum approaches: Grover's algorithm and a quantum algorithm for accelerating backtracking algorithms. We compare the performance of optimised versions of these algorithms, when applied to random problem instances, against leading classical algorithms. Even when considering only problem instances that can be solved within one day, we find that there are potentially large quantum speedups available. In the most optimistic parameter regime we consider, this could be a factor of over 105 relative to a classical desktop computer; in the least optimistic regime, the speedup is reduced to a factor of over 103 . However, the number of physical qubits used is extremely large, and improved fault-tolerance methods will likely be needed to make these results practical. In particular, the quantum advantage disappears if one includes the cost of the classical processing power required to perform decoding of the surface code using current techniques.
This study explores how well Grover's Algorithm performs in solving the Boolean Satisfiability Problem (SAT) using quantum circuits. The algorithm is implemented with IBM's Qiskit framework and compared to classical brute-force methods. Experiments focus on 3-SAT, 4-SAT, and 5-SAT problems, using quantum simulators and IBM quantum hardware. The results show that Grover's Algorithm is more efficient, offering a theoretical quadratic speedup over classical methods. However, practical issues like limited qubit availability, hardware noise, and optimization challenges impact its current performance. The data highlights the potential for quantum computing to scale and solve NP-complete problems. This research shows how quantum computing can improve problem-solving and lays the groundwork for future studies on more complex SAT problems and advanced quantum hardware.
This study explores how well Grover's Algorithm performs in solving the Boolean Satisfiability Problem (SAT) using quantum circuits. The algorithm is implemented with IBM's Qiskit framework and compared to classical brute-force methods. Experiments focus on 3-SAT, 4-SAT, and 5-SAT problems, using quantum simulators and IBM quantum hardware. The results show that Grover's Algorithm is more efficient, offering a theoretical quadratic speedup over classical methods. However, practical issues like limited qubit availability, hardware noise, and optimization challenges impact its current performance. The data highlights the potential for quantum computing to scale and solve NP-complete problems. This research shows how quantum computing can improve problem-solving and lays the groundwork for future studies on more complex SAT problems and advanced quantum hardware.