終於,科學家們找到了只有量子計算機才能解決的問題

2021-02-15 DeepTech深科技

年度訂閱用戶可加入科技英語學習社區，每周科技英語直播講堂，詳情查看「閱讀原文」

科學家們過去一直在尋找只有量子計算機才能解決的問題。現在他們終於找到了。

早在量子計算研究剛剛興起時，科學家們就知道這種未來主義的機器蘊含著某種無限的潛能。而在今年 5 月發表的一篇論文中，計算機科學家 Ran Raz（普林斯頓大學兼魏茨曼科學研究院教授） 和 Avishay Tal（史丹福大學博士後研究員）為「量子計算在能力上將遠超一切傳統計算」這一概念提供了科學證據。

1993 年時，計算機學家將那些傳統計算望塵莫及，只有量子級計算才能解決的問題定義為 BQP 問題。而自 BQP 概念問世以來，計算機科學家們就一直在尋找夠格的 BQP 問題，他們將可能的 BQP 問題與那些傳統計算能解決的問題（也稱 PH 問題）進行對比，以此來判定某一特定問題是否屬於 BQP 問題。而在於 5 月發表的這篇論文中，Raz 和 Tal 已經成功的找到了第一個合格的 BQP 問題。

雖然論文對於實際構建一臺量子計算機的工作來說沒有任何實際意義，但它確實地證明了「成熟的量子計算將會在量級上完虐傳統計算」這一概念。

量子級計算


理論計算機研究中的一個基本項目就是將問題根據複雜程度進行分類，也稱複雜度分級（Complexity Classes），即根據解決問題所需資源（如時間和內存）的多少進行分類。

其中最著名的兩個分類是「P」和「NP」，P 是傳統計算可以快速解決的所有問題。 （「這個數字是否是質數？」屬於 P）NP 是傳統計算機並不能迅速解決，但如果存在一個已知答案能夠快速驗證的問題（如「這個數的質因數有哪些？」屬於 NP）。計算機科學家認為 P 和 NP 是不同的類別，但證明 P 與 NP 不同卻是該領域最難以及最重要的問題之一。

1993 年，計算機科學家 Ethan Bernstein 和 Umesh Vazirani 為複雜度分類創造了一個新的類別，「有限錯誤量子多項式時間」類（bounded-error quantum polynomial time）」，即上文中所提到過的 BQP 問題。該定義類中包含量子計算機可以高效解決的所有決策問題，即答案為是或否的問題。兩位科學家同時還證明了量子計算機可以解決傳統計算機可以解決的所有問題，也就是證明了 BQP 分類中包含了 P 分類（這裡分類看為數學中集合的概念）。

但 Ethan 和 Umesh 無法確定 BQP 中是否也包含「多項式層次結構（Polynomial Hierarchy）」類問題，也稱 PH 類問題。PH 是 NP 的拓展，包含所有由 NP 類延伸出的問題，如通過添加「對於所有...來說是否存在...」。 當今的傳統計算機無法解決 PH 中的大多數問題，但如果 P 等於 NP，則可以將 PH 看作是傳統計算機可以解決的所有問題。換句話說，比較 BQP 和 PH 這兩種問題分類，便是為了確定量子計算機是否真的較傳統計算機具有優勢。

關於不同複雜度類別的問題可以參考「旅行推銷員問題（TSP）」。「是否存在通過若干個城市的一些路徑比另一些路徑更短」是一個 NP 問題。而一個 PH 問題則是「是否通過這幾個城市的最短路徑就是某個特定距離」。

德克薩斯大學的計算機科學家 Scott Aaronson 說：「PH 是最基本的古典複雜度分類之一。而我們想知道，量子計算在古典複雜度分類的標準中處於什麼樣的位置。」

區分出兩個複雜類別的最好方法是，找到一個可被證明為僅屬於其中一類的問題。 然而，由於基礎研究上的不足以及技術上的障礙，一直沒人能找到符合這種要求的問題。

Aaronson 說，如果你想找到一個僅屬於 BQP 而不屬於 PH 的問題，你必須找到一個從定義上傳統計算機不能有效證明答案的問題，這樣的問題「傳統計算機甚至不能有效地驗證答案，更別說找到它了。這就排除了我們在計算機科學中所考慮的許多問題。」

