量子退火
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此条目需要补充更多来源。 (2023年7月21日) |
![]() | 此条目可参照英语维基百科相应条目来扩充。 (2023年7月21日) |
量子退火(英语:Quantum annealing)是一种量子涨落特性的次经验算法,可以在目标函数拥有多组候选解答的情况下,找到全局最优解。量子退火主要用于解决离散空间有多个局部最小值的问题(组合优化问题),例如查找自旋玻璃的基态。[1]
量子退火首先从权重相同的所有可能状态(候选状态)的量子叠加态开始运行,接着物理系统依含时薛定谔方程开始量子演化。根据横向场的时间依赖强度,状态之间产生量子穿隧,使得所有候选状态的几率幅不断改变,实现量子并发性。若横向场的变化速度足够慢,则系统会保持在接近瞬时哈密顿量的基态,此即为绝热量子计算。若横场的变化速度加快,则系统可能会暂时离开基态,而最终问题哈密顿量的基态将会增加更多的可能性,此即非绝热量子计算。横向场最终被关闭,并且预期系统已得到原优化问题的解,也就是到达相对应的经典易辛模型基态。在最初的理论被提出之后,随即有了随机磁体量子退火成功的实验证明。在一篇关于组合优化(NP困难)问题的介绍中,[2]列入了基于量子退火算法的一般结构,用于求解max-SAT,最小multicut问题这类算法的两个实例,以及D-Wave 系统公司所制造的量子退火系统产品。
与模拟退火法比较
[编辑]模拟退火法的“温度”参数可以模拟量子退火的“隧道场强度”。 在模拟退火中,温度决定了从单一当前状态转移到较高“能量”状态的概率。 在量子退火中,横向场的强度决定了改变所有并发状态几率幅的量子力学几率。 分析和数值证据表明量子退火在某些条件下优于模拟退火。
模拟与优势
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/12/Quant-annl.jpg/300px-Quant-annl.jpg)
隧道场基本上是一个动能项,它不与原始玻璃的经典势能部分交换。整个过程可以利用量子蒙地卡罗(或其他随机技术)在计算机上进行模拟,从而得到查找经典玻璃基态的启发式算法。
在对纯数学目标函数退火的例子中,可以将这个问题中的变量考虑为经典自由度,而代价函数(损失函数)则对应势能函数(经典哈密顿函数)。然后在哈密顿量中人为引入非交换变量(与原始数学问题变量拥有非零交换子的变量)组成的合适项,以发挥隧道场(动力学部分)的作用。这样就可以用前面构造出的量子哈密顿量(原始函数+非交换部分)进行模拟。退火的效率将取决于选择的非交换项。
在实验和理论上已经证明,在某些情况下,尤其在较浅的局部极小值被非常高但很薄的势垒(成本)围绕的例子中,量子退火确实优于热退火(模拟退火)[来源请求]。因为热跃迁概率(正比于,为温度,为波兹曼常量)仅相依于能障高度,对于非常高的能障,热波动很难使系统从这样的局部最小值出来,然而在1989年Ray、Chakrabarti和Chakrabarti提出,对相同能障的量子穿隧几率不仅取决于势垒的高度,还取决于它的宽度,几率大约为,为穿隧场。若势垒够窄(即),则量子波动肯定会使系统脱离浅局部最小值,对于自旋玻璃,正比于,对于横向场的线性退火,可以得到退火时间正比于 (不同于热退火, 正比于 ),甚至在 减少快于等于 的情形下,变成与无关的。
据推测,在量子计算机中,这种模拟比传统计算机更精确有效,因为它可以直接执行穿隧而不需手动添加。 此外,因为没有用到传统量子算法中所用的量子纠缠,它可在不这么严格的错误控制下完成工作。
参见
[编辑]参考资料
[编辑]- ^ P Ray, BK Chakrabarti, A Chakrabarti. Sherrington–Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations. Phys. Rev. B 39, 11828 (1989). [2018-10-10]. (原始内容存档于2021-05-11).
- ^ S.E. Venegas-Andraca, W. Cruz-Santos, C. McGeoch, and M. Lanzagorta. "A cross-disciplinary introduction to quantum annealing-based algorithms". Contemporary Physics Vol. 59, Issue 02, pp. 174–196 (2018). (原始内容存档于2019-07-01).