Beijing Academy of Quantum Information Sciences

Home>News>Research Highlights
BAQIS Research Featured on Cover of Nature Computational Science alongside Invited Research Briefing

2026/08/24

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 solving computational complexity challenges using quantum computing. Their paper, "Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers," was selected as the cover article for the August 2026 issue of Nature Computational Science. Simultaneously, the journal published an invited Research Briefing titled "Quantum scaling advantage using reduced search in an NP-complete problem," co-authored by Associate Researcher Shijie Wei (BAQIS) and Professor Gui-Lu Long (Vice President of BAQIS and Professor at Tsinghua University).

8.24.png

Figure 1 | Cover of Nature Computational Science, August 2026 issue.


The cover highlights how the enhanced quantum solver with the Restricting Space Reduction Algorithm (RSRA) operates within a reduced computational region (glowing lines), rather than exploring the full search space (background lines).

Variational quantum algorithms represent one of the most promising approaches for achieving quantum advantage in the noisy intermediate-scale quantum (NISQ) era, effectively balancing quantum and classical computational resources. However, the extent of their computational scaling advantage remains poorly understood. The research team introduced enhanced quantum solvers incorporating the Restricting Space Reduction Algorithm (RSRA) to narrow the search space and improve computational scaling. Using the 1-in-3 Boolean satisfiability problem—a practically relevant NP-complete problem—as a benchmark, the authors demonstrated that the approach achieves favorable empirical scaling compared to classical solvers in large-scale simulations and validation on superconducting quantum processors.

Research Briefing and International Recognition

In the accompanying Research Briefing, the authors outline how the RSRA framework uses a "relax-then-restrict" strategy to compress the search space from Ο(2n）to Ο(2n-k） and construct a unique "problem-heuristic ansatz." This approach significantly lowers quantum resource requirements and exhibits a clear scaling advantage in the NISQ era. The work received high praise from international peers and journal editors:

  • John Golden, Expert at Los Alamos National Laboratory: "This is a clear, careful paper with a neat classical reduction (RSRA) that has the potential to improve NISQ feasibility for combinatorial optimization, through qubit or gate savings and a subspace-preserving design."

  • Jie Pan, Senior Editor at Nature Computational Science:"This work advances the feasibility of quantum computing in the NISQ era—a topic that has been actively debated in the field. The authors have developed enhanced quantum solvers for the NP-complete Boolean satisfiability problem, relevant to practical applications such as combinatorial optimization and cryptography, and demonstrate empirical scaling advantages over state-of-the-art classical solvers through large-scale simulations on superconducting quantum processors."

Authorship and Support

The co-first authors of this work are Quanfeng Lu (intern at BAQIS and Ph.D. student at Tsinghua University) and Dr. Shijie Wei (Associate Researcher at BAQIS). The corresponding authors are Dr. Shijie Wei and Dr. Jinfeng Zeng (Assistant Researcher at BAQIS). Professor Gui-Lu Long (Vice President of BAQIS and Professor at Tsinghua University) served as the senior corresponding author overseeing the entire project.

Co-authors include Keren Li (Assistant Professor, Shenzhen University), Pan Gao (Assistant Researcher, BAQIS), Bao Yan (State Key Laboratory of Mathematical Engineering and Advanced Computing), Muxi Zheng (Ph.D. student, Tsinghua University), and Haoran Zhang (Postdoctoral Researcher, Nanyang Technological University). This work was supported by the Beijing Nova Program and the National Natural Science Foundation of China.


Original Links: