我們對“量子霸權（quantum supremacy）”的追求證明了量子計算機比普通計算機能夠更快地做一些事情，但是，卻自相矛盾地導致了準量子典型算法的繁榮。
假設你有一個神秘的盒子，它接受了兩種可能的輸入——你可以按下紅色的按鈕或藍色的按鈕——然后得到兩種可能的輸出一——紅球或藍球。不管你按哪個顏色的按鈕，如果盒子從頭至尾總是歸還一種顏色的球，那么它都是常數(shù); 如果球的顏色隨著按鈕的顏色而變化，那么它是平衡的。你的任務是通過讓盒子是只執(zhí)行一次操作，就判斷出你能得到哪一種類型的盒子。
乍一看，這項任務似乎毫無希望解決。事實上，當物理學家David Deutsch在1985年描述了這一思想實驗時，計算機科學家們相信，任何由經(jīng)典物理學規(guī)則操作的機器都可以用少于兩種查詢的方法來學習盒子的標識:每一種方法對應每一個輸出。
然而，Deutsch發(fā)現(xiàn)，通過將問題轉化為量子力學，實際上可以實現(xiàn)一個單一的查詢解決方案。他提出了一種簡單的五步算法，可以在只有兩個量子位的量子計算機上運行，這兩個量子位是量子信息的基本單位。
Cristian Calude是奧克蘭大學的一名數(shù)學家和計算機科學家，他設計出了模仿某些量子算法的經(jīng)典算法。
盡管它沒有實際的用途，但Deutsch的算法：第一種量子算法——成為了量子計算的獨特力量的一個無處不在的例子，它可能有一天會改變諸如密碼學、藥物發(fā)現(xiàn)和材料工程等領域?！叭绻阍谶^去10年左右的時間里打開一本量子計算的教科書，它就會從這個例子開始，”新西蘭奧克蘭大學的數(shù)學家和計算機科學家Calude說道。
但有些事情困擾著他。如果Deutsch的算法真的很好，就像早期的教科書所宣稱的那樣，沒有一種經(jīng)典的算法可以存在。這是真的嗎? Calude說:“當我看到這樣的說法時，我就開始思考:我如何證明它?”
然而，他無法證明出來，這就意味Deutsch的算法是錯誤的。在2007年的一篇論文中，他將Deutsch的算法分解為其組成的量子部分(例如，將兩種經(jīng)典的二進制位表示為兩種“疊加”)，并將這些指令與經(jīng)典操作結合在一起：一種稱為“量子化”的過程。通過這種方式，他為Deutsch的黑箱之謎構建了一個經(jīng)典的解決方案。事實證明，量子解決方案并不總是更好的。
論文地址：http://www.worldscientific.com/doi/abs/10.1142/S021974990700292X
一個普遍的誤解是量子計算的潛在和限制必須來自硬件。在數(shù)字時代，我們已經(jīng)習慣了在時鐘速度〔計算機中央處理器處理指令速度的計算單位〕和記憶方面取得進步。同樣，來自英特爾和IBM等公司的50個量子位量子計算機也激發(fā)了我們的預言，即我們正接近“量子霸權”——量子計算機的能力開始超越傳統(tǒng)機器。
但是量子的霸主地位并不是一個單一的、徹底的勝利。它將由問題，量子算法與經(jīng)典算法建立起來?！霸诹孔佑嬎銠C中，進步的不僅僅是速度，”說悉尼科技大學的量子理論學家Michael Bremner說道。“這更多的是關于算法在游戲中的復雜性?！?/p>
換句話說，Calude的故事并不是唯一的。矛盾的是，關于強大量子計算的報告正在推動對經(jīng)典理論的改進，這使得量子計算機更難獲得優(yōu)勢。Calude說:“大多數(shù)時候，當人們談論量子計算時，經(jīng)典計算就會被忽視，就像過去的黃金時代一樣。”但事實并非如此。這是一場持續(xù)的競爭?！?/p>
而規(guī)則也在改變。加州理工學院的理論物理學家John Preskill說:“當談到它的極限在哪里的時候，這取決于最好的經(jīng)典算法到底有多好。隨著它們變得越來越好，我們不得不繞過這一界限。”
在20世紀80年代量子計算機的夢想成形之前，大多數(shù)計算機科學家都想當然地認為經(jīng)典計算是存在的。該領域的先驅們令人信服地指出，經(jīng)典計算機應該能夠計算出物理領域中所有可計算的東西，從基本運算到股票交易，再到黑洞碰撞。
不過，經(jīng)典的機器不一定能有效地完成所有這些計算。假設你想要理解分子的化學行為。這種行為依賴于分子中的電子的行為，而分子中的電子在許多經(jīng)典態(tài)的疊加態(tài)中存在。讓事情變得更復雜的是，每個電子的量子態(tài)都依賴于所有其他電子的狀態(tài)——這是由于被稱為“糾纏”的量子力學現(xiàn)象。經(jīng)典地計算這些糾纏態(tài)，即使是非常簡單的分子，也會成為指數(shù)級增加復雜性的噩夢。
相比之下，量子計算機可以通過疊加和糾纏自己的量子位來處理電子的糾纏態(tài)。這使計算機能夠處理大量的信息。你添加的每一個量子位都可以使系統(tǒng)同時存儲的狀態(tài)加倍:兩個量子位可以存儲4個狀態(tài)，3個量子位可以存儲8個狀態(tài)，以此類推。因此，你可能需要50個糾纏的量子位來模擬量子態(tài)，這些量子態(tài)需要指數(shù)級的許多經(jīng)典位——1.125千萬億個量子位來編碼。
因此，量子機器可能會制造出一個經(jīng)典的難以解決的問題，即模擬大型量子力學系統(tǒng)的可追蹤性。“自然不是經(jīng)典的，該死的，如果你想要做一個自然的模擬，你最好把它變成量子力學，”物理學家Richard Feynman在1981年的名言中說道?！斑@是一個非常棒的問題，因為它看起來不那么容易。”
當然,它不是。
甚至在有人開始擺弄量子硬件之前，理論學家們就一直在努力想出合適的軟件。早些時候，F(xiàn)eynman和Deutsch了解到，他們可以用從線性代數(shù)中借來的數(shù)學運算來控制量子信息，他們將它稱之為“gates”。與經(jīng)典的邏輯門（logic gates）類似，量子門（quantum gates）以各種方式操縱量子位——引導它們進入一連串的疊加和糾纏，然后測量它們的輸出。通過混合和匹配gates來形成電路，理論學家們可以很容易地組裝出量子算法。
20世紀80年代，物理學家Richard Feynman提出了量子計算機的想法，他打趣說:“這是一個很好的問題，因為它看起來不那么容易?！?/p>
而構想出的運算法則，保證了清晰的計算收益，這是比較困難的。到21世紀初，數(shù)學家們只提出了幾個優(yōu)秀的候選。最著名的是，在1994年，貝爾實驗室的一名年輕的工作人員Peter Shor命名了一種量子算法，它的指數(shù)比任何已知的經(jīng)典算法都要快得多，這一效率可以讓它破解許多流行的加密方案。兩年后，Shor的同事Lov Grover也設計出了一種算法，通過未分類的數(shù)據(jù)庫加快了傳統(tǒng)數(shù)據(jù)庫的搜索過程?！坝懈鞣N各樣的例子表明量子計算能力大于傳統(tǒng)的計算能力?！眲虼髮W量子信息科學家Richard Jozsa說道。在1992年,Jozsa幫助Deutsch擴展他的有許多可能的輸入的黑箱問題,他們的量子解決方案仍然是無可比擬的。
但Jozsa和Calude和其他人一樣，也會發(fā)現(xiàn)各種各樣的例子，就像Deutsch的原始算法一樣，表明了相反的情況。Jozsa說:“事實證明，許多量子過程很難在經(jīng)典計算機上模擬。但是，用巧妙的、微妙的數(shù)學技巧，你就能知道它們會怎么做?！盝ozsa和他的同事們發(fā)現(xiàn)，他們可以利用這些技術來有效地模擬或去量化數(shù)量驚人的量子電路。例如，忽略糾纏的電路會落入這個陷阱，就像那些只糾纏有限數(shù)量的量子位或者只使用特定種類的糾纏門的電路一樣。
那么，怎樣保證像Shor這樣的算法是獨一無二的呢? Jozsa說:“這是一個非常開放的問題。我們從來沒有真正地理解為什么有些算法是很容易模擬的，而另一些則不是。很明顯，糾纏很重要，但這并不是故事的結局?！睂＜覀冮_始懷疑，他們所相信的許多量子算法是否都看上去優(yōu)越，但結果可能很普通。
直到最近，對量子能的追求在很大程度上是一個抽象的概念。Jozsa說:“我們并沒有真正關心算法能否實施，因為沒人相信在未來會有一臺量子計算機可以去做這件事?！崩纾\行Shor的整數(shù)算法，以解鎖一個標準的128位加密密鑰，需要成千上萬的量子位——可能還需要數(shù)千個量子位來糾正錯誤。
但到了2011年，情況開始好轉。在布魯塞爾的一次會議上，Preskill推測，“嚴格控制的量子系統(tǒng)可以超越傳統(tǒng)時代”的任務可能不會太遙遠。他說，最近的實驗結果可能很快就會讓量子機器擁有近似100個量子位。讓它們?nèi)ネ瓿梢恍俺壗?jīng)典”的壯舉也許并不是不可能的。(盡管D-Wave系統(tǒng)的商業(yè)化的量子處理器可以在那時與128個量子位對抗，現(xiàn)在已經(jīng)擁有超過2000個量子位，但他們只處理特定的優(yōu)化問題;許多專家懷疑他們可能會超越經(jīng)典的計算機。)
Preskill說:“我只是想強調我們已經(jīng)接近了我們最終可能會到達人類文明的一個真正的里程碑，在那時，量子技術成為我們擁有的最強大的信息技術?！彼Q這一里程碑為“量子霸權”。
關于“量子霸權”的討論反映了人們對這一領域的強烈關注，是的，但也許更多的是在2004年由IBM物理學家Barbara Terhal和David DiVincenzo預言的一篇論文中所提出的一系列理論突破。在他們努力理解量子資產(chǎn)的過程中，他們把注意力轉向了被稱為采樣問題的基本量子謎題。隨著時間的推移，這類問題將成為實驗主義者最大的希望，證明在早期的量子機器上有一個明確的加速。
David Deutsch是牛津大學的物理學家，他提出的第一個可以通過量子計算機來解決的問題。
采樣問題利用了量子信息難以捉摸的特性。假設你將gate的一個序列應用到100個量子位上。這個電路可以將量子位變成一個數(shù)學的單元數(shù)，相當于2100個經(jīng)典位元的順序。但是一旦你測量了這個系統(tǒng)，它的復雜性就會崩潰到只有100個位元。這個系統(tǒng)將會輸出一個特定的字符串或樣本，其中有一些概率是由你的電路決定的。
在抽樣問題中，我們的目標是產(chǎn)生一系列看起來像是來自這個電路的樣本。這就像反復扔硬幣來表明它會(平均)有50%的正面概率和50%的反面概率。除了這里，每次“投擲”的結果都不是一個單獨的值——正面或反面——它有許多值，每一個值都可能受到其他值的一些(甚至全部)的影響。
對于一個運轉良好的量子計算機來說，這個練習是顯而易見的。它理所當然的。另一方面，經(jīng)典的計算機在最壞的情況下，它們必須對所有可能的輸出字符串（全部的2100個字符串）進行計算概率這樣的笨拙工作，然后隨機從該分布中選擇樣本。
Terhal和DiVincenzo展示了即使是一些簡單的量子電路仍然很難通過經(jīng)典的方法來進行采樣。因此，如果實驗主義者能得到一個量子系統(tǒng)來吐出（spit out）這些樣本，他們就有充分的理由相信他們做了一些經(jīng)典的無法對抗的事情。
理論家們很快將這一思路擴展到其他類型的抽樣問題。最有希望的提議之一來自MIT的一名計算機科學家Scott Aaronson和他的博士生學生Alex Arkhipov。在2010年發(fā)表的一篇文章中，他們描述了一種量子機器，這種機器通過光路傳輸光子，通過量子力學的方式來改變和分裂光線，從而產(chǎn)生出特定概率的輸出模式。復制這些模式被稱為“玻色子取樣（boson sampling）”。Aaronson和Aaronson的理由是，玻色子的取樣將會應變大約30個光子的經(jīng)典資源，這是一個可行的實驗目標。
草案：https://arxiv.org/abs/1608.00263
同樣誘人的是被稱為“瞬時量子多項式（instantaneous quantum polynomial）”的計算，也就是“IQP”電路。一個“IQP”電路有所有的“gate”，這意味著它們可以在不改變結果的情況下以任何順序進行操作——就像2+5=5+2一樣。Bremner說:“我們開始研究它們，因為它們更容易分析。”
到2016年，玻色子的采樣器還沒有超過6個光子。然而，谷歌和IBM的團隊正在朝著接近50個量子位的芯片上努力;今年8月，谷歌悄悄發(fā)布了一份草案，列出了在這些“短期”設備上展示量子霸主地位的路線圖。
草案：https://arxiv.org/abs/1608.00263
本文為編譯文章，轉載請注明出處。
聯(lián)系客服
