IBM、D-Wave相繼開放其量子計(jì)算平臺(tái)，分別介紹其“求15的質(zhì)因數(shù)”與“地圖填色問題”官方案例，以體驗(yàn)與傳統(tǒng)開發(fā)之間差異。

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

當(dāng)今兩大領(lǐng)跑者IBM與D-Wave(Google聯(lián)合NASA采購過其計(jì)算機(jī))，已先后對(duì)其量子計(jì)算能力進(jìn)行了部分開放或開源^[2][3]（分別為去年5月、今年1月）。

受其“誘惑”筆者近兩個(gè)月到相關(guān)園子里做了一圈調(diào)查體驗(yàn)（注：筆者與大多數(shù)IT從業(yè)者一樣，在量子計(jì)算、量子物理方面背景為零），三句話概括當(dāng)前感受的話：

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

2015年Google曾實(shí)測(cè)D-Wave 2X（1000+個(gè)量子位）量子退火方式計(jì)算機(jī)，對(duì)規(guī)模為1000比特的問題，相比用傳統(tǒng)硬件模擬退火算法要快上10^8倍^[4]。這種退火(Annealing)方式能將一部分NP-Complete復(fù)雜度問題轉(zhuǎn)換為多項(xiàng)式復(fù)雜度，具體通過將問題先編寫/映射成QMI指令再物理作用到量子比特上的方式來進(jìn)行，本文中將以官方文檔中的“地圖填色問題”為例做體驗(yàn)式介紹。而在更高級(jí)的機(jī)器學(xué)習(xí)圖像識(shí)別領(lǐng)域，Google也已公開過實(shí)績^[5](2009年)。

IBM則采用了更為通用的量子門設(shè)計(jì)模式，能對(duì)一元二元乃至多元量子比特做相當(dāng)于經(jīng)典邏輯門的計(jì)算。這種Universal的架構(gòu)，能用于處理Shor算法這樣在已知量子算法中堪稱復(fù)雜而最具實(shí)際價(jià)值的問題——因?yàn)樗苡脕砉テ?strong>當(dāng)今數(shù)字安全基石RSA加密的數(shù)學(xué)核心、即“大質(zhì)因數(shù)分解”；本文也將介紹IBM官方文檔中“求15的質(zhì)因數(shù)”的實(shí)例。不過IBM通用設(shè)計(jì)仍只實(shí)現(xiàn)了5個(gè)量子位^[6]，據(jù)稱幾年內(nèi)將達(dá)到50位、實(shí)現(xiàn)“量子霸權(quán)”(即計(jì)算力超過地球所能容納的最大傳統(tǒng)計(jì)算機(jī) 注:未考慮DNA NUTM計(jì)算機(jī))。

那么為什么兩家要先后對(duì)這一尖端、高價(jià)值的研究成果予以開放呢？

答案是“生態(tài)圈”。盡管量子計(jì)算已經(jīng)取得了一定成果，但距離實(shí)用商業(yè)化還有較長一段距離(4_{5年[^MIT_enval])；而如讀者很快將領(lǐng)略到的，量子計(jì)算與傳統(tǒng)開發(fā)之間存在著極大差異（如果不是說完全不同的話}~），且仍處于比傳統(tǒng)匯編語言更初級(jí)的階段。佳果雖好，尚未緋紅，要讓更多傳統(tǒng)人才加入量子計(jì)算領(lǐng)域、研究出更多算法/應(yīng)用，盡快提升自家果園的成熟度的話，開放，應(yīng)該會(huì)是一個(gè)多贏的選擇。

限于調(diào)查時(shí)間，文章主干之外一定還會(huì)存在未盡問題，將以“#延伸思考#”標(biāo)簽標(biāo)識(shí)；而限于篇幅，對(duì)于主干內(nèi)容之外的關(guān)聯(lián)知識(shí)，也將標(biāo)記“#擴(kuò)展閱讀#”標(biāo)簽、或提供外部鏈接方式。

二、果園外的藩籬

即便只是想要一睹佳果芳澤，都需翻越過幾片并不算低淺的藩籬，

1. 需一定的量子物理知識(shí)

量子力學(xué)(Quantum Mechanics)奠基人費(fèi)曼和波爾都曾告誡過自己學(xué)生，“不要問為什么，而只要搞清楚量子力學(xué)允許你去做什么”，此后100多年大家確實(shí)只是照著這樣做、就已收獲了豐碩果實(shí)：

• 電子一脈：晶體管、電腦、手機(jī)…
• 光子一脈：激光
• 其他：能源、核聚變

可另一方面，先賢的話也確實(shí)界定了量子力學(xué)的理解難度——尤其是因?yàn)槠?em>有違直覺(counter-intuitive)，后文將會(huì)擇要講解理解量子計(jì)算所需的兩個(gè)量子力學(xué)知識(shí)：

• 量子疊加態(tài)（superpostion）
• 量子糾纏（entanglement）

1. 缺乏中文資料
   量子力學(xué)的普及文章是有的，但截至發(fā)稿為止、尚未見到對(duì)兩大陣營開放平臺(tái)的較為深入的中文評(píng)測(cè)、對(duì)比。
   因此，文中也會(huì)適當(dāng)出現(xiàn)英文用語以便于擴(kuò)展閱讀、及避免歧義。

2. 對(duì)缺少數(shù)學(xué)背景的開發(fā)者來說較為頭痛的數(shù)學(xué)算式
   主要是線性代數(shù)，但很多又是專門用來表征“有違直覺”的量子力學(xué)的，如狄拉克符號(hào)、布洛赫球面、貝爾不等式，足以令心智不堅(jiān)者卻步。好在相關(guān)的英文版維基百科更新得很完整及時(shí)，可供查證。

3. 概念多多，卻缺乏系統(tǒng)逐級(jí)深入的資料（即便是英文的院系教程），需自行篩選整理才能深入

循著筆者的足跡，可望以盡量短的路徑穿越過這些藩籬。

三、D-Wave的量子果園

D-Wave果園坐標(biāo)（依照推薦足跡順序）

• qbsolv Example: mapColoringUSStates - D-Wave開源工具官方范例@GitHub，只需編譯運(yùn)行
• 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環(huán)境（qbsolv需被make），就能輕松執(zhí)行起demoStates.sh觀看退火算法(模擬器)得出的結(jié)果，

