近日，北京量子信息科学研究院（以下简称“量子院”）量子算法应用研发团队与清华大学等单位合作，在量子计算求解复杂性难题领域取得重要进展。通过开发增强型量子求解器，在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 (2 ⁿ )有效降低至 O (2 ^(n-m) )，极大提升了量子求解器的效率；（2）利用 RSRA 构建启发式拟设（ Problem Heuristic Ansatz ），确保量子态始终在含解子空间，简化问题哈密顿量，有效规避了 VQE 求解中常见的“贫瘠高原（ Barren Plateaus ）”问题。

研究团队通过理论分析、规模达150个变量的大规模数值模拟以及实体量子计算机的实验验证，明确发现：在经典求解器常遭遇性能瓶颈的临界子句-变量比率范围m/n ∈[0.55，0.75]内，新构造的增强型量子求解器展现出优于现有最优经典算法的指数级标度性能。该工作为结构化NP完全问题在现实约束下的量子加速提供了思路，标志着量子求解器在处理复杂逻辑约束问题上迈出了重要一步。