如何評價 2015 年 12 月 10 日谷歌在發布會上稱發現了一個比傳統演算法快一億倍的量子演算法？

01-02

12月10日消息，據Engadget UK網站報道，本周三谷歌宣布在量子計算領域取得了突破性進展。公司認為他們發現了一個量子演算法可以以比傳統過程快1億倍的速度解決問題。一旦被證實，這項發現不僅將導致類似iRobot的人工智慧的發展，還能促進美國太空項目的研發。
2013年谷歌和美國宇航局共同研發了D-Wave X2 計算系統，這個D-Wave應該是世界上第一個功能正常的量子計算機，儘管公司內外的專家從未總結性的證明這台機器真正進行了量子計算，而現在這已經成為過去式。
本周三谷歌的宣布主要關注於「量子退火」演算法，這種技術確定了當面臨一系列潛在解決方案時，一個特定函數的全局極小值。通俗來說，就是當給定一系列選項時，它能夠確定完成一個任務所需的最優（也就是最有效）整體行動方案。科學家們一直都在研究量子退火，儘管使用的兩種主要技術模擬退火演算法(Simulated Annealing，簡稱SA)和「量子蒙特卡洛」只是運行在傳統硬體上的模擬系統。而另一方面，D-Wave系統是硬體編碼在自身量子陣列里運行量子退火演算法。

近期谷歌在概念驗證實驗里測試了最新的量子退火演算法，並與運行模擬退火和蒙特卡洛方法的傳統系統進行了對比，結果非常鼓舞人心。從以上圖表可以看出，谷歌的方法輕而易舉的打敗了另外兩種方法，以快1億倍的速度解決了具有1000個二進位變數的函數。
谷歌將這個結果稱為「非常有趣且鼓舞人心」，儘管在將這項研究投入消費者市場之前還有很長一段路要走。然而一旦成功，它將掀起新一波的科技革命。利用它人工智慧研究人員或可以開發更智能、反應更靈敏的計算機學習系統，美國宇航局可以利用它模擬火箭發射（或者整個太空項目），即使是普通的材料科學也可以從這項技術里受益。

謝 @徐浩浩邀，久等。

2013年谷歌和美國宇航局共同研發了D-Wave X2 計算系統，這個D-Wave應該是世界上第一個功能正常的量子計算機，儘管公司內外的專家從未總結性的證明這台機器真正進行了量子計算，而現在這已經成為過去式。

D-wave是世界上第一種商用的利用量子效應進行計算的機器。它最準確的稱呼是量子退火機（Quantum Annealing Machine），只能運行量子退火演算法。量子退火演算法是用來解決最優化問題的。

新聞里還有一些謬誤。D-wave System是加拿大公司D-wave Inc.研發的，Google和NASA花了一千萬美元買了一台。

最優化（Optimization）是機器學習/人工智慧中必不可少又十分消耗計算的一步，所以Google對量子退火非常上心。與Google聯合建立量子人工智慧實驗室（Quantum AI Lab）的NASA也很傾心D-wave，也是因為宇宙飛船的遠距離航線是非常複雜的最優化問題。亞馬遜的創始人貝佐斯和CIA是D-wave這家公司的兩大股東。亞馬遜可以用退火機來優化物流運輸線。CIA的目的我就猜不到了。

由於D-wave不能運行其他量子演算法，不能進行量子邏輯門（Quantum Gate）操作，不是通用型量子計算機，相當一部分科學家不認為D-wave是真正的量子計算機。

但是，D-wave毫無疑問是具有一台具有量子計算功能的機器（Machine）。因為D-wave可運行絕熱量子計算，而且絕熱量子計算在理論上等價於基於邏輯門的標準量子計算。

絕熱量子計算和量子退火的關係有一些模糊。但是量子退火演算法的提出者西森教授認為絕熱量子計算是量子退火的子集。更多情況下，這兩者的原理和目的非常接近，以至於很多paper都沒做特別的區分。

目前實驗上最主要的關注點在組合優化上，尤其是對二進位變數函數的優化。一方面是，經典計算機解決凸優化（Convex Optimization）問題相當高效，一方面是D-wave的晶元本身還很初級，目前還表示不了太複雜的函數。D-wave的量子比特是由通電流的超導環製成的，電流逆時針即表示邏輯0，順時針則表示邏輯1。所以D-wave表示二進位變數非常容易。

在谷歌這次實驗之前，一直有相當多的人懷疑D-wave是否可以比經典計算機更快的解決組合優化問題。D-wave也一直沒有給出確鑿的實驗證據。這次Google的實驗算是一個顯著的支持證據。不管D-wave能不能叫量子計算機，D-wave都比一個單核的經典計算機更快（快1億倍）地解決了這個組合優化問題。