• 輸入：美國51州的關(guān)聯(lián)定義usa.adj，空白美國地圖blank_US_state_map.svg
• 輸出：已填色美國地圖usa.qbout.xaa.svg，中間文件usa.qubo,usa.qbout

圖3-1 D-Wave qbsolv工具范例“美國地圖填色”運(yùn)行結(jié)果

四色問題屬于NP-Completed復(fù)雜度問題，傳統(tǒng)專業(yè)課必教、易于描述但卻神秘（19世紀(jì)提出至今未獲人工證明），很適合用來展現(xiàn)量子計(jì)算的能力。

最初GitHub上的這個(gè)官方Sample運(yùn)行結(jié)果還不正確，提交Bug后修改了usa.adj文件中兩個(gè)州的鄰接關(guān)系解決了問題。

3.2 第二站，“開關(guān)組游戲”講解QUBO問題

緊接著第二站，Quantum Computing Primer的1.3節(jié)、1.4節(jié)給出了簡單易懂的“開關(guān)組游戲”例子，簡而言之，就是我們要能令如下算式取得最低值的x序列解，

QUBO問題：求令此算式取最低值的x解（Q為矩陣，x為向量）

D-Wave的退火式量子計(jì)算最擅長解決的這種QUBO問題^[7]（二次非約束二進(jìn)制優(yōu)化，目前有簡述成“離散最優(yōu)化”的），可更直觀的表述為下圖，

圖3-2 開關(guān)組游戲 - 求weight、strength矩陣乘積最小解

引入兩個(gè)概念就能解釋這個(gè)游戲，

• 權(quán)重(weight)：由每個(gè)開關(guān)上的數(shù)字標(biāo)識(shí)，相當(dāng)于QUBO算式中的Qii，當(dāng)該開關(guān)打開時(shí)將計(jì)入合計(jì)值
• 強(qiáng)度(strength)：由兩個(gè)開關(guān)之間的數(shù)字標(biāo)識(shí)，相當(dāng)于QUBO算式中的Qij，當(dāng)兩個(gè)開關(guān)均打開時(shí)將計(jì)入合計(jì)值

在D-Wave官方資料中，會(huì)對(duì)weight、strength命名為h、J，或是a、b、以及Qii、Qij，請(qǐng)注意其實(shí)質(zhì)即可。

問題在于，這樣的一個(gè)圖論“游戲”，是無法簡單求解的，而只能暴力求解（對(duì)每個(gè)開關(guān)嘗試開或關(guān)），也就意味著NP復(fù)雜度(=O(2^N))，在10個(gè)開關(guān)時(shí)還算好，當(dāng)有100個(gè)開關(guān)時(shí)、嘗試次數(shù)就已暴漲到1,267,650,600,228,229,401,496,703,205,376(=10^30)！

據(jù)估算，此游戲的開關(guān)數(shù)達(dá)到500個(gè)時(shí)，傳統(tǒng)計(jì)算機(jī)就得計(jì)算到宇宙末日了……

奇妙的地方來了。

3.2.1 量子疊加態(tài) - 初階簡易理解

在量子計(jì)算機(jī)中，最基本的單元——量子比特(quantum bit，簡稱qubit)，或者說上述游戲中的“開關(guān)”，是“同時(shí)”以1(開)或0(關(guān))方式存在的。沒錯(cuò)，你可以把這段話多讀上幾遍。

這就是研讀量子計(jì)算所需涉及的兩個(gè)量子力學(xué)主題中的一個(gè)——疊加態(tài)(superposition)。量子力學(xué)是那么的“有違直覺”(counter-intuitive)，所幸這個(gè)簡化版的解釋已足夠了解D-Wave的例子了。

你只需看作，這些量子“開關(guān)”在猶豫不決于它們?cè)撎幱诤畏N狀態(tài)，對(duì)于給定的如前圖的“開關(guān)組游戲”，傳統(tǒng)情境下還需要人工逐一去遍歷嘗試，而在微觀量子情境下，所有的可能性已經(jīng)同時(shí)并存在那里了！而退火機(jī)制則提供了一種方式，通過施加然后撤除特定的“權(quán)重、強(qiáng)度”磁場(chǎng)（即Q矩陣，參照QUBO算式）、量子“開關(guān)”進(jìn)入然后又脫離疊加態(tài)、決定自己“開”或“關(guān)”（稱為“坍縮”），最終整體安定于一個(gè)“最低能量狀態(tài)”，也就求得了QUBO問題的最優(yōu)解或次優(yōu)解（QC Primer - 1.4）。IBM的量子門機(jī)制則留待后述。

重要的一點(diǎn)，量子計(jì)算機(jī)的結(jié)果是概率式(probabilistic)的，不同于傳統(tǒng)計(jì)算機(jī)的決定式(deterministic)。也就是說運(yùn)行幾百或幾千遍，重復(fù)出現(xiàn)次數(shù)最高的、才是“最優(yōu)解”中真正的最優(yōu)。當(dāng)然這種額外開銷對(duì)于10^30這樣的傳統(tǒng)計(jì)算指數(shù)級(jí)成本來說可以忽略，而且作為副產(chǎn)品的“次優(yōu)解”、對(duì)很多研究來說恰恰是大有用處的。

“沒有對(duì)比就沒有傷害”，100個(gè)開關(guān)時(shí)， 原本需高達(dá)10³⁰次的遍歷(O(2^N))，使用100個(gè)量子開關(guān)，1次經(jīng)過控制的“坍縮”就可能解決；因此核心問題已經(jīng)轉(zhuǎn)變成、如何將目標(biāo)問題轉(zhuǎn)換成QUBO問題？

糾正：目前不少非專業(yè)新聞中報(bào)導(dǎo)量子計(jì)算之所以性能卓著是因?yàn)椤俺?、1之外，還能表示‘0或1’狀態(tài)”（于是…三進(jìn)制?），純屬訛傳。

#擴(kuò)展閱讀#　如果不介意額外切換出去20分鐘，有一個(gè)經(jīng)典實(shí)驗(yàn)更具體的再現(xiàn)了“疊加態(tài)”、量子的這種“猶豫不決”，那就是雙縫干涉實(shí)驗(yàn)。（關(guān)鍵語句：“電子同時(shí)通過了兩條狹縫，然后，自己和自己發(fā)生了干涉！”“一旦想要觀察電子到底通過哪條狹縫？干涉條紋便立即消失了！”）

