谷歌一直在爭相開發量子增強型的處理器，這種處理器使用量子力學效應來增進資料處理速度。谷歌為此的短期目標是已經設計出了一種新型的量子增強演算法，可以在有真實噪聲的情況下執行。所謂的量子近似優化演算法（Quantum Approximate Optimisation Algorithm，簡稱 QAOA）是谷歌目前開發的抗噪聲量子增強演算法的基礎。

谷歌在量子近似優化演算法中採用的這一著名方法引發了廣泛的商業興趣，並激發了全球研究界探索其新穎應用的興趣。但是，對於谷歌的量子近似優化演算法的最終效能限制知之甚少。

最近，俄羅斯斯科爾科沃科技學院（Skoltech）深量子實驗室（Deep Quantum Laboratory）的一組科學家應對此提出了挑戰。研究團隊發現並量化了谷歌廣泛採用的量子演算法方法中的基本限制。研究團隊在論文報告中詳細介紹了所發現的可達性缺陷（reachability deficits）。作者表明，這些缺陷對量子近似優化演算法甚至近似解決問題的能力產生了根本性的限制。這一研究發表在最近的《物理評論通訊》上。

研究團隊的發現報告了變分量子近似優化演算法的明顯侷限性。由於其內部的從量子到經典的反饋過程，量子近似優化演算法和其他變分量子演算法已經證明使用已知的數學技術極其難以分析。也就是說，給定的量子計算只能執行固定的時間量。在此固定時間內，可以執行固定數量的量子運算。量子近似優化演算法試圖通過形成一系列越來越近的最佳逼近，以最小化目標函式來迭代利用這些量子運算。該研究發現了在該過程所體現的新的限制。

研究人員發現，對於任何固定深度的量子電路，量子近似優化演算法逼近最佳解的能力從根本上取決於問題“密度”。 對於稱為MAX-SAT的問題，可以將所謂的密度定義為問題約束與變數計數的比率，有時也稱為子句密度（clause density）。研究人員發現了具有高密度解決方案的問題例項，這些最優解決方案無論演算法的執行時間如何，都無法保證成功地近似估計。

如圖所示，表示在問題密度增加的情況下，隨機生成的MAX-SAT例項上固定深度量子近似優化演算法電路的效能，即量子近似優化演算法最優值與精確最優值之間的差異。 儘管較高深度的版本可實現更好的效能，但它們仍顯示出可達性缺陷。

基於這個研究結果，看來谷歌宣稱的量子至上，其支撐基礎之一的量子增強演算法，還不是那麼樂觀，還有一段更長的路要走。

介紹完了這篇研究論文，有人會覺得量子近似優化演算法具體是什麼還是不太清楚，下面給感興趣的讀者再進一步具體介紹一下。

量子近似優化演算法是可以在近期量子計算機中實現的演算法之一，並且曾被視為證明量子至上性的最有希望的演算法之一。量子近似優化演算法是一種近似演算法，這意味著它不會提供“最準確”、“最佳”的結果，而只會提供“足夠好”的結果，其特徵在於達到所需要的近似率。

量子近似優化演算法的數學基礎之一是數學優化處理，即從一組可能的解決方案中，根據一定標準，找出問題的最佳解決方案。通常，優化問題即被表述為最小化問題，試圖根據解決方案尋求最小化誤差，最優解決方案具有最小誤差。數學優化處理廣泛應用於許多科技領域中。隨著所涉及資料的複雜性和資料量的增加，需要更有效的方法來解決優化問題。

量子計算能力可以解決經典計算機上實際上不可行的問題，或者相對於經典演算法而言可以大大提高速度。量子優化演算法主要涉及到下面方面的基本問題。

量子資料擬合

資料擬合是構建最適合一組資料點的數學函式的過程。擬合的品質是通過某些標準，如通常是函式與資料點之間的距離來進行衡量的。

量子最小二乘擬合

資料擬合的最常見型別之一是解決最小二乘問題，以最小化資料點與擬合函式之間的平方差。許多人都知道，最小二乘法是迴歸分析的一種標準方法，它通過最小化每個方程式結果中的殘差平方和來近似超定系統，其中

