初尝量子计算开放果实

IBM、D-Wave相继开放其量子计算平台，分别介绍其“求15的质因数”与“地图填色问题”官方案例，以体验与传统开发之间差异。

一、引子：佳果香腮尚未绯^[1]

当今两大领跑者IBM与D-Wave(Google联合NASA采购过其计算机)，已先后对其量子计算能力进行了部分开放或开源^[2][3]（分别为去年5月、今年1月）。

受其“诱惑”笔者近两个月到相关园子里做了一圈调查体验（注：笔者与大多数IT从业者一样，在量子计算、量子物理方面背景为零），三句话概括当前感受的话：

• 果甚香
• 果未甘
• 有藩篱

2015年Google曾实测D-Wave 2X（1000+个量子位）量子退火方式计算机，对规模为1000比特的问题，相比用传统硬件模拟退火算法要快上10^8倍^[4]。这种退火(Annealing)方式能将一部分NP-Complete复杂度问题转换为多项式复杂度，具体通过将问题先编写/映射成QMI指令再物理作用到量子比特上的方式来进行，本文中将以官方文档中的“地图填色问题”为例做体验式介绍。而在更高级的机器学习图像识别领域，Google也已公开过实绩^[5](2009年)。

IBM则采用了更为通用的量子门设计模式，能对一元二元乃至多元量子比特做相当于经典逻辑门的计算。这种Universal的架构，能用于处理Shor算法这样在已知量子算法中堪称复杂而最具实际价值的问题——因为它能用来攻破当今数字安全基石RSA加密的数学核心、即“大质因数分解”；本文也将介绍IBM官方文档中“求15的质因数”的实例。不过IBM通用设计仍只实现了5个量子位^[6]，据称几年内将达到50位、实现“量子霸权”(即计算力超过地球所能容纳的最大传统计算机 注:未考虑DNA NUTM计算机)。

那么为什么两家要先后对这一尖端、高价值的研究成果予以开放呢？

答案是“生态圈”。尽管量子计算已经取得了一定成果，但距离实用商业化还有较长一段距离(4_{5年[^MIT_enval])；而如读者很快将领略到的，量子计算与传统开发之间存在着极大差异（如果不是说完全不同的话}~），且仍处于比传统汇编语言更初级的阶段。佳果虽好，尚未绯红，要让更多传统人才加入量子计算领域、研究出更多算法/应用，尽快提升自家果园的成熟度的话，开放，应该会是一个多赢的选择。

限于调查时间，文章主干之外一定还会存在未尽问题，将以“#延伸思考#”标签标识；而限于篇幅，对于主干内容之外的关联知识，也将标记“#扩展阅读#”标签、或提供外部链接方式。

二、果园外的藩篱

即便只是想要一睹佳果芳泽，都需翻越过几片并不算低浅的藩篱，

1. 需一定的量子物理知识

量子力学(Quantum Mechanics)奠基人费曼和波尔都曾告诫过自己学生，“不要问为什么，而只要搞清楚量子力学允许你去做什么”，此后100多年大家确实只是照着这样做、就已收获了丰硕果实：

• 电子一脉：晶体管、电脑、手机…
• 光子一脉：激光
• 其他：能源、核聚变

可另一方面，先贤的话也确实界定了量子力学的理解难度——尤其是因为其有违直觉(counter-intuitive)，后文将会择要讲解理解量子计算所需的两个量子力学知识：

• 量子叠加态（superpostion）
• 量子纠缠（entanglement）

1. 缺乏中文资料
   量子力学的普及文章是有的，但截至发稿为止、尚未见到对两大阵营开放平台的较为深入的中文评测、对比。
   因此，文中也会适当出现英文用语以便于扩展阅读、及避免歧义。

2. 对缺少数学背景的开发者来说较为头痛的数学算式
   主要是线性代数，但很多又是专门用来表征“有违直觉”的量子力学的，如狄拉克符号、布洛赫球面、贝尔不等式，足以令心智不坚者却步。好在相关的英文版维基百科更新得很完整及时，可供查证。

3. 概念多多，却缺乏系统逐级深入的资料（即便是英文的院系教程），需自行筛选整理才能深入

循着笔者的足迹，可望以尽量短的路径穿越过这些藩篱。

三、D-Wave的量子果园

D-Wave果园坐标（依照推荐足迹顺序）

