量子計算擅長什麼（又不擅長什麼）

一份誠實的加速評分表

讓我們先從整個領域裡最重要的一句誠實話講起：量子電腦不是一個能同時核對每個答案的魔法盒子。疊加態確實讓許多可能性以振幅的形式同時存在，但你永遠無法把它們全部讀出來。當你測量時，你只會得到恰好一個結果，其機率由玻恩定則決定。量子演算法的全部藝術，就在於安排干涉，讓錯誤答案的振幅相互抵消，而正確答案的振幅增長——*然後*你才去測量。

正因如此，你能得到的加速完全取決於問題的結構，而不是量子位元的原始數量。並不存在一個統一的「量子快 X 倍」的數字。相反，大致可以分為三類：少數問題能獲得指數級加速，更寬泛的一類能獲得平方級（開平方）加速，而絕大多數問題根本得不到任何有用的加速。判斷一個問題落入哪一類，正是「理解量子計算」的大部分含義所在。

PROBLEM TYPE              SPEEDUP            EXAMPLE
-------------------------------------------------------------
structured (periodicity)  exponential        factoring (Shor)
simulating quantum systems exponential*       chemistry, materials
unstructured search        quadratic (sqrt N) database-style search
linear algebra (special)   sometimes large    certain solvers (caveats)
general-purpose computing  none worth it      email, spreadsheets, web
-------------------------------------------------------------
* exponential in the right regime; a classical computer cannot
  efficiently simulate large quantum systems at all.

一份腳踏實地的評分表。一個問題落入哪一類，由它的結構決定，而不是由你擁有多少量子位元決定。

絕佳契合：因數分解、模擬、部分搜尋

皇冠上的明珠是Shor 演算法。它把因數分解重新表述為尋找週期，並利用量子傅立葉轉換透過干涉提取出那個週期，從而以比任何已知古典方法都快指數級的速度分解大數。正是這一結果威脅到了 RSA 和 ECC——但前提是要存在一台大型的、帶糾錯的量子電腦，而這樣的機器目前還不存在。

可能更重要的契合是模擬量子系統本身：分子、催化劑、材料、奇異物態。大自然本質上是量子的，因此古典電腦即便要追蹤一個不算大的分子的量子態，也得付出指數級的代價。而量子電腦能夠原生地表示這種狀態。這正是費曼當初提出量子電腦的初衷，也是諸如 VQE 以及偏向最佳化的 QAOA 等近期方法的基礎。

接下來是搜尋。Grover 演算法能在一個含 N 個元素的無結構列表中，用大約 sqrt(N) 步而非 N 步找到被標記的項，它藉助振幅放大把機率往正確答案上「泵」。這是一個貨真價實、可被證明的平方級加速——有價值、適用面廣，卻也經常被誇大。它並不能讓你瞬間完成搜尋，而且對許多實際任務來說，運行一台量子電腦的開銷會把這點開平方的優勢吃掉。

Grover, roughly:

  start:   every item equally likely  (flat amplitudes)
           |x0> |x1> |x2> ... |x*> ...   <- x* is the answer

  repeat ~sqrt(N) times:
     [oracle]  flip the sign of the answer's amplitude
     [diffuse] reflect all amplitudes about their average
               -> answer's amplitude grows, others shrink

  measure -> answer with high probability

  cost: ~sqrt(N) iterations, NOT 1, NOT log(N)

Grover 演算法逐步放大正確答案的振幅。它是 sqrt(N)，一種平方級的勝利——而不是一次性的查表。

糟糕契合：大多數日常運算

現在說說誠實的壞消息：電腦每天所做的大部分事情得不到任何有用的量子加速。寄郵件、算繪網頁、運行試算表、播放串流影片、為客戶記錄資料庫提供服務、訓練許多機器學習模型——這些任務要麼用古典方法本就高效，要麼缺乏量子演算法所利用的那種特殊結構（比如隱藏的週期性）。對這些任務而言，量子電腦會比你已經擁有的筆電更慢、更貴，而且脆弱得多。

