量子退火

维基百科,自由的百科全书
跳到导航 跳到搜索

量子退火(英語:Quantum annealing )是一種量子漲落特性的次經驗演算法英语Metaheuristic,可以在目標函數擁有多組候選解答的情況下,找到全局最優解。量子退火主要用於解決離散空間有多個局部最小值的問題(組合優化問題),例如尋找自旋玻璃的基態。[1]

量子退火首先從權重相同的所有可能狀態(候選狀態)的量子疊加態開始運行,接著物理系統依含時薛丁格方程開始量子演化。根據橫向場的時間依賴強度,狀態之間產生量子穿隧,使得所有候選狀態的機率幅不斷改變,實現量子並行性。若橫向場的變化速度足夠慢,則系統會保持在接近瞬時哈密頓量的基態,此即為絕熱量子計算英语Adiabatic quantum computation。若橫場的變化速度加快,則系統可能會暫時離開基態,而最終問題哈密頓量的基態將會增加更多的可能性,此即非絕熱量子計算(diabatic quantum computation)。橫向場最終被關閉,並且預期系統已得到原優化問題的解,也就是到達相對應的經典易辛模型基態。在最初的理論被提出之後,隨即有了隨機磁體量子退火成功的實驗證明。在一篇關於組合優化(NP困難)問題的介紹中,[2]列入了基於量子退火演算法的一般結構,用於求解max-SAT,最小multicut問題這類演算法的兩個實例,以及D-Wave 系统公司所製造的量子退火系統產品。

與模擬退火法比較[编辑]

模擬退火法的“溫度”參數可以類比量子退火的“隧道場強度”。 在模擬退火中,溫度決定了從單一當前狀態轉移到較高“能量”狀態的概率。 在量子退火中,橫向場的強度決定了改變所有並行狀態機率幅的量子力學機率。 分析和數值證據表明量子退火在某些條件下優於模擬退火。

類比與優勢[编辑]

Quant-annl.jpg

隧道場基本上是一個動能項,它不與原始玻璃的經典勢能部分交換。整個過程可以利用量子蒙地卡羅英语Quantum_Monte_Carlo(或其他隨機技術)在計算機上進行模擬,從而得到尋找經典玻璃基態的啟發式算法。

在對純數學目標函數退火的例子中,可以將這個問題中的變量考慮為經典自由度,而代價函數(損失函數)則對應勢能函數(經典哈密頓函數)。然後在哈密頓量中人為引入非交換變量(與原始數學問題變量擁有非零交換子的變量)組成的合適項,以發揮隧道場(動力學部分)的作用。這樣就可以用前面構造出的量子哈密頓量(原始函數+非交換部分)進行模擬。退火的效率將取決於選擇的非交換項。

在實驗和理論上已經證明,在某些情況下,尤其在較淺的局部極小值被非常高但很薄的勢壘(成本)圍繞的例子中,量子退火確實優於熱退火(模擬退火)[來源請求]。因為熱躍遷概率(正比於為溫度,波茲曼常數)僅相依於能障高度,對於非常高的能障,熱波動很難使系統從這樣的局部最小值出來,然而在1989年Ray、Chakrabarti和Chakrabarti提出,對相同能障的量子穿隧機率不僅取決於勢壘的高度,還取決於它的寬度,機率大約為為穿隧場。若勢壘夠窄(即),則量子波動肯定會使系統脫離淺局部最小值,對於自旋玻璃,正比於,對於橫向場的線性退火,可以得到退火時間正比於 (不同於熱退火, 正比於 ),甚至在 減少快於等於 的情形下,變成與無關的。

據推測,在量子計算機中,這種模擬比傳統計算機更精確有效,因為它可以直接執行穿隧而不需手動添加。 此外,因為沒有用到傳統量子算法中所用的量子糾纏,它可在不這麼嚴格的錯誤控制下完成工作。

D-Wave實現[编辑]

參見:D-Wave 系统公司

参见[编辑]

參考資料[编辑]

  1. ^ P Ray, BK Chakrabarti, A Chakrabarti. Sherrington–Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations. Phys. Rev. B 39, 11828 (1989). 
  2. ^ S.E. Venegas-Andraca, W. Cruz-Santos, C. McGeoch, and M. Lanzagorta. "A cross-disciplinary introduction to quantum annealing-based algorithms". Contemporary Physics Vol. 59, Issue 02, pp. 174–196 (2018). (原始内容存档于2019-07-01). 

外部連結[编辑]