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