此外還有一項高昂的輸入/輸出稅。許多被提出的量子加速都假定你的資料已經載入到了一個量子態中，而把大型古典資料集載入量子位元，其本身的代價就可能和加速所節省的一樣多。最後的一次測量只會從一個機率分布中給你一個樣本，而不是把裡面的所有內容完整讀出來。因此，即便核心數學運算更快，把資料送進去、把答案取出來的過程也可能把優勢抹平。

量子電腦不是一顆更快的 CPU

有一個該刪掉的思維模型：*「量子電腦就像我的 CPU，只是核心多得多。」*並非如此。一個古典核心執行的是許多快速、可靠、可自由複製的操作。量子位元則是另一種生物：它們的狀態無法被複製（不可複製定理），每一個閘都必須是可逆的且么正的，而讀取一個量子位元會摧毀它的疊加態。你不是靠把普通指令分攤到更多核心上來為量子電腦寫程式——你是在雕琢振幅，好讓干涉揭示出答案。

而且今天的硬體確實脆弱。我們正處於 NISQ 時代——含噪中等規模量子（Noisy Intermediate-Scale Quantum）——在這個時代，量子位元會在微秒到毫秒的尺度上失去其狀態（去相干，由 T1 和 T2 刻畫），而且每一個閘都帶有誤差。目前還沒有大規模的容錯量子電腦。像表面碼這樣的糾錯在原理上能解決這個問題，但前提是誤差要低於大約 1% 的閾值，且代價極其殘酷：每一個可靠的邏輯量子位元需要數千個物理量子位元。正是這種開銷，使得 Shor 規模的因數分解仍然要等上數年，而不是一件你買得到的產品。

WRONG picture:                CLOSER picture:

  CPU with 1000 cores           1000 fragile qubits
  -> 1000x more work            -> one carefully tuned
     done in parallel              interference pattern
  -> copy/inspect freely        -> can't copy (no-cloning)
  -> read anytime               -> measure once, state
                                   collapses, get 1 sample

量子電腦是一種不同種類的機器，而不是一顆渦輪增壓的 CPU。「更多量子位元」並不等於「更多核心」。

批判地閱讀炒作

現在你已經具備了足夠的本事，能像懷疑者而不是粉絲那樣去讀量子計算的新聞標題。那少數幾種套路一次又一次地出現，一旦你能把它們叫出名字來，炒作大多就自行瓦解了。目標並不是憤世嫉俗——量子計算是真實的，它在那些狹窄的勝利上確實令人振奮。目標是把狹窄而真實的勝利，與寬泛而虛幻的勝利區分開來。

「一次性嘗試所有答案。」不對。疊加態持有許多振幅，但測量只返回一個結果；真正的功夫在於讓干涉偏向正確的那一個。把這句話當作整篇文章其餘部分的一個危險信號。
「對一切都快指數級。」不對。只有 Shor 類的有結構問題以及量子模擬才能獲得指數級加速。Grover 式搜尋是平方級的。大多數任務什麼也得不到。
「我們有 N 個量子位元，所以它很強大。」要問品質，而不只是數量：閘誤差、相干時間、連通性，以及它們是含噪的物理量子位元還是經過糾錯的邏輯量子位元。少數幾個好的量子位元可以勝過許多糟糕的。
「量子如今就能破解一切加密。」不對。破解 RSA 需要一台尚不存在的大型容錯機器，而後量子密碼學（能抵抗量子攻擊的古典演算法）已經在部署中了。另外要注意，QKD 是一個獨立的、基於物理的概念——它與後量子密碼學並不是一回事。
「量子霸權意味著它有用。」未必。一次量子優勢演示，可能只是在一個人為構造、毫無實際收益的基準測試上擊敗了古典機器。永遠要問：到底對*什麼*有用，又是與*最好的*古典方法相比？