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

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

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

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

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

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

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

那么為什么兩家要先后對這一尖端料睛、高價值的研究成果予以開放呢丐箩？

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

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

二塞俱、果園外的藩籬

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

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

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

• 電子一脈：晶體管九秀、電腦、手機…
• 光子一脈：激光
• 其他：能源粘我、核聚變

可另一方面鼓蜒，先賢的話也確實界定了量子力學(xué)的理解難度——尤其是因為其有違直覺(counter-intuitive)，后文將會擇要講解理解量子計算所需的兩個量子力學(xué)知識：

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

1. 缺乏中文資料
   量子力學(xué)的普及文章是有的征字，但截至發(fā)稿為止都弹、尚未見到對兩大陣營開放平臺的較為深入的中文評測、對比柔纵。
   因此缔杉，文中也會適當(dāng)出現(xiàn)英文用語以便于擴展閱讀、及避免歧義搁料。

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

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

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

三仁堪、D-Wave的量子果園

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

• 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環(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工具范例“美國地圖填色”運行結(jié)果

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

最初GitHub上的這個官方Sample運行結(jié)果還不正確欺冀，提交Bug后修改了usa.adj文件中兩個州的鄰接關(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的退火式量子計算最擅長解決的這種QUBO問題^[7]（二次非約束二進(jìn)制優(yōu)化悴灵，目前有簡述成“離散最優(yōu)化”的），可更直觀的表述為下圖骂蓖，

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

引入兩個概念就能解釋這個游戲，

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

在D-Wave官方資料中缰贝，會對weight、strength命名為h畔濒、J剩晴，或是a、b、以及Qii赞弥、Qij毅整，請注意其實質(zhì)即可。

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

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

奇妙的地方來了彻舰。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.4 第四站灼捂，官方編程手冊四色問題詳解

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

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

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

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

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

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

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

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

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

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

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

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

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

#擴展閱讀#　用多個而非一個物理qubit來映射一個“邏輯qubit”，是因為需要在表征命題對象的邏輯qubit組內(nèi)部建立起“完全連接”（兩兩之間都有連接）兔簇，但硬件架構(gòu)上無法直接對4個qubit建立完全連接炕置，可參看硬件概述 1.1、1.2中的圖解男韧。

幾個要點：

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

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

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

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

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

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

※※※※※※※※

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

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

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

四、IBM的量子果園

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

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

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

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

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

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

4.1.1 Quantum Score（量子五線譜）

初入IBM園林，不僅有高懸的奇香異果她倘，甚至還有悠揚的仙樂飄來璧微。

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

圖4-1-1 量子譜曲器

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

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

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

亂入：園林深處，奇幻靈動的量子邏輯門安接，美妙的神之樂章翔忽，竟令人不禁想起了身著紅色神斗衣的搖光星米伊美、在撫動魔音盏檐。歇式。。

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

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

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

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

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

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

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

上圖稱為布洛赫球面（Bloch Sphere）痹栖，球半徑為1亿汞，分別有X、Y揪阿、Z三個維度疗我，量子比特的“奇幻靈動”位置咆畏、就必可表征為球面上的某個點，

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

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

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

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

• Y軸最有違直觀矗烛，不過也無非因為引入了復(fù)數(shù)i（即i^2=-1）辅柴，更直觀的話，可采用軸間夾角θ與φ表征一個量子向量|ψ>瞭吃。

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

4.1.3 量子邏輯門

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

單量子位門

第一組：X門

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

其矩陣表述為：

X門變換矩陣

第二組：H門

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

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

其矩陣表述為：

H門變換矩陣

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

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

Z門滤淳，是基于Z軸的軸變換，即180度旋轉(zhuǎn)砌左，會使得|+>被轉(zhuǎn)成|->脖咐。

S門，則是繞著Z軸作90度旋轉(zhuǎn)汇歹，會使得|+>被轉(zhuǎn)到Y(jié)軸正向相位屁擅。但因為S門不是對合可逆的，所以設(shè)置一個它的逆操作S+門产弹。

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

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

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

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

多量子位門

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

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

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

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

4.1.4 量子糾纏態(tài)

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

簡單的說，形如以下算式（參考單量子位取值|+>時）拧簸，兩個量子既不處于標(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)盆赤。

反向糾纏的量子對贾富，只可能以相反的坍縮值被測量

事實上，算式分子部分還可以是|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)作基底），盡管無法做三維表述庸追。

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

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

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

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

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

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

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

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

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

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

有了更堅實的基礎(chǔ)概念赘理、量子門工具打底宦言，就可以去采摘更具實用價值的果實了。

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

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

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

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

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

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

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

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

尋階問題(Period finding)

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

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

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

舉例而言之景，令N=15斤富、a=7，遍歷嘗試過程如下锻狗，

使得取模為1的第一個指數(shù)r满力，就是階焕参。

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

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

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

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

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

量子計算簡化尋階問題

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

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

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

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

而f(x) = a*x mod N 就可以被作為一個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矩陣可以通過如下的量子門電路實現(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]即可（因為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的退火機制目前尚無法實現(xiàn)Shor算法^[21]。

※※※※※※※※

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

4.3 第三站男公，Composer或QASM

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

當(dāng)你使用Composer時會要求你登錄。無需申請賬號低剔，國內(nèi)使用GitHub賬號即可速梗。

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

圖4-3 QASM量子匯編代碼

4.4 第四站屋摔，IBM量子體驗社區(qū)

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

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

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

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

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

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

量子計算的前路并不平坦，與傳統(tǒng)計算之間有著較大的差異嫁赏，也因此IBM與D-Wave紛紛著力于宣傳相關(guān)的技術(shù)其掂，邀請有志人士參與了解、凝聚成更強的社區(qū)力量潦蝇。希望本文能為相關(guān)的知識普及款熬、范式轉(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é)松鼠會 ? 走近量子糾纏（8）——糾纏態(tài)及實驗: http://songshuhui.net/archives/83645 ?

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

18. 量子通信京滬干線——歐美沒有的攘乒，讓我先來做| 徐令予: 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é)松鼠會 ? 走近量子糾纏（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ā)布：《麻省理工科技評論》發(fā)布2017年全球十大突破性技術(shù)榜單 http://www.v4.cc/News-3674473.html ?