幾位答主都提到了一個問題，為什麼實驗結果是快一個常數倍？對於不了解量子退火的人來說不太容易理解。主要原因是因為量子退火演算法的時間複雜度和基於門操作的演算法的時間複雜度很難比較。基於邏輯門的演算法，無論是經典的還是量子的都會寫成類似於 $O(f(n))$ 的形式。像Shor演算法雖然從來沒有在量子計算機上運行過，但沒人質疑它是不是真的更快，因為它是基於邏輯門的演算法，時間複雜度就是邏輯門操作的次數。

經典演算法解決谷歌實驗組這個二進位變數函數優化問題的時間複雜度就是 $O(2^n)$ 。搜索空間會以2的指數倍增長。而量子退火演算法的時間複雜度是 $O( frac{1}{ Delta E^2})$ 。這個是基態和第一激發態的能量差，這個比較正式的說法叫譜隙（Spectral Gap）。

（等等，為什麼機器學習、優化問題會有量子力學裡的基態？最後解釋。）

也就是說，無論這個優化問題有多麼複雜，哪怕搜索空間比整個宇宙的粒子數目還多得多，量子退火的速度都可能很快。現在是 $2^{1000}$ 的搜索空間，量子退火已經快一億倍了。如果2000個變數呢？那麼，最完美的情況（Spectral Gap還是同一個量級）是比普通的單核電腦快一億億倍左右。

就算2000個變數不夠，那10000個變數總夠了吧？D-wave最新型號是1024比特（實際上是1097比特）。每一代D-wave的比特數都會翻倍，每兩年就能推出新型號。幾年之內，D-wave比特數就能達到萬的量級。處理組合優化問題上，D-wave勝過天河二號是遲早的事。現在樂觀的估計是一個十年（decade）。

量子退火/量子優化/絕熱量子計算為什麼備受關注？因為標準量子計算以十年為單位規劃藍圖，而量子退火以月為單位向前邁進。

為什麼機器學習、最優化會有基態？是這樣的。一個機器學習問題總會被轉化為求解一個最優化問題。而一個最優化問題的cost function和一個量子系統的能量有類似的數學結構。理論上來講，總是存在一個量子系統對應一個機器學習系統（但我們未必能構造這個量子系統）。這個量子系統的能量就是我們要優化的cost function。D-wave就是一種可以表示一大類機器學習（比如clustering）和最優化問題（比如組合優化）的量子系統。

Spectral Gap和n有什麼關係？仍然沒有答案。只能簡單地想像一下，n增加，量子系統變複雜，複雜的量子系統一般有更小Spectral Gap，但是變小的幅度肯定不會快到 $2^n$ 倍。想一下原子的能譜結構和最簡單的旅行商問題就明白。Spectral Gap和n關係，比較糟糕的一點是，最近一篇Nature說，一般情形下的 Spectral Gap 是不可判定(Undecidability)的。（這裡有個簡單的介紹Nature 和 Science 上有哪些非常有趣而又腦洞大開的文章？ - Climber.pi 的回答）或許，除了不停地實驗以外，我們永遠都不知道D-wave的極限在哪裡。

這次的實驗的確可以算是一個里程碑。512比特的D-wave沒辦到的，1024比特D-wave辦到了，第一次超越一台電子計算機一億倍。這一系列的實驗還會繼續下去，在解決問題的速度上和表示問題的廣度（更廣義的組合優化問題，甚至是連續變數的非凸優化問題）上要繼續前進。

應該不會補充了。

現在最想做的就是早點把自己設計的演算法實現了。

量子演算法，快一億倍，兩者放在一起沒什麼稀奇。實際上計算機科學家一般不說快一億倍。一方面是因為快一億倍「太少了」，一般也很少出這種提高常數倍的結果。

而會說，e.g. 從 $n^3$ 優化到 $n^2$ ，快了 $n$ 倍。這裡 $n$ 一般是輸入的長度。如果用來處理長度為一億的數據，那也就快了一億倍。

注意新聞中提到，「以快1億倍的速度解決了具有1000個二進位變數的函數」。就是說當輸入的「大小」是 1000 時，谷歌的量子演算法比其它方法快了 $10^8$ 倍。（從新聞來看，「其它方法」可能不包括其它研究組使用 D-Wave 的結果，所以比較 tricky。）如果問題的大小稍微大一點，加速的倍數還能顯著增長（一般是指數增長）。

