量子計算機僅僅是比經典計算機強了那麼一點點、快了那麼一點點、效率高了一點點嗎？我們都知道，答案是“不”。
然而，為了證明量子計算機的真正實力，科學家頗費了一番功夫。在量子計算機研究的早期，計算機科學家提出了一個問題。他們知道，這個問題的答案會深刻揭示這些未來機器的威力。然而，25年後的今天，這個問題差點還是沒能解決。
現在，他們終於找到了一個只有量子計算機才能解決的問題。
今年5月底在網上發表的一篇論文中，計算機科學家冉·拉茲（Ran Raz，普林斯頓大學和魏茨曼科學學院的教授）和阿維沙伊·塔爾（Avishay Tal，斯坦福大學博士後研究員）提出了有力的證據，證明量子計算機擁有任何傳統計算機都不可能達到的計算能力。
拉茲和塔爾定義了一個具體的計算問題，然後證明，量子計算機可以有效地解決這個問題，而傳統計算機永遠都解決不了。從1993年開始，計算機科學家就一直在尋找這樣一個問題。在那一年，計算機科學家首次定義了一類涵蓋量子計算機能解決的所有問題集，統稱為“BQP”。
從那時起，計算機科學家希望將BQP與被稱為“PH”的一類問題進行比較。PH涵蓋經典計算機可以解決的所有問題，哪怕是未來文明建造的、先進到不可思議的經典計算機。想要進行那種比較，就必須找到一個問題，證明這個問題屬於BQP，但不屬於PH。現在，拉茲和塔爾做到了。
他們的研究結果並沒有使量子計算機在實際應用中超越經典計算機。理論計算機科學家已經知道，量子計算機可以解決經典計算機能解決的任何問題。工程師們還在努力研製切實可用的量子計算機。但拉茲和塔爾的論文證明，量子計算機和經典計算機是兩碼事——即使經典計算機的表現超出了所有的現實期望，量子計算機仍然會高高在上。
量子級計算
理論計算機科學的一個基本任務是把問題進行復雜性歸類。一個複雜性類包含在某一特定的資源預算內可以解決的所有問題。這裡的資源可以是像時間或者內存這樣的東西。 兩個最著名的複雜性類是“P”和“NP”。P是經典計算機能迅速解決的所有問題（“這個數字是質數嗎”屬於P），NP是經典計算機未必能迅速解決的所有問題，但在給出答案的情況下，經典計算機能迅速證明答案是否正確（“其質因數是什麼”屬於NP）。計算機科學家認為，P和NP是截然不同的類，但真正證明這一點是該領域裡最困難、最重要的問題。
1993年，計算機科學家伊森·伯恩斯坦（Ethan Bernstein）和烏梅什·瓦茲拉尼（Umesh Vazirani）定義了一個新的複雜性類，他們稱之為BQP，即“有界誤差量子多項式時間”。這個類包含量子計算機可以有效解決的所有判定性問題（答案為“是”或者“否”）。同時，他們也證明了量子計算機可以解決經典計算機能解決的所有問題，即BQP包含P中的所有問題。
但他們無法確定BQP是否包含PH中沒有的問題。PH代表“多項式層次結構”，是NP的泛化，這意味著PH包含通過分層限定語句（比如“那裡有”和“所有人”）使NP問題更加複雜的所有問題。當前的經典計算機無法解決大多數的PH問題，但如果P等於NP，PH就是經典計算機可以解決的那一類問題。換句話說，比較BQP和PH是為了確定量子計算機是否比經典計算機更具優勢，即使經典計算機以後可以（出人意料地）解決比現在更多得多的問題。
“PH是最基本的經典複雜性類之一。”得克薩斯大學奧斯汀分校計算機科學家斯科特·阿倫森（Scott Aaronson）說，“因此，我們想知道，量子計算在經典複雜性理論的世界裡處於什麼位置？”
區分兩個複雜性類的最好方法，是找到一個可證明屬於其中一類但不屬於另一類的問題。但由於基礎性和技術性障礙，很難找到這樣一個問題。
如果想找到一個屬於BQP但不屬於PH的問題，必須先找到一個“經典計算機無法有效驗證答案，更別說得出答案”的問題。阿倫森說：“這排除了計算機科學家想到的很多問題。”
BQP還是PH？
假設你有兩個隨機數生成器，每個會生成一串數字。你向計算機提出的問題是：這兩串數字是彼此完全獨立，還是存在隱藏關聯（一串數字是另一串數字的“傅里葉變換”）？阿倫森在2009年提出了這個“傅換關聯”（forrelation）問題，並證明它屬於BQP。然後是更加困難的第二步——證明傅換關聯問題不屬於PH。
普林斯頓大學理論計算機科學家冉·拉茲找到了區分兩個計算類的方法
從某種意義上來說，這就是拉茲和塔爾所做的事。他們的論文實現了BQP和PH的“Oracle”（或者說“黑匣子”）分離。這是計算機科學領域裡的一種常見結果。如果研究人員想要證明的東西超出了他們力所能及的範圍之外，他們便求助於“Oracle”。
區分BQP和PH等複雜性類的最好方法，是衡量解決問題所需的計算時間。但多倫多大學計算機科學家亨利·袁（Henry Yuen）說，計算機科學家“對真正的計算時間缺乏深刻的瞭解，也沒有能力去衡量。”
因此，計算機科學家衡量其他指標，希望藉此洞悉他們無法衡量的計算時間。他們算出計算機詢問“Oracle”以得到答案所需的時間。Oracle就像暗示者，你不知道祂是如何得出暗示的，但你知道暗示是可信的。
如果你的問題是弄清楚兩個隨機數生成器是否存在隱藏關聯，你可以問Oracle“每個生成器的第六個數字是什麼？”然後，你根據每一類計算機解決這個問題所需的暗示數量，來比較它們的計算能力。計算機需要的暗示越多，速度就越慢。
“從某種意義上講，我們更瞭解這種模式。它更多地是關於信息而非計算。”塔爾說。
斯坦福大學理論計算機科學家阿維沙伊·塔爾利用“Oracle”分離來區分BQP和PH
拉茲和塔爾的新論文證明，量子計算機解決傅換關聯問題所需的暗示數量遠遠少於經典計算機。事實上，量子計算機只需要一個暗示，而PH算法哪怕獲得無數的暗示，也解決不了這個問題。“這意味著量子算法可以非常有效地解決那個問題，”拉茲說，“但如果只考慮經典算法，哪怕是非常高級的經典算法也不行。”因此，傅換關聯問題屬於BQP，但不屬於PH。
拉茲和塔爾在差不多四年前就快要得出這一結果，但他們那時無法完成其證明過程的最後一步。不久前，塔爾看到了一篇關於偽隨機數列生成器的論文。他意識到，那篇論文中談到的方法正好可以幫助他和拉茲完成他們自己的論文。“這是缺失的一環，”塔爾說。
BQP和PH被分離的消息迅速傳播。在拉茲和塔爾發表其論文的第二天，佐治亞理工學院計算機科學家蘭斯·福特諾（Lance Fortnow）寫道：“量子複雜性世界轟動了。”
這篇論文有力地證明，量子計算機存在於一個跟經典計算機不同的計算領域（至少在涉及神諭的問題上）。拉茲和塔爾的論文證明，即便是在P等於NP的情況下，有些問題仍然只有量子計算機才能解決。
福特諾說：“即使P等於NP，哪怕有了這個強假設，也不足以把握量子計算。”
翻譯：于波
校對：李莉
造就：劇院式的線下演講平臺，發現最有創造力的思想
閱讀更多 造就 的文章