3.3 第三站，軟件架構(gòu)（Software Architecture）

原文濃縮為下圖，只需看QUBO的部分。

圖3-3 D-Wave軟件架構(gòu)

具體到開源的qbsolv“美國地圖填色”范例，目標(biāo)問題(這次是地圖填色，而非開關(guān)組了)、也需要被表征為一個(gè)QUBO問題或者說QUBO矩陣，具體是通過adj2qubo.py，將美國51州相鄰關(guān)系數(shù)據(jù)轉(zhuǎn)成了usa.qubo文件，其格式非常簡單：

c 中間文件usa.qubo，表征了一個(gè)Q矩陣，將成為qbsolv工具的輸入
c AK                 <--- c打頭為注釋行，AK是州名縮寫
  0 0 -1             <--- 定義權(quán)重Qii，所以前兩位相等，第三位即權(quán)重值
  1 1 -1 
  2 2 -1 
  3 3 -1             <--- 注意用4個(gè)物理位來定義一個(gè)邏輯節(jié)點(diǎn)（4色）
c AK   1 neighbors  4 external couplers  <--- 注釋，將定義AK內(nèi)部連接
  0 1 2              <--- 4個(gè)物理位之間的窮舉連接
  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             <--- 定義強(qiáng)度Qij，前兩位為關(guān)聯(lián)qubit序號(hào)，第三位即強(qiáng)度
  1 41 1 
  2 42 1 
  3 43 1 

這個(gè)Q矩陣將會(huì)被神秘(但已開源)的qbsolv工具用模擬退火算法生成一個(gè)最優(yōu)解usa.qbout（本例中是204個(gè)量子位的序列，每個(gè)州需用4個(gè)位表征，原理后述），如果開啟qbsolv的-r seed隨機(jī)種子，還能獲得不同的解。最終plotmap.sh將被用來基于usa.qbout對(duì)空白美國地圖SVG文件填色。

那么，adj2qubo.py又是按照什么算法基于一份地區(qū)相鄰關(guān)系數(shù)據(jù)、決定出QUBO矩陣中權(quán)重與(連接)強(qiáng)度的取值的呢？

3.4 第四站，官方編程手冊(cè)四色問題詳解

最后一站，會(huì)略有燒腦情節(jié)。

限于篇幅精力只做簡述，以便體會(huì)“目標(biāo)問題如何轉(zhuǎn)為QUBO問題”。如需開發(fā)解決新問題，還請(qǐng)參考原文。

如何通過設(shè)置Q矩陣使得目標(biāo)命題的要求條件被蘊(yùn)含其中，從而在最終QUBO算式的最低能量解“火退石出”(退火)時(shí)、讓X向量自動(dòng)指向目標(biāo)命題的解呢？

• QUBO算式：f(x) = SUM(Qii Xi) + SUM(Qij Xi Xj)，退火能在給定Q矩陣情況下、自動(dòng)調(diào)整X向量、取得最低值解

• Q矩陣：Qii=節(jié)點(diǎn)i的權(quán)重，Qij=節(jié)點(diǎn)i,j之間連接的強(qiáng)度
• X向量：Xi=節(jié)點(diǎn)i，經(jīng)典態(tài)下取1或0

方法一，通過預(yù)設(shè)特定的Qii、Qij，使得不合適的量子比特Xi組合無法成為最低值解

觀察兩個(gè)qubit(量子比特)X1,X2的情況，f(x) = Q1*X1 + Q2*X2 + Q12*X1*X2（權(quán)重Qii簡化表示為Qi，后同）。

• 當(dāng)X1=X2=0時(shí)，f(x)=0。只需設(shè)置Q1<0, Q2<0就能使得這種情況被排除（即其他解永遠(yuǎn)會(huì)比0取值更低）
• 當(dāng)X1=X2=1時(shí)，如果想把這一種相等情況也排除，該怎么設(shè)置？
  使得Q1 + Q2 + Q12 = 0就能排除了！
• 綜合而言，不妨令Q1=-1, Q2=-1，然后Q12=2就能排除X1=X2

這就是最簡單的，滿足了“兩個(gè)量子比特有且僅有一個(gè)為1”這一要求條件的Q矩陣取值；而這一條件，就可以被映射到“四色問題”中“一個(gè)地區(qū)有且僅有一色有效”這樣的命題條件上（可自行計(jì)算，4個(gè)qubit或更多時(shí)設(shè)置Qii=-1, Qij=2仍能滿足該條件）。

回顧前文的usa.qubo中權(quán)重與內(nèi)部連接的取值，是不是正是-1與2。任意一個(gè)地區(qū)(如AK)也都需要4個(gè)qubit來表征（代表四種顏色）。

方法二，用兩個(gè)以上物理位(chain)表征一個(gè)邏輯位，一組邏輯位(unit cell)表征一個(gè)命題對(duì)象，進(jìn)一步設(shè)置對(duì)象間連接的強(qiáng)度值

圖3-4 地區(qū)的物理比特表征，及地區(qū)間不同色命題條件表征

我們先看左側(cè)、即一個(gè)地區(qū)，竟然用了8個(gè)“qubit”來構(gòu)成?？善鋵?shí)你只需要記得這是“考慮到了硬件可行性”的物理qubit，每排的2個(gè)物理qubit會(huì)映射到一個(gè)邏輯qubit、這才是usa.qubo中定義的一個(gè)節(jié)點(diǎn)。而這種由4個(gè)邏輯qubit（合成1個(gè)unit cell）表征的地區(qū)，還能進(jìn)一步連接到其他地區(qū)（如右側(cè)）滿足“不同色邏輯關(guān)聯(lián)”(命題條件)的需求。

#擴(kuò)展閱讀#　用多個(gè)而非一個(gè)物理qubit來映射一個(gè)“邏輯qubit”，是因?yàn)樾枰诒碚髅}對(duì)象的邏輯qubit組內(nèi)部建立起“完全連接”（兩兩之間都有連接），但硬件架構(gòu)上無法直接對(duì)4個(gè)qubit建立完全連接，可參看硬件概述 1.1、1.2中的圖解。

幾個(gè)要點(diǎn)：

