近日，本源量子聯合中科大研究團隊在量子近似優化演算法（QuantumApproximateOptimizationAlgorithm，後稱“QAOA”）的研究中取得最新進展。該研究證明了S-QAOA演算法（ShortcutstoQuantumApproximateOptimizationAlgorithm，後稱“S-QAOA”）是利用現階段的含噪聲量子電腦求解組合優化問題的理想選擇，進一步推進了量子計算在組合優化問題上的應用。
（圖片由本源量子授權發佈）
什麼是組合優化問題？以著名的旅行商問題（TSP）為例，假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑長度為所有路徑之中的最小值。這就是一個典型的組合優化問題。
從廣義上講，組合優化問題是涉及從有限的一組對象中找到"最佳"對象的問題。“最佳”是通過給定的評估函數來測量的，該函數將對象映射到某個分數或者成本，目標是找到最高評估分數和最低成本的對象。組合優化往往涉及排序、分類、篩選等問題。
組合優化問題在現實生活中具有廣泛的應用，比如交通、物流、調度、金融等領域的許多問題都是組合優化問題。並且很多組合優化問題對應的經典演算法都有較高的複雜度，在問題規模較大時，經典電腦難以快速地找到這些問題的最優解。因此，利用量子計算加速組合優化問題的求解具有重要的意義。
在含噪聲的中等規模（NISQ）的量子時代，可靠的量子操作數會受到量子噪聲的限制（目前量子噪聲包括量子退相干、旋轉誤差等）。因此，人們對量子-經典混合演算法很感興趣，這類混合演算法可以借助經典優化器來優化量子線路中的參數，從而選擇最優的演化路徑，以降低量子線路深度。比較著名的一類量子-經典混合演算法就是量子近似優化演算法（QAOA），它有望為組合優化問題的近似解的求解帶來指數級的加速。
研究人員表示，理論上，如果量子線路足夠深，QAOA可以得到較好的近似解。但由於量子噪聲引起的誤差會隨著量子線路深度的增加而累積，當量子線路深度較大時，QAOA的性能實際上會下降。因此，在當前的量子電腦上展現QAOA演算法的優勢是一項具有挑戰性的任務，降低QAOA演算法的線路深度對於在現階段的量子電腦上展現QAOA演算法的優勢具有重要意義。
為了減少量子電路的深度，研究人員提出了一種新的思路，稱為“ShortcutstoQAOA”:（S-QAOA）。首先，在S-QAOA中考慮了額外的兩體相互作用，在量子電路中加入與YY相互作用相關的雙門以補償非絕熱效應，從而加速量子退火過程，加速QAOA的優化；其次，釋放了兩體相互作用（包括ZZ相互作用和YY相互作用）的參數自由度，增強量子電路的表示能力，從而降低量子線路的深度。數值模擬結果表明，與QAOA相比，S-QAOA在量子線路更淺的情況下可以獲得較好的結果。
研究人員通過引入更多的兩體相互作用和釋放參數自由度來改進QAOA演算法，降低QAOA演算法需要的線路深度，使得QAOA演算法更適合現階段的含噪聲的量子電腦。由於該演算法利用了STA（Shortcutstoadiabaticity）的原理，因此研究人員將其稱為“ShortcutstoQAOA”。
本源量子研究人員表示：“在S-QAOA中，參數自由度的釋放是通過對梯度較大的參數進行進一步的優化，但是是否有更好的方式挑選出最重要的參數做優化，還是值得探索和研究的一個方向。我們將在下一步的工作中研究更多的案例，以驗證和完善我們的想法。我們希望我們的方法可以為儘早實現量子優越性提供新的方法和思路。”（張夢怡、楊夏，圖片由本源量子授權發佈）