💡这项突破是什么?
近日，北京量子信息科学研究院（以下简称“量子院”）量子算法应用研发团队与清华大学等单位合作，在量子计算求解复杂性难题领域取得重要进展。通过开发增强型量子求解器，在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）”问题。
图1 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
