『壹』 什麼叫組合優化
組合優化（Combinatorial Optimization）問題的目標是從組合問題的可行解集中求出最優解，通常可描述為：令Ω＝{s1，s2，…，sn}為所有狀態構成的解空間，C(si)為狀態si對應的目標函數值，要求尋找最優解s*，使得對於所有的si∈Ω，有C(s*)＝minC(si)。組合優化往往涉及排序、分類、篩選等問題，它是的一個重要分支。
典型的組合優化問題有旅行商問題（Traveling Salesman Problem－TSP）、加工調度問題（Scheling Problem，如Flow-Shop，Job-Shop）、0-1背包問題（Knapsack Problem）、裝箱問題（Bin Packing Problem）、圖著色問題（Graph Coloring Problem）、聚類問題（Clustering Problem）等。這些問題描述非常簡單，並且有很強的工程代表性，但最優化求解很困難，其主要原因是求解這些問題的演算法需要極長的運行時間與極大的存儲空間，以致根本不可能在現有計算機上實現，即所謂的「組合爆炸」。正是這些問題的代表性和復雜性激起了人們對組合優化理論與演算法的研究興趣。
『貳』 本源量子聯合中科大在量子近似優化演算法研究中取得新進展
近日，本源量子聯合中科大研究團隊在量子近似優化演算法（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中，參數自由度的釋放是通過對梯度較大的參數進行進一步的優化，但是是否有更好的方式挑選出最重要的參數做優化，還是值得 探索 和研究的一個方向。我們將在下一步的工作中研究更多的案例，以驗證和完善我們的想法。我們希望我們的方法可以為盡早實現量子優越性提供新的方法和思路。」