量子退火

量子退火（英语：Quantum annealing ）是一种量子漲落特性的次经验演算法，可以在目标函数拥有多组候选解答的情況下，找到全局最优解。量子退火主要用于解決离散空间有多个局部最小值的问题(组合优化问题)，例如寻找自旋玻璃的基态。^[1]

量子退火首先从权重相同的所有可能狀态（候选狀态）的量子疊加态开始运行，接著物理系统依含时薛丁格方程开始量子演化。根据橫向场的时间依赖强度，狀态之间产生量子穿隧，使得所有候选狀态的机率幅不断改变，实现量子并行性。若橫向场的变化速度足够慢，则系统会保持在接近瞬时哈密顿量的基态，此即为绝热量子计算。若橫场的变化速度加快，则系统可能会暫时离开基态，而最终问题哈密顿量的基态将会增加更多的可能性，此即非绝热量子计算(diabatic quantum computation)。橫向场最终被关闭，并且預期系统已得到原优化问题的解，也就是到达相对应的经典易辛模型基态。在最初的理论被提出之后，随即有了随机磁体量子退火成功的实验证明。在一篇关于组合优化（NP困难）问题的介紹中，^[2]列入了基于量子退火演算法的一般结构，用于求解max-SAT，最小multicut问题这类演算法的两个实例，以及D-Wave 系统公司所制造的量子退火系统产品。

与模擬退火法比较

模擬退火法的“温度”参数可以类比量子退火的“隧道场强度”。在模擬退火中，温度決定了从单一当前狀态转移到较高“能量”狀态的概率。在量子退火中，橫向场的强度決定了改变所有并行狀态机率幅的量子力学机率。分析和数值证据表明量子退火在某些条件下优于模擬退火。

类比与优势

隧道场基本上是一个动能项，它不与原始玻璃的经典势能部分交换。整个过程可以利用量子蒙地卡罗(或其他随机技术)在计算机上进行模擬，从而得到寻找经典玻璃基态的启发式算法。

在对纯数学目标函数退火的例子中，可以将这个问题中的变量考慮为经典自由度，而代价函数(损失函数)则对应势能函数(经典哈密顿函数)。然后在哈密顿量中人为引入非交换变量(与原始数学问题变量拥有非零交换子的变量)组成的合適项，以发揮隧道场(动力学部分)的作用。这样就可以用前面构造出的量子哈密顿量(原始函数+非交换部分)进行模擬。退火的效率将取決于选择的非交换项。

在实验和理论上已经证明，在某些情況下，尤其在较浅的局部极小值被非常高但很薄的势壘(成本)围绕的例子中，量子退火确实优于热退火（模擬退火）^{[来源请求]}。因为热跃迁概率(正比于 $e^{-\frac{\Delta}{k_B T}}$ ， $T$ 为温度， $k_B$ 为波茲曼常数)仅相依于能障高度 $\Delta$ ，对于非常高的能障，热波动很难使系统从这样的局部最小值出来，然而在1989年Ray、Chakrabarti和Chakrabarti提出，对相同能障的量子穿隧机率不仅取決于势壘的高度 $\Delta$ ，还取決于它的宽度 $w$ ，机率大约为 $e^{-\frac{\sqrt{\Delta} w}{\Gamma}}$ ， $\Gamma$ 为穿隧场。若势壘够窄(即 $w \ll \sqrt{\Delta}$ )，则量子波动肯定会使系统脫离浅局部最小值，对于 $N$ 自旋玻璃， $\Delta$ 正比于 $N$ ，对于橫向场的线性退火，可以得到退火时间 $\tau$ 正比于 $e^{\sqrt{N}}$ (不同于热退火， $\tau$ 正比于 $e^N$ )，甚至在 $w$ 減少快于等于 $1/\sqrt{N}$ 的情形下，变成与 $N$ 无关的。