南科大翁文康NSR論文：「量子霸權」的基礎概念和可行方案

選自NSR，作者：翁文康，機器之心編譯，參與：Panda。

《國家科學評論》（NSR）近日發表了南方科技大學物理系副教授翁文康撰寫的短篇綜述論文《量子霸權：一些基本概念》，討論了量子霸權相關的一些基礎概念和可行方案。機器之心對該論文進行了全文編譯。

論文：Quantum supremacy: some fundamental concepts

原文地址：https://doi.org/10.1093/nsr/nwy072

三十多年前，費曼設想只有利用量子計算才能有效解決量子問題 [1]。問題在於，我們如何證明量子計算相比於經典計算具有優勢？在比較量子計算機與經典計算機時，一個常見誤解是：量子比特可以表達一個包含指數數量狀態的疊加態，這是經典比特無法實現的。這種表述雖然是正確的，但卻沒告訴我們全部信息，具體來說：究竟量子計算機能有效求解哪些經典計算機不能求解的問題？事實上，正是基於費曼發明的路徑積分技術，任意量子線路的輸出，比如躍遷幅度（transition amplitude），都存在一個經典的計算方法只需使用以多項式數量增長的內存去得到（儘管時間成本會呈指數增長）。因此，任意量子計算都可以用經典的方式模擬，關鍵的是時間上的效率問題。

目前已經有很多研究，試圖利用計算複雜性理論來判斷量子計算機的能力。尤其需要指出，可通過量子計算機有效求解的計算（決策）問題的類別被稱為 BQP（有界誤差量子多項式時間）；對應的經典計算機能有效求解的問題被稱為 P（多項式時間）。當然，BQP 不會弱於 P；理論上量子計算機可以有效模擬經典計算機。但關鍵的問題是，如果無法證明 BQP 嚴格超過 P（即 BQP≠P），則量子計算的優越性基礎無法確立。從這個意義上看，這個問題就跟證明 P≠NP（非確定性多項式時間）這一著名難題一樣重要。

大數分解問題是一個著名的 NP 問題；Shor 的量子演算法能夠在多項式時間內進行大數分解，而迄今為止人類發現的最好的經典演算法也無法完成這一任務。嚴格來說，能有效進行大數分解的經典演算法也許存在，但是我們仍然不能嚴格排除這一可能性。同樣，儘管沒有證明，人們還是普遍相信量子計算機也無法求解某些 NP 問題。事實上，這個猜想（如果成立）的證明能提供 P≠NP 的可行證明途徑。

或許一類更容易解決的問題是：我們考慮量子計算機何時能夠執行某些明確（但不一定跟任何實際問題有關）的計算任務，這些任務在某個合理的時間內不能被當前任何經典計算機解決？這一狀態的實現被稱為「量子霸權（quantum supremacy）」[2]。有人可能會問，能提供平方加速的 Grover 搜索演算法如何？我們能說 Grover 演算法實現了量子霸權嗎？問題在於，量子霸權並不是取 大 N 極限，而是要求我們確定需要多少個量子比特和量子門，經典計算機才沒有辦法在合理時間內模擬。

為了進一步闡述，我們先來談論兩個經典模擬的概念，即「強模擬（strong simulation）」和「弱模擬（weak simulation）」。強模擬是指在多項式時間內高精度地計算躍遷概率（或可觀測量的期望值）。弱模擬則要求精確地重現概率分布，這涉及到從量子器件的輸出結果中採樣。某些量子線路雖然不能用經典的方法作有效的強模擬，但也許能進行有效的弱模擬。[3]

然而，我們應該注意模擬任務中的精度要求。比如說，對於很多決策問題而言，將躍遷幅度計算到加法誤差而非乘法誤差內可能就足夠了。換句話說，量子計算問題的經典可模擬性取決於精度要求。

目前，實現量子霸權有三種常見的模型（參見圖 1），即（i）玻色採樣 [4]，（ii）IQP 線路採樣 [5]，（iii）混沌量子線路採樣 [6]。這些方法的共同點在於，不同比特串或光子數的分布都是從量子器件中採樣的。此外，它們全都假設經典計算機無法有效計算躍遷振幅，和/或重現（或近似）執行採樣的量子器件的分布。這在強模擬和弱模擬兩方面都是如此。

圖 1：三種實現量子霸權的不同方法。（a）玻色採樣，（b）IQP 線路，（c）混沌量子線路

在玻色採樣中，多個單光子被注入線性光學網路的不同模（mode）中，目標是確定輸出的光子分布。玻色採樣的關鍵特徵是，躍遷振幅與復矩陣的積和式相關，而要準確計算或者把積和式近似到一個乘法誤差內一般來說是很難的——#P-hard 複雜度級別的難。此外，對玻色採樣的有效弱模擬被認為是不可能的，除非多項式層級（Polynomial Hierarchy）坍縮到第三級。但是，近期一項數值研究表明，要使用玻色採樣實現量子霸權，將需要同時生成至少 50 或更多個單光子，而這仍然是個很大的技術挑戰。

在玻色採樣的設定中，一個有趣的問題是：線性光學能否被應用於求解決策問題？在這種情況下，躍遷振幅可能只需要被確定到一個加法誤差。但是，我們發現，有一大類與玻色採樣相關的決策問題都可被經典計算機模擬 [7]，這解決了 Aaronson 和 Hance 提出了一個開放問題 [9]。

IQP 線路代表著一種簡化的量子線路模型。線路的初始量子態都為零態： |000...0>，之後每個量子比特都被作用一個 Hadamard 門。接著，在這些量子比特上作用對角的門，最後再次在每個量子比特上作用 Hadamard 門。IQP 線路的經典複雜度證明與玻色採樣的情況類似。實際上，玻色採樣的複雜度證明是受 IQP 線路的複雜度結果啟發而得到的。當受到雜訊影響時，IQP 線路可能可以用經典方式模擬 [8]。

最後，混沌量子線路是指按特定規則作用兩比特門，以及隨機從某個集合中抽取並作用單比特門。這類線路的輸出概率接近所謂的 Porter-Thomas 分布，這是量子混沌的一個特徵。近期已經出現了一些數值研究，旨在探索經典計算在模擬低深度量子線路中的極限。在理想情況下，為了對量子霸權進行基準評測，既需要考慮量子比特數，還需要考慮線路深度。然而，在有雜訊存在的情況下，高深度混沌量子線路也可能通過經典方式模擬 [10]。

最後，除了這三種方法，人們應該還能預見量子霸權可能在很多實際應用上實現，比如量子化學或量子機器學習。這一天什麼時候才會到來呢？耐心等待吧！

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