• qbsolv Example: mapColoringUSStates - D-Wave开源工具官方范例@GitHub，只需编译运行
• Quantum Computing Primer - D-Wave - 只需读1.3、1.4
• Software Architecture - Dwave
• Programming with D-Wave: Map Coloring Problem - 四色问题编程详解

3.1 第一站，qbsolv工具范例

只需搭建有cygwin/unix + python + make环境（qbsolv需被make），就能轻松执行起demoStates.sh观看退火算法(模拟器)得出的结果，

• 输入：美国51州的关联定义usa.adj，空白美国地图blank_US_state_map.svg
• 输出：已填色美国地图usa.qbout.xaa.svg，中间文件usa.qubo,usa.qbout

图3-1 D-Wave qbsolv工具范例“美国地图填色”运行结果

四色问题属于NP-Completed复杂度问题，传统专业课必教、易于描述但却神秘（19世纪提出至今未获人工证明），很适合用来展现量子计算的能力。

最初GitHub上的这个官方Sample运行结果还不正确，提交Bug后修改了usa.adj文件中两个州的邻接关系解决了问题。

3.2 第二站，“开关组游戏”讲解QUBO问题

紧接着第二站，Quantum Computing Primer的1.3节、1.4节给出了简单易懂的“开关组游戏”例子，简而言之，就是我们要能令如下算式取得最低值的x序列解，

QUBO问题：求令此算式取最低值的x解（Q为矩阵，x为向量）

D-Wave的退火式量子计算最擅长解决的这种QUBO问题^[7]（二次非约束二进制优化，目前有简述成“离散最优化”的），可更直观的表述为下图，

