量子退火是一种利用量子涨落来搜索系统低能量构型的计算方法。它将优化问题表示为能量函数,解越好,对应的能量就越低。系统从有利于制备某个量子态的初始条件出发,其相互作用逐渐调整,最终变为表示待求问题的相互作用。演化结束后,通过测量得到候选解。与基于量子门的量子计算机不同,量子退火机通常通过连续调控物理相互作用来实现这一演化过程,而不是执行一系列离散的逻辑操作。
这种方法将量子力学、统计物理学和数学优化联系起来。其核心出发点是,包括隧穿在内的量子跃迁,在探索某些复杂的能量景观时,可能采取不同于经典热搜索的路径。量子退火既被用作优化技术,也被用来研究相互作用的量子系统。其性能取决于具体问题、演化方案、环境效应和物理实现方式;仅有量子行为的存在,并不足以证明它具有计算优势。
起源与发展
量子退火源于寻找具有多种竞争相互作用的系统中低能态的研究。在受挫磁性系统中,满足一种相互作用可能会妨碍另一种相互作用得到满足,从而产生大量局部能量极小值。调度、图划分及其他离散优化问题中也会出现类似的数学结构。这种联系使统计物理学的方法在优化算法的发展中产生了尤为重要的影响。
量子退火在经典方法上的一个重要先驱是模拟退火。斯科特·柯克帕特里克、C. 丹尼尔·格拉特和马里奥·韦基在1983年一项影响深远的研究中,将模拟退火引入了优化领域。这种方法借鉴了通过冷却使材料趋向低能构型的思路。在较高的有效温度下,搜索过程可以接受使目标函数值增大的变动;随着温度降低,此类变动出现得越来越少。这提供了一种逃离局部极小值的机制,而纯粹的贪心方法则可能陷于其中。量子退火使用量子涨落来替代或补充热涨落,并通过横向磁场等参数来控制量子涨落。
早期的几项研究从不同方面奠定了这一思路。1994年,A. B. 芬尼拉及其合作者将量子退火描述为一种求多维函数最小值的方法。1998年,门胁正和西森秀稔分析了横场伊辛模型中的退火过程,这一表述后来成为相关研究的核心。他们的工作比较了无序自旋系统中减弱量子涨落与经典冷却的效果。J. 布鲁克及其同事于1999年发表的实验研究,探索了无序磁性材料 中的量子退火,将这一计算方案与实验室中对缓慢磁弛豫的研究联系起来。
与之密切相关的一项发展是绝热量子计算。爱德华·法希及其合作者于2000年提出了这一方法,并于2001年发表了一项关于可满足性问题的研究。这种方法强调让系统以足够缓慢的速度演化,使其始终跟随某个低能瞬时本征态。此后,量子退火逐渐成为一个更宽泛的术语,既涵盖近似绝热的方案,也包括有限时间、有限温度以及刻意采用非绝热演化的方案。
商业化开发主要围绕 D-Wave Systems 公司展开。该公司于2011年推出的 D-Wave One 系统以配备128量子比特处理器为卖点。后续几代系统增加了物理量子比特的数量,并提高了连接度,其中包括2020年推出、拥有超过5,000个物理量子比特的 Advantage 系列。这些机器使研究人员能够开展可编程退火实验,其规模超出了小型实验室演示的水平。它们的发展也进一步凸显了三种主张之间的区别:观测到量子效应、在某项特定基准测试中取得改进,以及确立普遍的计算加速优势——这三种主张各自需要不同类型的证据。
能量函数与退火哈密顿量
标准的数学描述采用随时间变化的哈密顿量,即确定系统能量并生成其量子演化的算符。一种常见形式为
其中, 为退火时间。驱动哈密顿量 产生量子涨落,而问题哈密顿量 则编码优化目标。通常,在退火过程中, 逐渐减小, 逐渐增大。它们的具体形式、端点值以及可用的控制范围取决于所用的设备或算法。
对于伊辛型优化问题,问题哈密顿量通常写为
这里, 是作用于量子比特 的泡利矩阵,其测量所得的本征值为 。系数 指定局部偏置,而 指定两两相互作用。在这一符号约定下,正的 倾向于使 和 取相反值;负值则倾向于使二者取相同值。读出所有量子比特后,就会得到一个经典构型,其目标函数值可以直接计算。
常用的驱动项是横场,
由于 与 不对易,这一项会引发经典构型之间的跃迁。其基态是各量子比特上两个计算基态的等权叠加态的直积。尽管这一初态很简单,退火过程中的相互作用却可以产生量子纠缠和强关联态。随着驱动项减弱,最终的测量结果会越来越多地反映由 定义的经典能量景观。
在理想的孤立系统中,演化遵循薛定谔方程,
这一方程描述的是概率幅,而不是在不同构型之间移动的经典轨迹。能量景观的图像有助于形成直观理解,但其中的谷地和势垒表示的是定义在离散构型上的目标函数,不一定对应真实的空间势能。
哈密顿量的整体尺度具有重要的物理意义。将目标函数的所有系数乘以一个正常数,虽然不会改变数学上的最小值点,却会改变能量差相对于温度、控制噪声和可用演化时间的尺度。因此,两个在数学上等价的目标函数,在硬件上可能表现不同。所以,退火调度、系数归一化和驱动项强度都是计算方法的组成部分,而不仅仅是实现细节。
绝热演化、隧穿与热动力学
量子绝热定理为缓慢退火提供了理想化的理论依据。在适当条件下,如果系统的哈密顿量变化得足够缓慢,那么初始处于非简并基态的系统就会始终接近瞬时基态。一个核心量是基态与第一激发态之间的谱隙:
谱隙较小通常会使绝热演化的实现条件更加苛刻。所需时间的界限还取决于哈密顿量的导数、跃迁矩阵元、边界条件以及期望达到的精度;不存在仅凭最小谱隙就能确定运行时间的通用公式。
避免交叉现象说明了这一困难。随着退火参数变化,两个低能态可能彼此接近,却不会变得完全简并。如果系统过快地穿越这一区域,就可能有一部分布居转移到激发态。在某些问题族中,最小谱隙会随着变量数增加而呈指数级缩小。此时,即使采用量子力学,沿基态演化的策略也可能需要指数级长的演化时间。
量子隧穿提供了另一种互补的理解图景。越过势垒的热激活过程大致受到因子 的抑制,其中 是势垒高度。隧穿不仅取决于势垒的高度,还取决于其宽度和形状。这表明,对于某些热搜索难以跨越的高而窄的势垒,隧穿可能具有优势。不过,在自旋问题中,“宽度”涉及不同构型之间的变化,往往牵涉多个自旋。在某一种势垒几何形状下具有优势,并不意味着在包含许多相互竞争的瓶颈的完整优化实例中也具有优势。
实际的退火器还会与周围环境相互作用。量子退相干、能量弛豫和热激发使它们成为开放量子系统,而不是薛定谔方程所描述的完全孤立系统。当相关谱隙与 相当或更小时,热跃迁就可能显著影响各态布居。弛豫有时能使布居回到较低能态,而热激发则可能使布居离开这些态。因此,相干时间短本身并不能排除量子辅助跃迁的可能性,但在没有进一步证据的情况下,也不能将整个计算过程视为理想的相干演化。
另一个效应是动力学冻结:相对于退火进程的剩余时间,相关态之间的跃迁变得过于缓慢。于是,最终输出所反映的可能是退火较早阶段形成的布居分布,而非最终哈密顿量下的热平衡分布。暂停、改变退火速率以及采用其他演化路径,都可以改变这些布居分布。一些有效的方案会有意允许非绝热跃迁,因此,实际效果最佳的退火调度未必是最慢的。
优化问题的编码
许多退火流程以二次无约束二元优化问题(简称 QUBO)为起点:
通过代换 ,可以将这一目标函数转化为伊辛能量,其中 。这一转换会改变系数并引入一个常数偏移,但使目标函数取最小值的变量赋值之间仍保持对应关系。因此,QUBO 形式和伊辛形式是表示同一类二元二次问题的两种常见接口。
约束通常通过惩罚项来表示。如果一组二元变量必须满足
则可以在目标函数中加入一个非负惩罚项
由于 ,该表达式仍是二次式。当且仅当恰好选中一个变量时,它的值为零;其他情况下均为正值。类似的构造也可用于编码资源限制、分配要求和一致性条件,有时还会使用辅助二元变量来表示整数松弛量。
惩罚强度的选择至关重要。如果 太小,违反约束反而可能使加上惩罚项后的目标函数值更优。如果它大得没有必要,就可能需要压缩整个系数范围以适应硬件限制,从而缩小可行解之间的物理能量差。因此,正确建模不仅要得到代数上成立的表达式,还需要在约束的有效施加与精度、噪声及有限温度的影响之间取得平衡。
图问题提供了一些直观的例子。在加权最大割问题中,每个顶点都被赋予一个自旋;当一条边两端的自旋不同时,这条边就计入割中。对于非负边权 ,割的权值为
最大化 等价于最小化相应的伊辛目标函数。调度问题的编码通常没有这么直接,例如,可能需要为每一种作业与时间的分配组合设置一个二元变量。即使尚未考虑物理实现,这些编码也可能引入大量变量和相互作用。
通过引入辅助变量和一致性惩罚项,有时可以将高阶目标函数化为二次形式。只有在归约构造正确且惩罚足够强时,才能保留原优化问题的某些特定性质。额外的变量既会增大逻辑问题规模,也会增加嵌入成本。许多相关问题具有NP难性,但将它们表示在退火器上并不会消除这种困难:输出仍然只是一个候选解,其质量和可行性都必须经过评估。
计算能力及其与经典计算的关系
量子退火并不等同于通用量子计算。在适当的构造下,一般的绝热量子计算可以用多项式开销模拟标准的电路模型。这种等价性适用于表达能力足够强的哈密顿量和受控演化;它并不意味着,相互作用种类受限的商用退火机能够高效执行任意量子电路。可用的耦合、控制精度、几何结构、态制备和测量方式都很重要。
对于横场伊辛退火机而言,这一区别尤为重要。它们的哈密顿量在计算基下通常是非正非对角型的:非对角矩阵元均为实数且不大于零。这种结构在某些路径积分蒙特卡罗表述中避开了通常的符号问题,使一些实用的经典模拟方法成为可能,但并不保证模拟能够高效进行。采样过程的混合速度仍可能非常缓慢,而复现量子的实时动力学,可能远比表示平衡态统计权重困难。
一种用于比较的经典方法是模拟量子退火,它通常使用量子蒙特卡罗方法,对与退火哈密顿量对应的平衡分布进行采样。它无需在量子硬件上运行,也能捕捉量子涨落的某些影响。不过,它的算法动力学并不是量子退火机的物理动力学。在基准测试中表现相近,可能说明存在有用的经典解释或有竞争力的经典方法;但这并不能证明两者具有相同的微观机制。
其他比较对象包括传统的模拟退火、并行回火、分支定界法、整数规划和专用图算法。它们各自的优势取决于问题结构。退火机与简单的局部搜索相比可能表现出色,却仍可能慢于针对问题专门设计的经典求解器。因此,讨论计算复杂性时,需要关注具体任务、实例族以及资源需求如何随规模增长,而不能只看某次计算是否利用了量子效应。
退火也不同于那些具有显著量子加速效果的电路算法。肖尔算法利用了算术问题的结构和傅里叶变换,而格罗弗算法则为无结构搜索提供了查询次数上的平方级优势。对于任意目标函数,缓慢减小横场并不会自动实现这两种算法中的任何一种。为问题构造低能态编码,并不等于为该问题构造了高效的量子算法。
对于优化任务,所关注的结果可能是精确解、近似解,也可能是能量低于目标值的样本。这些任务的难度和验证要求各不相同。计算返回的变量赋值所对应的能量通常很容易;证明不存在更好的赋值则可能困难得多。目前并没有一般性定理证明,标准量子退火能够高效求解所有 NP 难优化问题。
物理硬件与连接性
最知名的可编程量子退火器采用超导电路,工作温度在数十毫开尔文量级。一种常见实现使用磁通量子比特,以环流状态作为两个计算态。外部控制可调节局域能量偏置、相互作用以及态间的隧穿振幅。这些器件属于更广泛的超导量子比特家族,不过其设计和工作区间与许多基于量子门的超导处理器有所不同。
可编程耦合器用于实现两两相互作用。耦合器的物理布局决定了硬件连接图:只有在存在适当耦合器的地方,两个变量才能直接相互作用。D-Wave 的 Chimera 架构将量子比特组织为彼此连接的单元,每个单元内部采用二分图连接结构;后来的 Pegasus 架构则提高了连接度。物理量子比特数量庞大,并不意味着能够直接表示规模同样大的任意逻辑图。
将逻辑图映射到稀疏硬件图上,往往需要进行图子式嵌入。一个逻辑变量由一组相互连通的物理量子比特表示,这组量子比特通常称为一条链,并通过强铁磁相互作用尽量保持同向排列。链间的耦合实现逻辑相互作用。这使稀疏硬件的使用更加灵活,但也会消耗量子比特,并在计算中引入额外的选择。
链强度带来了实际的权衡。链过弱可能会断裂,导致同一逻辑变量的物理表示不一致。链过强则可能迫使所编程的问题系数相对于器件的可用范围缩小。因此,解码也成为求解器的一部分:对于断裂的链,可以通过多数表决,或采用考虑能量的经典方法来确定其取值。嵌入方式、链强度和解码方法都可能改变测得的性能。
模拟硬件中的非理想因素会影响实际实现的哈密顿量。偏置偏移、耦合器误差、串扰、漂移以及有限的系数精度,都可能扰动所编程的目标函数,尤其是在相关能量差很小时。校准可以减轻这些影响,但无法将其消除。自旋反转变换,即改变选定自旋的符号并相应调整系数,使得逻辑等价的问题实例能够以不同的物理形式编程实现。汇总这些运行的结果,可以降低对某些系统性偏差的敏感性。
其他实验平台,包括囚禁离子和中性原子,也支持相关的模拟演化过程和优化问题编码。这些平台的原生相互作用和控制方式与超导量子退火器不同,因此必须结合实际实现的模型来解读结果。对各种平台而言,提升实际可用的求解能力都不只是增加物理量子比特数量:连接性、噪声、控制分辨率和可复现性共同决定了哪些逻辑问题仍在可处理的范围内。
编程工作流程与退火协议
典型的工作流程始于数学建模,而不是向硬件提交任务。首先将目标函数和约束条件转化为二次二元形式,进行化简和缩放,并用小规模实例检验其正确性。随后,将处理器无法直接支持的相互作用嵌入处理器的连接图中。软件接口将系数和退火调度设置发送给设备,并接收多组测量得到的构型,通常还会同时返回相应的能量和出现次数。
重复采样至关重要,因为退火过程具有随机性。即使编程设置完全相同,也可能返回不同的变量赋值,其中包括激发态,以及在采用惩罚项的模型中仍不满足约束的无效解。因此,必须对样本进行解码,依据原始约束进行检验,并按原始目标函数排序。经典后处理可以修复违反约束的解,或改进局部选择。这类处理作为实用求解器的一部分是合理的,但应将其贡献与量子硬件的贡献区分开来。
正向退火从较强的驱动项出发,逐渐演化至问题哈密顿量。反向退火则从选定的经典构型出发,在退火进程中先增强量子涨落,随后再将其减弱。这样便可在当前最优解附近进行探索。它并不只是把正向退火倒放:初始化方式和完整的调度过程共同决定最终的搜索行为。因此,将反向退火作为迭代式经典—量子工作流程的一部分加以研究很有价值。
暂停和淬火提供了额外的控制手段。暂停使系统保持在退火调度的某个中间位置,可能使系统得以弛豫,或使各状态之间的占据分布重新调整。快速淬火则使系统迅速趋向适于测量的终点,但这一过程本身也可能改变各状态的占据概率。在硬件支持的情况下,还可以为各个量子比特设置单独的退火偏移,改变它们各自经历的退火时序。这些控制手段有助于研究瓶颈,但也引入了需要调节的参数;调参时必须避免使某种基准测试方法获得不公平的优势。
大型应用通常采用分解方法。经典控制器选出一个规模足够小、可由退火器处理的子问题,固定其余变量或对其进行概括表示,调用设备,再将返回的解与规模更大的当前最优解结合起来。其他混合方法则将退火器与种群搜索、禁忌搜索或数学规划协同使用。即使所求解的逻辑问题规模远超硬件容量,这样构建的求解器仍然可以发挥作用。
要厘清这类系统中各部分对性能的贡献,需要精心设计实验。一种有用的测试方法是保留工作流程的其余部分,用性能强劲的经典子求解器替换量子组件。这有助于将问题分解、预处理和软件工程带来的价值,与量子演化可能带来的价值区分开来。同样,处理器退火时间、编程时间、重复读出开销、网络延迟和经典处理耗时也应分别报告。
基准测试与量子加速
有意义的性能声明必须明确具体任务。可能的任务包括寻找基态、达到目标函数的指定值、生成多样化的低能构型,或从指定分布中采样。退火求解器可能在某项任务上表现良好,在另一项任务上却表现不佳。例如,反复返回同一个优质构型或许有助于优化,却不适合要求相对概率准确的采样应用。
对于固定目标,常用的指标是求解时间。如果各次独立运行的成功概率为 ,那么要达到预期的累积成功概率 ,所需的运行次数为
将 乘以单次运行时间,即可得到基本估计。实际部署时,可能还需要计入编程、读出、解码和通信等额外耗时。样本之间的相关性、设备漂移,以及成功概率估计中的不确定性,都可能使这一计算变得复杂。
退火时间本身也应经过优化。延长退火时间可能提高成功概率,但也会减少固定预算内可进行的尝试次数。反过来,如果将固定的短时退火与调优不充分的经典方法进行比较,也可能呈现出表面上的规模扩展优势。公平的研究应采用可比的流程来调优各个求解器,并将用于调优的实例与用于评估的实例分开。此外,还必须明确随机实例的生成方式、精度要求以及成功的定义。
相比单一的耗时比,规模扩展表现更有参考价值。关于量子加速的声明,取决于随着问题规模或难度增加,所需资源相对于适当的经典基准如何变化。它也取决于比较的范围:优于某个选定的经典算法,远不如优于现有最佳经典方法有说服力。有限规模的实验可以揭示重要行为,但不足以确立渐近意义上的结论。
问题实例的结构尤其重要。专门设计为包含狭窄势垒或特定隧穿事件的问题,可以用于检验物理机制。相比之下,工业问题可能包含可供预处理、分解或专用优化方法利用的规律。根据任务的不同,强有力的经典基准方法可能包括并行回火、团簇更新、张量网络方法或精确求解器。经典计算中的图形处理器加速和并行计算也会影响实际比较结果。
纠缠、隧穿或与量子模型相符的证据,能够证实设备行为的某些方面,却不会自动证明其计算性能优于经典方法。反过来,在某项基准测试中未观察到加速,也不意味着不存在量子效应。这些是彼此独立的实验问题,需要分别进行测量并设置对照。
在优化、采样和物理学中的应用
优化是量子退火最受关注的应用领域。研究原型已将交通路径规划、生产调度、图划分、投资组合选择、设施选址和资源分配建模为退火问题。这些问题是否适合用量子退火求解,在很大程度上取决于编码开销。能够用紧凑的二元二次模型表示的任务可能天然适用,而细致的调度约束或较大的数值范围则可能需要大量辅助变量和惩罚项。
实际评估必须保留原始任务的要求。例如,路径规划模型为了得到可实现的 QUBO(无约束二元二次优化)形式,可能会近似处理行程时间、将可选方案离散化,或省略实际运行中的约束。精确求解这一 QUBO,并不一定意味着能以同样的标准解决原始路径规划问题。因此,比较时应评估原始应用中的可行性和目标函数表现,并将任何修复流程纳入考量。展示一种编码方案是重要的第一步,但并不能证明端到端的优势。
采样是另一种用途。应用所需要的可能不只是寻找最低能量,而是获取大量具有特定统计性质的构型。平衡态模型会赋予各构型如下形式的概率:
其中, 为配分函数,。实际退火器产生的样本不一定遵循由所设定的最终能量函数给出的这一分布:非平衡演化、冻结、残余量子效应和控制误差都可能产生影响。因此,用有效温度拟合得到的描述是一种有待检验的模型,而非可以自动成立的表征。
这一问题在机器学习中尤为重要。研究人员已探索利用退火器训练玻尔兹曼机等基于能量的模型,这些模型的学习过程可能需要从难以采样的概率分布中获取样本。退火器也被用于探索特征选择及其他组合子问题。这些应用面临经典采样算法和经过优化的数字硬件的竞争。实际效用取决于采样质量和总训练成本,而不仅仅是生成设备读出结果的速度。
可编程退火器也可作为多体物理的实验平台。研究人员可以在有控制地改变相互作用的条件下,研究无序磁体、受挫晶格、自旋玻璃行为和非平衡动力学。在这类研究中,目标可能是复现或探索某种物理过程,而不是优化某个工业目标。相关可观测量包括关联、缺陷密度、响应函数,以及相变附近的标度行为。
这类实验将量子退火与量子模拟联系起来。某种处理器即便在通用优化方面不具优势,仍可能为特定量子模型提供有用的物理实现。其科学价值因而取决于控制的保真程度、可获取的可观测量,以及在能够进行比较的参数区间内,能否通过理论或可信计算来验证其结果。
局限与当前研究问题
核心的未决问题是:计入现实成本后,量子动力学究竟能在哪些情形下带来可重复的计算优势。这比“退火器是否具有量子特性”的问题更具体,又比“它能否快速求解某个选定的基准问题”的问题更宽泛。要给出有意义的刻画,就必须明确相关问题实例的结构、所需资源,以及这种优势在与哪些经典方法比较时依然成立。
一个研究方向是改变演化路径,而不仅仅是延长演化时间。额外的驱动相互作用或中间“催化”项可以改变避免能级交叉和相变。研究者探索了非化学计量型(nonstoquastic)相互作用,希望借此改变难以处理的动力学过程;这类相互作用不再保持标准的非正非对角元形式。此类修改可以改善特定模型的表现,但实现起来更困难,也不能普遍保证优化速度更快。
另一个方向关注噪声与保护。物理冗余、一致性检查和能量惩罚可以减轻某些特定的误差机制。这些思路不同于容错电路架构中使用的完整量子纠错。同样,嵌入链也不会自动成为这种意义上受到保护的逻辑量子比特:它的主要作用是在连接受限的器件上,用多个物理量子比特表示一个变量。评估任何保护方案时,都必须考虑它额外消耗的量子比特、耦合和控制资源。
模拟精度是另一个独立的规模扩展难题。随着逻辑问题规模增大,即使量子比特数量充足,在物理器件上实现预期的目标函数也可能变得更加困难。系数的微小扰动就可能改变近简并构型的能量排序。鲁棒建模力求在此类扰动下仍能保留有用的解,而校准和统计技术则试图减轻这些扰动的影响。数学上的条件性与硬件误差之间的相互作用,仍是实际问题设计中的重要考量。
验证同样取决于任务。对于返回的构型,可以检查它是否违反约束,并计算其能量,但要确认全局最优性,通常需要独立的界或证书。对于采样任务,验证关注的是分布性质,而不只是低能量。对于规模超出经典方法可处理范围的多体动力学,研究者会综合利用小系统结果的一致性、极限情形、对称性、独立可观测量以及跨平台比较来进行验证。
针对退火调度学习、反向退火、连接性改进、更完善的开放系统模型和混合算法的研究也在持续推进。每个方向都针对不同的潜在瓶颈:棘手的能谱结构、环境诱发的跃迁、嵌入开销,或低效的流程协调。因此,衡量进展的依据是具体能力与受控比较,而不只是物理量子比特的数量。