| 編者按 |
12月7日，谷歌D-Wave研究組在arXiv.org上傳了一篇文章溯职，聲稱其在2013年購買的D-Wave機(jī)器在解決某類特定問題的速度是經(jīng)典計(jì)算機(jī)的10^8倍精盅。
這究竟是炒作還是貨真價(jià)實(shí)的大新聞？D-Wave是量子計(jì)算機(jī)嗎缸榄？而所謂的“一億倍”的加速又是怎么回事渤弛？
D-Wave是加拿大的一家公司。2010年甚带，D-Wave宣布開始生產(chǎn)世界上第一臺商用量子計(jì)算機(jī)她肯。量子計(jì)算機(jī)被認(rèn)為有希望比經(jīng)典計(jì)算機(jī)更快解決地解決一些問題，對于一些問題鹰贵，例如大整數(shù)的因子分解晴氨，它與已知的經(jīng)典算法相比有指數(shù)級的速度提升。
事實(shí)上碉输，D-Wave問世至今籽前，針對它的討論此起彼伏，從未停止過敷钾。一些意見認(rèn)為枝哄，D-Wave機(jī)器是否真的利用量子現(xiàn)象實(shí)現(xiàn)計(jì)算還不確定，它是否比經(jīng)典計(jì)算機(jī)更有優(yōu)勢也不確定阻荒。
Scott Aaronson挠锥，美國麻省理工學(xué)院電子工程與計(jì)算機(jī)科學(xué)副教授，曾一度擔(dān)任“D-Wave首席懷疑官”（Chief D-Wave Skeptic）侨赡。兩年前蓖租，他在其博客上發(fā)表了一篇《D-wave: 最終，真相開始浮出水面》（D-Wave: Truth finallystarts to emerge）羊壹，對相關(guān)的討論進(jìn)行了總結(jié)蓖宦，并號召人們用科學(xué)理性的態(tài)度認(rèn)識D-Wave所達(dá)到的成就。
因此油猫，在經(jīng)歷兩年的“風(fēng)平浪靜”之后稠茂，關(guān)于D-Wave的新聞一經(jīng)出現(xiàn)，很多業(yè)內(nèi)人士的目光便都轉(zhuǎn)向了Scott情妖。讓我們來看看這位曾經(jīng)的“D-Wave首席懷疑官”對此會有怎樣的反應(yīng)吧主慰。
撰文 | Scott Aaronson
翻譯 | 張林峰
校譯 | 林梅嚣州、劉丁、陳明城
編者注：由于文章本身的專業(yè)性该肴，我們首先解釋其中的核心概念和觀點(diǎn)如下：
（1）模擬退火：模擬退火是一種通用的經(jīng)典概率算法，用來在固定時(shí)間內(nèi)在一個(gè)搜索空間內(nèi)找到最優(yōu)解藐不。其原理與金屬退火的原理類似匀哄，遂得此名。其解依概率收斂到全局最優(yōu)解雏蛮。
（2）量子退火：模擬退火的“量子”版本涎嚼。不同的是，經(jīng)典模擬退火依賴的是邏輯運(yùn)算挑秉，量子退火需要依賴量子力學(xué)特有的“隧道效應(yīng)”法梯，更像是讓“大自然”自己去運(yùn)算。
（3）量子蒙特卡羅（QMC犀概，Quantum Monte Carlo）：是一種用來尋求量子體系基態(tài)的經(jīng)典算法立哑。蒙特卡羅方法本身是指使用隨機(jī)數(shù)（或者更常見的偽隨機(jī)數(shù)）來解決很多計(jì)算問題的方法。
（4）時(shí)間復(fù)雜度：是指算法在編寫成可執(zhí)行程序后姻灶，運(yùn)行時(shí)所需要的時(shí)間資源铛绰。時(shí)間復(fù)雜度在數(shù)學(xué)上有更為嚴(yán)格的定義。一般人們關(guān)心的時(shí)間復(fù)雜度是指運(yùn)行時(shí)間隨問題規(guī)模增加的漸近行為产喉。因?yàn)椤胺菨u近”的行為會隨問題規(guī)模的增大而顯得不重要捂掰。特別的，如果該漸進(jìn)行為是多項(xiàng)式（Polynomial曾沈，P）的这嚣，那么人們認(rèn)為這一算法是有效的。對于一些問題塞俱，經(jīng)典算法尚未發(fā)現(xiàn)有多項(xiàng)式的姐帚，而有人提出了多項(xiàng)式的量子算法（例如針對大整數(shù)因子分解的Shor算法）。
（5）最新D-Wave文章中展示的兩個(gè)1億倍加速：第一個(gè)1億倍是“量子退火”與“模擬退火”相比的1億倍漸進(jìn)的加速敛腌，對此卧土，該文章同樣也指出與“量子蒙特卡羅“這一經(jīng)典算法相比惫皱，”量子加速“并不明顯像樊。第二個(gè)1億倍是在D-Wave上運(yùn)行“量子退火”算法與在單核經(jīng)典計(jì)算機(jī)上運(yùn)行“量子蒙特卡羅”算法相比的1億倍常數(shù)的加速。這種常數(shù)加速可能會受問題規(guī)模和計(jì)算機(jī)性能本身的變化而改變旅敷，因此一般不是人們所關(guān)心的生棍。
回想起來，我一直很奇怪媳谁，一年多過去了涂滴，怎么就沒有什么關(guān)于D-Wave的大新聞友酱，也沒有人讓我迅速做出反應(yīng)。這場辯論真的已經(jīng)結(jié)束了嗎柔纵？或者是還沒有“結(jié)束”缔杉，不過就像一直以來本應(yīng)該的樣子，掌握在那些可能不是激烈反對搁料，但至少在聲稱有多少加速時(shí)還蠻謹(jǐn)慎的科學(xué)家手中或详？反正至少能讓我這位前D-Wave首席懷疑官騰出點(diǎn)手來干些更“來錢”的項(xiàng)目，就像在互聯(lián)網(wǎng)上對社會正義無休止的辯論中畫一條中間道路出來郭计，對嗎霸琴？
不，當(dāng)然不是昭伸。
大家現(xiàn)在已經(jīng)看到梧乘，這周一（編者注：2015年12月7日）谷歌的一個(gè)研究小組把一篇重要的研究論文掛在了網(wǎng)上【1】，展示了他們在D-Wave 2X上做的最新的實(shí)驗(yàn)結(jié)果庐杨。對此可以參見Hartmut Neven（編者注：Google 工程負(fù)責(zé)人选调，量子人工智能實(shí)驗(yàn)室主任）的博客【2】。意料之中的是辑莫，大眾媒體對這一結(jié)果的解讀【3】為学歧，D-Wave 2X 在某些方面已經(jīng)比標(biāo)準(zhǔn)經(jīng)典芯片快1億倍，因此剩下的問題就是這一設(shè)備是否為“真正的量子計(jì)算機(jī)”各吨。
在這種情況下枝笨，我做的第一件事就是向Matthias Troyer（編者注：瑞士蘇黎世聯(lián)邦理工學(xué)院教授）求助。他可以算得上是世界上量子退火實(shí)驗(yàn)領(lǐng)域最為博學(xué)揭蜒、公正而又值得信任的人了横浑。令我高興的是，Matthias簡直是慷慨大方屉更，他跟Ilia Zintchenko和Ethan Brown合作徙融，針對新的結(jié)果寫了一篇長達(dá)3頁文章【4】，解釋這一結(jié)果的來龍去脈瑰谜，并允許我與大家分享欺冀。純粹從科學(xué)的角度來講，我的帖子到此已經(jīng)可以結(jié)束了萨脑，只需要給出他們這篇文章的鏈接隐轩。
不過，依舊是從純科學(xué)的角度來看渤早，這個(gè)帖子可能應(yīng)該更早地結(jié)束职车，把谷歌文章的鏈接放上來就是了，因?yàn)檫@篇文章并沒有隱藏一些關(guān)鍵信息，讓它的懷疑者仔細(xì)挖掘才能發(fā)現(xiàn)悴灵。相反扛芽，文章的作者中有這一領(lǐng)域中最為謹(jǐn)慎的人物，把人們可能問到的問題都解釋清楚了积瞒。所以川尖，在某種意義上，我或者M(jìn)atthias可以做的茫孔，僅僅是告訴你空厌，如果讀這些文章，你會學(xué)到些什么银酬。
那么嘲更，D-Wave 2X 是否加速1億倍呢？這是我認(rèn)為能做到不誤導(dǎo)人揩瞪、最為簡短的答案：
是的赋朦，確實(shí)存有明顯漸進(jìn)行為的1億倍加速，并且與量子蒙特卡羅（Quantum Monte Carlo, QMC）算法相比李破，也存在1億倍的加速宠哄。但是，漸進(jìn)的加速僅僅是在與模擬退火（simulated annealing）比較時(shí)得到的嗤攻，而超過QMC的1億倍加速則是一個(gè)常數(shù)因子毛嫉，不是漸進(jìn)的。而且妇菱，在一般情況下承粤，如果與其他經(jīng)典算法比較，兩種加速都會消失闯团。另外辛臊，常數(shù)因子的加速與其說和量子力學(xué)相關(guān)，倒不如說可能和D-Wave極度專業(yè)化的硬件本身更為相關(guān)房交，而后在模擬此專業(yè)化硬件這一問題上再與經(jīng)典芯片做比較（即在D-Wave的Chimera graph架構(gòu)上進(jìn)行Ising自旋最小化）彻舰。因此，雖然確實(shí)是有貨真價(jià)實(shí)而又有趣的進(jìn)展候味，但是與已知最知名的經(jīng)典算法相比刃唤，目前尚不清楚D-Wave的方法速度是否會提高，更別說那些還滿足漸近的或者具有重要實(shí)際意義的最知名的經(jīng)典算法白群。事實(shí)上尚胞，所有這些問題對于整個(gè)量子退火領(lǐng)域來說也都還是個(gè)謎。
展開來說川抡，谷歌這篇文章實(shí)際上有三個(gè)獨(dú)立的結(jié)果：
1. 作者通過Chimera graph中扮演核心角色的8量子比特“集群”辐真，利用高而窄的能壘擋住了前往全局最小的路，從而構(gòu)造了Chimera 實(shí)例崖堤。然后他們發(fā)現(xiàn)侍咱，正如2002年Farhi、Goldstone和Gutmann理論預(yù)言【5】的那樣（這個(gè)預(yù)言我們此前經(jīng)常在這個(gè)博客上討論）密幔，對于這些特殊的實(shí)例楔脯，量子退火達(dá)到全局極小的速度要指數(shù)級快于經(jīng)典模擬退火，而D-Wave利用了這一優(yōu)勢胯甩。就我而言昧廷，由此可以確定，在D-Wave中偎箫，或者至少在8量子比特集群中木柬，發(fā)生了與計(jì)算有關(guān)的集體量子隧穿。另一方面淹办，作者指出眉枕，還有其他經(jīng)典算法，像Selby（在Hamze 以及 de Freitas的基礎(chǔ)上）所構(gòu)造的【6】怜森，可以將這一8量子比特集群打包成可有256種取值的大變量速挑，從而擺脫阻礙模擬退火的能壘。他們還通過經(jīng)驗(yàn)得出副硅，這些經(jīng)典算法的表現(xiàn)要?jiǎng)龠^D-Wave姥宝。作者利用量子蒙特卡羅方法也得到了與D-Wave相仿的漸近復(fù)雜度性能（雖然沒有那個(gè)起主要作用的常數(shù)）。量子蒙特卡羅（盡管名字里有量子二字）是一種經(jīng)典的算法恐疲，經(jīng)常被用來尋找量子力學(xué)系統(tǒng)的基態(tài)腊满。
2. 作者提出：可以隧穿高而窄能壘的這種能力——量子退火目前已經(jīng)展現(xiàn)出來的相較于經(jīng)典退火的核心優(yōu)勢——可能至少跟某些現(xiàn)實(shí)世界中的優(yōu)化問題相關(guān)。他們試圖通過研究一個(gè)經(jīng)典的NP完全問題——數(shù)字劃分（Number Partitioning）培己，來說明這一點(diǎn)糜烹。在這個(gè)問題中，給定一個(gè)含N個(gè)正整數(shù)的集合漱凝，你的目標(biāo)是把它們劃分成2個(gè)子集疮蹦，使得二者各自總和的差別盡可能小。通過在經(jīng)典計(jì)算機(jī)上的數(shù)值研究茸炒，他們發(fā)現(xiàn)愕乎，對于隨機(jī)的數(shù)字劃分問題，量子退火（在理想情況下）和量子蒙特卡羅的速度應(yīng)該都超過了模擬退火壁公，超過的程度也差不多感论。請注意，本文的這一部分不涉及對D-Wave本身的任何實(shí)驗(yàn)紊册，所以我們不知道誤差校準(zhǔn)比肄、編碼丟失等問題是否會抹殺其在理論上所具有的優(yōu)勢快耿。不過即使沒有抹殺，這仍然不能產(chǎn)生一個(gè)“真正的量子加速”芳绩，因?yàn)椋ㄔ僬f一遍）掀亥，量子蒙特卡羅是一種近乎完美的經(jīng)典算法，其在這些問題上的漸近復(fù)雜度與量子退火相當(dāng)妥色。
3. 最后搪花，對于這些能壘高而窄的特殊Chimera實(shí)例，作者發(fā)現(xiàn)嘹害，比起在單核計(jì)算機(jī)上運(yùn)行的量子蒙特卡羅算法撮竿，D-Wave 2X達(dá)到全局最優(yōu)的速度要快約1億倍。但是笔呀，非常有趣的是幢踏，他們還發(fā)現(xiàn)，這種加速不會隨問題規(guī)模的增長而增長许师，而是在大約1億倍的時(shí)候就飽和了惑折。換句話說，這是一個(gè)常數(shù)因子的加速枯跑，而不是漸進(jìn)的惨驶。是的，顯然敛助，用“僅有”1億倍加速（而不是漸進(jìn)加速）的算法解決一個(gè)問題仍然具有實(shí)用價(jià)值粗卜！但重要的是，要知道纳击，這個(gè)常數(shù)因子加速僅僅是在解決此類Chimera graph實(shí)例所對應(yīng)的問題時(shí)才有的——或者本質(zhì)上來講续扔，是在解決“模擬D-Wave本身”這一問題時(shí)才有的！如果你想解決實(shí)際的問題焕数，你首先需要將它嵌入到Chimera graph纱昧，而目前還不清楚的是，這些常數(shù)因子的加速能力是否還存在堡赔。盡管這篇文章中沒有明確說明识脆，我依然相信，在任何情況下善已，當(dāng)我們將其跟（比方說）Selby 算法相比時(shí)灼捂，常數(shù)因子加速會消失，更別說跟量子蒙特卡羅相比换团！
這篇新的谷歌文章給出了關(guān)于D-Wave能力到目前為止最為清晰的展示悉稠。但我要提醒的是，關(guān)于D-Wave的整個(gè)方案艘包，量子計(jì)算研究者們從一開始便擔(dān)心的問題是：糾錯(cuò)能力的缺失的猛、有限溫度量子退火的限制耀盗，我們?nèi)狈γ鞔_的證據(jù)表明它能給出量子加速，以及急著搞出來更多的而不是更好的量子比特卦尊。我還會說叛拷，所有這些擔(dān)憂不僅依然存在，而且還因?yàn)楹芏嘀?jié)問題也開始被人們處理猫牡，從而更加清楚明白地顯現(xiàn)了出來。D-Wave 2X是一個(gè)偉大的工程邓线。但是如果仍然不能在最廣為人知的經(jīng)典算法上展現(xiàn)出漸進(jìn)加速的性能——這篇新的谷歌文章很清楚地表明它沒有——那么這些擔(dān)憂就不是無關(guān)痛癢的淌友。更何況，這些原因似乎和十多年D-Wave 所做出的根本的設(shè)計(jì)選擇是相關(guān)的骇陈。
現(xiàn)在明顯的問題是：是否能通過改進(jìn)D-Wave的設(shè)計(jì)震庭，來得到一個(gè)漸進(jìn)的加速，并且對所有的經(jīng)典算法（包括QMC和Selby算法）都成立你雌，還可以克服將“真實(shí)世界”的問題編碼為Chimera graph所帶來的時(shí)間代價(jià)器联？也許能，也許不能吧婿崭。谷歌這篇文章一遍又一遍地回到D-Wave的未來改進(jìn)計(jì)劃這一主題拨拓，并探討它們可能如何清除那些障礙，達(dá)到“真正的”量子加速氓栈。粗略地說渣磷，如果我們排除推翻重來的辦法，那么主要有四件事情可以試試看是否有效：
1. 更低的溫度（因此有更長的量子比特生命期授瘦，以及在不發(fā)生躍遷到激發(fā)態(tài)的情況下獲得更小的安全能隙）醋界。
2. 對量子比特及其耦合更好的校準(zhǔn)（因此能以更高的精度來編碼感興趣的問題，例如之前提到的數(shù)字劃分問題）提完。
3. 能夠運(yùn)用“非量子隨機(jī)”哈密頓量的能力形纺。（D-Wave現(xiàn)有的機(jī)器都受限于量子隨機(jī)的哈密頓量，后者被定義為所有非對角項(xiàng)均為非正實(shí)數(shù)的哈密頓量徒欣。從工程的角度來看量子隨機(jī)的哈密頓量是更容易的逐样，對于經(jīng)典算法，例如QMC來說打肝，它們也是最容易被模擬的——如此容易官研，以至于人們還在爭論非量子隨機(jī)量子退火是否在理論上可以有真正的量子加速）
4. 量子比特之間更好的連通性（從而減少將實(shí)際感興趣的問題編碼到Chimera graph中所付出的巨大代價(jià)）。
（注意闯睹，“更多的量子比特”不在這個(gè)名單上：如果利用D-Wave真能實(shí)現(xiàn)“真正的量子加速”戏羽，那么它們擁有的1000多個(gè)量子比特早夠讓人們看出個(gè)究竟了。）
不管怎樣楼吃，這些當(dāng)然都是D–Wave 的設(shè)計(jì)者們知道而且在不久的將來會做的事情始花。但是妄讯，即便D-Wave在這四個(gè)方面都做出了改進(jìn)，我們?nèi)匀徊恢朗欠駮霈F(xiàn)一個(gè)真實(shí)的酷宵、漸近的亥贸、勝過Selby算法的、克服編碼代價(jià)的量子加速浇垦。我們只是不能肯定地說出那個(gè)否定的答案炕置。
與此同時(shí)，在博客上討論很容易被遺忘的是男韧，D-Wave只是實(shí)驗(yàn)量子計(jì)算領(lǐng)域的一個(gè)真子集朴摊，而在過去的一兩年里，許多其他方面取得了更為令人興奮的成就此虑。特別是甚纲，谷歌的John Martinis組（編者注：John Martinis是加州大學(xué)圣芭芭拉分校物理學(xué)教授，2014年加入谷歌朦前，也是谷歌關(guān)于D-Wave文章的共同作者之一）現(xiàn)在有相干時(shí)間比D-Wave高幾個(gè)數(shù)量級的超導(dǎo)量子比特介杆，并對其中的9個(gè)初步展示了量子糾錯(cuò)。他們現(xiàn)在在討論的是將其擴(kuò)展到大約40個(gè)質(zhì)量超高的韭寸、耦合可控的量子比特——不是在遙遠(yuǎn)的未來春哨，而是在最近幾年里。如果他們做到了這一點(diǎn)恩伺，我將非常樂觀地認(rèn)為悲靴，他們將能夠就某件事情展示出明顯的量子優(yōu)勢（例如，一些像玻色抽樣那樣的抽樣任務(wù)）——如果不一定是有實(shí)際意義的事情的話莫其。我上周剛訪問過的IBM Yorktown Heights同樣也在致力于合成相干時(shí)間達(dá)很多微秒的超導(dǎo)量子比特癞尚。與此同時(shí)，一些頂級的離子阱研究組乱陡，例如馬里蘭大學(xué)的Chris Monroe組浇揩，也正在討論類似的他們希望能夠盡快做到的大新聞。對于量子計(jì)算研究的“學(xué)術(shù)方法”——不妨概括為“理解量子比特憨颠、控制它們胳徽、保持其量子力學(xué)特性，最終在此基礎(chǔ)上將其擴(kuò)展”——終會結(jié)出多汁的果實(shí)爽彤。
我依舊不知道什么時(shí)候甚至是否我們會得到一個(gè)實(shí)用的养盗、通用的、能容錯(cuò)的量子計(jì)算機(jī)适篙，能夠?qū)?0000位的數(shù)字進(jìn)行質(zhì)因子分解等往核。但是現(xiàn)在看起來，讓Gil Kalai（編者注：Kalai為以色列希伯來大學(xué)數(shù)學(xué)系教授）和其他量子計(jì)算懷疑者們承認(rèn)錯(cuò)誤只是幾年時(shí)間的問題——這不管怎樣嚷节，都是一直以來我所關(guān)心的主要用途聂儒！
對于量子計(jì)算來說虎锚，這是一個(gè)令人興奮的時(shí)代。很多事情接踵而至衩婚，比我預(yù)想的都更快窜护。當(dāng)我們朝著這個(gè)計(jì)算新世界勇敢地、相干地非春、希望非量子隨機(jī)地柱徙、可能容錯(cuò)地蹣跚前進(jìn)時(shí)，我對于我這個(gè)博客的目標(biāo)永遠(yuǎn)跟過去的十年一樣：不胡亂預(yù)言奇昙，不挑選贏家护侮，而僅僅是試著去理解和解釋那些已經(jīng)被證實(shí)的和還未被證實(shí)的事情。
參考文章相關(guān)鏈接：
【1】谷歌論文“What is theComputational Value of Finite Range Tunneling?”敬矩，鏈接：http://arxiv.org/abs/1512.02206
【2】Hartmut Neven關(guān)于D-Wave機(jī)器最新進(jìn)展的博文概行，http://googleresearch.blogspot.ca/2015/12/when-can-quantum-annealing-win.html
【3】美國科技媒體對D -Wave的解讀：http://www.techtimes.com/articles/114614/20151209/googles-d-wave-2x-quantum-computer-100-million-times-faster-than-regular-computer-chip.htm
http://www.theregister.co.uk/2015/12/09/googles_quantum_computer/
【4】Matthias Troyer文章鏈接：http://www.scottaaronson.com/troyer.pdf
【5】Edward H. Farhi蠢挡，Jeffrey Goldstone和SamGutmann弧岳，三人均為麻省理工學(xué)院理論物理學(xué)教授，文章鏈接：http://arxiv.org/abs/quant-ph/0201031
【6】Alex Selby,劍橋大學(xué)數(shù)學(xué)博士业踏，Selby算法發(fā)明人禽炬，文章鏈接：http://arxiv.org/abs/1409.3934
本文經(jīng)Scott Aaronson授權(quán)翻譯，發(fā)表時(shí)有部分刪節(jié)勤家，更多更新及討論請點(diǎn)擊Google, D-Wave, and the case of the factor-10^8 speedup for WHAT?
知識分子腹尖，為更好的智趣生活。
《知識分子》由饒毅伐脖、魯白热幔、謝宇三位學(xué)者創(chuàng)辦并擔(dān)任主編。
投稿讼庇、授權(quán)事宜請聯(lián)系：zizaifenxiang@163.com绎巨。