量子最小二乘擬合算法使用量子演算法的線性方程組（HHL）版本，並輸出係數 λ 和擬合品質估計 E。 它由三個基本部分組成：一個用於執行偽逆運算的演算法，一個用於擬合品質估計的例程，以及一個用於學習擬合引數的演算法。由於量子演算法主要基於HHL演算法，因此在以下情況下提出了指數改進。F是稀疏的，並且兩者的條件數，即最大特徵值與最小特徵值之比 FF 和 FF 都小。

量子半定程式設計（Quantum semidefinite programming）

半定程式設計（Semidefinite programming，簡稱 SDP）是一種優化子區域，用於處理正半定矩陣的圓錐與仿射空間的交點上的線性目標函式，即要最小化或最大化的使用者指定函式的優化。目標函式是矩陣的內積 C 作為輸入與變數 X。 表示為 Sn 所有空間 n x n 對稱矩陣。變數 X 必須位於正半定對稱矩陣的（閉合凸）錐中。兩個矩陣的內積定義為：

該問題可能具有其他約束（作為輸入），通常也被表述為內積。每個約束迫使矩陣的內積，其中Ak作為輸入，優化變數X小於指定值bk（作為輸入）。最後，半定程式設計問題可以寫成：

量子演算法

演算法輸入為：A1 ... Am，C，b1 ... bm以及與關於解的跡的引數，有關精度和最佳值，即最佳點處目標函式的值有關的引數。

量子演算法由幾個迭代組成。在每次迭代中，它都會解決一個可行性問題，即找到滿足以下條件，給出一閾值 t 的任何解決方案：

在每次迭代中，不同的閾值 t 被選擇，並且演算法輸出解決方案 X 這樣其他約束也得到滿足，或表明不存在這樣的解決方案。該演算法執行二進位制搜尋以找到最小閾值 t 為此解決方案 X 仍然存在：這為半定程式設計問題提供了最起碼的解決方案。

在一般情況下，量子演算法提供了優於最佳經典演算法的二次改進，而當輸入矩陣的維度較低時，則會提供指數級的改進。

量子組合優化

組合優化問題旨在從一組有限的物件中找到一個最佳物件。問題可以表述為目標函式的最大值，該目標函式是布林函式之和。每個布林函式 Cα：{0，1} → {0，1} 作為輸入 n 位字串 = z1 z2 ...... zn 並給出一位（0或1）作為輸出。 n 位元位和 m 子集的組合優化問題是尋求 n 位字串 z，使下述函式最大化：

量子近似優化演算法

對於組合優化，量子近似優化演算法具有比任何已知的多項式時間經典演算法，對於某個問題，具有更好的逼近率，直到提出一種更有效的經典演算法。

量子近似優化演算法的核心依賴於與2p角度相關的么正算符的運用。在泛函分析中，么正算符（unitary operator，或稱酉算符）是定義在希爾伯特空間上的有界線性算符。其中，p>1 是輸入整數。這些運算元被迭代地應用到一個狀態上，該狀態是計算基礎上所有可能狀態的均等權重的量子疊加。在每次迭代中，狀態都是在計算基礎上測量的，計算C(z) 。 經過足夠的重複次數後，C(z) 幾乎是最佳狀態，並且被測狀態也接近最佳狀態。

最後簡單地小結一下。量子近似優化演算法是否有用？量子近似優化演算法是否比經典演算法更好？目前答案是未知的。儘管量子近似優化演算法還不可能完全肯定超越傳統演算法，但它確實也顯示出一定的量子優越性。量子近似優化演算法能夠解決傳統計算機無法解決的問題。換句話說，如果可以經典地模擬量子近似優化演算法，則 P = NP。

最後，量子近似優化演算法實施受門保真度的限制。在當前的噪聲量子計算機中，p的層數很可能會導致更差的精度，因為門誤差會抵消較高p的好處。但是，這並不排除量子近似優化演算法可以在嘈雜的中型量子計算機中使用，以在不久的將來協助達到量子至上。