Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization

在现代计算领域，人们一直在努力解决那些对于标准机器来说过于复杂、而对于最强大的新工具来说又过于僵化的问题。这些被称为约束优化问题，它们出现在从规划配送路线到调度航空公司航班的方方面面。其目标是为许多移动部件找到单一的最佳排列方式，但必须遵守严格的规则；一个虽然节省时间但违反了规则的方案是毫无用处的。最近，科学家们转向了量子计算机，利用奇特的物理定律来同时探索多种可能性。然而，这些机器目前仍具有噪声且并不完美。它们经常产生看起来很有前景但却无法满足问题严格规则的答案，导致研究人员面对大量无法使用的数据。挑战在于，如何在不丢弃其中隐藏的有价值模式的情况下，理解这些有缺陷的输出。

一个研究团队开发了一种新的方法来弥补这一差距，将量子计算机原始、混乱的输出转化为可靠的有效解流。他们并没有试图强迫量子机器直接产生完美的答案，而是将机器的输出视为第二个经典步骤的起点。想象一下，量子计算机就像一个技术精湛但略显笨拙的射手，向靶心射箭。通常，箭会落在牛眼附近，虽然没中靶心，但仍显示出了朝向它的清晰方向。研究人员的方法包括将每一支落在附近的箭轻轻地“推”向靶心。这种“推”是一个固定的数学规则，用于修复箭路径中的任何错误，将一次近失转化为一次完美的命中。通过将这种修复规则应用于每一次射击，该团队发现，量子计算机将箭簇拥在最佳解附近的自然倾向变得足够强大，从而能以比以往认为的更少的尝试次数找到最优解。

这项发现的核心在于一个叫做“前推”（pushforward）的概念，它描述了当每一个结果都通过一个规则进行转换时，概率分布是如何移动的。在他们的工作中，研究人员展示了当量子计算机生成一团可能的答案（其中许多是无效的）时，一个经典的修复过程可以扫过所有靠近一个好解的无效解，并将它们映射到那个好解上。这实际上扩大了目标区域。这意味着量子计算机不需要精准命中某一个特定的完美配置，它只需要命中任何可以被轻松修复成那个完美配置的众多有缺陷的配置即可。这种转变彻底改变了游戏规则。这意味着量子计算机不需要如此精确或在计算上如此深入才能成功，因为经典的修复步骤承担了收集所有分散的、近失尝试并将其整合为单一有效结果的重任。

为了测试这个想法，该团队专注于旅行商问题，这是一个经典的谜题，即旅行者必须恰好访问一次列表中的城市，并返回家中，同时覆盖最短的距离。他们使用一种旨在尊重问题基本结构的量子算法来模拟这一场景，例如确保每个城市都被访问一次，但允许在最终排列中出现错误。当他们将修复方法应用于结果时，他们发现量子计算机正将其概率质量集中在特定的、可以被修复为最佳路径的缺陷答案组上。在涉及十个城市的模拟中，经过修复的量子方法在大约一千次尝试中找到了最优解。相比之下，没有这个修复步骤的原始方法需要一百万次尝试才能达到同样的结果。这种所需尝试次数的大幅减少证明了量子计算机确实保留了关于最佳解的有益信息，即使其原始输出在技术上是不正确的。

研究人员还将他们的方法应用到了一个真实的量子处理器——一台由 IBM 构建的 127 位量子比特机器上，以观察其在面对实际硬件的噪声和误差时的表现。他们在这一物理设备上运行了相同的旅行商问题，该设备比完美的模拟环境要嘈效得多。即使面对真实机器的缺陷，修复过程也成功地将原始的、往往混乱的输出转化为了有效的路径。对于较小的测试案例，修复后的结果与已知的最佳解相匹配。对于更大、更难的案例，修复后的解甚至优于标准软件库提供的参考答案。这证实了该方法不仅在理论或模拟中有效，在现有的不完美硬件上同样有效。关键发现是，量子计算机生成的并非随机噪声，而是一个偏置分布，其中最有用的、可修复的错误聚集在一起，而修复过程能够利用这种偏置来寻找高质量的解。

这项工作为我们在不久的将来如何使用量子计算机提出了新的设计原则。我们不必等待机器变得足够完美以直接解决难题，而是可以构建混合系统，其中量子部分负责执行繁重的探索解空间任务，而经典部分则充当过滤器和修复机制。量子计算机的任务是识别问题空间中最可能包含答案的区域，即使它无法精确锁定确切的答案。随后的经典修复规则则提取这些有希望的区域，并从中提取出最佳解。这种方法将“量子优势”（即在有用区域集中概率的能力）与“经典优势”（即强制执行严格规则和修复错误的能力）分离开来。通过结合两者的优势，研究人员表明，我们可以利用现有的不完美量子硬件，在解决复杂问题方面取得显著改进。

研究还强调了噪声如何影响这一过程。当量子计算机噪声过大时，它会将信息泄露到有效解空间之外，将数据发送到无法修复的区域。研究人员发现，随着这种泄露的增加，修复方法的优势也会减弱，最终使过程变成随机搜索。然而，对于当前机器中存在的噪声水平，该方法仍然非常有效。团队推导出了数学界限，可以预测修复过程能在多大程度上提供帮助，结果显示它可以降低寻找解所需的量子电路深度。这是一个至关重要的细节，因为更深的电路更容易受到误差的影响。通过允许使用更浅的电路，修复方法使得在现有硬件上运行更复杂的任务成为可能，而不至于让结果被噪声破坏。

最终，这篇论文确立了量子采样器在约束优化中的价值，不仅在于它产生的完美答案，还在于其错误的结构。量子计算机创造了一个景观，其中的“错误”答案并非随机散布，而是以特定的方式聚集，指向正确的答案。通过利用这种结构，并通过确定性的修复规则进行利用，我们可以解锁一个单独依靠量子机器或经典计算机都无法实现的性能水平。来自模拟和真实硬件实验的结果提供了强有力的证据，证明这种方法是当前处于噪声中规模量子设备（NISQ）时代实现量子优势的一条可行路径。它将处理不可行输出的问题从一种失败模式转变为一种特性，使研究人员能够依靠量子计算机去做它最擅长的事：找到路径，哪怕它需要一点点帮助来保持在路面上。