量子計算和經典計算的競爭由來已久。研究人員不斷尋找量子算法能夠顯著優于經典算法的問題，這些努力構成了量子計算領域進步的主要動力。

2025 年 3 月，D-Wave 團隊在Science期刊發表研究，聲稱使用量子退火處理器在模擬量子動力學方面實現了超越經典計算的能力。他們研究了二維、三維和無限維自旋玻璃系統的量子退火動力學，并指出經典算法無法在合理時間內達到相同精度。

圖丨相關論文（來源：Science）

這一聲明很快受到挑戰。瑞士洛桑聯邦理工學院的研究者開發了時變變分蒙特卡洛方法（arXiv:2503.08247），而 Flatiron 研究所的團隊則展示了張量網絡與信念傳播結合的方法（arXiv:2503.05693）。兩個團隊均證明，經典算法不僅能匹配，甚至能超越量子退火器的結果。

這種情形其實在量子計算歷史上一直反復出現：量子算法宣稱突破，而后經典算法迅速趕上。這種競爭促進了兩個領域的進步，但也讓人懷疑量子計算是否真能在實用問題上提供無可爭議的優勢。不過，2024 年由谷歌 Quantum AI 團隊提出的一種量子算法——解碼量子干涉測量（DQI，Decoded Quantum Interferometry）算法似乎打破了這一循環，展示了一種在數學上可證明的量子加速，這一點至今未被經典算法所匹敵。

圖丨相關論文（來源：arXiv）

將經典問題空間轉化為量子概率振幅空間

與其他量子算法不同，DQI 采用了全新的技術路徑，這也是其能夠實現真正量子加速的關鍵。傳統量子優化算法如量子退火通常從能量視角出發，將最優解對應到最低能量狀態。這種方法雖然直觀，但往往難以證明其在計算復雜性上的優勢。而 DQI 則基于波動觀點，利用量子物理學的波動性質來解決優化問題，這種范式轉變使得量子加速的數學證明成為可能。

DQI 的核心機制可以詳細分解為幾個關聯緊密的步驟。首先，算法使用量子傅里葉變換將優化問題的所有可能解決方案映射為量子波。這不僅是一個數學轉換，更是一個物理概念的轉變——將經典問題空間轉化為量子概率振幅空間。在這個空間中，每個可能的解對應一個量子態，這些態的疊加構成了問題的完整表示。

圖丨 DQI 算法的步驟示意圖（來源：arXiv）

轉換完成后，DQI 在量子空間中通過特殊的量子門操作調整這些波的振幅，這一過程使得對應更優解決方案的狀態獲得更高的量子振幅。量子門操作的序列依賴于具體問題的結構，但其目的始終是強化那些代表更好解的量子態。這種調制過程在傳統量子計算中并不常見，但這也正是 DQI 的創新之處。

最后，也是最具突破性的部分，DQI 應用了源自經典通信理論的解碼技術。在通信中，解碼用于從噪聲信號中恢復原始信息；在 DQI 中，解碼成為了從復雜量子狀態中提取最優解的關鍵工具。這種跨領域的方法融合是 DQI 最顯著的創新點——它將通信理論的解碼原理與量子計算相結合，創造了一種全新的算法范式。

具體而言，DQI 采用的解碼技術源自 20 世紀 60 年代開發的用于找出并修復編碼消息中單個錯誤的算法。這種解碼方法在 DQI 中被重新構想，用于從量子振幅分布中識別“正確”的解。這一步驟解決了量子計算中的一個核心挑戰——如何有效地從量子疊加態中提取有用信息而不喪失量子優勢。

DQI 針對的優化問題是一類在數學上被稱為“低度多項式擬合”的問題：給定一組數據點，需要找到一個不過于復雜（度數有限）的多項式函數，使其通過盡可能多的點。這個問題看似簡單，但實際上與密碼學、錯誤糾正碼以及機器學習中的核心問題有著深刻聯系。這種問題的數學表述可以看作是在一個高維空間中找到最接近給定點集的低復雜度曲面，這是一個計算復雜性較高的任務。

從技術角度看，DQI 實現了這一任務的指數級加速。經典算法需要逐一評估可能的多項式或使用復雜的近似方法，其運行時間隨問題規模呈多項式或更高增長。相比之下，DQI 利用量子疊加態同時處理所有可能的多項式，然后通過量子干涉和解碼提取最優解，理論上實現了指數級加速。

充滿意外的開發過程

這項成果的主要作者，來自 Google Quantum AI 的物理學家 Stephen Jordan 表示，開發 DQI 的過程其實充滿了意外。

圖丨 Stephen Jordan（來源：X Prize）

最開始，這項研究的目標實際上并不明確，它的發現源于團隊對量子波動性質的基礎探索，這種探索最終導向了實用的算法突破。

Jordan 在 2023 年加入 Google 時，開始與量子算法領域的資深研究者 Eddie Farhi 合作。Farhi 之前的研究主要基于能量視角，將優化問題映射為能量最小化問題。但 Jordan 決定探索不同路徑，轉向量子物理學的波動性質。這種方法選擇不僅是技術上的區別，更反映了對量子計算本質的不同理解。

