近日，北京量子信息科学研究院量子算法应用研发团队在量子计算求解复杂性难题领域取得的新进展《Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers》成功入选《Nature Computational Science》2026年8月刊封面论文（Cover Article）。同时，期刊以专题形式同步在线发表了由魏世杰副研究员和北京量子院科研副院长、清华大学教授龙桂鲁受邀撰写并署名的 Research Briefing（研究简报）：《Quantum scaling advantage using reduced search in an NP-complete problem》。

  本期封面直观呈现了团队的核心创新——限制空间约化算法（RSRA）。变分量子算法是实现“含噪声中等规模量子”（NISQ）时代量子优势最有前景的方法之一，因为它们能有效平衡量子与经典计算资源。然而，关于其计算扩展优势的程度，目前尚缺乏深入了解。在本期中，北京量子院与清华大学联合团队介绍了一种增强型量子求解器，该求解器结合了“限制空间缩减算法”（RSRA），旨在缩小搜索空间并改善计算扩展性能。作者以“一选三布尔可满足性问题”（一种具有实际意义的NP-完全问题）为基准，在超导量子处理器上展示了该方法在大规模模拟中相比经典求解器所具备的良好经验扩展特性。本期封面展示了这种结合RSRA的增强型量子求解器如何在缩减后的计算区域（发光线条）内运行，而非探索整个搜索空间（背景线条）。

  在同期发布的Research Briefing中，作者详细梳理了RSRA算法如何通过“先松后紧”的策略，将搜索空间从O2n有效压缩至O2n−k，并构建出独特的“问题启发式Ansatz”，在NISQ时代显著降低了量子资源需求并展现出标度优势。该工作获得了国际同行与期刊编辑的高度评价：

  洛斯阿拉莫斯国家实验室（Los Alamos National Laboratory）专家John Golden评价：“这是一篇清晰、严谨的论文，其巧妙的经典约化（RSRA）通过节省量子比特和设计子空间保持方案，展现出提升NISQ时代组合优化可行性的潜力。”

  《Nature Computational Science》高级编辑Jie Pan点评：“该工作推进了量子计算在NISQ时代的实用可行性——这一直是该领域广受关注的热点话题。作者针对NP完全布尔可满足性问题开发了增强型量子求解器（该问题与组合优化和密码学等实际应用息息相关），并通过大规模数值模拟，展示了优于最先进经典求解器的经验性标度优势。”

  这一系列成果的正式刊发与专题推介，标志着国际学术界对该团队在结构化NP完全问题量子加速领域中取得的进展给予了广泛认可与持续关注。

  该工作第一作者为北京量子院实习生、清华大学博士生陆全枫、北京量子院副研究员魏世杰，通讯作者为北京量子院副研究员魏世杰、助理研究员曾进峰，北京量子院科研副院长、清华大学龙桂鲁教授为全文末位通讯作者，统筹指导全部研究工作。论文合作者还包括深圳大学助理教授李可仁、北京量子院助理研究员高攀、数学工程与先进计算国家重点实验室闫宝、清华大学博士生郑沐曦、新加坡南洋理工大学博士后张浩然。该工作得到北京市科技新星计划和国家自然科学基金等项目的支持。