• chain的內(nèi)部取平均值
  用來表征一個(gè)邏輯qubit的多個(gè)物理qubit被稱為chain，chain內(nèi)的物理位的權(quán)重是要取平均值的(e.g.-0.5)，與其他chain之間的連接強(qiáng)度也取平均值(e.g.1)。若使用qbsolv工具的話已經(jīng)無需關(guān)注物理位映射邏輯位問題了。
• “一個(gè)地區(qū)有且僅有一色”條件的滿足
  這個(gè)之前已講過，具體到上圖(3-4)，就是4個(gè)chain(即邏輯qubit)之間的連接強(qiáng)度取值為2，4個(gè)邏輯qubit各自的權(quán)重取值為-1即可。
• “相鄰地區(qū)間不同色”條件的滿足
  讀者可先自行思索一下如何設(shè)置Q矩陣。
  這個(gè)命題條件的實(shí)質(zhì)，可以表達(dá)為“當(dāng)某一色在一側(cè)被采用，且在另一側(cè)也被采用時(shí)，對(duì)QUBO算式加入懲罰值”；上圖(3-4)中的每個(gè)跨地區(qū)連接、連接了代表本地區(qū)取相應(yīng)顏色的邏輯位，因此是一個(gè)2 qubit的算式，在Q1=0, Q2=0, Q12=1時(shí)，兩側(cè)都取相同顏色的情況就會(huì)遭受f(x)=1的懲罰。Q1=0, Q2=0不影響既有值，因此只需設(shè)置代表地區(qū)間連接的Qij=1即可?？蓹z查usa.qubo是否是這樣。

方法三，用多個(gè)unit cell的合并(clone)表征特殊的命題對(duì)象

首先請(qǐng)注意在qbsolv范例的usa.qubo文件中并沒有看到這種合并(clone)，可能是qbsolv中的算法已能自動(dòng)解決了。

圖3-4:2 采用clone來表征與四個(gè)以上州有連接的州

官方編程手冊(cè)3.4節(jié)中的這張圖顯得未免繁瑣——對(duì)于有4個(gè)以上接壤州的“大州”、竟然需要象“華容道”一樣人工編排各州的位置、來使得用2個(gè)unit cell合并出的“大州”能獲得正確的相鄰關(guān)系表征？所幸是在qbsolv工具的.qubo文件中、solve.c中都已不再看到相關(guān)內(nèi)容。如果需做這種“clone”(合并)的話，使得兩個(gè)邏輯位權(quán)重為1、連接強(qiáng)度為-2就能達(dá)到“合二為一”的效果。

另外，當(dāng)QUBO矩陣大到硬件環(huán)境不能接受時(shí)，可以被分割成subQUBO逐一解決、再合并得出結(jié)果^[7](參見qbsolv中的solve.c)。

※※※※※※※※

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

如上可知，D-Wave的量子計(jì)算機(jī)具有一定局限性，不過對(duì)于能用QUBO算式表征的課題確實(shí)性價(jià)比很高，硬件方面最新已推出了高達(dá)2,000量子比特的四代機(jī)(2017/1/25)^[11]。

#延伸思考#　退火方式對(duì)目前機(jī)器學(xué)習(xí)開發(fā)帶來的改變。這方面官方雖沒有提供范例，但早已有了實(shí)際成果^[5]。對(duì)于能轉(zhuǎn)換成QUBO矩陣的問題、可采用“四色問題”的辦法，機(jī)器學(xué)習(xí)則屬于不能人工給出Q矩陣的，怎么辦？可采用類似監(jiān)督學(xué)習(xí)的方法，讓程序自行演化出一個(gè)最合適的QUBO矩陣（QC Primer - 2.3、2.4）。

四、IBM的量子果園

相比起D-Wave果園在整合上的欠缺，IBM接待四海八荒賓朋的園林就顯得中規(guī)中矩得多了：

IBM果園坐標(biāo)——“量子體驗(yàn)”Quantum Experience

• Beginner's Guide
• Full User Guide
• Quantum Composer　獨(dú)具特色的可視化邏輯門編程工具，可委托真機(jī)計(jì)算、或虛擬機(jī)執(zhí)行
• Community
• 大量關(guān)聯(lián)的維基百科詞條，應(yīng)該也是由IBM專家維護(hù)

硬件方面IBM雖然只做到5個(gè)量子比特^[6]，但他們有能力對(duì)每個(gè)比特做類似于傳統(tǒng)邏輯門的運(yùn)算、具有通用性，因此才說50個(gè)量子比特就已能實(shí)現(xiàn)“量子霸權(quán)”。

4.1 第一站，零基礎(chǔ)者成長手冊(cè)

這第一站，在筆者第一遍訪問時(shí)還沒有，屬于新裝修的，不過對(duì)零基礎(chǔ)的人來說，確實(shí)大大降低了學(xué)習(xí)曲線的攀爬陡峭度。

4.1.1 Quantum Score（量子五線譜）

初入IBM園林，不僅有高懸的奇香異果，甚至還有悠揚(yáng)的仙樂飄來。

原來IBM把自家的量子開發(fā)IDE，硬是打造成了一部譜曲器（Composer）：

圖4-1-1 量子譜曲器

十分直觀易懂，似乎多余的講解都會(huì)唐突到設(shè)計(jì)者的匠心。5個(gè)量子比特構(gòu)成名副其實(shí)的“五線譜”(Score)，可將右側(cè)琳瑯滿目的量子邏輯門拖曳到五線譜上、譜寫成“量子樂章”，最后粉色儀表盤一樣的操作、將從量子位測(cè)量結(jié)果存放到傳統(tǒng)比特寄存器中。圖示的簡單例子，就使得兩個(gè)量子位達(dá)到了反向的“量子糾纏態(tài)”（后述）。

選擇右上角的委托真機(jī)運(yùn)行(Run)或模擬器即刻運(yùn)行(Simulate)，就能獲得演奏這一段曲目的效果。例如如下的柱狀圖，便顯示了在反向糾纏態(tài)下兩個(gè)量子比特會(huì)取相反值（01、10各半）。注意，第一個(gè)量子比特會(huì)出現(xiàn)在最低位(最右側(cè))，與傳統(tǒng)習(xí)慣一致。

圖4-1-1:2 量子譜曲器 - 結(jié)果柱狀圖

