量子計算機如何輕鬆搞定經典演算法不可能完成的任務？

全文約12000字，閱讀時間預計8分鐘。

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

量子技術正在成為計算機科學的前沿領域，包括Intel、IBM、中科院、谷歌等都在奮力研發，尋求突破。

量子計算的計算能力要比經典計算要強，速度也要更快，計算效率更加節能，這一點我們已經非常清楚。科學界一直沒能證明量子演算法可以，如今他們終於為這個問題找到了答案。

普林斯頓大學和魏茨曼科學研究所教授RanRaz和斯坦福大學的博士後研究員教授Avishay Tal在五月份發表的一項研究用強有力的證據表明，量子計算機具有超出傳統計算機所能達到的運算能力。

在比較量子計算機和二進位計算機的計算能力之前，我們先來看一下劃分計算機問題複雜等級的圖。

圖中最小的一個框P代表的是傳統計算機所能快速解決的一系列問題，而NP則是傳統計算機不一定能夠迅速解決，但是如果提供一個答案，他們可以快速驗證答案的所有問題的集合。而NP繼續向外延伸就會得到PH（polynomialhierarchy），也就是所謂的「多項式層次結構」問題。而最外圍的PH可以被理解為傳統計算機在現在和未來可能解決的所有問題的總和。

而對於量子計算機解決的問題的複雜等級而言，它可以解決的所有問題被統稱為BQP（bounded-error quantum polynomial time ）-「有界誤差量子多項式時間」。這一類問題的集合早在1993年就被來自哈佛大學的計算機科學家Ethan Bernstein和Umesh Vazirani第一次定義。BQP包含一系列決策問題，兩位計算機科學家證明量子計算機可以高效地解決這些問題。

這兩位計算機同時還證明量子計算機可以解決傳統計算機已經解決的所有問題。也就是說，BQP包含了P中的所有問題。

所以，要證明量子計算機優於傳統計算機，具有傳統計算機所不能解決的問題的優勢就必須找到在BQP包含PH中找不到的問題。由於基礎設施和技術的局限，這兩位科學家在1993年沒能找到這些問題的答案，這個問題在科學界也一直是一個挑戰。

那麼Raz和Tal兩位科學家是如何找到這一類問題的呢？

事實上，Raz和Tal在實驗時利用了科學家Aaronson在提出的一種「關係」命題，並證明這個「關係」命題不在PH範圍內。Aaronson提出了下面一個問題，並證明它屬於BQP範圍：

現在有兩個隨機數生成器，每個生成器隨機產生一個數字序列。你的計算機的問題是這樣的：這兩個序列是完全獨立與彼此，還是有相關關係（比如，一個序列是另一個序列的「傅里葉變換」）？

為了證明這個「關係」命題不在PH範圍內，Raz和Tal採取的方法是比較兩種計算機為了解決每個問題需要向「oracle」提示系統索取線索的次數，從而比較傳統計算機和量子計算機解決問題的能力。

舉個具體例子，如果你的問題是要弄清楚兩組隨機數是否相關，你可以詢問oracle的問題，例如「每個發生器的第六個數字是什麼？」然後，根據每種計算機需要的提示數量來比較計算能力解決問題。需要更多提示的計算機速度較慢。

Raz和Tal的新論文證實了量子計算機需要比傳統計算機少得多的提示來解決相關問題。實際上，量子計算機只需要一個提示就能解決這些問題，而傳統計算機即使有無限提示，也沒有可以解決問題的演算法——「即使你非常高級別的經典演算法，也不能解決這些問題」，Raz說。

這項研究對量子計算機的計算能力加以有力的肯定，證明它們比傳統計算機能力高出甚多。特別是在解決優化問題時，量子計算機就能夠大放光彩。由於一些優化問題過於複雜，如果交由傳統計算機來處理，可能會耗費大量的時間和資源，而量子計算機由於計算能力非常強，能夠在同一時間嘗試不同的選擇，實現了真正的並行計算，這也就是它得以碾壓傳統計算機的底氣所在。

量子計算機有什麼實際的應用意義？

基於量子計算機強大的計算能力，我們可以推測一旦量子計算能夠達到商用之後，可以迫切地解決當前二進位計算機的計算複雜性的問題，處理計算問題的效率得到極大的提高。

再具體一點的說，就是在銀行、金融、安全系統。甚至新葯的研究、新材料的研究，這些對普通生活和工業界產生巨大影響的領域，才會第一步去使用量子計算機。到那個時候人們可能在很短的時間內，就能得到關於諸如新葯、新材料的一些新的特性。我們的生活模式跟商業模式也會得到極大的改變。

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

-End-

本文章圖片來源於網路

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！