但新聞沒有提這方面，原因是因為谷歌無法用 D-Wave 在更大的問題上進行計算了。與傳統計算瓶頸在計算能力不同。對量子計算來所，存儲能力才是瓶頸。前一代 D-Wave 只能同時維持大約一千量子比特。估計這一代也不會有多大突破。因此谷歌用 D-Wave 時，只有在問題大小在幾千位是才能用純的量子演算法。既然更大的問題谷歌還算不了，新聞就不提及了。

「2013年谷歌和美國宇航局共同研發了D-Wave X2 計算系統」，呵呵，D-Wave公司要哭死了。這才是那篇新聞最大的錯誤好嗎。

D-Wave這個東西很神奇的，大家已經用了好幾年，沒人知道為什麼work，沒人知道什麼時候會不work。就這麼一直用。現在終於有個特製演算法能在某個條件下快一億倍了。

需要注意的是，作為對比的演算法，是在傳統硬體上的模擬量子蒙特卡洛，換句話說，把真機運行和模擬器拿來比速度，呵呵。其實這是以其人之道還治其人之身了。以前大家是用傳統演算法在傳統機器和D-Wave上跑，得出D-Wave慢一億倍，現在變成反之亦然了。

謝邀，我不是研究量子計算的，但我想引用一下量子計算的專家Scott Aaronson博客（Shtetl-Optimized）上的評論來回答這個問題。對於D-Wave X2 是否真的比經典演算法快一億倍的問題，Scott Aaronson認為不一定。原因主要有三個，其一，D-wave只和模擬退火和量子蒙特卡洛演算法進行了比較，不能證明D-wave比最優的經典計算快一億倍；其二，在與量子蒙特卡洛演算法的比較中，沒有排除D-wave優化了硬體導致加速的影響，一億倍的加速可能和量子計算關係並不大；其三，D-wave選擇了得到最優結果的例子去和經典計算比較，但對於一般性的問題，計算速度應該比一億倍低。此外，Scott Aaronson對D-Wave的本身設計也表示憂慮，比如D-Wave用了大量的量子比特，卻沒有用量子糾錯碼。總之，現有的結果還不能證明D-Wave的計算機實現了真正的量子計算。

我覺得信息還不夠完整，因為目前的這些「非常快的量子演算法」，說的都只是計算階段。而獲取結果的時間也是相當長的，而且計算還有可能會失敗，這些問題都不可忽視，不知道文章有沒有提到。

想起個笑話：量子計算機可以在同時存在的所有結果中直接退火出排序好的結果

http://mp.weixin.qq.com/s?__biz=MzA3OTgzMzUzOA==mid=401108697idx=1sn=9e4f69e382d613b3e92a721f9e39cee5scene=0#wechat_redirect

分享一個剛看的塞先生的量子糾纏科普文。

不是作量子信息的，只能作一個前端的科普，文中有提到D-wave演算法。

個人猜測這個在技術上是一個重大的突破！

答主問的問題太前沿了，不太適合知乎吧。估計只有量子信息的專家和研究生能回答。

跟上時代永遠是很困難的事，估計大多數程序員不會蛋疼到去看量子力學吧。。。

知乎首答。

作為一個研究量子演算法剛剛開始入門的研究生，我主要想介紹一下最近讀完的兩篇文章，&（以下簡稱文1）和&（以下簡稱文2）。英文網址似乎沒有自動截取標題功能，也不知道怎麼把超鏈接加到標題上，所以……下載地址分別是http://arxiv.org/abs/1401.2910和http://arxiv.org/abs/1512.02206。

文1是14年1月發表的，結論是D-Wave 2(DW2)在執行退火演算法的時候相比於經典計算機並沒有量子加速效應的體現，無論是耗費的時間還是時間複雜度的增長都與經典計算機相近。文2就是題主提到的谷歌最近做出來的，在新購入的D-Wave 2X(DW2X)上取得的研究成果，這次的結論是D-Wave在945個qubits的情況下可以比使用單核的Intel Xeon E5-1650運行的模擬退火演算法快一億倍。為什麼時隔兩年得出來的結論會有這麼大的差別？其實原因很簡單，因為兩次跑的基準問題（benchmark problem）是不一樣的。

接下來我盡量嘗試把兩篇文章的基本概念和得出結論的過程講清楚，然後再談談自己的看法。

首先，我們需要知道是誰跟誰比快一億倍，或者更準確地說，是什麼樣的量子演算法和什麼樣的經典演算法快一億倍：