BQP 和 PH


假如你現在有兩個隨機數字序列生成器，而你需要解決這樣一個問題：這兩組序列是完全獨立的，還是以某種隱藏的形式相關聯的（比如一組是另一組序列的「傅立葉變換」）。Aaronson 在 2009 年首次提出了這種「關係（forrelation）」問題，並證明它屬於 BQP。但解決該問題的第二步將更為困難，因為你需要證明該關係不屬於 PH 類的集合。

Raz 和 Tal 這篇論文的成就便是實現了一種名為「Oracle（也稱「黑匣子」）」的 BQP 與 PH 的區分方式。 區分 BQP 和 PH 的最佳方式是測量解決每個問題所需的計算時間。但多倫多大學的計算機科學家 Henry Yuen 認為，目前我們對計算所需時間的認識還不足以讓人們得出某一問題所需的計算時間。

圖 | 普林斯頓大學理論計算機科學家 Ran Raz

正如 Yuen 所說的那樣，計算機科學家一般會測量一些其他的量來衡量計算所需的時間，比如計算出計算機在解決問題的過程中詢問「oracle」的次數。oracle 就像是一個提示，你不知道它是怎樣產生的，但你知道它是可靠的。

回到解決兩組數列是否相關的問題上，你可以先詢問 oracle 類似「每個發生器的第六個數字是什麼？」的問題，然後，根據每種計算機所需的提示數量來比較計算能力（需要更多提示的計算機計算速度較慢）。

Tal 說：「從某種意義上來說，我們更好地理解了這個模型。 模型更多涉及到的是信息而不是計算。」

圖 | 史丹福大學理論計算機科學家 Avishay Tal

Raz 和 Tal 的這篇論文證明了量子計算機在解決 forrelation 問題時較傳統計算機所需的提示更少。 事實上，量子計算機只僅要一個提示就能解決問題，而即使有無限個提示，PH 中也沒有可以解決問題的算法。Raz 說： 「這意味著有一個非常有效的量子算法能夠解決這類問題，即那些傳統算法無法解決的問題。這說明了 forrelation 問題在分類上屬於 BQP 而不是 PH。」

Raz 和 Tal 在四年前就已接近證明出這一結論，但他們無法完成證明中的重要一步。 然後就在論文發表的一個月前，Tal 看到一篇關於偽隨機數列產生器的論文，意識到這篇論文中的技術正是他和Raz的證明所需要的，於是才有了這篇論文的發表。

BQP 和 PH 得以區分的消息迅速傳遍了學界。在論文發表的第二天，喬治亞理工學院的計算機科學家 Lance Fortnow 便寫下 「量子複雜性分類層級真是搖擺不定。」 以示感慨。

該論文為量子計算的優越性提供了一個保證，即存在只有量子計算機才能解決問題。「即使 P 等於 NP，甚至存在更強的假設，傳統計算也無法達到量子計算級別。」 Fortnow 說。

-End-

編輯：Peter，戴青

參考：https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-able-to-solve-20180621/