亂入：園林深處，奇幻靈動(dòng)的量子邏輯門，美妙的神之樂章，竟令人不禁想起了身著紅色神斗衣的搖光星米伊美、在撫動(dòng)魔音。。。

4.1.2 量子疊加態(tài) - 高階三維度詮釋

在講述IBM架構(gòu)的特色“量子邏輯門”之前，需要在至今為止的“量子疊加態(tài)”定義上做進(jìn)一步的提升——或者說“升維”解釋。

“同時(shí)以0和1方式存在”（參照D-Wave章節(jié)），聽起來似乎只是在1個(gè)維度上取離散值，可實(shí)際上卻需要用3個(gè)維度來做可視化表征。

先從1維升至2維。引入狄拉克符號(hào)，一個(gè)量子比特包含兩個(gè)能量等級(jí)|0>、|1>，我們只需借用線性代數(shù)中的概念、先簡單將其理解成兩個(gè)正交的二維向量，相當(dāng)于|0>、|1>各占據(jù)不相干的維度。

圖4-1-2 狄拉克符號(hào)表征標(biāo)準(zhǔn)基準(zhǔn)(standard basis)

再從2維升至3維。一個(gè)量子比特取0或1的概率，可以在這樣一個(gè)等式中用系數(shù)來表征：a|0>+b|1>，其中參數(shù)a、b各自的絕對(duì)值平方，將分別映射到取0或1的概率，可知總滿足|a|²+|b|²=1（當(dāng)a或b等于1時(shí)取值|0>或|1>）。而a、b不僅可取任意正數(shù)負(fù)數(shù)、甚至還可以是復(fù)數(shù)，由此推出，

圖4-1-2:2 布洛赫球面

上圖稱為布洛赫球面（Bloch Sphere），球半徑為1，分別有X、Y、Z三個(gè)維度，量子比特的“奇幻靈動(dòng)”位置、就必可表征為球面上的某個(gè)點(diǎn)，

• Z軸維度最為直觀，正向|0>負(fù)向|1>為標(biāo)準(zhǔn)基準(zhǔn)(standard basis)。對(duì)量子的測(cè)量只能基于Z軸進(jìn)行，如需測(cè)量其它軸坐標(biāo)、需進(jìn)行軸對(duì)稱變換、即經(jīng)過量子邏輯門計(jì)算(后述)。

  • 注：|0>是能量等級(jí)最低的狀態(tài)，稱為ground state(基態(tài))，物理上通過接近絕對(duì)零度的溫控來近似達(dá)到（IBM做到了15mk，即比絕對(duì)零度僅高0.015度），使得在測(cè)量時(shí)只有極低概率坍縮為取1值。

• X軸也并不復(fù)雜，當(dāng)位于正負(fù)軸向球面上時(shí)，a^2=b^2=1/2，量子都可能有一半概率坍縮到0或1；其它沿著XZ平面相切于球面的點(diǎn)也是類似含義。

  • X軸正負(fù)向的極點(diǎn)被命名為|+>和|->，稱為對(duì)角基準(zhǔn)(diagonal basis)。

• Y軸最有違直觀，不過也無非因?yàn)橐肓藦?fù)數(shù)i（即i^2=-1），更直觀的話，可采用軸間夾角θ與φ表征一個(gè)量子向量|ψ>。

  • 新出現(xiàn)的圍繞Z軸的旋轉(zhuǎn)角度φ，表征了量子的相位(phase)，這一部分也是用傳統(tǒng)計(jì)算機(jī)所無法模擬出的關(guān)鍵所在。

4.1.3 量子邏輯門

理解了布洛赫球面對(duì)量子比特的三維表征后，譜曲器中琳瑯滿目的邏輯門的本質(zhì)就無非就只是各種軸對(duì)稱變換和旋轉(zhuǎn)變換。

單量子位門

第一組：X門

顧名思義，X門將使得量子位繞X軸做對(duì)稱變換（即旋轉(zhuǎn)180度）。常用場(chǎng)景，將居于Z軸頂端的|0>（也是能量被壓至最低的初始狀態(tài)）、經(jīng)X門計(jì)算后轉(zhuǎn)為|1>（激發(fā)態(tài)）。

其矩陣表述為：

X門變換矩陣

第二組：H門

H門的含義，是繞X軸Z軸的45度夾角軸、作軸對(duì)稱變換。其作用尤為常用，就是使得基態(tài)|0>被轉(zhuǎn)變成|+>，即具有平均概率的疊加態(tài)。

之前我們說過，對(duì)量子比特只能做基于Z軸的測(cè)量，那么如何做基于X軸的測(cè)量呢？只需先進(jìn)行H門轉(zhuǎn)換（軸對(duì)稱是可逆操作），再基于Z軸測(cè)量即可。

其矩陣表述為：

H門變換矩陣

第三組：Z門、S/S+門、T/T+門

這一組的邏輯門，都屬于相位(phase)操作，即、繞Z軸的旋轉(zhuǎn)。

Z門，是基于Z軸的軸變換，即180度旋轉(zhuǎn)，會(huì)使得|+>被轉(zhuǎn)成|->。

S門，則是繞著Z軸作90度旋轉(zhuǎn)，會(huì)使得|+>被轉(zhuǎn)到Y(jié)軸正向相位。但因?yàn)镾門不是對(duì)合可逆的，所以設(shè)置一個(gè)它的逆操作S+門。

T門，是繞著Z軸作45度相位旋轉(zhuǎn)，也有一個(gè)逆操作T+門。在Toffoli門中發(fā)揮到作用（本文略）。注：T門也是第一個(gè)出現(xiàn)的“非Clifford門”，在“深度”(個(gè)數(shù))足夠時(shí)，能使得量子比特能位于布洛赫球面的任意位置。^[15]

同理可知，量子比特基于Y軸的測(cè)量如何實(shí)現(xiàn)？先用一個(gè)S+門轉(zhuǎn)換到X軸，再用H門轉(zhuǎn)換到Z軸，即可基于Z軸測(cè)量了。

所有相位變換，令其繞Z軸旋轉(zhuǎn)的夾角(即相位)為φ的話，可用一個(gè)變換矩陣來表達(dá)：

相位變換矩陣，e^iφ = cos(φ)+i*sin(φ)，φ=[-2π,2π]