Jordan 最初的思路是將量子傅里葉變換應用于優化問題。量子傅里葉變換是量子計算中的基本操作，能夠在指數級大小的空間中高效地轉換數據表示。通過這種變換，Jordan 將問題解空間表示為量子波的疊加，理論上更優的解對應更大的波（更高的量子振幅）。這一思路在概念上優雅，但實際實現面臨著巨大挑戰。

在量子系統中，直接測量“哪個振幅最大”并不像觀察海灘上最高的波那么簡單。量子測量會導致波函數坍縮，單次測量只能獲得一個可能的結果，而非完整的振幅分布。這一基本困難使得從量子狀態中提取最優解成為一個非常復雜的任務。

經過多次失敗嘗試后，Jordan 取得了重大突破。他意識到，從量子狀態中選擇最佳解的過程與通信系統中剔除編碼消息錯誤的過程在數學上存在深刻相似性。這一認識將他引向了通信理論和錯誤糾正領域，這些領域擁有豐富的技術可供探索。通過將優化問題轉換為量子問題，并應用解碼的概念框架，Jordan 發現了發展量子算法的新途徑。

于是 Jordan 開始與 Google 的同事 Noah Shutty 合作測試各種解碼方案，評估它們在不同優化問題上與經典算法的競爭力。最初的結果并不理想，Jordan 回憶道：“經典算法很難被擊敗。經過幾個月的嘗試，我們仍然沒有為量子算法取得任何勝利。”

關鍵的轉折點出現在他們發現了一種特定的解碼方法，這種方法最初在 20 世紀 60 年代被開發用于通信中的錯誤糾正。將這種解碼方法與量子算法結合，他們幾乎立即發現了量子加速的證據。這種結合不僅提供了技術上的解決方案，也建立了兩個看似不相關領域之間的理論橋梁。

為了確保這一發現的可靠性，他們咨詢了編碼理論專家 Mary Wootters（她恰好是 Shutty 在斯坦福大學的前博士導師）。她進行了全面的分析，尋找可能與 DQI 性能匹敵的已知經典算法。這種嚴格的評估對于驗證量子優勢至關重要，因為許多聲稱的量子優勢最終被證明可以被巧妙的經典算法復制。在這種嚴格審查下，DQI 的優勢依然存在，這增強了研究團隊的信心。

圖丨 Mary Wootters（來源：Mary Wootters）

“每一種新算法都是慶祝的理由。”

從理論層面來說，DQI 的核心價值在于它提供了一個數學上可證明的量子加速案例。與很多量子算法不同，DQI 的加速不依賴于啟發式方法或實驗觀察，而是基于嚴格的計算復雜性分析，也就是我們前面所提到的，對于低度多項式擬合問題，DQI 在時間復雜度上相比最佳已知經典算法實現了指數級改進。

這種理論上的確定性是量子計算研究中的黃金標準，但很少有算法能夠達到這一標準。量子計算的知名懷疑者，Reichman 大學的 Gil Kalai 對此高度評價：“尋找顯示優于經典算法的量子算法是過去三十年來一項非常令人興奮的工作，而顯示出這種優勢的確定算法數量并不多。因此，每一種新算法都是慶祝的理由。”

DQI 的理論基礎建立在幾個關鍵要素上：量子疊加原理允許同時處理指數級數量的可能解；量子干涉可以增強對應優解的振幅；解碼技術提供了從這種增強狀態中高效提取信息的方法。這些要素相互配合，形成了一個在理論上健全且實際可行的量子算法。

而這種算法的應用范圍也遠遠超過了初始問題。研究團隊已將其擴展到更廣泛的優化問題類別，包括：

1. 密碼學：在某些密碼系統的分析中，多項式重構是核心挑戰。

2. 錯誤糾正：在通信系統中，找到最佳編碼方案涉及類似的優化問題。

3. 機器學習：某些模型訓練和特征選擇問題可以重新表述為 DQI 擅長解決的格式。

但其實際應用目前還面臨硬件限制。Jordan 坦言：“DQI 無法在現有量子計算機上運行。”現有量子處理器的量子比特數量、相干時間和錯誤率都無法支持完整的 DQI 實現。

此外，DQI 的理論假設了理想的量子操作和測量，實際實現中的噪聲和不完美會影響算法的性能。研究人員需要開發適應現實量子硬件限制的修改版算法，這可能涉及量子噪聲緩解技術和混合量子-經典方法的結合。

盡管存在這些挑戰，DQI 仍然代表了量子算法研究的重要里程碑。即使在實際硬件實現之前，它提供了一個有力的概念證明，表明量子計算在某些問題上確實可以提供數學上可證明的計算優勢。這種理論上的確定性為量子計算的實用價值提供了有力支持。

參考資料：

1.https://www.quantamagazine.org/quantum-speedup-found-for-huge-class-of-hard-problems-20250317/

2.https://arxiv.org/abs/2408.08292

3.https://www.science.org/doi/10.1126/science.ado6285

運營/排版：何晨龍