近日，清华大学物理系龙桂鲁教授团队与北京量子信息科学研究院等单位合作，在量子计算求解复杂性难题领域取得新进展。相关成果以封面论文形式发表于Nature Computational Science 2026年8月刊，并同步发表了受邀撰写的题为“Quantum scaling advantage using reduced search in an NP-complete problem”的 Research Briefing（研究简报）专文报道。

研究背景与核心方法

在有噪声中等规模量子（NISQ）时代，量子优化算法多采用启发式，缺乏解析复杂度证明。因此，证明量子优势的核心指标在于通过标度比较，证明量子资源的需求增长速度慢于最优秀的经典算法。团队针对布尔可满足性问题（如 1-in-3 SAT）这一典型的 NP-complete 难题，提出了一种限制空间约化算法（RSRA）。该方法通过将子句松弛为模 2 宇称约束，将有效搜索空间从全部指派压缩至低维解空间，并在此基础上构建了“问题启发式 Ansatz”，有效降低了求解过程中对量子比特及计算资源的需求。

同期刊出的封面图片直观呼应了该研究：发光的线条与节点展示了增强型量子求解器在由 RSRA 缩减后的计算子区域（而非全搜索空间）内的运行机制。

学术评价与反响

该研究通过大规模数值模拟与超导量子处理器上的实验验证，在特定子句-变量比率区间内，观察到了增强型量子求解器相较于经典基准的经验性标度优势。相关进展在 Research Briefing 中获得了同行的高度评价：

洛斯阿拉莫斯国家实验室 John Golden 指出：该研究通过经典的 RSRA 约化与子空间保持设计，为提升 NISQ 时代组合优化的可行性提供了切实可行的方案。

Nature Computational Science 高级编辑 Jie Pan 评论认为：该工作针对 NP 完全布尔可满足性问题开发了增强型量子求解器，通过大规模模拟与实体处理器实验展示了经验性标度优势，推进了 NISQ 时代量子计算实用可行性的相关研究。

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

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