多量子位門

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

首先請(qǐng)記得多量子比特的情況下，第一個(gè)量子比特也是被表示于最右側(cè)，例如|0001>表示第一個(gè)量子比特為|1>。

CNOT門的含義，就是僅當(dāng)?shù)谝粋€(gè)量子位為|1>時(shí)，才使得第二個(gè)量子取反（即X門），是條件邏輯的基石。

多量子門使得信息在量子比特間獲得關(guān)聯(lián)流轉(zhuǎn)。而涉及更多量子位的邏輯門，都可以由之前介紹的邏輯門合成（將在量子算法章節(jié)舉例）。

4.1.4 量子糾纏態(tài)

在了解了多量子位的基礎(chǔ)上，就能以觀察兩個(gè)量子比特為例，引出第二個(gè)量子力學(xué)核心概念——量子糾纏態(tài)。

簡單的說，形如以下算式（參考單量子位取值|+>時(shí)），兩個(gè)量子既不處于標(biāo)準(zhǔn)基準(zhǔn)（如|00>或|01>），又在兩者之間表現(xiàn)出“有關(guān)聯(lián)”（算式分子部分如果是|00>+|01>就屬于無關(guān)聯(lián)了），就稱它們?yōu)樘幱?strong>“糾纏態(tài)”(Entanglement)。

反向糾纏的量子對(duì)，只可能以相反的坍縮值被測(cè)量

事實(shí)上，算式分子部分還可以是|11>+|00>，以及|11>-|00>、|10>-|01>。這四種狀態(tài)，被稱為“貝爾態(tài)”(Bell States)，所有的雙量子狀態(tài)都可以這4種貝爾態(tài)為基底作線性組合表述（當(dāng)然也可以以4種標(biāo)準(zhǔn)基態(tài)作基底），盡管無法做三維表述。

著名的“薛定諤的貓”，其實(shí)也是在經(jīng)典實(shí)體"貓"和量子"放射性原子"兩者之間構(gòu)建了“糾纏態(tài)”：a|活貓, 原子未衰變> +b|死貓, 原子衰變了>^[16]

當(dāng)對(duì)量子的研究也經(jīng)歷了“無極生太極”(單量子，疊加態(tài))、“太極生兩儀”(雙量子，糾纏態(tài))之后，后續(xù)的變化就比傳統(tǒng)二進(jìn)制時(shí)代更為豐富多彩了。

量子糾纏態(tài)下“一個(gè)量子被測(cè)定/坍縮為0時(shí)、其關(guān)聯(lián)量子必定會(huì)被測(cè)定/坍縮為1”（反向糾纏時(shí)）的特性，首先就是，使得信息仿佛能被以“超過光速的速度”傳遞！當(dāng)然其實(shí)這傳遞并不是基于動(dòng)作，而是基于關(guān)聯(lián)。量子隱形傳輸（以1993年IBM的Bennett等六人團(tuán)隊(duì)的研究為開始^[17]）、量子加密等一系列研究已不斷基于糾纏態(tài)結(jié)出碩果（至今，中科大專家領(lǐng)銜鋪設(shè)的量子通信京滬干線已達(dá)到了2000km的水平^[18][19]）。

希望對(duì)量子力學(xué)方面做更全面了解的IT技術(shù)者，推薦參考張?zhí)烊乩蠋煹?a target="_blank">科普文章，以及郭光燦院士的公開課視頻。

如何在計(jì)算環(huán)境中產(chǎn)生一對(duì)糾纏態(tài)的量子比特呢？有了邏輯門就十分簡單，

圖4-1-4 量子門實(shí)現(xiàn)雙量子位糾纏態(tài)(反向)

利用之前的知識(shí)可知，對(duì)q[0]使用了H門使之進(jìn)入了疊加態(tài)(|+>)，對(duì)q[1]則使用了X門使之反轉(zhuǎn)為|1>，如此一來，在CNOT門的作用下，最終坍縮的結(jié)果只可能是|10>或者|01>（記得第一位位于最右端），實(shí)現(xiàn)“糾纏”。

（細(xì)心的讀者可以發(fā)現(xiàn)這一邏輯門設(shè)置與圖4-1-1是一樣的，其最終測(cè)量結(jié)果也就是圖4-1-2所示的結(jié)果）

#擴(kuò)展閱讀# 三粒子糾纏態(tài)。進(jìn)一步擴(kuò)展到三個(gè)量子比特時(shí)，會(huì)出現(xiàn)拓?fù)鋵W(xué)中有趣的Borromean環(huán)和Hopf環(huán)。^[20]

4.2 第二站，完整用戶手冊(cè)——量子算法

有了更堅(jiān)實(shí)的基礎(chǔ)概念、量子門工具打底，就可以去采摘更具實(shí)用價(jià)值的果實(shí)了。

筆者第一次來訪時(shí)就只有這第二站的“完整用戶手冊(cè)”，等到出了簡明扼要的“新手手冊(cè)”才深切感受到內(nèi)容編排效果的差異…（當(dāng)然這也可能是完整版手冊(cè)的作者確實(shí)懂得的太多不適應(yīng)科普簡化所致）

建議，可直接跳到“量子算法”章節(jié)(新鏈接)，這部分是完整版手冊(cè)特有的。

4.2.1 量子計(jì)算發(fā)展史簡介

完整用戶手冊(cè)中講解的經(jīng)典算法，都曾在量子計(jì)算發(fā)展史上具有重大意義。為此我們先回顧一下“歷代記”。