模擬退火演算法(Simulated Annealing，簡稱SA)是用來求最優化問題的，在兩篇文章中則轉化為求全局極小值（global minimum)的問題。SA的思路是在溫度高的時候讓系統可以處於任意一個態上，逐漸降低溫度，系統能量也隨之減少，最後穩定在一個局域極小值（local minimum）上。更詳細的步驟見大白話解析模擬退火演算法。
量子退火演算法（Quantum Annealing），按照我從上述兩篇文章中了解到的信息，就是量子絕熱演化（Quantum Adiabatic Evolution）。系統哈密頓量寫作 $H(t)=-A(t)sum_{j=1}^{N}{sigma_{j}^{x} } +B(t)H_{P}$ ，其中 $H_{P}$ 表示待求問題的哈密頓量。系統初態是 $sum_{j=1}^{N}{sigma_{j}^{x} }$ 的基態， $A(0)ll B(0)$ 並且當T很大時 $A(T)gg B(T)$ ，絕熱定理保證了只要演化時間足夠長系統最後就會處於 $H_{P}$ 的基態，有了基態很容易就能求出待求的基態能量。

單從上面的說明似乎還看不出經典和量子演算法之間的聯繫，我的理解是，我們可以從退火演算法的角度去看待絕熱演化，把初態，即 $sum_{j=1}^{N}{sigma_{j}^{x} }$ 的基態用 $H_{P}$ 的本徵態做展開，可以得到一系列的相對高能態。同時把總哈密頓量的第一項 $-A(t)sum_{j=1}^{N}{sigma_{j}^{x} }$ 看作一個擾動，類似於高溫的效果，隨時間增加這個擾動程度減小，類似於溫度降低。並且QA與SA一樣的，結果仍然有可能是一個局域極小值。

下面來看文1，文章中為了檢測真實的量子加速效應，儘可能的使參數最優化（optimal），即調整參數使得某個變數規模下演算法以某個概率（通常是99%)得到正確結果所花的時間最短，以防止次優化（suboptimal）掩蓋加速效果。然後就是對比SA和QA在分別調到最優的情況下計算Ising模型的基態能量所耗費的時間，結論就是沒有比較可靠的證據說明有量子加速效應的存在。

文2給出了改變如此巨大的解釋，就是QA相比於SA的加速效果體現在量子隧穿（tunneling）上，假如問題的勢能函數變動比較劇烈，形成又高又窄的勢壘，則QA將會有明顯的加速。看文章里的這幅圖：

黑色的線代表勢壘，假如兩種演算法下同樣的從A點出發跑到最小值D點，SA需要跨過中間的三個勢壘，這個概率將會很小；而QA可以沿著紅線輕鬆地穿透勢壘，藍線代表隧穿過程。也就是說有理由相信在擁有很大高且窄的勢壘情況下，QA將產生明顯的量子加速效應。接下來文章中就給出了他們精心製作的「崎嶇的能量風景」（rugged energy landscape），也就是說這個新問題符合前面給出的要求。同樣調整到最優化的情況下，在945個二進位變數的問題規模下，QA比SA就快了一億倍。然而需要指出，對於這個問題還有很多經典演算法比QA和SA都要快，因此D-Wave 2X暫時還不具有實用性。

（未完）

哈，Google在暗示RSA（等一切可以窮舉暴力破解的加密演算法）已經玩壞了，RSA安全加密時代結束！

接著下一個會議主題會是：「安全領域震驚，專家緊急研討量子加密方案」！

天天看他們吹牛逼，我都看煩了。你們是不是缺經費了。。

量子排要重出人間了

如果是「快一億倍」這個描述按字面意思來理解的話似乎並沒有什麼本質上的提升，演算法的複雜度並不會因為乘上一個常數而降低

我只是覺得我的比特幣就要貶值了……

這裡貼一個Scott Aaronson的blog作參考...裡面Scott回答了他對這個paper的看法……

http://www.scottaaronson.com/blog/?p=2555

其實我納悶的是，為什麼只快這麼一點點。。。

可以去看看google寫的論文並沒有這麼誇張也不是發現了一個演算法而是早已經有的量子退火演算法谷歌證明了它能夠比模擬退火快十的八次方倍但他們自己也說了離實用的距離還很遙遠。

假挖賊禿一億！

第一反應是，google好流弊，趕緊買點google股票，到這玩意大範圍商用那一天我就發財了

第二反應是，擦，到這玩意能商用那一天，我那發了財的用AES-256加密的股票賬戶也早被黑客掏空了吧……

谷歌開啟未來

如果你只是問AI的話

幾十年前就有科學家預言要是計算機性能提高。。。

然後現在的電腦隨隨便便把幾十年前電腦描成渣渣。。。然後呢

好複雜啊｀。就問你能不能玩喜愛服啊～不能玩有個鬼用