量子退火

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

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

與模擬退火法比較[編輯]

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

模擬與優勢[編輯]

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

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

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