1981年5月，理查德?費(fèi)曼在波士頓MIT校園、做了題為“Simulating Physics With Computers”的報(bào)告，使得計(jì)算機(jī)科學(xué)家也開始關(guān)注量子力學(xué)。
1992年12月，Deutsch–Jozsa算法問世，這也是第一個(gè)顯示出量子計(jì)算能比傳統(tǒng)計(jì)算提升指數(shù)級(jí)性能的算法。
1994年，Shor算法問世于貝爾實(shí)驗(yàn)室，量子計(jì)算的研究才真正成為學(xué)術(shù)界及一些大型工業(yè)研究部門的矚目課題——因?yàn)镾hor算法大幅降低了“大質(zhì)因數(shù)分解”的復(fù)雜度、動(dòng)搖到了被認(rèn)為最不可破解的RSA加密算法的基石！
1996年5月，Grover算法同樣問世于貝爾實(shí)驗(yàn)室，將遍歷查找的復(fù)雜度降低為N的根號(hào)倍，這使得常用的對(duì)稱鍵加密算法也受到了挑戰(zhàn)。
2001年7月，IBM研究中心研制出一臺(tái)7量子比特的NMR(核磁共振)計(jì)算機(jī)，并成功用它演示Shor算法做了15=3x5的質(zhì)因子分解。
2011年5月，加拿大D-Wave公司公布了第一臺(tái)128量子比特的“商用量子計(jì)算機(jī)”D-Wave-One，并售出了1000萬美金的高價(jià)。
2013年5月，谷歌與NASA合作成立了量子人工智能實(shí)驗(yàn)室，配置了512位的D-Wave量子計(jì)算機(jī)，邀請(qǐng)科學(xué)家參與量子機(jī)器學(xué)習(xí)的研究。
2016年5月，IBM開放量子體驗(yàn)平臺(tái)。
2017年1月，D-Wave將qbsolv工具開源。

量子算法如何對(duì)“同時(shí)存在的2^N種可能性”做出驚鴻一瞥、取得目標(biāo)解的呢？讓我們借著名的Shor算法做一了解。

4.2.2 Shor算法——大質(zhì)因數(shù)分解

當(dāng)一個(gè)整數(shù)大到232位數(shù)時(shí)， 已經(jīng)需要2,000個(gè)CPU年來求解其質(zhì)因數(shù)了，這屬于一個(gè)復(fù)雜度呈指數(shù)增長的NP-Hard問題，也因此被用作為RSA加密算法的核心。

尋階問題(Period finding)

早在1970年代，就發(fā)現(xiàn)若能破解另一個(gè)NPH問題——求得取模指數(shù)方程的“階”，就能降低質(zhì)因數(shù)分解的復(fù)雜度。

階(Period)的定義：對(duì)于給定的N(因數(shù)分解的對(duì)象)和a(與N互質(zhì))，找到能使得a^r-1成為N的倍數(shù)的最小的那個(gè)r，該值就稱為“a對(duì)N取模的階(period)”。

如何保證a與N互質(zhì)呢？可參照一下多數(shù)開發(fā)者都應(yīng)該學(xué)過的、能快速求出最大公約數(shù)的GCD算法（歐幾里得輾轉(zhuǎn)相除法）。

舉例而言，令N=15、a=7，遍歷嘗試過程如下，

使得取模為1的第一個(gè)指數(shù)r，就是階。

IBM這篇完整手冊(cè)對(duì)“period”的描述有失直觀，其實(shí)r的本質(zhì)是一個(gè)周期數(shù)，即a^0 mod N等于1、直至a^r mod N再次為1之間、其實(shí)余數(shù)是以周期性循環(huán)出現(xiàn)的（如1,7,4,13,1..，由模乘的特性決定）。

從階到質(zhì)因數(shù)分解

首先需要找到一個(gè)偶數(shù)階。隨機(jī)取a，如果GCD算法獲得與N的公約數(shù)則直接得到質(zhì)因數(shù)，否則滿足互質(zhì)可求階，階為奇數(shù)時(shí)重選a即可，統(tǒng)計(jì)已證明絕大多數(shù)的階為偶數(shù)。

第二步，a^r-1是N的倍數(shù)，就意味著N的質(zhì)因數(shù)（通常只有2個(gè)，否則破解難度就更低了）有極高概率分別分布在它的兩個(gè)因數(shù)之中！

• a^(r/2)-1不可能是N倍數(shù)（否則r/2應(yīng)該才是階）
• 當(dāng)a^(r/2)+1也不是N倍數(shù)時(shí)，即上式右側(cè)的兩個(gè)乘數(shù)都不可能包含N的所有因數(shù)、而只可能各自都包含(至少)一個(gè)。于是“質(zhì)因數(shù)分解”問題簡化為、將N分別與a^(r/2)-1和a^(r/2)+1做GCD運(yùn)算。
• 當(dāng)a^(r/2)+1是N倍數(shù)時(shí)，重選隨機(jī)數(shù)a。

量子計(jì)算簡化尋階問題

限于篇幅本文需做出較多的省略。Shor算法中會(huì)涉及Deutsch–Jozsa算法中用到過的量子干涉(interference)特性、Grover算法中用到過的神諭酉矩陣電路、以及相位估算(phase estimation)算法。需深入了解這些概念的讀者可查看相關(guān)各章節(jié)。

首先，“神諭”矩陣(Oracle)是一個(gè)當(dāng)符合特定值時(shí)會(huì)促成振幅放大(amplitude amplification)、否則維持基本不變的特殊酉矩陣。如下圖、就是經(jīng)過兩次(兩種)Oralce矩陣變換后、符合特定值的表征比特獲得高出平均值振幅的圖例。

圖4-2-2 Oracle矩陣變換的效果

反復(fù)這一“搖簽”一樣的過程，就最終能獲得一根“神諭”的上上簽……

而f(x) = a*x mod N 就可以被作為一個(gè)Oracle矩陣Ua。繼續(xù)以a=7, N=15為例，從“x=1”起，輸出(7)作為新的x輸入首尾相連的話（注：相當(dāng)于a^r mod N中r=1,2,3…），將滿足1 → 7 → 4 → 13 → 1 → …的周期循環(huán)。這種Ua矩陣可以通過如下的量子門電路實(shí)現(xiàn)：

U7電路，輸入為1(Q4經(jīng)過X門bit-flip為1)，輸出將為7

上圖紅框部分即為U7電路(a=7)，可自行證明其滿足上述輸入輸出周期循環(huán)的要求（原理參見Markov and Saeedi 2012）。

有了Ua電路，通過相位估算法就能近似求得Ua矩陣的特征值(eigenvalues)、即e^iψ周期（參照相位變換矩陣）——a的階r，特征向量使用[0,0,…,1]即可（因?yàn)?code>a^0=1）。（為了求得高精度，這里還用到了一個(gè)技巧，即不直接用Ua來求，而是使用特征值相同的Ub(b=a,a^2,a^4...a^(2^p); 2^p≈N^2)）

