如何評價谷歌的量子霸權計劃：宣稱有望明年底突破經典計算極限？
A critical question for the field of quantum computing in the near future is
whether quantum devices without error correction can perform a well-defined
computational task beyond the capabilities of state-of-the-art classical
computers, achieving so-called quantum supremacy. We study the task of sampling
from the output distributions of (pseudo-)random quantum circuits, a natural
task for benchmarking quantum computers. Crucially, sampling this distribution
classically requires a direct numerical simulation of the circuit, with
computational cost exponential in the number of qubits. This requirement is
typical of chaotic systems. We extend previous results in computational
complexity to argue more formally that this sampling task must take exponential
time in a classical computer. We study the convergence to the chaotic regime
using extensive supercomputer simulations, modeling circuits with up to 42
qubits - the largest quantum circuits simulated to date for a computational
task that approaches quantum supremacy. We argue that while chaotic states are
extremely sensitive to errors, quantum supremacy can be achieved in the
near-term with approximately fifty superconducting qubits. We introduce cross
entropy as a useful benchmark of quantum circuits which approximates the
circuit fidelity. We show that the cross entropy can be efficiently measured
when circuit simulations are available. Beyond the classically tractable
regime, the cross entropy can be extrapolated and compared with theoretical
estimates of circuit fidelity to define a practical quantum supremacy test.
------ https://arxiv.org/abs/1608.00263
補一篇 Aram Harrow 和 Ashley Montanaro 今年的綜述: Quantum computational supremacy.
簡單介紹並比較了幾種可能達到 quantum supremacy 的選擇, 比如 Boson sampling / IQP / QAOA 和 random circuits, 以及常見的 assumption, 比如 polynomial hierarchy 和 average case. 不過 Google 用的 random circuits 有若干個 negative results, 給出的 qubit 數量估計都在在 附近......
------------------------------------------
首先，quantum supremacy 這說法和Google半毛錢關係都沒有啊。。。網上那幾篇中文報道寫的都什麼亂七八糟的；還有某些公眾號，把質疑二十年前已經被廣泛接受的里程碑式工作的「民科」風格文章發上來，說是「討論」。本來嘛，這些事情確有爭論，Gil Kalai 和 Aram Harrow 還在2012年左右在兩人博客上進行過一系列公開辯論（見Quantum Supremacy and Complexity和Gil Kalai的http://www.ams.org/publications/journals/notices/201605/rnoti-p508.pdf），一部分質疑就集中在糾錯編碼的可行性本身。即便真有問題，quantum Fourier transform 可是給出了一系列工作的，倒是用他的做法攻擊一下整個體系和近年工作看看？盯著二十年前的東西不放算哪門子事，HSP近年的進展又不是沒有。
11年的時候，John Preskill在第二十五屆索爾維會議上提到了quantum supremacy （文稿見見 http://arxiv.org/abs/1203.5813）。簡單的說，用少量的qubit來驗證量子計算機與經典計算機相比可以得到的超多項式加速。這東西的目的之一，就是證偽extended church－turing thesis，即有效計算不等於圖靈機有效計算。當然，這也確實是實驗和理論的絕佳結合處：由理論研究者提出只需要少量qubit的問題，再由實驗研究者在實際系統上實現（比如說十年內數十qubit）。最為出名的工作就是Boson Sampling，除此之外還有IQP / commuting Hamiltonians和Quantum Approximate Optimization Algorithm（QAOA）；叉院近期也有一篇相關的工作，給出了複雜性結果和實驗方案，見http://arxiv.org/abs/1607.04947。既然如此，那麼想來這些可能的驗證當然將會發生在世界上最好的幾個實驗組，比如John Martinis組；標題這麼寫自然也沒什麼不妥。
當然了，這玩意確實是Scott Aaronson的最愛，參見此公在Quora的回答（https://www.quora.com/What-work-in-quantum-computing-are-you-most-excited-about）：
In experimental QC, what excites me the most right now is the race to achieve what some people are calling quantum supremacy: that is, a clear, unambiguous demonstration of the use of quantum computing hardware to achieve a speedup over the best known classical algorithms for some well-defined mathematical task, however useless and contrived, and however specialized and non-scalable the hardware. I think this will be a major scientific milestone, disproving the people who said quantum computing can』t possibly work, putting the Extended Church-Turing Thesis on termination notice, and setting the stage for future hardware advances that could aim in a more practical direction. And unlike with a full scalable, fault-tolerant, universal QC, which will take longer, I』m optimistic that quantum supremacy can be achieved within the next 5–10 years. And I feel like the hardware builders should be focusing on this, rather than 「entangling」 the issue with practical applications—-why not achieve the clear milestone first, and then worry about practical applications?
As far as I can tell, the group that』s most laser-focused right now on passing the quantum supremacy milestone is that of John Martinis at Google, which is aiming in a couple years to have 40–50 superconducting qubits with good coherence times and controllable couplings integrated in a 2D array on a chip. (In case anyone is wondering, 40 qubits that are the quality of John Martinis』s are much more interesting to me than 2,000 qubits that are the quality of D-Wave』s!) But there are many others to watch as well: for example, Rob Schoelkopf at Yale and the IBM group in superconducting qubits; Chris Monroe at the University of Maryland, Rainer Blatt in Austria, and David Wineland at NIST in ion traps; Jeremy O』Brien at Bristol in optical QC, and others who I』m forgetting.Now, along with all this engineering work, a convincing demonstration of quantum supremacy is also going to need support from complexity theory! As theorists, we』ll need to be able to tell the experimentalists what they should do with their hardware, how to verify the results, and most importantly, how strong the grounds are for believing that it would』ve been much harder to get the same results with a classical computer.BosonSampling, which my student Alex Arkhipov and I proposed in 2011, was an attempt to answer all three of those questions in the context of linear-optical quantum computing. There have been other recent proposals along similar lines, like the Bremner-Jozsa-Shepherd 「IQP / commuting Hamiltonians」 model (related to what I』ve called Fourier Sampling), and the Farhi-Goldstone-Gutmann 「Quantum Approximate Optimization Algorithm」 (QAOA). But probably what will be needed will be to tailor a theoretical proposal to the hardware that will actually become available in the next few years. This will involve a closer collaboration between complexity theorists and experimentalists than I ever would』ve imagined when I started in this field ~18 years ago. But it』s something that I hope to spend a large fraction of my time working on at UT Austin: the convincing overthrow of the Extended Church-Turing Thesis is an event that』s only going to happen once, and me passing up the opportunity to be involved would seem almost criminal.
謝邀。
首先，我們先澄清一件事，Google有一整套量子機器學習的計劃，但是沒有一個「量子霸權」這麼中二的名字。可能是因為Supremacy在字典上第一個意思就是霸權，編譯就把Quantum Supremacy翻譯成「量子霸權」，還把這個當成Google項目的名字吸引眼球。New Scientist的標題是Google"s plan for quantum computer supremacy，首字母小寫的supremacy。文章提到了without error correction這點，因為error correction一直是製造量子計算機的難點。如果沒有error correction的機器就能解決一些問題，這無疑會讓Quantum Supremacy離我們更近。
裡面有部分內容我大概讀了一下也有一些疑惑，歡迎更多知友的補充。
不少物理學家認為，通用量子計算機實用化或許是太過困難的事，但能實用化專屬目的的（尤其機器學習相關）量子計算機就已經有巨大的學術價值和工業價值了。可以看出來，雖然新聞題目很勁爆，但是Google的量子計劃還是切合實際一步步走的。有興趣的朋友可以記住John M. Martinis這個名字，UCSB物理系教授，Google量子項目帶頭人，可能會幫人類邁出一小步。Google能不能實現彎道超車，率先造出第一台有實用價值的量子機？讓我們拭目以待。考慮到大家接下來幾年大家可能會見證很多量子計算機的進展，我在這裡就限於這個問題本身的範圍作答，不展開了。
感覺文章里說的不是突破極限，而是驗證在沒有糾錯機制的條件下，量子計算機是否能完成與經典計算機等價的任務。
突破是肯定突破了的，但目前必須依賴糾錯機制。另外supremacy這裡直譯為"霸權"我覺得不是很合理，我覺得用"優越性"一詞更加合理。因為相對於傳統計算機而言，現在的量子計算機只能在特殊的領域依賴特殊的機制展現出出較好的性能。也就是說，僅憑目前的狀況，完全無法說量子計算機比傳統計算機優越。所以文章里說的實驗，主要就是驗證量子計算機是否具有優越性。一個連優越都不優越的東西，怎麼就一步到霸權了呢？
這篇論文好像沒有提到時間表。新科學（NewScientis）採訪了一票量子計算機界的研發人員，認為明年底之前谷歌有可能實現量子霸權，這和谷歌自己宣稱是兩碼事。
文章是說google的量子計算機能否在沒有糾錯機制下任務完成效率超過傳統計算機，來達到所謂的量子高度，文章用了so-called，所謂的，也就是文章作者對quantum supremacy持懷疑態度，而這邊的supremacy直譯為霸權我認為不妥，前面幾個回答所說的優越性表達的意思最為接近
誰給翻譯一下Scott Aaronson在Quora的回答？
可以參考前段時間Google AI實驗室在Reddit上的AMA（Ask Me Anything）：
問：AI實驗室和量子實驗室有合作嗎？
Jeff Dean：我會去聽他們的講座。除此之外，大概十年內不會有什麼可合作的。據說Google已經造出了50量子比特的量子計算機。。。。
推薦閱讀：
※如何看待浙江大學超算隊在 ASC16 中遭遇不公平對待，隊伍不承認比賽成績？
※地球上最強的25台超級計算機算，除了中國的還有哪些？
※什麼是量子計算機？
※全球最快計算機天河二號的研發意義是什麼？