如何理解「量子退火」?

一切缘起这篇研究前沿报道 Analogue quantum computers: Still wishful thinking? -- Science…
关注者
2,015
被浏览
327,523
登录后你可以
不限量看优质回答私信答主深度交流精彩内容一键收藏

不邀自来,见识浅薄,还请诸位大神指正。

量子退火法,是一种基于量子特性的量子计算机算法,脱胎于经典计算机上的模拟退火算法。实际上,模拟退火算法的步骤和思路,与金属的退火确实有着异曲同工的妙处。

将金属加温到某个高于再结晶温度的一点并维持此温度一段时间,再将其缓慢冷却。
—— 退火 - Wikipedia

关于通用量子计算机的原理和特性,可以参见我的另一个回答:

量子计算机有什么实际的应用意义? - Cheny Dimpurr 的回答

作为量子退火机应用较多的一种特性,再补充一种神秘的「量子隧道效应」。这种效应一般来说,指的是微观粒子有一定纪律穿过穿过不可能穿越的壁障,出现在壁障的另一端的情况。因为一个微观量子并不存在一个精确的位置,而是以一定概率分布在一片区域,化学上的电子云概念就是这样的。


假设容器的边缘有一个粒子,蓝色的深浅标出了它的德布罗意波,即它可能出现的位置的可能性大小。可以注意到,在很小的几率下,这个粒子会出现在容器的对面。不是漏出,也不是穿过,而是瞬移!但是这也不是瞬移,因为对于电子来说,它本来就有可能出现在那里,只是在你观测的时候,本来存在于一定范围的电子忽然给出了一个正好的容器外的位置。

首先,我们先来看看我们都熟悉的一种贪心算法,爬山算法。

爬山算法指的是以以一个任意值为起始点,计算临近的解,然后不断判断这个解和符合条件的差距,选择选择更适合的方向继续计算,直到达到一个任意方向都是更劣解的位置。


来看看这幅图。假设蓝线的位置就是正解的位置。

首先,一个登山者(计算机)从 FE 段的任意一处出发。对他来说,向下走无疑是更接近正解的。只不过,当他走到了山谷,也就是 E 点时,他会发现:此时无论他往哪边走,都会距离谷底更远!

我们的爬山者被困在山谷底,或者说「势阱」了。

至于模拟退火法,引入了一个随机的扰动,也就是温度 T

我们可以这样来概括它的步骤:

  1. 在值域内,按照随机扰动 Δ ,产生一个一定范围距离的新解
  2. 判断新解和正解的距离,与当前解与新解的距离进行比较
  3. 如果可以接受,那么在当前 T 的范围内,有一定可能性改用新解
  4. 当确定正解在某个区间以内时,缩小范围继续应用模拟退火算法

实际上,就模拟退火算法的具体实现来说这个概括不是很准确。不过这样一来,就可以看出它和爬山算法的最大区别:我们的登山者一次被困在山谷 E 时,他可以选择瞬移到 DC 段的某处,并且惊喜的发现这里更接近正解!在对「整座山」通过统计学方法「退火」时,他就会发现最接近正解的区间 BCD ,从而集中精力在 C 处寻找精确解了。

退火法还有很多有趣的性质,比如初温 T 越高,得到正解的概率也越高,因为此时计算机会更勇敢的选择新解,相当于退火的更彻底。相应的,要达到对「整座山」锁定目标需要的耗时就越长。这个问题,量子退火中就可以得到改善。

那么,这次我们的登山者不同寻常,是一位量子登山者。


看到这幅图也许已经有人明白了:此时这个登山者不仅处在 DE 段上的某一点,其实他「同时」存在于这四周的一大块区域!在它的可能性范围所能触及的区域,他发现了 CD 段上有着更低的一点。利用量子隧道,我们的登山者逃出了山谷!

还不仅仅如此。我们还记得在模拟退火法的第一步上,我们提到了我们会从图像(山脉)的某处开始搜索。但是,因为量子的叠加性质,我们的量子计算元件可以同时处在图中的很多个位置!这样以来,搜索的效率可以以(2 的)指数性增长!

这样优秀(当然,适合处理的问题有所局限)的算法,让我们来看看这个庞然大物, D-Wave Two 是怎么实现的。

首先,在合适的环境下,制备好一系列量子比特。 D-Wave Two 拥有 128 个量子比特。

接着,为这些量子设置好三维的伊辛模型,也就是设置好他们的初始位置和自旋状态。这个初始模型就决定了接下来的计算,可以说就是编好的程序。

随后,减弱量子间的相互作用,通过向超导电路通入特殊电流,向设置好的模型施加一个横磁场。这种情况下,量子就进入了自旋的叠加状态,相当于同时具有 0 和 1 状态的比特。

最终,我们进行「退火」。我们慢慢撤去横磁场,增强相互作用,最终,量子们稳定下来,我们得出了最终解。

就像别的答案中提到的,量子退火机就是让大自然自己去进行计算,我们等着看结果:最终稳定下来的量子,一定是在这个三维伊辛模型中,相互间能量很小的状态。意即只要模型设置得当,我们就有非常大的机率落到最低的「山谷」当中。

因为算法本身基于统计学而非遍历的性质,我们可以理解,即使量子退火算法在模拟退火算法的基础上提高了算力,还是有只得出近似解的情况存在。因此, D-Wave Two 据说会针对每次计算任务重复 4000 次,选择其中的最优解得出解答。



最终,和大家预想的不一样, Dwave Two 确实「只是」一台量子退火机。在吭哧吭哧工作时,还得全程由液氮保护运行在 0.02 K,也就是 -273.13 ℃ 下。不过,相比经典计算机,量子退火机还是在特定领域达到了上万甚至上亿倍的算力提升。我们可以期待,一个真正的通用量子计算机,将会给科技行业乃至人类智慧带来极大的革命。