内容来源于论文：Adversarial Examples: Attacks and Defenses for Deep Learning
发表在IEEE TRANSACTIONS ON NEURAL Programming with D-Wave: Map Coloring Problem
第一作者是E. D. Dahl，来自D-wave项目团队
量子计算机利用量子比特（qubits）来保存信息。每一个量子比特的行为都受量子力学定律的控制，使量子比特处于“叠加”状态——即，同时是0和1，直到外部事件导致它“崩溃”为0或1。这一性质与我们在宏观世界中的日常经验不同，但它是构建量子计算机的基础。利用这一特性，量子计算机能够快速解决某些复杂问题，如优化、机器学习和采样问题。量子计算机的编程与传统计算机的编程有很大的不同。为了使用量子计算机进行编程，用户需要将一个问题映射到搜索“广袤空间的最低点”中，而最低点与最佳可能结果相对应。本文描述了使用D-wave量子计算机解决图着色的方案。
图1：加拿大地图
如图所示这是一幅加拿大地图，我们要解决的问题是为地图上每一个区域着色，使得我们可以使用肉眼区分每一个区域。这要求共享同一边界的两个区域不可以拥有相同的颜色。该问题可以分为三步解决：
1.使用量子比特表示一个区域的颜色
2.实现相邻区域之间颜色不同的约束
3.将解决方案扩展到整个问题
我们必须首先介绍对我们的编程模型至关重要的概念。第一个这样的概念是量子比特，它是最终取值为0或1的变量（如q）。D-wave系统有许多量子比特，所以我们经常用下标来标记我们的量子比特：
。量子计算机不允许编程人员直接设置这些量子比特的值。但是，我们可以影响量子比特，而D-wave系统对我们提供的影响作出反应。我们如何影响量子比特？有两种方法。首先，与每个量子比特相关联的是一个权重，它是每个QMI的一部分，并且是程序员控制的一部分。我们用符号
来表示与量子比特
相关的权重。第二种方法依赖于耦合的概念，它允许我们控制一个量子比特对第二个量子比特的影响。一个耦合总是用两个量子比特来精确的标识，所以我们说耦合连接了量子比特。正如一个权重与每一个量子位相关一样，我们将一个强度与每一个耦合器联系起来。如果耦合器连接量子比特
和
，则用
表示耦合器的强度。
既然我们已经定义了量子比特、权重、耦合强度，我们可以写下一个目标函数，该目标函数将权重（
）、强度（
）和量子比特（
）的值作为输入，返回一个目标值，有时更简单地说是一个目标：
而我们的工作是将问题的各种可能的解决方案编码到量子比特变量
中的一个优化问题。然后我们将优化问题中的约束转化为权重
和强度
的值。当目标最小化时，量子比特
就是我们需要的解决方案。下面我们将利用这种方法解决开始时提出的问题。
设c为颜色数。为每个区域使用可能的颜色的一元编码，将C量子比特分配给地图的每个区域。如果将第i个颜色指定给一个区域，那么与该区域相关联的第i个量子比特将具有值1，而与该区域相关联的其他C-1量子比特将具有值0。这种编码规定了构建目标函数所需的三个步骤。
我们首先给一个区域着色。根据4色定理我们知道我们需要4种颜色，即需要解决的4个量子比特中只有一个为1。这里将问题简化，首先解决了打开两个量子比特中的一个的简单问题。对于双量子比特系统，目标是：
列举分布中的四种可能状态（见表1）。我们的任务是选择
、
和
值，使我们的解决方案由
=0和
=1的状态以及
=1和
=0的状态组成。其他两种状态中，两个
均等于0或两个
均等于1，不应出现在我们的解决方案中。
表1：双量子比特系统的四种状态，加上目标
我们很容易找到约束
=
=-1，
=2，目标函数取最小值时有
=1或
=1两种情况，满足打开两个量子比特中的一个。我们将其推广到4个量子比特。对于4量子比特系统，我们选取
=
=
=
=-1，
=
=
=
=
=
=2，目标函数取最小值时有
=1，
=1，
=1，
=1四种情况，满足打开四个量子比特中的一个。
图2：基本单元
由于在D-wave中采用的是Ising模型。所以在物理结构上去寻找四个节点的全连接图是不可能的。我们尝试将每个节点对应到两个实际物理量子比特上，我们就可以得到如上图所示的结构图，而该结构图在D-wave是可以实现的。首先考虑节点内的双量子比特系统，很明显这里要求量子比特同时为1或0表示一个节点是否打开，从上面两节点状态表中我们可以轻易得知我们只需选取
=
>0，
<0即可。这时我们需要考虑如何将双量子比特系统对应至节点上，由于对于完全图的4量子比特系统，我们只需要让每个节点的权重为-1，节点间的耦合强度为2，即可达到我们的目标，而每个节点对应着两个实际物理量子比特，在这里需要将节点的权重和耦合强度均分至每一个物理量子比特上。那么对应着每个量子比特权重为-1/2，耦合强度为1。由于节点的权重最终结果是叠加得到的，为了方便计算，我们设定节点内两个实际的物理量子比特权重为1/2，耦合强度为-1。这时我们就可以用一个8量子系统来表示一个区域颜色的选择，其中量子比特的权重为0，表示同种颜色的量子比特之间的耦合强度为-1，表示不同种颜色的量子比特之间的耦合强度为1。
图3：邻近单元连接图
接下来我们需要实现相邻区域不同颜色的约束，我们可以在d-wave中实现上图的连接方式。而这种连接方式使得完成区域间约束变得十分容易。我们要求相邻区域颜色不能相同，也就是说区域连接的两个量子比特不能同时为1。根据上面对双量子系统分析，我们只需要设定量子比特的权重为0，耦合强度为1即可。
图4：D-wave单元阵列
最后一步，我们需要将约束扩展到整个解决方案，在D-wave中整个单元可以如上图所示连接起来，看起来像一个棋盘，所以我们将加拿大地图区域连接关系也简化成这种棋盘模式，如下图所示，但我们发现NT周围有超过4个区域与其相连接，需要使用多个颜色单元表示一个区域，这就要求多个颜色单元使用同一种颜色。从上文的双量子系统的分析可知，我们只需将对应单元权重增加1，耦合强度设为-2即可。
图5：加拿大13个区域到D-wave单元阵列的一部分的映射
到这里我们已经完成将问题映射至D-wave可以处理的退火算法，我们只需添加对量子比特的约束，当我们的系统处于能量最低点时，该系统的解便是我们所需的解。
关于 天 方 夜 “谈”
天方夜谈原意讲不切实际的东西，而这里想要 “脚踏实地”真正弄懂并感受一篇文章的思想。
方班人有自己的浪漫，
我们探讨知识，谈论理想，
采摘科研的繁星，
脚下是星辰大海。
天：代表我们的理想犹如天空般浩荡
方：代表方班
夜：代表代码人的冷静与静谧
谈：代表方班愿与您，就领域内的经典思想和前沿成果“秉烛夜谈”