![图3-2 开关组游戏 - 求weight、strength矩阵乘积最小解(出处^[8])](http://upload-images.jianshu.io/upload_images/80770-341d139d60e4c3d9.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

引入两个概念就能解释这个游戏，

• 权重(weight)：由每个开关上的数字标识，相当于QUBO算式中的Qii，当该开关打开时将计入合计值
• 强度(strength)：由两个开关之间的数字标识，相当于QUBO算式中的Qij，当两个开关均打开时将计入合计值

在D-Wave官方资料中，会对weight、strength命名为h、J，或是a、b、以及Qii、Qij，请注意其实质即可。

问题在于，这样的一个图论“游戏”，是无法简单求解的，而只能暴力求解（对每个开关尝试开或关），也就意味着NP复杂度(=O(2^N))，在10个开关时还算好，当有100个开关时、尝试次数就已暴涨到1,267,650,600,228,229,401,496,703,205,376(=10^30)！

据估算，此游戏的开关数达到500个时，传统计算机就得计算到宇宙末日了……

奇妙的地方来了。

3.2.1 量子叠加态 - 初阶简易理解

在量子计算机中，最基本的单元——量子比特(quantum bit，简称qubit)，或者说上述游戏中的“开关”，是“同时”以1(开)或0(关)方式存在的。没错，你可以把这段话多读上几遍。

这就是研读量子计算所需涉及的两个量子力学主题中的一个——叠加态(superposition)。量子力学是那么的“有违直觉”(counter-intuitive)，所幸这个简化版的解释已足够了解D-Wave的例子了。

你只需看作，这些量子“开关”在犹豫不决于它们该处于何种状态，对于给定的如前图的“开关组游戏”，传统情境下还需要人工逐一去遍历尝试，而在微观量子情境下，所有的可能性已经同时并存在那里了！而退火机制则提供了一种方式，通过施加然后撤除特定的“权重、强度”磁场（即Q矩阵，参照QUBO算式）、量子“开关”进入然后又脱离叠加态、决定自己“开”或“关”（称为“坍缩”），最终整体安定于一个“最低能量状态”，也就求得了QUBO问题的最优解或次优解（QC Primer - 1.4）。IBM的量子门机制则留待后述。

重要的一点，量子计算机的结果是概率式(probabilistic)的，不同于传统计算机的决定式(deterministic)。也就是说运行几百或几千遍，重复出现次数最高的、才是“最优解”中真正的最优。当然这种额外开销对于10^30这样的传统计算指数级成本来说可以忽略，而且作为副产品的“次优解”、对很多研究来说恰恰是大有用处的。

“没有对比就没有伤害”，100个开关时， 原本需高达10^{30次的遍历*(O(2}N))，使用100个量子开关，1次经过控制的“坍缩”就可能解决；因此核心问题已经转变成、如何将目标问题转换成QUBO问题？*

纠正：目前不少非专业新闻中报导量子计算之所以性能卓著是因为“除了0、1之外，还能表示‘0或1’状态”（于是…三进制?），纯属讹传。

#扩展阅读#　如果不介意额外切换出去20分钟，有一个经典实验更具体的再现了“叠加态”、量子的这种“犹豫不决”，那就是双缝干涉实验。（关键语句：“电子同时通过了两条狭缝，然后，自己和自己发生了干涉！”）

3.3 第三站，软件架构（Software Architecture）

原文浓缩为下图，只需看QUBO的部分。

![图3-3 D-Wave软件架构(出处^[9])](http://upload-images.jianshu.io/upload_images/80770-1c45ced451ef3c92.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

具体到开源的qbsolv“美国地图填色”范例，目标问题(这次是地图填色，而非开关组了)、也需要被表征为一个QUBO问题或者说QUBO矩阵，具体是通过adj2qubo.py，将美国51州相邻关系数据转成了usa.qubo文件，其格式非常简单：

c 中间文件usa.qubo，表征了一个Q矩阵，将成为qbsolv工具的输入
c AK <--- c打头为注释行，AK是州名缩写
 0 0 -1 <--- 定义权重Qii，所以前两位相等，第三位即权重值
 1 1 -1 
 2 2 -1 
 3 3 -1 <--- 注意用4个物理位来定义一个逻辑节点（4色）
c AK 1 neighbors 4 external couplers <--- 注释，将定义AK内部连接
 0 1 2 <--- 4个物理位之间的穷举连接
 0 2 2 
 0 3 2 
 1 2 2 
 1 3 2 
 2 3 2 
c AK linked to HI <--- 注释，将定义AK与HI之间连接
 0 40 1 <--- 定义强度Qij，前两位为关联qubit序号，第三位即强度
 1 41 1 
 2 42 1 
 3 43 1 

这个Q矩阵将会被神秘(但已开源)的qbsolv工具用模拟退火算法生成一个最优解usa.qbout（本例中是204个量子位的序列，每个州需用4个位表征，原理后述），如果开启qbsolv的-r seed随机种子，还能获得不同的解。最终plotmap.sh将被用来基于usa.qbout对空白美国地图SVG文件填色。

那么，adj2qubo.py又是按照什么算法基于一份地区相邻关系数据、决定出QUBO矩阵中权重与(连接)强度的取值的呢？

3.4 第四站，官方编程手册四色问题详解

最后一站，会略有烧脑情节。

限于篇幅精力只做简述，以便体会“目标问题如何转为QUBO问题”。如需开发解决新问题，还请参考原文。

如何通过设置Q矩阵使得目标命题的要求条件被蕴含其中，从而在最终QUBO算式的最低能量解“火退石出”(退火)时、让X向量自动指向目标命题的解呢？

• QUBO算式：f(x) = SUM(Qii Xi) + SUM(Qij Xi Xj)，退火能在给定Q矩阵情况下、自动调整X向量、取得最低值解

• Q矩阵：Qii=节点i的权重，Qij=节点i,j之间连接的强度
• X向量：Xi=节点i，经典态下取1或0

方法一，通过预设特定的Qii、Qij，使得不合适的量子比特Xi组合无法成为最低值解

观察两个qubit(量子比特)X1,X2的情况，f(x) = Q1*X1 + Q2*X2 + Q12*X1*X2（权重Qii简化表示为Qi，后同）。

• 当X1=X2=0时，f(x)=0。只需设置Q1<0, Q2<0就能使得这种情况被排除（即其他解永远会比0取值更低）
• 当X1=X2=1时，如果想把这一种相等情况也排除，该怎么设置？
  使得Q1 + Q2 + Q12 = 0就能排除了！
• 综合而言，不妨令Q1=-1, Q2=-1，然后Q12=2就能排除X1=X2

这就是最简单的，满足了“两个量子比特有且仅有一个为1”这一要求条件的Q矩阵取值；而这一条件，就可以被映射到“四色问题”中“一个地区有且仅有一色有效”这样的命题条件上（可自行计算，4个qubit或更多时设置Qii=-1, Qij=2仍能满足该条件）。

回顾前文的usa.qubo中权重与内部连接的取值，是不是正是-1与2。任意一个地区(如AK)也都需要4个qubit来表征（代表四种颜色）。

方法二，用两个以上物理位(chain)表征一个逻辑位，一组逻辑位(unit cell)表征一个命题对象，进一步设置对象间连接的强度值

![图3-4 地区的物理比特表征，及地区间不同色命题条件表征(出处^[10])](http://upload-images.jianshu.io/upload_images/80770-bdc7ca7abd6d890a.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

我们先看左侧、即一个地区，竟然用了8个“qubit”来构成。可其实你只需要记得这是“考虑到了硬件可行性”的物理qubit，每排的2个物理qubit会映射到一个逻辑qubit、这才是usa.qubo中定义的一个节点。而这种由4个逻辑qubit（合成1个unit cell）表征的地区，还能进一步连接到其他地区（如右侧）满足“不同色逻辑关联”(命题条件)的需求。

#扩展阅读#　用多个而非一个物理qubit来映射一个“逻辑qubit”，是由需在表征命题对象的逻辑qubit组内部建立起“完全连接”（每两个位之间都有连接）的需求决定的。硬件上无法直接对4个qubit建立完全连接，可参看硬件概述 1.1、1.2中的图解。

几个要点：

• chain的内部取平均值
  用来表征一个逻辑qubit的多个物理qubit被称为chain，chain内的物理位的权重是要取平均值的(e.g.-0.5)，与其他chain之间的连接强度也取平均值(e.g.1)。若使用qbsolv工具的话已经无需关注物理位映射逻辑位问题了。
• “一个地区有且仅有一色”条件的满足
  这个之前已讲过，具体到上图(3-4)，就是4个chain(即逻辑qubit)之间的连接强度取值为2，4个逻辑qubit各自的权重取值为-1即可。
• “相邻地区间不同色”条件的满足
  读者可先自行思索一下如何设置Q矩阵。
  这个命题条件的实质，可以表达为“当某一色在一侧被采用，且在另一侧也被采用时，对QUBO算式加入惩罚值”；上图(3-4)中的每个跨地区连接、连接了代表本地区取相应颜色的逻辑位，因此是一个2 qubit的算式，在Q1=0, Q2=0, Q12=1时，两侧都取相同颜色的情况就会遭受f(x)=1的惩罚。Q1=0, Q2=0不影响既有值，因此只需设置代表地区间连接的Qij=1即可。可检查usa.qubo是否是这样。

方法三，用多个unit cell的合并(clone)表征特殊的命题对象

首先请注意在qbsolv范例的usa.qubo文件中并没有看到这种合并(clone)，可能是qbsolv中的算法已能自动解决了。

![图3-4:2 采用clone来表征与四个以上州有连接的州（加拿大地图，出处^[10]）](http://upload-images.jianshu.io/upload_images/80770-f5f6aece95048046.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

官方编程手册3.4节中的这张图显得未免繁琐——对于有4个以上接壤州的“大州”、竟然需要象“华容道”一样人工编排各州的位置、来使得用2个unit cell合并出的“大州”能获得正确的相邻关系表征？所幸是在qbsolv工具的.qubo文件中、solve.c中都已不再看到相关内容。如果需做这种“clone”(合并)的话，使得两个逻辑位权重为1、连接强度为-2就能达到“合二为一”的效果。

另外，当QUBO矩阵大到硬件环境不能接受时，可以被分割成subQUBO逐一解决、再合并得出结果^[7](参见qbsolv中的solve.c)。

※※※※※※※※

D-Wave的量子果园采摘日便至此告一段落。

如上可知，D-Wave的量子计算机具有一定局限性，不过对于能用QUBO算式表征的课题确实性价比很高，硬件方面最新已推出了高达2,000量子比特的四代机(2017/1/25)^[11]。

#延伸思考#　退火方式对目前机器学习开发带来的改变。这方面官方虽没有提供范例，但早已有了实际成果^[5]。对于能转换成QUBO矩阵的问题、可采用“四色问题”的办法，机器学习则属于不能人工给出Q矩阵的，怎么办？可采用类似监督学习的方法，让程序自行演化出一个最合适的QUBO矩阵（QC Primer - 2.3、2.4）。

四、IBM的量子果园

相比起D-Wave果园在整合上的欠缺，IBM接待四海八荒宾朋的园林就显得中规中矩得多了：

IBM果园坐标——“量子体验”Quantum Experience

• Beginner's Guide
• Full User Guide
• Quantum Composer　独具特色的可视化逻辑门编程工具，可委托真机计算、或虚拟机执行
• Community
• 大量关联的维基百科词条，应该也是由IBM专家维护

硬件方面IBM虽然只做到5个量子比特^[6]，但他们有能力对每个比特做类似于传统逻辑门的运算、具有通用性，因此才说50个量子比特就已能实现“量子霸权”。

4.1 第一站，零基础者成长手册

这第一站，在笔者第一遍访问时还没有，属于新装修的，不过对零基础的人来说，确实大大降低了学习曲线的攀爬陡峭度。

4.1.1 Quantum Score（量子五线谱）

初入IBM园林，不仅有高悬的奇香异果，甚至还有悠扬的仙乐飘来。

原来IBM把自家的量子开发IDE，硬是打造成了一部谱曲器（Composer）：

![图4-1-1 量子谱曲器(出处^[12])](http://upload-images.jianshu.io/upload_images/80770-9b18cbae23a7db9d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

十分直观易懂，似乎多余的讲解都会唐突到设计者的匠心。5个量子比特构成名副其实的“五线谱”(Score)，可将右侧琳琅满目的量子逻辑门拖曳到五线谱上、谱写成“量子乐章”，最后粉色仪表盘一样的操作、将从量子位测量结果存放到传统比特寄存器中。图示的简单例子，就使得两个量子位达到了反向的“量子纠缠态”（后述）。

选择右上角的委托真机运行(Run)或模拟器即刻运行(Simulate)，就能获得演奏这一段曲目的效果。例如如下的柱状图，便显示了在反向纠缠态下两个量子比特会取相反值（01、10各半）。注意，第一个量子比特会出现在最低位(最右侧)，与传统习惯一致。

![图4-1-1:2 量子谱曲器 - 结果柱状图(出处^[12])](http://upload-images.jianshu.io/upload_images/80770-fd4da34ddb53fe35.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

乱入：园林深处，奇幻灵动的量子逻辑门，美妙的神之乐章，竟令人不禁想起了身着红色神斗衣的摇光星米伊美、在抚动魔音。。。

4.1.2 量子叠加态 - 高阶三维度诠释

在讲述IBM架构的特色“量子逻辑门”之前，需要在至今为止的“量子叠加态”定义上做进一步的提升——或者说“升维”解释。

“同时以0和1方式存在”（参照D-Wave章节），听起来似乎只是在1个维度上取离散值，可实际上却需要用3个维度来做可视化表征。

先从1维升至2维。引入狄拉克符号，一个量子比特包含两个能量等级|0>、|1>，我们只需借用线性代数中的概念、先简单将其理解成两个正交的二维向量，相当于|0>、|1>各占据不相干的维度。

![图4-1-2 狄拉克符号表征标准基准(standard basis)(出处^[13])](http://upload-images.jianshu.io/upload_images/80770-fb2857327bb95c83.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

再从2维升至3维。一个量子比特取0或1的概率，可以在这样一个等式中用系数来表征：a|0>+b|1>，其中参数a、b各自的绝对值平方，将分别映射到取0或1的概率，可知总满足|a|^2+|b|2=1（当a或b等于1时取值|0>或|1>）。而a、b不仅可取任意正数负数、甚至还可以是复数，由此推出，

![图4-1-2:2 布洛赫球面(出处^[14])](http://upload-images.jianshu.io/upload_images/80770-79f356f0bde3b2ea.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

上图称为布洛赫球面（Bloch Sphere），球半径为1，分别有X、Y、Z三个维度，量子比特的“奇幻灵动”位置、就必可表征为球面上的某个点，

• Z轴维度最为直观，正向|0>负向|1>为标准基准(standard basis)。对量子的测量只能基于Z轴进行，如需测量其它轴坐标、需进行轴对称变换、即经过量子逻辑门计算(后述)。

  • 注：|0>是能量等级最低的状态，称为ground state(基态)，物理上通过接近绝对零度的温控来近似达到（IBM做到了15mk，即比绝对零度仅高0.015度），使得在测量时只有极低概率坍缩为取1值。

• X轴也并不复杂，当位于正负轴向球面上时，a^2=b^2=1/2，量子都可能有一半概率坍缩到0或1；其它沿着XZ平面相切于球面的点也是类似含义。

  • X轴正负向的极点被命名为|+>和|->，称为对角基准(diagonal basis)。

• Y轴最有违直观，不过也无非因为引入了复数i（即i^2=-1），更直观的话，可采用轴间夹角θ与φ表征一个量子向量|ψ>。

  • 新出现的围绕Z轴的旋转角度φ，表征了量子的相位(phase)，这一部分也是用传统计算机所无法模拟出的关键所在。

4.1.3 量子逻辑门

理解了布洛赫球面对量子比特的三维表征后，谱曲器中琳琅满目的逻辑门的本质就无非就只是各种轴对称变换和旋转变换。

单量子位门

第一组：X门

顾名思义，X门将使得量子位绕X轴做对称变换（即旋转180度）。常用场景，将居于Z轴顶端的|0>（也是能量被压至最低的初始状态）、经X门计算后转为|1>（激发态）。

其矩阵表述为：

X门变换矩阵

第二组：H门

H门的含义，是绕X轴Z轴的45度夹角轴、作轴对称变换。其作用尤为常用，就是使得基态|0>被转变成|+>，即具有平均概率的叠加态。

之前我们说过，对量子比特只能做基于Z轴的测量，那么如何做基于X轴的测量呢？只需先进行H门转换（轴对称是可逆操作），再基于Z轴测量即可。

其矩阵表述为：

H门变换矩阵

第三组：Z门、S/S+门、T/T+门

这一组的逻辑门，都属于相位(phase)操作，即、绕Z轴的旋转。

Z门，是基于Z轴的轴变换，即180度旋转，会使得|+>被转成|->。

S门，则是绕着Z轴作90度旋转，会使得|+>被转到Y轴正向相位。但因为S门不是对合可逆的，所以设置一个它的逆操作S+门。

T门，是绕着Z轴作45度相位旋转，也有一个逆操作T+门。在Toffoli门中发挥到作用（本文略）。注：T门也是第一个出现的“非Clifford门”，在“深度”(个数)足够时，能使得量子比特能位于布洛赫球面的任意位置。[^ibm_fullug_3-3]

同理可知，量子比特基于Y轴的测量如何实现？先用一个S+门转换到X轴，再用H门转换到Z轴，即可基于Z轴测量了。

所有相位变换，令其绕Z轴旋转的夹角(即相位)为φ的话，可用一个变换矩阵来表达：

相位变换矩阵，e^iφ = cos(φ)+i*sin(φ)，φ=[-2π,2π]

多量子位门

CNOT：带控制位的NOT（Controlled-NOT）

首先请记得多量子比特的情况下，第一个量子比特也是被表示于最右侧，例如|0001>表示第一个量子比特为|1>。

CNOT门的含义，就是仅当第一个量子位为|1>时，才使得第二个量子取反（即X门），是条件逻辑的基石。

多量子门使得信息在量子比特间获得关联流转。而涉及更多量子位的逻辑门，都可以由之前介绍的逻辑门合成（将在量子算法章节举例）。

4.1.4 量子纠缠态

在了解了多量子位的基础上，就能以观察两个量子比特为例，引出第二个量子力学核心概念——量子纠缠态。

简单的说，形如以下算式（参考单量子位取值|+>时），两个量子既不处于标准基准（如|00>或|01>），又在两者之间表现出“有关联”（算式分子部分如果是|00>+|01>就属于无关联了），就称它们为处于“纠缠态”(Entanglement)。

反向纠缠的量子对，只可能以相反的坍缩值被测量

事实上，算式分子部分还可以是|11>+|00>，以及|11>-|00>、|10>-|01>。这四种状态，被称为“贝尔态”(Bell States)，所有的双量子状态都可以这4种贝尔态为基底作线性组合表述（当然也可以以4种标准基态作基底），尽管无法做三维表述。

著名的“薛定谔的猫”，其实也是在经典实体"猫"和量子"放射性原子"两者之间构建了“纠缠态”：a|活猫, 原子未衰变> +b|死猫, 原子衰变了>[^zhangtianrong_8]
[^zhangtianrong_8]: 科学松鼠会 » 走近量子纠缠（8）——纠缠态及实验: http://songshuhui.net/archives/83645

当对量子的研究也经历了“无极生太极”(单量子，叠加态)、“太极生两仪”(双量子，纠缠态)之后，后续的变化就比传统二进制时代更为丰富多彩了。

量子纠缠态下“一个量子被测定/坍缩为0时、其关联量子必定会被测定/坍缩为1”（反向纠缠时）的特性，首先就是，使得信息仿佛能被以“超过光速的速度”传递！当然其实这传递并不是基于动作，而是基于关联。量子隐形传输（以1993年IBM的Bennett等六人团队的研究为开始^[15]）、量子加密等一系列研究已不断基于纠缠态结出硕果（至今，中科大专家领衔铺设的量子通信京沪干线已达到了2000km的水平^[16][17]）。

希望对量子力学方面做更全面了解的IT技术者，推荐参考张天蓉老师的科普文章，以及郭光灿院士的公开课视频。

如何在计算环境中产生一对纠缠态的量子比特呢？有了逻辑门就十分简单，

图4-1-4 量子门实现双量子位纠缠态(反向)

利用之前的知识可知，对q[0]使用了H门使之进入了叠加态(|+>)，对q[1]则使用了X门使之反转为|1>，如此一来，在CNOT门的作用下，最终坍缩的结果只可能是|10>或者|01>（记得第一位位于最右端），实现“纠缠”。

（细心的读者可以发现这一逻辑门设置与图4-1-1是一样的，其最终测量结果也就是图4-1-2所示的结果）

#扩展阅读# 三粒子纠缠态。进一步扩展到三个量子比特时，会出现拓扑学中有趣的Borromean环和Hopf环。^[18]

4.2 第二站，完整用户手册——量子算法

有了更坚实的基础概念、量子门工具打底，就可以去采摘更具实用价值的果实了。

笔者第一次来访时就只有这第二站的“完整用户手册”，等到出了简明扼要的“新手手册”才深切感受到内容编排效果的差异…（当然这也可能是完整版手册的作者确实懂得的太多不适应科普简化所致）

建议，可直接跳到“量子算法”章节，这部分是完整版手册特有的。

4.2.1 量子计算发展史简介

完整用户手册中讲解的经典算法，都曾在量子计算发展史上具有重大意义。为此我们先回顾一下“历代记”。

1981年5月，理查德•费曼在波士顿MIT校园、做了题为“Simulating Physics With Computers”的报告，使得计算机科学家也开始关注量子力学。
1992年12月，Deutsch–Jozsa算法问世，这也是第一个显示出量子计算能比传统计算提升指数级性能的算法。
1994年，Shor算法问世于贝尔实验室，量子计算的研究才真正成为学术界及一些大型工业研究部门的瞩目课题——因为Shor算法大幅降低了“大质因数分解”的复杂度、动摇到了被认为最不可破解的RSA加密算法的基石！
1996年5月，Grover算法同样问世于贝尔实验室，将遍历查找的复杂度降低为N的根号倍，这使得常用的对称键加密算法也受到了挑战。
2001年7月，IBM研究中心研制出一台7量子比特的NMR(核磁共振)计算机，并成功用它演示Shor算法做了15=3x5的质因子分解。
2011年5月，加拿大D-Wave公司公布了第一台128量子比特的“商用量子计算机”D-Wave-One，并售出了1000万美金的高价。
2013年5月，谷歌与NASA合作成立了量子人工智能实验室，配置了512位的D-Wave量子计算机，邀请科学家参与量子机器学习的研究。
2016年5月，IBM开放量子体验平台。
2017年1月，D-Wave将qbsolv工具开源。

量子算法如何对“同时存在的2^N种可能性”做出惊鸿一瞥、取得目标解的呢？让我们借著名的Shor算法做一了解。

4.2.2 Shor算法——大质因数分解

当一个整数大到232位数时， 已经需要2,000个CPU年来求解其质因数了，这属于一个复杂度呈指数增长的NP-Hard问题，也因此被用作为RSA加密算法的核心。

寻阶问题(Period finding)

早在1970年代，就发现若能破解另一个NPH问题——求得取模指数方程的“阶”，就能降低质因数分解的复杂度。

阶(Period)的定义：对于给定的N(因数分解的对象)和a(与N互质)，找到能使得a^r-1成为N的倍数的最小的那个r，该值就称为“a对N取模的阶(period)”。

如何保证a与N互质呢？可参照一下多数开发者都应该学过的、能快速求出最大公约数的GCD算法（欧几里得辗转相除法）。

举例而言，令N=15、a=7，遍历尝试过程如下，

使得取模为1的第一个指数r，就是阶。

IBM这篇完整手册对“period”的描述有失直观，其实r的本质是一个周期数，即a^0 mod N等于1、直至a^r mod N再次为1之间、其实余数是以周期性循环出现的（如1,7,4,13,1..，由模乘的特性决定）。

从阶到质因数分解

首先需要找到一个偶数阶。随机取a，如果GCD算法获得与N的公约数则直接得到质因数，否则满足互质可求阶，阶为奇数时重选a即可，统计已证明绝大多数的阶为偶数。

第二步，a^r-1是N的倍数，就意味着N的质因数（通常只有2个，否则破解难度就更低了）有极高概率分别分布在它的两个因数之中！

• a^(r/2)-1不可能是N倍数（否则r/2应该才是阶）
• 当a^(r/2)+1也不是N倍数时，即上式右侧的两个乘数都不可能包含N的所有因数、而只可能各自都包含(至少)一个。于是“质因数分解”问题简化为、将N分别与a^(r/2)-1和a^(r/2)+1做GCD运算。
• 当a^(r/2)+1是N倍数时，重选随机数a。

量子计算简化寻阶问题

限于篇幅本文需做出较多的省略。Shor算法中会涉及Deutsch–Jozsa算法中用到过的量子干涉(interference)特性、Grover算法中用到过的神谕酉矩阵电路、以及相位估算(phase estimation)算法。需深入了解这些概念的读者可查看相关各章节。

首先，“神谕”矩阵(Oracle)是一个当符合特定值时会促成振幅放大(amplitude amplification)、否则维持基本不变的特殊酉矩阵。如下图、就是经过两次(两种)Oralce矩阵变换后、符合特定值的表征比特获得高出平均值振幅的图例。

图4-2-2 Oracle矩阵变换的效果

反复这一“摇签”一样的过程，就最终能获得一根“神谕”的上上签……

而f(x) = a*x mod N 就可以被作为一个Oracle矩阵Ua。继续以a=7, N=15为例，从“x=1”起，输出(7)作为新的x输入首尾相连的话（注：相当于a^r mod N中r=1,2,3…），将满足1 → 7 → 4 → 13 → 1 → …的周期循环。这种Ua矩阵可以通过如下的量子门电路实现：

U7电路，输入为1(Q4经过X门bit-flip为1)，输出将为7

上图红框部分即为U7电路(a=7)，可自行证明其满足上述输入输出周期循环的要求（原理参见Markov and Saeedi 2012）。

有了Ua电路，通过相位估算法就能近似求得Ua矩阵的特征值(eigenvalues)、即e^iψ周期（参照相位变换矩阵）——a的阶r，特征向量使用[0,0,…,1]即可（因为a^0=1）。（为了求得高精度，这里还用到了一个技巧，即不直接用Ua来求，而是使用特征值相同的Ub(b=a,a^2,a^4...a^(2^p); 2^p≈N^2)）

为了搭建Ua“模乘”(modular multiplication)这样的量子电路、还涉及到量子操作必须能“可逆”的特性，对此感兴趣的可参考可逆量子电路(reversible classical circuits)。

D-Wave的退火机制目前尚无法实现Shor算法^[19]。

※※※※※※※※

#扩展阅读# “量子纠错”：在有量子门的真机环境中（退火机制下无此需求），伴随着物理原理的问题、如退相干(Decoherence)，使得需为纠错校验付出额外的资源。

4.3 第三站，Composer或QASM

量子谱曲器(Composer)在第一站中已经做过说明。IBM用户手册中每一篇主题的最后，都有量子门的示例，并可以直接点击用谱曲器打开，或是直接观看计算结果，十分方便。

当你使用Composer时会要求你登录。无需申请账号，国内使用GitHub账号即可。

另外，凡是能在谱曲器中打开的量子五线谱，都能通过点击位于量子门右侧的“QASM”分页切换到QASM代码模式，这种量子汇编代码本身就很直观，加上能与可视化编辑的五线谱互换后就更加通俗易懂了。

![图4-3 QASM量子汇编代码 (出处^[12])](http://upload-images.jianshu.io/upload_images/80770-a6a8baabbf2c5d1d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

4.4 第四站，IBM量子体验社区

这里也是IBM做得相对更好的地方，直接面向互联网集思广益，突出了开放平台的初衷。

笔者目前并未在社区中深入更多，不过看到过一份量子门版的解“地图填色”问题的实例，读者可自行参考。

图4-4 5地区填色问题

图4-4:1 5地区填色问题量子门设置

五、小结：风雨几经到枝魁^[1]

2017年初，MIT、也就是36年前费曼第一次宣讲量子力学可与计算机结合的大学，评选了全球十大突破性技术^[20]，实用型量子计算机名列其中，成熟期预估为4~5年。

量子计算的前路并不平坦，与传统计算之间有着较大的差异，也因此IBM与D-Wave纷纷着力于宣传相关的技术，邀请有志人士参与了解、凝聚成更强的社区力量。希望本文能为相关的知识普及、范式转换尽一份微力。

原文发布时间为：2017.04.14
本文作者：天空之诚
本文来源：好奇心日报，如需转载请联系原作者。