← 最新论文
⚛️ 量子物理

Proven optimality for LABS with quantum-classical branch and bound

本文介绍了一种量子-经典分支定界算法,该算法利用固定角度的 QAOA 采样来解决低自相关二进制序列(LABS)优化问题,在不依赖量子加速的情况下,成功证明了序列长度高达 30 时的全局最优性,并提供了认证的下界和收敛指标。

原作者: András Czégel

发布于 2026-11-20
📖 1 分钟阅读🧠 深度阅读

原作者: András Czégel

原始论文采用 CC BY 4.0 许可(http://creativecommons.org/licenses/by/4.0/)。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性,请参阅原始论文。 阅读完整免责声明

在现代技术的隐藏架构中,存在着一类被称为低自相关二进制序列(low autocorrelation binary sequences)的数学难题。这些并非抽象的奇思妙想,而是我们进行通信和感知世界的基石。当雷达系统发送脉冲以探测飞机时,或者当数字信号同步手机连接时,它依赖于一种特定的正负值模式。这种模式的质量决定了系统是看到一个清晰的目标,还是看到一团混乱的虚假回波。目标是寻找一个其内部重叠(即相关性)尽可能小的序列。这是一个极其困难的问题,类似于在数十亿个参差不齐的针头中寻找一根完美光滑的针。几十年来,计算机一直难以证明它们已经找到了绝对最佳的模式,通常只能在不知道是否存在更好方案的情况下,满足于一个非常好的猜测。

研究员安德拉斯·切格尔(András Czégel)现在展示了一种能够以绝对确定性解决这一问题的方法,该方法采用了一种结合了经典计算与量子采样(quantum sampling)的混合手段。这项工作并不声称比现有的最佳传统方法更快;事实上,作者明确指出并没有速度上的提升。其成就之处在于“证明”。通过将量子算法嵌入到一个严谨的经典搜索框架中,该团队证明了长度为 2 到 30 的序列的最优解。这是一个重要的里程碑,因为以往针对该问题的量子尝试只能找到优秀的序列,却永远无法保证它们是最优的,也无法衡量一个猜测距离完美还有多远。这种新方法提供了一个最优性证书(certificate of optimality),即一份数学保证,证明不存在更好的序列,并能精确测量搜索随时间收敛的过程。

该方法的核心是“分支定界”(branch and bound)策略,这是一种通过切断死路来系统性探索可能性的方法。想象一棵向四面八方生长的树,每一条分支代表着对序列中某个值的设定决策。经典计算机通常会在这种树上行走,通过检查边界来判断某条分支是否可能产生更好的解。如果一条分支看起来“代价过高”,它就会被剪枝掉。切格尔的创新之处在于,他在这个经典树结构中植入了一个量子采样器,具体来说是一个定角量子算法(fixed-angle quantum algorithm)。在每一个必须做出决策的节点处,量子采样器都会对可能性的景观进行快速观察。它并不解决整个问题,而只是提供一个目前为止发现的最佳候选方案,并建议下一步该探索哪条路径。随后,经典计算机利用这些建议来引导搜索,同时利用自身的严格数学规则来修剪树枝并验证最终结果。

这种混合方法的测试结果涵盖了长度达 30 的序列。对于该范围内的每一个长度,该算法都成功证明了最优能量值,这意味着它确认了没有任何其他序列能拥有更低的平方相关性之和。该过程在不同的设置下进行了测试,包括深度为 12 和深度为 1 的量子采样器。在深度较大的设置中,量子采样器在许多情况下能立即找到最佳解,从而让经典部分能够专注于证明不存在更好的解。对于较长的序列(特别是长度在 27 及以上的序列),研究人员发现主要问题在于量子采样器无法直接处理如此庞大的规模,因此他们在采样之前,先基于对称性将问题拆分为较小的、可处理的部分。即使在这些复杂的情况下,系统依然返回了最优性的认证证明。

研究还仔细考察了量子采样器究竟对成功做出了怎样的贡献。事实证明,采样器的主要价值在于过程早期找到最佳解的能力。一旦找到了最佳解,量子采样器对于下一步路径的建议并不总是能改进搜索;在某些情况下,简单的随机选择或固定规则的表现甚至与之持平或更好。这表明量子采样器并不是一个能瞬间解决谜题的魔杖,而是一个帮助经典计算机更快找到目标的工具,从而让严谨的证明机制接管工作。研究人员在无噪声计算机上运行了模拟,同时也模拟了系统在真实量子硬件(如来自 IBM 和 Quantinuum 的设备)上的表现。他们发现,虽然目前的硬件尚不足以高保真度地处理最大规模的问题,但该方法在存在噪声时依然有效,因为算法的经典部分提供了最终的正确性证明。

这项工作代表了评估量子算法方式的一种转变。与其仅仅竞逐于尽可能快地找到一个好答案,这里的重点在于提供一个经过验证、经过认证的答案。研究人员记录了整个搜索过程,测量了在每一时刻最佳解与理论下界之间的差距。这个“原对偶积分”(primal-dual integral)充当了算法效率的计分卡,展示了算法缩小可能性范围的速度。研究证实,量子采样可以集成到精确算法中,从而为那些此前只能由启发式算法或无法通过量子手段验证的经典方法所解决的问题,提供最优性的证明。虽然目前解决的问题范围仅限于长度 30(远低于目前最佳经典方法达到的 66),但概念验证是明确的:量子算法现在可以交付一份真相的证书,而不不仅仅是一个猜测。

您所在领域的论文太多了?

获取与您研究关键词匹配的最新论文每日摘要——附技术摘要,使用您的语言。

试用 Digest →