量子退火算法入门(6):初识量子退火算法的发明过程

薛定谔了么
2024-11-13 18:48:53
本帖最后由 薛定谔了么 于 2024-11-14 10:22 编辑

一、量子计算机

量子计算机就是使用量子bit实现的计算机。之前提到过,可以分为两类,量子门(gate)方式和量子退火(annealing)方式。量子门方式的实现和现代计算机的电子逻辑门很像,比较容易理解,但是需要自己设计逻辑电路,现在开发的算法太少了,而且量子bit容易收到周围环境的影响,噪音比较多。

量子退火方式的话,只能用来解决组合优化问题,但是用户只需要设计QUBO就可以黑盒操作。但是要理解QUBO真正的硬件计算逻辑,还是需要一些物理知识的,本篇就讲一下需要的物理知识。

下面是NTT公司的量子计算指南总结的各种流派。

这个分类我觉得,量子退火机其实还是应该属于Ising machine的。因为,量子退火机解决的还是寻找Ising model的ground state的问题。当然这个分类也不是很重要,大家只要理清楚量子退火方式和Ising model的关系就好了。


用来解决组合优化问题的特殊机器,除了基于激光实现的CIM,还有以下几个:

1.基于一种叫空间光学伊辛机的特殊硬件
2.基于现代计算机电路进行物理模拟的算法(Simulated CIM,Hopfield-Tank,STATICA,Restricted Boltzmann machine)
使用量子退火机解决组合优化问题的步骤如下图所示:


二、模拟退火算法

想理清楚量子退火的物理模型的物理机制,我们要先理解模拟退火算法的原理。

纵轴H 代表需要最小化的Hamilton量,Si代表求解的binary变量,所以Si应该是不连续的,函数曲线不应该是一个平滑的曲线,这里为了方便说明,大家不要误解。

Si模拟退火算法中,有一个和物理温度成反比的参数β 。算法运行时,越过山峰的概率和下面👇的式子成比例。

所以,以下温度的变化过程,也被称作热涨落。

·温度越高,参数β 越小,上面👆的式子的值越大,越过山峰的概率越高;

·温度降到足够低时,越过山峰的概率就很低了,算法就找到一个谷底的最优解。

这里有一个设定,非常重要:

·温度必须降低得足够慢,降低得足够慢,降低得足够慢,模拟退火才可以可靠地获得最优解,但如果温度降低得太快,则可能会陷入局部解中。

三、量子退火算法的物理基础

1. 量子涨落替换热涨落,提出量子退火算法

1998年在东京工业大学的門脇正史(当时在读博士课程)和西森秀稔教授(当时的指导教授)提出了使用基于薛定谔动力学的 Ising 模型作为问题哈密顿量和横向磁场作为量子涨落(fluctuation)项,来替代模拟退火中的热涨落,从而提出量子退火算法。这个研究,只是理论上的探索,当时没有太多人关注。

Tadashi Kadowaki and Hidetoshi Nishimori, "Quantum annealing in the transverse Ising model." Phys. Rev. E 58, 5355 (1998), arXiv:9804280

 

1994年发表的下面👇论文里就出现过Quantum annealing的提法。

Tadashi Kadowaki and Hidetoshi Nishimori, "Quantum annealing in the transverse Ising model." Phys. Rev. E 58, 5355 (1998), arXiv:9804280


其实,在門脇和西森之前,利用量子隧穿效应来寻找自旋玻璃模型本身的最小能态的想法,已经在下文👇里提出了。

P. Ray, B. K. Chakrabarti, and Arunava Chakrabarti, "Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations." Phys. Rev. B 39 11828


下图👇代表,量子退火算法有趣的地方时,m mm个状态,不是独自寻找最优解,它们直接互相干涉,同时去寻找最优解。

量子退火算法中,有一个和模拟退火算法中的物理温度概念相似的概念,叫横向磁场强度。

·横向磁场强度越弱,相邻S i 就会偏向于朝着不同方向,系统能量就越高,各个S i 就各自寻找自己的局部解。
·横向磁场强度越强,相邻S i 就会偏向于朝着相同方向,系统能量就越低,就越容易找到最优解。

和模拟退火算法类似,如果横向磁场强度下降太快,量子退火算法也会找不到最优解。

2. 绝热量子演化解决横向磁场强度缓慢变化

绝热量子计算(AQC:adiabatic quantum computation)是由 Edward Farhi 等人在 2000 年提出的。然而,此时并没有证明通用量子计算是可能的,所做工作与解决组合优化问题的量子退火研究几乎相同。新颖之处在于,作为量子算法提出(和模拟退火无关)和使用绝热定理分析。相关论文如下:

E. Farhi, et al. "Quantum computation by adiabatic evolution." arXiv preprint quant-ph/0001106 (2000)
E. Farhi, et al. "A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem." Science 292, 5516 (2001), arXiv:quant-ph/0104129

 

绝热量子计算和量子退火的关系可以总结为:

绝热量子计算,解决了量子退火算法中的横向磁场强度缓慢变化问题。

3. D-Wave Systems公司实现物理量子退火机

在 2010 年左右,根据的門脇和西森的理论设计,以及Edward Farhi 等人提出绝热量子演化算法,D-Wave Systems Inc. 基于超导量子bit制造出了第一台量子退火机。细节论文,如下:

M. B. Hastings, "The Power of Adiabatic Quantum Computation with No Sign Problem" arXiv:2005.03791

 

总结

该篇总结了量子退火算法的提出过程,以及相关原理。很多细节还没有讲透,后续会把量子退火算法的公式和绝热量子演化的公式讲清楚。
————————————————

本文转载自CSDN博主:gang_unerry

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
                        
原文链接:https://blog.csdn.net/gangshen1993/article/details/127667437

55
0
0
0
关于作者
相关文章
  • 量子退火算法入门(7):QUBO中的三次多项式怎么转换? ...
    前言本文还是大部分截图来自于:《最適化問題とWildqatを用いた量子アニーリング計算入門》 http ...
    了解详情 
  • 量子退火算法入门(5):旅行商问题的QUBO建模「下篇之Python实现」 ...
    一,旅行商问题QUBO的两种实现看过上篇的读者应该已经注意到,因为旅行商问题需要最终返回到初始 ...
    了解详情 
  • 量子退火算法入门(4):旅行商问题的QUBO建模「上 篇」 ...
    了解详情 
  • 量子退火算法入门(3):整数分割问题的QUBO建模
    整数分割问题:QUBO建模最重要的就是,把建模对象中的变量映射为binary(0/1 或者 -1/+1)的变量 ...
    了解详情 
在本版发帖返回顶部
快速回复 返回顶部 返回列表