Ⅰ 本源量子聯合中科大在量子近似優化演算法研究中取得新進展
近日，本源量子聯合中科大研究團隊在量子近似優化演算法（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中，參數自由度的釋放是通過對梯度較大的參數進行進一步的優化，但是是否有更好的方式挑選出最重要的參數做優化，還是值得 探索 和研究的一個方向。我們將在下一步的工作中研究更多的案例，以驗證和完善我們的想法。我們希望我們的方法可以為盡早實現量子優越性提供新的方法和思路。」
Ⅱ 量子遺傳演算法的國內外研究現狀
當前科學技術正進入多學科互相交叉、互相滲透、互相影響的時代，生命科學與工程科學的交叉、滲透和相互促進是其中一個典型例子，也是近代科學技術發展的一個顯著特點。遺傳演算法的蓬勃發展正體現了科學發展的這一特點和趨勢。
製造機器智能一直是人類的夢想，人們為此付出了巨大的努力。人工智慧技術的出現，就是人們得到的成果。但是，近年來，隨著人工智慧應用領域的不斷拓廣，傳統的基於符號處理機制的人工智慧方法在知識表示、處理模式信息及解決組合爆炸等方面所碰到的問題已變得越來越突出，這些困難甚至使某些學者對強人工智慧提出了強烈批判，對人工智慧的可能性提出了質疑。
眾所周知，在人工智慧領域中，有不少問題需要在復雜而龐大的搜索空間中尋找最優解或准優解。像貨朗擔問題和規劃問題等組合優化問題就是典型的例子。在求解此類問題時，若不能利用問題的固有知識來縮小搜索空間則會產生搜索的組合爆炸。因此，研究能在搜索過程中自動獲得和積累有關搜索空間的知識，並能自適應地控制搜索過程，從而得到最優解或准有解的通用搜索演算法一直是令人矚目的課題。遺傳演算法就是在這種背景下產生並經實踐證明特別有效的演算法。
遺傳演算法(Genetic Algorithm, GA)是近年來迅速發展起來的一種全新的隨機搜索與優化演算法,其基本思想是基於Darw in的進化論和Mendel的遺傳學說。該演算法由密執安大學教授Holland及其學生於1975年創建。此後，遺傳演算法的研究引起了國內外學者的關注。自1985年以來.國際上已召開了多次遺傳演算法的學術會議和研討會.國際遺傳演算法學會組織召開的ICGA( International Conference on Genetic Algorithms)會議和FOGA( Workshop on Foundation of Genetic Algorithms)會議。為研究和應用遺傳演算法提供了國際交流的機會。
作為一種通用的問題求解方法，遺傳演算法採用簡單的編碼技術來表示各種復雜的結構並通過對一組編碼表示進行簡單的遺傳操作和優勝劣汰的自然選擇來指導學習和確定搜索的方向。
近年來，遺傳演算法已被成功地應用於下業、經濟答理、交通運輸、工業設計等不同領域.解決了許多問題。例如，可靠性優化、流水車間調度、作業車間調度、機器調度、設備布局設計、圖像處理以及數據挖掘等。本文將從遺傳演算法的理論和技術兩方而概述目前的研究現狀。描述遺傳演算法的主要特點、基木原理以及各種改進演算法，介紹遺傳演算法的程序設計。
遺傳程序設計是借鑒生物界的自然選擇和遺傳機制，在遺傳演算法的基礎上發展起來的搜索演算法，它己成為進化計算的一個新分支。在標準的遺傳演算法中，由定長字元串(問題的可行解)組成的群體藉助於復制、交叉、變異等遺傳操作不斷進化找到問題的最優解或次優解。遺傳程序設計運用遺傳演算法的思想，常採用樹的結構來表示計算機程序，從而解決問題。對於許多問題，包括人工智慧和機器學習上的問題都可看作是需要發現一個計算機程序，即對特定輸入產生特定輸出的程序，形式化為程序歸納，那麼遺傳程序設計提供了實現程序歸納的方法。
把遺傳演算法和計算機程序結合起來的思想出現在遺傳演算法中，Holland把產生式語言和遺傳演算法結合起來實現分類系統，還有一些遺傳演算法應用領域的研究者將類似於遺傳演算法的遺傳操作施加於樹結構的程序上。
近年來，遺傳程序設計運用遺傳演算法的思想自動生成計算機程序解決了許多問題，如預測、分類、符號回歸和圖像處理等，作為一種新技術它己經與遺傳演算法並駕齊驅。 1996年，舉行了第1次遺傳程序設計國際會議，該領域己引起越來越多的相關學者們的興趣。
1967年，Holland的學生J.D.Bagley在博士論文中首次提出「遺傳演算法（Genetic Algorithms）」一詞。此後，Holland指導學生完成了多篇有關遺傳演算法研究的論文。1971年，R.B.Hollstien在他的博士論文中首次把遺傳演算法用於函數優化。1975年是遺傳演算法研究歷史上十分重要的一年。這一年Holland出版了他的著名專著《自然系統和人工系統的自適應》（Adaptation in Natural and Artificial Systems），這是第一本系統論述遺傳演算法的專著，因此有人把1975年作為遺傳演算法的誕生年。Holland在該書中系統地闡述了遺傳演算法的基本理論和方法，並提出了對遺傳演算法的理論研究和發展極其重要的模式理論（schema theory）。該理論首次確認了結構重組遺傳操作對於獲得隱並行性的重要性。同年，K.A.De Jong完成了他的博士論文《一類遺傳自適應系統的行為分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。該論文所做的研究工作，可看作是遺傳演算法發展進程中的一個里程碑，這是因為，他把Holland的模式理論與他的計算實驗結合起來。盡管De Jong和Hollstien 一樣主要側重於函數優化的應用研究，但他將選擇、交叉和變異操作進一步完善和系統化，同時又提出了諸如代溝（generation gap）等新的遺傳操作技術。可以認為，De Jong的研究工作為遺傳演算法及其應用打下了堅實的基礎，他所得出的許多結論，迄今仍具有普遍的指導意義。
進入八十年代，遺傳演算法迎來了興盛發展時期，無論是理論研究還是應用研究都成了十分熱門的課題。1985年，在美國召開了第一屆遺傳演算法國際會議（International Conference on Genetic Algorithms ，ICGA），並且成立國際遺傳演算法學會（International Society of Genetic Algorithms ，ISGA），以後每兩年舉行一次。
1989年，Holland的學生D.E.Goldberg出版了專著《搜索、優化和機器學習中的遺傳演算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。該書總結了遺傳演算法研究的主要成果，對遺傳演算法及其應用作了全面而系統的論述。同年，美國斯坦福大學的Koza基於自然選擇原則創造性地提出了用層次化的計算機程序來表達問題的遺傳程序設計( genetic programming, GP)方法，成功地解決了許多問題。
在歐洲，從1990年開始每隔一年舉辦一次Parallel Problem Solving from Nature 學術會議，其中遺傳演算法是會議主要內容之一。此外，以遺傳演算法的理論基礎為中心的學術會議還有Foundations of Genetic Algorithms，該會也是從1990年開始隔年召開一次。這些國際會議論文，集中反映了遺傳演算法近些年來的最新發展和動向。
1991年，L.Davis編輯出版了《遺傳演算法手冊》（Handbook of Genetic Algorithms），其中包括了遺傳演算法在工程技術和社會生活中的大量應用實例。
1992年，Koza發表了他的專著《遺傳程序設計:基於自然選擇法則的計算機程序設計》」。1994年，他又出版了《遺傳程序設計，第二冊:可重用程序的自動發現》深化了遺傳程序設計的研究，使程序設計自動化展現了新局面。有關遺傳演算法的學術論文也不斷在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machines》\《IEEE Transactions on Neural Networks》,《IEEE Transactions on Signal Processing》等雜志上發表。1993年，MIT出版社創刊了新雜志《Evolutionary Computation》。1997年，IEEE又創刊了《Transactions on Evolutionary Computation》。《Advanced Computational Intelligence》雜志即將發刊，由模糊集合創始人L.A.Zadeh教授為名譽主編。目前，關於遺傳演算法研究的熱潮仍在持續，越來越多的從事不同領域的研究人員已經或正在置身於有關遺傳演算法的研究或應用之中。