隨機生成的“MAX-SAT”實例圖展示了隨著問題密度的增加，固定深度的QAOA電路性能（即QAOA最優值和精確最優值之間的差異）的變化趨勢。雖然深度越高，實現的性能就越好，但是它們仍然表現出“可達性缺陷”。
美國谷歌公司（Google）正在全力開發量子增強處理器，希望在未來用量子力學效應顯著加快數據處理速度。最近，谷歌已經設計出了新的量子增強算法，它可以在真實的噪聲環境中運行。 “量子近似優化算法”（簡稱QAOA），是推動現代抗噪量子增強算法發展的基石。谷歌在QAOA上採用的著名方法已經在市場中引發了熱烈反響，點燃了全球科研機構開發新穎應用途徑的熱情。然而，對於QAOA算法的最終性能限制，我們還所知甚少。
據美國“優睿科”網站3月5日消息稱，俄羅斯斯科爾科沃科技學院（SkolTech）的深量子實驗室的科學家們接受了這一當代挑戰。這個由Jacob Biamonte教授領導的團隊不僅發現了谷歌廣泛採用方法的一個基本限制，還對其進行了量化。在《物理評論快報》刊發的一篇報道文章中，該團隊詳細描述了他們發現的“可達性缺陷”，並展示了這些缺陷如何對QAOA的能力造成根本性限制。
具體說來，該團隊的研究成果，是發現了變分QAOA量子算法的明顯侷限性。科學家已經證明，基於“量子—經典”的內部反饋過程，運用已知的數學技術來分析QAOA和其他變分量子算法是非常困難的。也就是說，一個給定的量子運算任務只能在某段固定的時間內運行。在這個固定的時間段內，可以執行固定數量的量子操作。QAOA試圖通過形成一個不斷優化的近似序列來迭代地利用這些量子運算，以求最小化某個目標函數。這項研究對這一過程提出了新的限制條件。
研究人員發現，對於任何固定的深度量子電路，QAOA形成近似最優解的能力在根本上依賴於問題的“密度”。在被稱為“MAX-SAT”的問題中，密度可以定義為問題約束條件個數與變量個數之比，這有時被稱為“子句密度”。研究結果顯示，對於高密度的問題實例，無論算法的運行時間長短如何，其最優解決方案都無法保證接近成功。
編譯：朱明逸 審稿：西莫 責編：雷鑫宇
期刊編號： 0031-9007
原文鏈接： https://www.eurekalert.org/pub_releases/2020-03/sios-ssb030520.php
閱讀更多 科技工作者 的文章
