量子近似優化演算法 (QAOA)
量子近似最佳化演算法（QAOA）與 Max-Cut 問題
量子近似最佳化演算法（Quantum Approximate Optimization Algorithm, QAOA）是另一種針對組合優化問題的量子演算法，屬於變分量子演算法的範疇airitilibrary.com。QAOA最初由Farhi等人於2014年提出，目標是在量子計算機上以近似方式求解NP-hard的組合最佳化問題airitilibrary.com。它利用量子位的疊加與糾纏特性，在多項式時間內產生比傳統演算法更接近最優的解airitilibrary.com。QAOA的核心思想是將待解的組合問題轉換為一個對應的哈密頓量 $H_P$，其基態（最低能量態）編碼了原問題的優化解。演算法通過交替應用兩種參數化的量子邏輯門（通常稱為「問題哈密頓量演化」和「混合哈密頓量演化」），來逐步逼近目標哈密頓量的基態mindspore.cnmindspore.cn。具體而言，在 $p$ 層QAOA迭代中，量子電路依次施加： (1) 根據問題哈密頓量 $H_P$ 演化一段時間（參數為 $\gamma$），(2) 根據一個混合哈密頓量 $H_M$（通常選擇為所有量子比特的 $X$ 方向場）演化一段時間（參數為 $\beta$）。這兩步構成一層迭代mindspore.cn。透過調整參數集 $(\boldsymbol{\gamma}, \boldsymbol{\beta})$，理論上可以讓最終量子態對應的測量結果最大化問題的目標函數期望值。由於只能實現近似最優，QAOA屬於近似演算法，但在量子計算機上有望以更高效方式獲得高品質解。
Max-Cut問題是QAOA經典應用示例之一mindspore.cnmindspore.cn。Max-Cut屬於NP完全問題，給定一圖的頂點集合和邊集合，目標是將頂點分成兩組，使跨分組的邊數量最大mindspore.cn。QAOA解Max-Cut的思路是：將每個圖頂點對應到一個量子比特，比特的兩種狀態（例如 |0> 和 |1>）表示頂點被分到兩個不同組別mindspore.cn。定義問題哈密頓量 $H_P$ 使其基態能量對應Max-Cut的負的割邊數，例如對每條邊連接的兩頂點，若二者處於不同組（量子態相異），則給予哈密頓量一個負能量貢獻（如 -1）；若處於同組則貢獻為0mindspore.cn。如此一來，$H_P$ 的基態能量最低時正對應割邊數最大的切割方式mindspore.cn。QAOA通過參數化量子電路逼近此基態，經由測量讀出各頂點分組的結果，即可得到近似的Max-Cut解。mindspore.cnmindspore.cn在實驗中，對於節點數較少的圖，可以比較QAOA所得結果與暴力搜尋的精確解，以驗證QAOA的有效性mindspore.cn。隨著圖的規模增大，暴力解變得不可行，而QAOA仍可在多項式時間內提供一組參數來近似最大割mindspore.cn。這凸顯了QAOA作為一種近似優化工具的價值。
實現條件與挑戰：
QAOA屬於離線的量子閘模型演算法，需要門型量子計算機來執行。相對於量子退火的連續演化，QAOA以離散的量子門操作模擬退火過程，每層包含對問題哈密頓量的模擬（通常是一系列Z門和兩比特ZZ互作用門）以及對混合哈密頓量的模擬（一系列X旋轉門）。要得到高品質近似解，往往需要多層迭代（即較大的 $p$ 值），但這會增加電路深度並引入更多量子門。當前的NISQ（雜訊中等規模量子）硬體在執行深度電路時易受累積誤差影響，使QAOA的性能下降airitilibrary.com。研究表明，在嘈雜的量子處理器上，即使理論上QAOA可近似求解，實際測得的近似比率往往因量子雜訊大幅降低airitilibrary.com。因此，如何在有限相干時間內完成QAOA電路並保持量子優勢，是實作上的主要難題之一airitilibrary.com。此外，QAOA需要借助經典優化器來調整參數 $(\boldsymbol{\gamma}, \boldsymbol{\beta})$。這是一個高維非凸優化問題，在某些情況下會遇到梯度平坦（高原）等問題，使參數訓練困難。對較大問題，參數空間複雜度增高，也增加了尋找最佳參數的經典計算成本。
當前技術瓶頸：
總的來說，QAOA在NISQ時代面臨兩難：一方面需要增加電路深度和比特數以求解更大問題，另一方面硬體雜訊限制了可承受的電路深度，導致實際可解問題規模有限airitilibrary.com。有研究指出，對於目前量子裝置，QAOA求解的近似比率（即所得解與最佳解目標值之比）會隨問題規模和門數上升而惡化airitilibrary.com。即便如此，QAOA仍被視為在有限量子資源下展示量子優越性的一個潛在路徑。一些改進策略正在探索中，例如通過巧妙選擇初始參數、分層迭代增量地增大 $p$、或與經典演算法交替結合，來提高參數優化效率和結果品質。同時，關於QAOA的理論分析也在深入進行，例如近期學者發現所謂「可達性缺陷」(reachability deficits)可能限制QAOA能探索到的解空間範圍scimonth.com.tw。這提醒我們，QAOA雖有漂亮的框架，但在取得全面超越經典演算法的效果之前，尚有許多問題需要解決。
應用現狀：
儘管挑戰重重，QAOA已在小規模問題上有所嘗試。以Max-Cut為例，IBM、Google等團隊在5到10個節點的小圖上以量子處理器實現了QAOA演算法，得到的近似解與最佳解僅差距很小，證明了基本可行性。一些實驗使用超導量子比特或離子阱系統執行一兩層QAOA迭代，成功找到例如6節點完全圖的最大割近似解mindspore.cnmindspore.cn。在組合優化其它問題上，QAOA的變體也有所應用，例如求解Max-SAT、圖著色、社區偵測等。值得注意的是，目前這些演示規模仍屬於可由經典算法驗證的小尺寸範圍，尚未真正展現對經典的計算優勢。然而，每一次更大規模或更高精度的實驗，都在逐步逼近量子優越性的門檻。例如，最近有研究將QAOA應用於投資組合優化，透過混合量子-經典計算在模擬環境下獲得了比傳統啟發式更高的收益近似值airitilibrary.com。隨著量子硬體比特數增加和容錯能力提升，未來QAOA有望在物流路由、機器學習中的參數調優等更多實際場景中測試。如果能在這些領域找到任何優於經典算法的實例，將是量子近似演算法的重要里程碑。
王培儒