钉子の次元

Dimpurr – 千里之行,始於足下。

如何用圈外人士能理解的文字解释「量子退火」?

此回答由本人原载于知乎:如何用圈外人士能理解的文字解释「量子退火」? – Cheny Dimpurr 的回答 – 知乎

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

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

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

关于通用量子计算机的原理和特性,可以参见我的另一个回答:量子计算机有什么实际的应用意义? – Cheny Dimpurr 的回答

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

d55d83bb687b4d982f0287f2974ea76e_b

量子隧道效应

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

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

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

b3c44a2f3adaf1b87a54906de4d85be4_b

解的示例图像

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

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

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

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

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

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

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

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

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

e7501a8947c1198bf4944280f095ccaa_b

量子登山者

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

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

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

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

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

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

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

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

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

b0063796af646363f4d2c4748ee7faed_b

D-Wave Two

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

  1. wicast说道:

    自叹不如!!有种智商被碾压的感觉……

  2. 宅醬说道:

    什麼“我們都熟悉的一種貪心算法啊”(
    這在同齡人中哪有人會啊(
    ((我還是去當大老師算了 TAT

  3. mooc说道:

    你为啥对这个感兴趣?

    1. Dimpurr说道:

      …… 因为感觉真心很奇妙很酷炫吧。所谓理性之美,不管是设计、信息科学、物理学、数学等等,都是共通的。
      这周末又花了一个周末研究康托尔对角线法解图灵停机问题,于是决定下周再码一篇科普文 ((

      1. mooc说道:

        我和你有些不同,大部分时候是为了达到某种目的…

        1. Dimpurr说道:

          我倒是曾经认真想过这个问题。比如说学习技术,学习编程和前端,终点是什么?为了做出一个作品么?那么做出作品又是想得到人气、喝彩或是金钱?最后我的答案是,这些并不重要,我还是喜欢做本身「有趣」的事情,这样。

          1. mooc说道:

            你是对的。我羡慕你。我的客观条件不允许我奢求自由。

            1. Dimpurr说道:

              说实话我倒是挺好奇这个「客观条件」是什么 ……
              以高中来说时间可能略显紧张,那么大学也还会有机会。求知是无止境的,人生毕竟并不是就是考完大学考研找工作。共同加油。