近日，北京量子信息科学研究院（以下简称“量子院”）量子算法应用研发团队与清华大学等单位合作，在量子计算求解复杂性难题领域取得重要进展。成果相关论文“Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers”成功入选Nature Computational Science杂志2026年8月刊封面论文。期刊以专题形式同期发布了由量子院魏世杰副研究员和量子院科研副院长/清华大学教授龙桂鲁受邀撰写并署名的Research Briefing“Quantum scaling advantage using reduced search in an NP-complete problem”。

图 1 Nature Computational Science杂志2026年8月刊封面。

封面图展示了结合“限制空间缩减算法”（RSRA）的增强型量子求解器如何在缩减后的计算区域（发光线条）内运行，而非探索整个搜索空间（背景线条）。

变分量子算法是实现“含噪声中等规模量子”（NISQ）时代量子优势最有前景的方法之一，因为它们能有效平衡量子与经典计算资源，然而关于其计算扩展优势的程度尚缺乏深入了解。研究团队提出一种增强型量子求解器，该求解器结合了“限制空间缩减算法”（RSRA），旨在缩小搜索空间并改善计算扩展性能。基于此方法，研究团队在超导量子处理器上展示了“一选三布尔可满足性问题”（一种具有实际意义的 NP-完全问题）在大规模模拟中展示了相比经典求解器更好的经验扩展性能。

Research Briefing与国际评价：

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

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

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

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

原文链接：

论文：https://www.nature.com/articles/s43588-026-01007-8

Research Briefing：https://www.nature.com/articles/s43588-026-01033-6