為了搭建Ua“模乘”(modular multiplication)這樣的量子電路、還涉及到量子操作必須能“可逆”的特性，對(duì)此感興趣的可參考可逆量子電路(reversible classical circuits)。

D-Wave的退火機(jī)制目前尚無法實(shí)現(xiàn)Shor算法^[21]。

※※※※※※※※

#擴(kuò)展閱讀# “量子糾錯(cuò)”：在有量子門的真機(jī)環(huán)境中（退火機(jī)制下無此需求），伴隨著物理原理的問題、如退相干(Decoherence)，使得需為糾錯(cuò)校驗(yàn)付出額外的資源。

4.3 第三站，Composer或QASM

量子譜曲器(Composer)在第一站中已經(jīng)做過說明。IBM用戶手冊(cè)中每一篇主題的最后，都有量子門的示例，并可以直接點(diǎn)擊用譜曲器打開，或是直接觀看計(jì)算結(jié)果，十分方便。

當(dāng)你使用Composer時(shí)會(huì)要求你登錄。無需申請(qǐng)賬號(hào)，國內(nèi)使用GitHub賬號(hào)即可。

另外，凡是能在譜曲器中打開的量子五線譜，都能通過點(diǎn)擊位于量子門右側(cè)的“QASM”分頁切換到QASM代碼模式，這種量子匯編代碼本身就很直觀，加上能與可視化編輯的五線譜互換后就更加通俗易懂了。

圖4-3 QASM量子匯編代碼

4.4 第四站，IBM量子體驗(yàn)社區(qū)

這里也是IBM做得相對(duì)更好的地方，直接面向互聯(lián)網(wǎng)集思廣益，突出了開放平臺(tái)的初衷。

筆者目前并未在社區(qū)中深入更多，不過看到過一份量子門版的解“地圖填色”問題的實(shí)例，讀者可自行參考。

圖4-4 5地區(qū)填色問題

圖4-4:1 5地區(qū)填色問題量子門設(shè)置

五、小結(jié)：風(fēng)雨幾經(jīng)到枝魁^[1]

2017年初，MIT、也就是36年前費(fèi)曼第一次宣講量子力學(xué)可與計(jì)算機(jī)結(jié)合的大學(xué)，評(píng)選了全球十大突破性技術(shù)^[22]，實(shí)用型量子計(jì)算機(jī)名列其中，成熟期預(yù)估為4~5年。

量子計(jì)算的前路并不平坦，與傳統(tǒng)計(jì)算之間有著較大的差異，也因此IBM與D-Wave紛紛著力于宣傳相關(guān)的技術(shù)，邀請(qǐng)有志人士參與了解、凝聚成更強(qiáng)的社區(qū)力量。希望本文能為相關(guān)的知識(shí)普及、范式轉(zhuǎn)換盡一份微力。

1. 詩句取自網(wǎng)絡(luò)：https://zhidao.baidu.com/question/15979565.html ? ?

2. IBM Is Now Letting Anyone Play With Its Quantum Computer：https://www.wired.com/2016/05/ibm-letting-anyone-play-quantum-computer/ ?

3. Quantum Computing Is Real, and D-Wave Just Open-Sourced It：https://www.wired.com/2017/01/d-wave-turns-open-source-democratize-quantum-computing/ ?

4. Research Blog: When can Quantum Annealing win https://research.googleblog.com/2015/12/when-can-quantum-annealing-win.html ?

5. Research Blog: Machine Learning with Quantum Algorithms https://research.googleblog.com/2009/12/machine-learning-with-quantum.html ? ?

6. IBM thinks it’s ready to turn quantum computing into an actual business, 2017/03: https://qz.com/924433/ibm-thinks-its-ready-to-turn-quantum-computing-into-an-actual-business/ ? ?

7. Partitioning QUBOs for quantum acceleration: http://www.dwavesys.com/sites/default/files/partitioning_QUBOs_for_quantum_acceleration-2.pdf ? ?

8. D-Wave Quantum Computing Primer: https://www.dwavesys.com/tutorials/background-reading-series/quantum-computing-primer ?

9. D-Wave Software: https://www.dwavesys.com/software ?

10. Programming with D-Wave: Map Coloring Problem: https://www.dwavesys.com/sites/default/files/Map%20Coloring%20WP2.pdf ? ?

11. The D-Wave 2000Q System: https://www.dwavesys.com/d-wave-two-system ?

12. IBM Quantum Experience - Composer: https://quantumexperience.ng.bluemix.net/qstage/#/editor ? ? ?

13. IBM Quantum Experience - Full User Guide, Section1-2: https://quantumexperience.ng.bluemix.net/qstage/#/tutorial?sectionId=71972f437b08e12d1f465a8857f4514c&pageIndex=1 ?

14. IBM Quantum Experience - Full User Guide, Section1-5: https://quantumexperience.ng.bluemix.net/qstage/#/tutorial?sectionId=71972f437b08e12d1f465a8857f4514c&pageIndex=4 ?

15. IBM Quantum Experience - User Guide, Section3-3: https://quantumexperience.ng.bluemix.net/qstage/#/tutorial?sectionId=050edf961d485bfcd9962933ea09062b&pageIndex=2 ?

16. 科學(xué)松鼠會(huì) ? 走近量子糾纏（8）——糾纏態(tài)及實(shí)驗(yàn): http://songshuhui.net/archives/83645 ?

17. 科學(xué)松鼠會(huì) ? 走近量子糾纏（18）——量子隱形傳輸（一）: http://songshuhui.net/archives/84316 ?

18. 量子通信京滬干線——?dú)W美沒有的，讓我先來做| 徐令予: https://zhuanlan.zhihu.com/p/25616262?refer=fengyun ?

19. China’s 2,000-km Quantum Link Is Almost Complete: http://spectrum.ieee.org/telecom/security/chinas-2000km-quantum-link-is-almost-complete ?

20. 科學(xué)松鼠會(huì) ? 走近量子糾纏（13）——從糾纏態(tài)到Qubit: http://songshuhui.net/archives/83860 ?

21. IBM Quantum Computing Push Gathering Steam: https://www.nextplatform.com/2016/07/15/ibms-quantum-story-reels-interest ?

22. 重磅發(fā)布：《麻省理工科技評(píng)論》發(fā)布2017年全球十大突破性技術(shù)榜單 http://www.v4.cc/News-3674473.html ?