相關焦點

  • 科學家們正在嘗試用量子計算機來重新發現希格斯粒子
    物理學家們已經在「使用量子技術來加速科研計算」的機器開發工作上付出了很多，他們希望這類量子計算機能幫助發現新的自然規律。最近，一個研究小組已經驗證，量子電路可以學習如何通過掃描原子粉碎實驗數據來搜索新的粒子。小組在這次「理論驗證性質」的研究中使用了由量子計算公司 D-Wave 搭建的機器，並用在了目前已解決了的希格斯玻色子案例中。但與傳統技術相比，該技術尚不具明顯優勢。
  • 用量子計算機解決材料問題 | 章魚通
    Quantum計算機具有巨大的潛力，可以利用新的算法進行計算，並涉及遠遠超過當今超級計算機容量的大量數據。雖然這些計算機已經建成，但仍處於起步階段，對解決材料科學和化學方面的複雜問題的適用性有限。例如，它們只允許為材料研究模擬幾個原子的特性。
  • 科學家在噪聲量子計算機上計算分子的性質來提高準確性
    近日據外媒報導，維吉尼亞理工大學化學和物理研究小組發表在《自然通訊》的論文表明，他們過設計一種算法來改進量子模擬，這種算法可以更有效地計算噪聲量子計算機上分子的性質。目前設想的大型糾錯的量子計算機可能要幾十年後才能實現，然而專家們正在積極地研究如何使用現有的和先進的量子處理器來解決有用的問題，儘管存在錯誤或「噪音」的局限性。一個關鍵的預期用途是模擬分子性質，從長遠來看，這可能導致材料改進和藥物發現方面的進展。量子計算機有望比目前使用的傳統計算機更有效地進行某些計算。
  • 用粒子加速器技術解決構建量子計算機中的令人煩惱的問題
    它們還可以解決量子計算機成功開發面臨的最大問題之一：量子比特的去相干性。圖片提供：費米實驗室（Fermilab）裡達（Reidar Hahn）去年，費米實驗室（Fermilab）的研究人員獲得了超過350萬美元的資助，這些資金用於研究新興的量子信息科學領域。
  • 這個已有90年歷史的數學問題表明了我們為什麼需要量子計算機
    在數學領域，這被稱為旅行推銷員問題。 為了解決多個「停頓」問題，幾乎肯定需要一臺量子計算機，這就是為什麼。如果你要遊覽的目的地數量眾多，那麼一條旅行路線會比其他所有路線都更有效率：這將使他們之間旅行所花費的時間和距離最少。上面的示例總共有四個目的地，但只有六個可能的路徑。
  • 計算機科學家設定基準以優化量子計算機性能
    計算機科學家表明，高速量子計算機如何使用其電路執行量子程序的現有編譯器會抑制計算機實現最佳性能的能力。具體來說，研究表明，改進量子編譯設計可以使計算速度比目前演示的速度快45倍。計算機科學家創建了具有最佳深度或大小的基準量子電路系列。在計算機設計中，電路深度越小，可以更快地完成計算。
  • 布里斯托的科學家指出量子計算機的奇異之處
    布裡斯託大學的研究人員發現，全世界的科學家和工程師都在競相建造的超強大的量子計算機，需要比以前認為的更強大的功能，才能擊敗當今的普通PC。量子計算機是一種在量子機械硬體上運行的新型機器，預計在解決某些問題方面將提供巨大的速度優勢
  • 一個裡程碑式的證明,解決了計算機、物理和數學領域的一系列問題
    但現在，一個裡程碑式的證明將它們結合在一起，解決了計算機科學、物理和數學領域的一系列開放問題。新的證明建立了量子計算機，通過糾纏量子比特或量子位來計算，而不是經典的1和0，理論上可以用來驗證大量問題的答案。糾纏和計算之間的對應關係讓許多研究人員感到震驚。「這完全是一個驚喜，」維也納量子光學和量子信息研究所研究量子物理學的米格爾·納瓦斯克說。
  • 超導體：量子計算機的"矽"
    量子計算機，對我們普通人而言可望不可急。為什麼會有這麼感慨呢？一方面，各國量子計算機都在加緊研發階段，另一方面，想達到量子運算能力必須有一種材料，它的電阻為零。科學家們不約而同地想到了&34;一． 超導體被各國科學家比喻為量子計算機的&34;我們知道，現在的晶片，一般是有矽晶片來製造。
  • 科學家們苦心孤詣,量子領域再進一大步,未來計算機將如何發展?
    其特別的地方在於，化學物質在兩種情況的交界處，那麼貓也理應處於生或死兩個情況的交界之中，所以，只有在觀察者觀察完畢之後，才能獲得某種單一狀態。從1980年以來，研究人員已經是能夠利用各種方法在實驗室中通過實驗，從而實現量子態的疊加。
  • 摩爾定律將令經典計算機至極限?量子科學家看法不一
    新華網黃山9月5日電（記者段世文）在今天閉幕的「2001年量子信息國際學術會議」上，與會的量子通信、量子計算領域的國內外科學家在接受本社記者專訪時，對「經典計算機何時遭遇極限？」這一問題做出了不同的回答。　　經典計算機即我們現在通用的矽晶片計算機。近30多年來，製造技術的革命大大提高了傳統矽晶片的集成度。
  • 科學家研製超級量子計算機，成現實版深思，或徹底改變未來
    英國薩塞克斯大學的科學家團隊已經制定了一個巨大的超級量子計算機的藍圖，其開源化的模塊設計理論上可以讓計算機達到足球場大小，能夠快速解決普通計算機需要幾十億年才能解決的問題薩塞克斯大學的科學家計劃在兩年內推出現實版「深思」的概念驗證早期原型，期望它能夠發揮比深思更大的作用，提供解決世界上最棘手問題的方案。量子計算機利用量子的糾纏態作為量子位，每個量子位可取0和1的狀態，也可是二者的疊加態，計算能力遠超普通計算機。
  • 地球算了一千萬年的終極問題,終於被兩位科學家一百萬小時解決了
    宇宙中最強大的電腦深思，為此為泛維度生物——老鼠們設計了一臺更偉大的有機電腦——地球，在運行了1000萬年，即將得到這個終極問題前5分鐘的時候，地球「砰」的一聲，被沃貢人給摧毀了。這個終極問題是什麼，也就誰不得而知了。
  • 量子計算機最新動態:大腦式量子計算機
    據谷歌最新報導，科學家正在構建一種「像大腦一樣」的量子計算機。這一最新研究項目旨在利用量子計算機的威力來構建一種新型的神經網絡，為量子神經網絡做準備。研究人員表示這項工作可以引領下一代人工智慧。人的大腦具有驚人的能力，使其在許多方面比世界上最先進的計算機都更強大。
  • 地球算了1000萬年的終極問題,終於被兩位科學家100萬小時解決了
    宇宙中最強大的電腦深思，為此為泛維度生物——老鼠們設計了一臺更偉大的有機電腦——地球，在運行了1000萬年，即將得到這個終極問題前5分鐘的時候，地球「砰」的一聲，被沃貢人給摧毀了。這個終極問題是什麼，也就誰也不得而知了。
  • 你知道什麼是量子計算機嗎?
    量子計算機刷屏全網網友們都為之驕傲欣喜但一打開文章大部分朋友看完都只能留下一地問號：「每個字我都認識但……」「量子計算機為啥這麼快？」答案需要嘗試1000×1000次，也就是要100萬次才能找到答案。但如果用量子計算機解決這個問題，就簡單多了。
  • 上海交大科研團隊捕獲馬約拉納費米子 造量子計算機的完美選擇之一
    通過反覆對比實驗，發現只有馬約拉納費米子才能產生這種自旋極化電流的現象。至此，馬約拉納費米子的神秘面紗終於被揭開，賈金鋒表示，這是他們的實驗首次觀測到馬約拉納費米子的自旋相關性質, 同時也提供了一種用相互作用調控馬約拉納費米子存在的有效方法，還為觀察神秘的馬約拉納費米子提供了一個直接測量的辦法。
  • 看完這篇 終於可以和別人聊量子計算機了!
    什麼是量子計算機？量子計算機為什麼厲害？量子霸權又是什麼？你都能在這裡找到看得懂的答案。量子計算機是計算機嗎？是，但和我們現在所理解的「電腦」差別很大—— 兩者的計算形式不一樣，電腦通過電路的開和關進行計算，而量子計算機則是以量子的狀態作為計算形式。
  • 看完這篇，終於可以和別人聊量子計算機了
    什麼是量子計算機？量子計算機為什麼厲害？量子霸權又是什麼？你都能在這裡找到看得懂的答案。 量子計算機擅長解決什麼問題？1994 年，為了分解一個 129 位的大數，科學家同時動用了 1600 臺高端計算機，花了 8 個月的時間才分解成功；但量子計算機理論上只需 1 秒鐘就可以破解。
  • 科學家們找到的10個解決海洋汙染問題的方式
    然而，科學家們仍在不斷地提出如何拯救環境的想法。從可降解的產品到塑料消費機器，我們可以找到許多來自科學家的發明。所以這次，擼哥就將帶來：科學家們找到的10個解決海洋汙染問題的方式。1、吃塑料的真菌大自然總是能夠創造很多讓人感到驚訝的事情。而作為在大自然生存著的生物，也都需要不斷的去努力適應。而這一次，科學家們發現了大自然回收塑料本身的一種方式。