Recently, the Quantum Algorithm Application R&D Team at the Beijing Academy of Quantum Information Sciences (BAQIS), in collaboration with Tsinghua University and other institutions, made significant progress  in using quantum computing to solve complex problem. By developing enhanced quantum solvers, the team observed an empirical scaling advantage of quantum computing when solving a class of NP-complete problems—the 1-in-3 satisfiability problem (1-in-3 SAT). On June 19, 2026, the related findings were published in Nature Computational Science under the title "Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers".

Current quantum computers are in the Noisy Intermediate-Scale Quantum (NISQ) era, vast majority of quantum algorithms cannot provide analytical proofs of quantum algorithm complexity. The core basis for determining a quantum advantage is an empirical scaling advantage—meaning that as the problem size grows, the required quantum computing resources increase at a significantly slower rate than those of  classical algorithms. When solving the most difficult NP-complete problems with quantum computers, there has been a persistent lack of convincing experimental and numerical demonstrations to practically prove quantum speedup.

To address this challenge, the research team proposed the Restricting Space Reduction Algorithm (RSRA) and constructed an enhanced quantum satisfiability (SAT) solver based on it. The core innovations of this algorithm include:

1. Optimizing quantum resources to achieve optimal search space reduction. The algorithm effectively reduces the search space dimension from O (2ⁿ) to O (2^(n-m)),greatly improving the operational efficiency of the quantum solver.

2. Utilizing RSRA to build a  unique problem heuristic ansatz. This ensures that quantum states always remain      within the solution-containing subspace, simplifies the problem Hamiltonian, and effectively avoids the "barren plateaus" problem commonly encountered in Variational Quantum Eigensolver (VQE) methods.

Figure Description:

• a. The Restricting Space Reduction Algorithm (RSRA) and its application in the 1-in-3 SAT quantum solver. RSRA relaxes the constraints of the 1-in-3 SAT problem into  "1-in-3 odd" constraints and reformulates the original problem  into a 2-SAT problem with a relaxed solution space, thereby yielding an effective Hamiltonian $H$ and a problem heuristic ansatz.

• b. Comparison between the  original quantum solver and the enhanced quantum solver. The upper section  shows the standard ansatz used by the original solver, while the lower  section shows the ansatz constructed by the enhanced solver based on RSRA.

Through theoretical analysis, large-scale numerical simulations with up to 150 variables, and experimental validation on physical quantum computers, the research team clearly discovered that within the critical clause-to-variable ratio range of m/n ∈[0.55，0.75]—where classical solvers often hit performance bottlenecks—the newly constructed enhanced quantum solver exhibits exponential scaling performance that outperforms current state-of-the-art classical algorithms. This work provides new insights into quantum speedup for structured NP-complete problems under real-world constraints, marking an important step forward for quantum solvers in handling complex logical constraint problems.

The co-first authors of the paper are Quanfeng Lu (intern at BAQIS and PhD student at Tsinghua University) and Shijie Wei (Associate Research Fellow at BAQIS). The corresponding authors are Shijie Wei and Jinfeng Zeng (Assistant Research Fellow at BAQIS), with Professor Guilu Long (Vice President of Research at BAQIS and Professor at Tsinghua University) serving as the last corresponding author who supervised and guided the entire research work. Other co-authors include Keren Li (Assistant Professor at Shenzhen University), Pan Gao (Assistant Research Fellow at BAQIS), Bao Yan (State Key Laboratory of Mathematical Engineering and Advanced Computing), Muxi Zheng (PhD student at Tsinghua University), and Haoran Zhang (Postdoctoral Researcher at Nanyang Technological University, Singapore). This work was supported by projects including the Beijing Nova Program and the National Natural Science Foundation of China.

Original Article Link: https://www.nature.com/articles/s43588-026-01007-8