近日，清华大学物理系龙桂鲁教授联合北京量子信息科学研究院、数学工程与先进计算国家重点实验室及新加坡南洋理工大学的研究人员开展合作，在量子计算求解复杂性难题领域取得重要进展。团队通过开发增强型量子求解器，在NP完全问题“1-3可满足问题（1-in-3 SAT）”的求解中，观测到量子计算明确的经验性标度优势（Empirical Scaling Advantage）。2026年6月19日，相关成果以“增强型量子求解器在一类NP完全问题上的扩展优势证据”（Evidence of scaling advantage on an NP-complete problem with enhanced quantum solvers）为题，发表于《自然·计算科学》（Nature Computational Science）。
当前量子计算机处于有噪中等规模量子（NISQ）阶段，无法对量子算法复杂度进行解析证明，因此判断量子优势的核心依据是“经验性标度优势”——即随着问题规模扩大，量子计算资源的增长速率显著慢于经典算法。然而，在最具挑战性的NP完全问题量子求解中，始终缺乏有说服力的实验与数值实证，难以切实证明量子计算的加速效果。
针对这一领域难题，研究团队提出“限制空间约化算法（Restricting Space Reduction Algorithm, RSRA）”，并基于该算法构造出增强型可满足（SAT）问题量子求解算法。其核心创新点包括：（1）优化量子资源配置，实现搜索空间的最优约化，将搜索空间维度从O (2n )有效降低至O (2(n-m) )，大幅提升量子求解器效率；（2）利用RSRA构建“问题启发式拟设（Problem Heuristic Ansatz）”，确保量子态始终处于含解子空间，简化问题哈密顿量，有效规避变分量子本征解（VQE）中常见的“贫瘠高原（Barren Plateaus）”问题。
a. 限制空间约化算法（RSRA）及其在1-3可满足问题量子求解器中的应用：RSRA将1-3可满足问题的约束放宽为“三取奇”约束，并将原问题重新表述为解空间放宽的2-SAT问题，进而得到有效的哈密顿量H与问题启发式拟设。b. 原始量子求解器与增强型量子求解器的对比：上半部分展示原始求解器采用的标准拟设，下半部分展示增强型求解器基于RSRA构建的拟设。
研究团队通过理论分析、规模达150个变量的大规模数值模拟，以及实体量子计算机的实验验证，明确发现：在经典求解器常遭遇性能瓶颈的“临界子句-变量比率”范围m/n ∈[0.55，0.75]内，新构造的增强型量子求解器展现出优于现有最优经典算法的指数级标度性能。该工作为结构化NP完全问题在现实约束下的量子加速提供了新思路，标志着量子求解器在处理复杂逻辑约束问题上迈出关键一步。
该论文第一作者为清华大学博士生陆全枫、北京量子信息科学研究院副研究员魏世杰；通讯作者为量子院副研究员魏世杰、助理研究员曾进峰、清华大学物理系教授龙桂鲁。龙桂鲁教授作为全文末位通讯作者，统筹指导全部研究工作。论文合作者还包括深圳大学助理教授李可仁、量子院助理研究员高攀、数学工程与先进计算国家重点实验室闫宝、清华大学博士生郑沐曦、新加坡南洋理工大学博士后张浩然。该工作得到北京市科技新星计划和国家自然科学基金等项目的支持。
原文链接：https://www.nature.com/articles/s43588-026-01007-8
