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

Quanfeng Lu, Shijie Wei, Keren Li, Pan Gao, Bao Yan, Muxi Zheng, Haoran Zhang, Jinfeng Zeng, Gui-Lu Long · 2025

Read Evidence of scaling advantage on an NP-Complete problem with enhanced quantum solvers by Quanfeng Lu, Shijie Wei, Keren Li, Pan Gao, Bao Yan, Muxi Zheng, Haoran Zhang, Jinfeng Zeng, Gui-Lu Long (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08869.txt.

Introduction

Quanfeng Lu and co-authors report evidence that enhanced quantum solvers can out-scale the best classical solvers on a hard logic problem, in a 2025 paper. The problem, one-in-three satisfiability, is NP-complete, meaning no fast classical method is expected to exist. True quantum advantage is hard to prove, so the field watches how the needed resources grow with problem size.

The team first adds a space-shrinking routine that cuts the search space to its best possible size, saving qubits and time. Two boosted solvers, one based on the QAOA method and one on slow quantum annealing, then beat leading classical solvers on test cases with up to 65 variables. The annealing solver set the floor for the method and showed the scaling edge. A run on a 13-qubit superconducting chip confirmed the predicted gains.

Catalog record

CREATORQuanfeng Lu, Shijie Wei, Keren Li, Pan Gao, Bao Yan, Muxi Zheng, Haoran Zhang, Jinfeng Zeng, Gui-Lu Long
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-08869

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Evidence of scaling advantage on an NP-Complete problem with enhanced quantum solvers Quanfeng Lu, Shijie Wei, Keren Li, Pan Gao, Bao Yan, Muxi Zheng, Haoran Zhang, Jinfeng Zeng, Gui-Lu Long Abstract Achieving quantum advantage remains a key milestone in the noisy intermediate-scale quantum era. Without rigorous complexity proofs, scaling advantage—where quantum resource requirements grow more slowly than their classical counterparts—serves as the primary indicator. However, direct applications of quantum optimization algorithms to classically intractable problems have yet to demonstrate this advantage. To address this challenge, we develop enhanced quantum solvers for the NP-complete one-in-three Boolean satisfiability problem. We propose a restricting space reduction algorithm (RSRA) that achieves optimal search space dimensionality, thereby reducing both qubits and time complexity for various quantum solvers. Extensive numerical investigations on problem instances with up to 65 variables demonstrate that our enhanced quantum approximate optimization algorithm (QAOA) and quantum adiabatic algorithm (QAA)-based solvers outperform state-of-the-art classical solvers, with the QAA-based solver providing a lower bound for our method while exhibiting scaling advantage. Furthermore, we experimentally implement our enhanced solvers on a superconducting quantum processor with 13 qubits, confirming the predicted performance improvements. Collectively, our results provide empirical evidence of quantum speedup for an NP-complete problem. I Introduction Quantum advantage remains the central objective in quantum computing. Quantum optimization algorithms, including the quantum approximate optimization algorithm (QAOA) farhi2014quantum and the variational quantum eigensolver (VQE) peruzzo2014variational , are promising candidates for achieving quantum advantage in the noisy intermediate-scale quantum (NISQ) era Preskill2018 , which is characterized by limited qubit counts Google2019Supremacy ; Wu2021Strong ; Kim2023Evidence and the absence of effective error correction mechanisms Acharya2023Suppressing ; Yu2023Nature ; Sivak2023Nature ; Lukin2024Nature . QAOA balances optimization accuracy with gate usage to mitigate noise, while VQE reduces quantum resource demands through classical optimization. Since these algorithms rely on classical optimization, their time complexities lack rigorous characterization. Demonstrating quantum advantage therefore requires comparing the scalings of their time complexities with those of the best classical algorithms. To date, systematic studies in this area remain limited. Notably, two significant studies have investigated the scaling advantages of QAOA for the Boolean satisfiability (SAT) problem boulebnane2024solving and the low autocorrelation binary sequences (LABS) problem shaydulin2024evidence . Table 1 : Comparison of scalings in time complexities for different one-in-three SAT solvers across various \frac{m}{n} ratios. All QAOA-based solvers utilize 25 layers, while all QAA-based solvers utilize 100 layers. Five types of classical solvers are used to calculate the optimal scaling of classical methods. Scalings lower than those of classical solvers are indicated in boldface. We observe that the enhanced QAOA- and QAA-based solvers exhibit better scalings than their classical counterparts and quantum methods without classical reduction across the critical region. |G| denotes the size of the set G which contains at least two variables in each clause, which is approximately 0.5n in the critical region. \mathbf{\frac{m}{n}} ratio Enhanced with the RSRA Original Classical \mathbf{|G|(\approx 0.5n)} qubits \mathbf{n} qubits QAA QAOA VQE Grover QAA QAOA Grover 0.626 1.008 1.006 1.020 1.084 1.039 1.041 1.345 1.013 0.55 1.005 1.002 1.012 1.098 1.029 1.021 1.327 1.012 0.575 1.006 1.004 1.013 1.093 1.032 1.027 1.334 1.012 0.6 1.006 1.005 1.019 1.089 1.037 1.035 1.340 1.013 0.65 1.009 1.008 1.020 1.078 1.041 1.037 1.350 1.013 0.675 1.009 1.009 1.025 1.073 1.043 1.031 1.355 1.013 0.7 1.010 1.010 1.030 1.067 1.046 1.044 1.359 1.013 0.725 1.009 1.011 1.029 1.061 1.048 1.043 1.363 1.013 0.75 1.008 1.011 1.020 1.055 1.049 1.045 1.367 1.013 The Boolean satisfiability problem (SAT) is a central topic in computer science, combinatorics, and logic, with broad applications spanning model checking biere1999symbolic ; bradley2011sat ; mcmillan2003interpolation ; amla2005analysis , combinatorial optimization zulkoski2017combining ; bejar2007regular ; banbara2010generating , automated deduction han2010making ; armando2005sat , and cryptography soos2009extending ; otpuschennikov2016encoding ; massacci2000logical ; mironov2006applications . The 3-SAT problem expressed in conjunctive normal form (CNF), as a conjunction of clauses where each clause is a disjunction of three literals, was the first problem proven to be NP-complete by the Cook-Levin theorem cook1971 . Notably, 3-SAT can also be expressed in one-in-three form, where each clause is satisfied if and only if exactly one literal is true. This problem is mutually reducible to 3-SAT in CNF and admits a simpler Hamiltonian representation, making it well-suited for quantum optimization (see Section S1 in Supplementary Information). To the best of our knowledge, no direct classical solver exists for the one-in-three SAT problem; existing classical methods typically rely on reductions to exact cover or SAT in CNF. These characteristics make the one-in-three SAT problem a compelling candidate for demonstrating quantum advantage over classical approaches. Several quantum algorithms have been proposed for solving the SAT problem using various quantum ground state solvers, including quantum annealing (QA) nusslein2023solving , the quantum adiabatic algorithm (QAA) albash2018adiabatic ; hogg2003adiabatic ; wang2016ultrafast ; farhi2001quantum ; young2008size ; young2010first , and the quantum approximate optimization algorithm (QAOA) farhi2014quantum ; golden2023quantum ; mandl2024amplitude ; bengtsson2020improved . A recent numerical study boulebnane2024solving demonstrated that the time complexity of QAOA with fixed parameters and constant depth, obtained from data training, for random 8-SAT problems with n\leq 20 variables scales as 1.23^{n} . However, these quantum algorithms are direct implementations of quantum optimization techniques applied to the SAT problem without optimizing the dimensionality of the search space, which can lead to large scalings or difficulties in parameter training boulebnane2024solving , hindering their ability to demonstrate quantum advantage over classical methods. In this paper, we introduce enhanced quantum one-in-three SAT solvers that exhibit quantum scaling advantage. We propose the restricting space reduction algorithm (RSRA), which reduces the number of candidate solutions from 2^{n} to approximately 2^{n-m} , where n denotes the number of variables and m represents the number of clauses. By integrating the RSRA with several quantum optimization algorithms, we develop enhanced VQE-, QAOA-, and QAA-based solvers with reduced time complexities. These enhanced quantum solvers exhibit the following key features: (1) Optimal search space reduction: The RSRA reduces the search space dimensionality from 2^{n} to approximately 2^{n-m} . (2) Problem heuristic ansatz: We utilize the RSRA to construct problem heuristic ansatz that ensure quantum states remain within the subspace spanned by solutions to the loosened problem while simultaneously simplifying the problem Hamiltonian. Compared to the original ansatz, the new ansatz demonstrate improvements in qubit usage and search space dimensionality. Additionally, we prove that the enhanced VQE-based solver can avoid barren plateaus. (3) Scalability in simulation and experiment: The RSRA enables large-scale numerical simulations and more feasible experimental demonstrations of SAT instances. Specifically, our VQE-based solver can handle instances with up to n=150 variables, while our QAOA- and QAA-based solvers scale to problems with up to n=100 variables. Experimentally, we demonstrate the feasibility of our approach on a superconducting quantum processor by using 13 qubits to solve instances with 20 variables, achieving meaningful results. (4) Quantum scaling advantage: The enhanced solvers exhibit clear scaling advantages. The QAOA-based solver achieves the best performance, while the QAA-based solver provides a lower bound. For problem sizes up to n=65 variables at the critical ratio \frac{m}{n}=0.626 , the enhanced QAOA-based solver with 25 layers and the QAA-based solver with 100 layers scale as 1.006^{n} and 1.008^{n} , respectively, both outperforming the 1.013^{n} scaling of state-of-the-art classical solvers. In summary, these advances

Read the complete text