当前位置: 首页 > > 天 方 夜 “谈” 第7期 | D-wave:量子退火解决图着色问题

天 方 夜 “谈” 第7期 | D-wave:量子退火解决图着色问题

发表于:2020-03-18 20:48 作者: 方滨兴班 阅读数(6439人)

内容来源于论文:Adversarial Examples: Attacks and Defenses for Deep Learning

发表在IEEE TRANSACTIONS ON NEURAL Programming with D-Wave: Map Coloring Problem

第一作者是E. D. Dahl,来自D-wave项目团队

文章地址:https://www.dwavesys.com/

Ⅰ. 问题

量子计算机利用量子比特(qubits)来保存信息。每一个量子比特的行为都受量子力学定律的控制,使量子比特处于“叠加”状态——即,同时是0和1,直到外部事件导致它“崩溃”为0或1。这一性质与我们在宏观世界中的日常经验不同,但它是构建量子计算机的基础。利用这一特性,量子计算机能够快速解决某些复杂问题,如优化、机器学习和采样问题。量子计算机的编程与传统计算机的编程有很大的不同。为了使用量子计算机进行编程,用户需要将一个问题映射到搜索“广袤空间的最低点”中,而最低点与最佳可能结果相对应。本文描述了使用D-wave量子计算机解决图着色的方案。

图片.png

图1:加拿大地图

如图所示这是一幅加拿大地图,我们要解决的问题是为地图上每一个区域着色,使得我们可以使用肉眼区分每一个区域。这要求共享同一边界的两个区域不可以拥有相同的颜色。该问题可以分为三步解决:

1.使用量子比特表示一个区域的颜色

2.实现相邻区域之间颜色不同的约束

3.将解决方案扩展到整个问题

Ⅱ. 定义

我们必须首先介绍对我们的编程模型至关重要的概念。第一个这样的概念是量子比特,它是最终取值为0或1的变量(如q)。D-wave系统有许多量子比特,所以我们经常用下标来标记我们的量子比特:图片.png。量子计算机不允许编程人员直接设置这些量子比特的值。但是,我们可以影响量子比特,而D-wave系统对我们提供的影响作出反应。我们如何影响量子比特?有两种方法。首先,与每个量子比特相关联的是一个权重,它是每个QMI的一部分,并且是程序员控制的一部分。我们用符号图片.png来表示与量子比特图片.png相关的权重。第二种方法依赖于耦合的概念,它允许我们控制一个量子比特对第二个量子比特的影响。一个耦合总是用两个量子比特来精确的标识,所以我们说耦合连接了量子比特。正如一个权重与每一个量子位相关一样,我们将一个强度与每一个耦合器联系起来。如果耦合器连接量子比特图片.png图片.png,则用图片.png表示耦合器的强度。             

既然我们已经定义了量子比特、权重、耦合强度,我们可以写下一个目标函数,该目标函数将权重(图片.png)、强度(图片.png)和量子比特(图片.png)的值作为输入,返回一个目标值,有时更简单地说是一个目标:

图片.png

而我们的工作是将问题的各种可能的解决方案编码到量子比特变量图片.png中的一个优化问题。然后我们将优化问题中的约束转化为权重图片.png和强度图片.png的值。当目标最小化时,量子比特图片.png就是我们需要的解决方案。下面我们将利用这种方法解决开始时提出的问题。

设c为颜色数。为每个区域使用可能的颜色的一元编码,将C量子比特分配给地图的每个区域。如果将第i个颜色指定给一个区域,那么与该区域相关联的第i个量子比特将具有值1,而与该区域相关联的其他C-1量子比特将具有值0。这种编码规定了构建目标函数所需的三个步骤。

Ⅲ. 单区域填充颜色

我们首先给一个区域着色。根据4色定理我们知道我们需要4种颜色,即需要解决的4个量子比特中只有一个为1。这里将问题简化,首先解决了打开两个量子比特中的一个的简单问题。对于双量子比特系统,目标是:

图片.png

列举分布中的四种可能状态(见表1)。我们的任务是选择图片.png图片.png图片.png值,使我们的解决方案由图片.png=0和图片.png=1的状态以及图片.png=1和图片.png=0的状态组成。其他两种状态中,两个图片.png均等于0或两个图片.png均等于1,不应出现在我们的解决方案中。

表1:双量子比特系统的四种状态,加上目标

图片.png

我们很容易找到约束图片.png=图片.png=-1,图片.png=2,目标函数取最小值时有图片.png=1或图片.png=1两种情况,满足打开两个量子比特中的一个。我们将其推广到4个量子比特。对于4量子比特系统,我们选取图片.png=图片.png=图片.png=图片.png=-1,图片.png=图片.png=图片.png=图片.png=图片.png=图片.png=2,目标函数取最小值时有图片.png=1,图片.png=1,图片.png=1,图片.png=1四种情况,满足打开四个量子比特中的一个。

图片.png

图2:基本单元

由于在D-wave中采用的是Ising模型。所以在物理结构上去寻找四个节点的全连接图是不可能的。我们尝试将每个节点对应到两个实际物理量子比特上,我们就可以得到如上图所示的结构图,而该结构图在D-wave是可以实现的。首先考虑节点内的双量子比特系统,很明显这里要求量子比特同时为1或0表示一个节点是否打开,从上面两节点状态表中我们可以轻易得知我们只需选取图片.png=图片.png>0,图片.png<0即可。这时我们需要考虑如何将双量子比特系统对应至节点上,由于对于完全图的4量子比特系统,我们只需要让每个节点的权重为-1,节点间的耦合强度为2,即可达到我们的目标,而每个节点对应着两个实际物理量子比特,在这里需要将节点的权重和耦合强度均分至每一个物理量子比特上。那么对应着每个量子比特权重为-1/2,耦合强度为1。由于节点的权重最终结果是叠加得到的,为了方便计算,我们设定节点内两个实际的物理量子比特权重为1/2,耦合强度为-1。这时我们就可以用一个8量子系统来表示一个区域颜色的选择,其中量子比特的权重为0,表示同种颜色的量子比特之间的耦合强度为-1,表示不同种颜色的量子比特之间的耦合强度为1。

Ⅳ. 临近单元约束

图片.png

图3:邻近单元连接图

接下来我们需要实现相邻区域不同颜色的约束,我们可以在d-wave中实现上图的连接方式。而这种连接方式使得完成区域间约束变得十分容易。我们要求相邻区域颜色不能相同,也就是说区域连接的两个量子比特不能同时为1。根据上面对双量子系统分析,我们只需要设定量子比特的权重为0,耦合强度为1即可。

V. 约束扩展到整个区域

图片.png

图4:D-wave单元阵列

最后一步,我们需要将约束扩展到整个解决方案,在D-wave中整个单元可以如上图所示连接起来,看起来像一个棋盘,所以我们将加拿大地图区域连接关系也简化成这种棋盘模式,如下图所示,但我们发现NT周围有超过4个区域与其相连接,需要使用多个颜色单元表示一个区域,这就要求多个颜色单元使用同一种颜色。从上文的双量子系统的分析可知,我们只需将对应单元权重增加1,耦合强度设为-2即可。

图片.png

图5:加拿大13个区域到D-wave单元阵列的一部分的映射

到这里我们已经完成将问题映射至D-wave可以处理的退火算法,我们只需添加对量子比特的约束,当我们的系统处于能量最低点时,该系统的解便是我们所需的解。

关于 天 方 夜 “谈”

天方夜谈原意讲不切实际的东西,而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。

方班人有自己的浪漫,

我们探讨知识,谈论理想,

采摘科研的繁星,

脚下是星辰大海。

天:代表我们的理想犹如天空般浩荡

方:代表方班

夜:代表代码人的冷静与静谧

谈:代表方班愿与您,就领域内的经典思想和前沿成果“秉烛夜谈”