如何理解「量子退火」？

11-16

一切緣起這篇研究前沿報道 Analogue quantum computers: Still wishful thinking? -- ScienceDaily。
文中說，quantum annealing是一種對量子計算機的模擬。

由於本人對量子計算機的理解僅僅停留在：「這種計算機是基於可以表示介於0和1兩種絕對狀態中間的不確定狀態的量子粒子做成的」，因此無法理解這句話，而這是看懂這篇報道的一個關鍵知識，因此我基本上沒有理解這篇報道的意義。
一番Google + Bing + Sogou （我用Hosts牆了百度）之後，我知道了quantum annealing是量子退火的意思，但退火不是中醫裡面的概念么？？？

希望有人能用通俗的話解釋（1）量子退火的定義，意義，最好用D-wave的例子加以說明（2）為什麼這個概念跟退火會產生關係。

不邀自來，見識淺薄，還請諸位大神指正。

量子退火法，是一種基於量子特性的量子計算機演算法，脫胎於經典計算機上的模擬退火演算法。實際上，模擬退火演算法的步驟和思路，與金屬的退火確實有著異曲同工的妙處。

將金屬加溫到某個高於再結晶溫度的一點並維持此溫度一段時間，再將其緩慢冷卻。
—— 退火 - Wikipedia

關於通用量子計算機的原理和特性，可以參見我的另一個回答：量子計算機有什麼實際的應用意義？ - Cheny Dimpurr 的回答

作為量子退火機應用較多的一種特性，再補充一種神秘的「量子隧道效應」。這種效應一般來說，指的是微觀粒子有一定紀律穿過穿過不可能穿越的壁障，出現在壁障的另一端的情況。因為一個微觀量子並不存在一個精確的位置，而是以一定概率分布在一片區域，化學上的電子云概念就是這樣的。

假設容器的邊緣有一個粒子，藍色的深淺標出了它的德布羅意波，即它可能出現的位置的可能性大小。可以注意到，在很小的幾率下，這個粒子會出現在容器的對面。不是漏出，也不是穿過，而是瞬移！但是這也不是瞬移，因為對於電子來說，它本來就有可能出現在那裡，只是在你觀測的時候，本來存在於一定範圍的電子忽然給出了一個正好的容器外的位置。

首先，我們先來看看我們都熟悉的一種貪心演算法，爬山演算法。
爬山演算法指的是以以一個任意值為起始點，計算臨近的解，然後不斷判斷這個解和符合條件的差距，選擇選擇更適合的方向繼續計算，直到達到一個任意方向都是更劣解的位置。

來看看這幅圖。假設藍線的位置就是正解的位置。
首先，一個登山者（計算機）從 FE 段的任意一處出發。對他來說，向下走無疑是更接近正解的。只不過，當他走到了山谷，也就是 E 點時，他會發現：此時無論他往哪邊走，都會距離谷底更遠！
我們的爬山者被困在山谷底，或者說「勢阱」了。

至於模擬退火法，引入了一個隨機的擾動，也就是溫度 T 。
我們可以這樣來概括它的步驟：

在值域內，按照隨機擾動 Δ ，產生一個一定範圍距離的新解
判斷新解和正解的距離，與當前解與新解的距離進行比較
如果可以接受，那麼在當前 T 的範圍內，有一定可能性改用新解
當確定正解在某個區間以內時，縮小範圍繼續應用模擬退火演算法

實際上，就模擬退火演算法的具體實現來說這個概括不是很準確。不過這樣一來，就可以看出它和爬山演算法的最大區別：我們的登山者一次被困在山谷 E 時，他可以選擇瞬移到 DC 段的某處，並且驚喜的發現這裡更接近正解！在對「整座山」通過統計學方法「退火」時，他就會發現最接近正解的區間 BCD ，從而集中精力在 C 處尋找精確解了。
退火法還有很多有趣的性質，比如初溫 T 越高，得到正解的概率也越高，因為此時計算機會更勇敢的選擇新解，相當於退火的更徹底。相應的，要達到對「整座山」鎖定目標需要的耗時就越長。這個問題，量子退火中就可以得到改善。

那麼，這次我們的登山者不同尋常，是一位量子登山者。

看到這幅圖也許已經有人明白了：此時這個登山者不僅處在 DE 段上的某一點，其實他「同時」存在於這四周的一大塊區域！在它的可能性範圍所能觸及的區域，他發現了 CD 段上有著更低的一點。利用量子隧道，我們的登山者逃出了山谷！
還不僅僅如此。我們還記得在模擬退火法的第一步上，我們提到了我們會從圖像（山脈）的某處開始搜索。但是，因為量子的疊加性質，我們的量子計算元件可以同時處在圖中的很多個位置！這樣以來，搜索的效率可以以（2 的）指數性增長！

這樣優秀（當然，適合處理的問題有所局限）的演算法，讓我們來看看這個龐然大物， D-Wave Two 是怎麼實現的。
首先，在合適的環境下，製備好一系列量子比特。 D-Wave Two 擁有 128 個量子比特。
接著，為這些量子設置好三維的伊辛模型，也就是設置好他們的初始位置和自旋狀態。這個初始模型就決定了接下來的計算，可以說就是編好的程序。
隨後，減弱量子間的相互作用，通過向超導電路通入特殊電流，向設置好的模型施加一個橫磁場。這種情況下，量子就進入了自旋的疊加狀態，相當於同時具有 0 和 1 狀態的比特。
最終，我們進行「退火」。我們慢慢撤去橫磁場，增強相互作用，最終，量子們穩定下來，我們得出了最終解。

就像別的答案中提到的，量子退火機就是讓大自然自己去進行計算，我們等著看結果：最終穩定下來的量子，一定是在這個三維伊辛模型中，相互間能量很小的狀態。意即只要模型設置得當，我們就有非常大的機率落到最低的「山谷」當中。
因為演算法本身基於統計學而非遍歷的性質，我們可以理解，即使量子退火演算法在模擬退火演算法的基礎上提高了算力，還是有隻得出近似解的情況存在。因此， D-Wave Two 據說會針對每次計算任務重複 4000 次，選擇其中的最優解得出解答。

最終，和大家預想的不一樣， Dwave Two 確實「只是」一台量子退火機。在吭哧吭哧工作時，還得全程由液氮保護運行在 0.02 K，也就是 -273.13 ℃ 下。不過，相比經典計算機，量子退火機還是在特定領域達到了上萬甚至上億倍的算力提升。我們可以期待，一個真正的通用量子計算機，將會給科技行業乃至人類智慧帶來極大的革命。

我覺得@summer clover答的很好了，但是圈外人士可能還是難以理解，所以我舉個比較直觀但是不太正確也不太全面的例子補充一下。
假設我們需要計算一枚炮彈的軌跡求出能否命中目標，我們有兩種辦法，
一種是寫出各種方程，考慮推力阻力引力自轉等等，然後求解方程，得到運動軌跡。這就是現在用計算機做的事情。
另一種奇妙的方法是，我造一個1比1000的微縮模型，控制好模型里的推力風速等等，砰的一聲打一個迷你炮彈出去，直接用尺子量出落點。這就叫做「讓大自然自然演化，給我們計算結果」。
量子退火，就是類似第二種的方法。

謝邀。

1）Introduction
Dwave是目前唯一的商業量子計算機，也是目前最有前景的量子計算機。
雖然本質上，它是量子退火機（quantum annealing machine）。

Quantum annealing is a method to solve combinatorial optimzation problems and was proposed by Kadowaki and Nishimori in 1998. Many problems in machine learning and artificial intelligence can be formulated as combinatorial optimization, and the development of efficient algorithms to solve combinatorial optimization problems has enormous practical significance.

退火的意思和模擬退火演算法一樣。「模擬退火」演算法是源於對熱力學中退火過程的模擬，在某一給定初溫下，通過緩慢下降溫度參數，使演算法能夠在多項式時間內給出一個近似最優解。

量子退火演算法則是量子力學的絕熱演化過程，模擬了量子力學裡的量子隧穿效應。通過讓量子效應緩慢下降（絕熱演化），找到一個解。
系統從一個初態絕熱演化到基態。初態和基態需要Dwave來構造。初態隨意早，末態（也就是基態）對應機器學習的costfunction。
不明白絕熱演化的人可以簡單地將其理解為「慢慢演化」。

Dwave是量子退火機。量子退火機和【「這種計算機是基於可以表示介於0和1兩種絕對狀態中間的不確定狀態的量子粒子做成的」】這種基於邏輯門的標準量子計算機基本上沒有什麼關係。
量子退火是基於絕熱量子計算的。我們不需要操作量子邏輯門。但是，絕熱量子計算其實等價於標準量子計算。
【Aharonov D, Van Dam W, Kempe J, et al. Adiabatic quantum computation is equivalent to standard quantum computation[J]. SIAM review, 2008, 50(4): 755-787.】

2）物理過程

最初，量子擾動非常強，解的概率分布幾乎是均勻的。然後，演化開始，量子擾動（quantum fluctuation）減小，cost function開始主導。最後，量子擾動徹底結束，解落到（近似）最優點。計算結束。

所以，Dwave就是用來構造costfunction和量子擾動的。

Dwave的晶元就長這個樣子。Dwave其實就是按著伊辛模型（Ising Model）來構造。

Dwave晶元的哈密頓量如上。Gama會隨時間變化。

Dwave晶元的哈密頓量如上。Gama會隨時間變化。
每一個比特用超導環電流方向來模擬。所以工作溫度要求20mk。
順時針/逆時針就是+1/-1。這和電子的自旋很類似。所以是Dwave晶元里沒有什麼0和1的任意疊加。
連接兩個比特的黑線就是哈密頓量里的Jij，是我們可以設定的參數。由於技術原因，每一個比特只能連接相鄰的比特。而理想情況下應該是任意兩個比特都能相互作用。

3）小結
實際上Dwave優勢在於，我們不去管該怎麼計算。我們知道大自然的計算結果總是對的。
我們構造一個物理系統去表示某個機器學習的costfunction。
我們只要求這個系統末態對應costfunction。我們給出這個系統，大自然自己就知道這個系統該怎麼演化。

簡單來說就是，讓大自然自己去進行計算，我們等著看結果...
而這麼詭異的計算方式居然是和量子邏輯門計算機等價的。

當然經典計算機也可以模擬量子退火演算法，但是計算複雜度太高了。

看了上面各位前輩的比較專業的回答，我感觸良多。鼓掌~贊同~感謝~
但是……Dwave原理的解釋似乎沒法「讓一個妹抖都能理解」……這裡請允許我抖（不止一）個機靈……獻上我的處女答（處女抖）——輔助只接受過高中數學訓練的妹抖們理解其猴版的本質。為啥？因為我是賣萌專業的。

——背景介紹，跳過不影響愉悅感——

可能關注M67前輩的人會看過一篇日誌，講的是姐夫·踏波（Jeff Tupper,百度這個名字的話，前面兩個鏈接都應該是你需要的）的「自我涉指不等式」——一個不等式的圖像畫出來正好是它自己。這裡，Jeff Tupper在同一篇論文里詳細論述了所謂的「Tupper區間演算法」。其數學基礎是「區間算術」（進一步了解，參考wiki:區間）。

——背景介紹結束——

這裡的區間，和數學中的區間概念上沒有大差別，開、閉、寬度都有，有時用來做誤差分析，指結果可能出現在這個區間里，且沒法精確地確定下來是哪一個點。

看到這裡，你有啥觸動沒？對於這種區域里的不確定性？……沒有也沒有問題。電子云——電子在原子核周圍的空間中被「抹開」的結果，不考慮其概率大小變化，就目測來說，正像是一個電子運動的區間（這個區間實際上是無限大的啦）。

我們聯繫生活實際（？）建立了一個簡單的模型，把量子現象看作是區間里的不確定性，問題就簡單了。所謂「量子退火」，就是把「解區間」利用量子現象從大縮小，直到「收斂」為一個滿足精確度要求的解。

來，用Jeff Tupper論文里出現過的畫圖神器GrafEq來畫個圖看看你就對退火有了直觀的感受了。

我們來方程繪製 $xcdot ycdot sinx=cosx^{y}$ 的圖像（選這個方程沒有其他意思，純屬是為了拉長繪圖時間，好讓我截圖……）。

剛開始程序關於這個方程的解一無所知，那麼方程的解的「概率雲」遍布整個平面。如下。

接著，程序開始讓解「退火」，捨去不可能的解區間，標為白色，留下可能有解存在的區間，標成漂亮的淺藍色。如下。

等待一段時間，我們就能拿到比較準確的圖像。你可以看到，解的概率雲縮小到比較小的區間里了。這個時候，還是淺藍色的區間表示這個區間中有方程的解，就是不知道精確的值是多少。但是已經能讓人把握方程的大致圖像了。如下。

於是，我們繼續做個類比：量子退火里的「大自然」，在這裡就成了被作圖的方程 $xcdot ycdot sinx=cosx^{y}$ ；最後確定的方程的近似圖像（方程解的所在區間），就成了量子退火演算法中得到的最優解。

結束啦。
*各位沒有對這個動態過程的直觀感受的話，可以去下GrafEq自己動手畫一畫。

**各位前輩看到這裡，應該已經聯想起級數收斂或波函數的坍縮了吧……我反正是被量子退火和區間演算法萌到了。

**發現了不足之處，求馬上指出啊……我是賣萌專業的，不是物理專業……難免會有錯誤……

好比用拉線繩的方式替代Dijkstra演算法求最短路徑或用模擬電路解微分方程。

我就說一點我懂的，我不知道中醫里退火是怎麼翻譯成英文的，但是，一般annealing是理解成在材料專業里的退火。至於這個退火的意思，是一種熱處理的方式，詳見退火（金屬熱處理工藝）
所以，這個退火確實和中醫沒關係。

推薦一本書吧：

量子コンピュータが人工知能を加速する

量子コンピュータが人工知能を加速する | 西森秀稔, 大関真之 |本 | 通販 | Amazon

看了這些答案感覺「退火」這個詞還是理解起來有歧義
中醫的退火或者降火出現得更普遍
在翻譯的過程中，可能也實在找不到合適的詞來代表這個意思了。
annealing ：
heat (metal or glass) and allow it to cool slowly, in order to remove internal stresses and toughen it.（退火工藝，金屬或者玻璃加熱到一定程度後緩慢降溫從而實現內部結構的細微調整）
recombine (DNA) in the double-stranded form following separation by heat.（雙鏈DNA加熱裂解後重新組裝恢復雙鏈結構）
從這個叫角度來看，annealing側重的是一個局部拆開重構的過程。如果要從字面意思能夠理解量子退火計算的話，可以翻譯為量子局部修復計算或者量子局部重構計算。

結合@Cheny Dimpurr 的答案，讓我作為圈外人士來試著解釋一下，雖然不保證一定準確，但應該更容易理解。

想像我們有一個任務，就是去測量一座大座山脈的最低坐標（高度）。

先按傳統方式，我們坐直升機，到了山脈上空，空投一個測量師，他降落後，遍歷整座山脈的山谷，然後得出一個結論，顯然這種方式邏輯簡單，效果明確，但工作量很大，效率很低，要想在短時間內知道答案就算是閃電俠也會累的吐血。

現在，讓我們用量子方式來試試，首先，我們得明白什麼是量子，量子不是一個單一的質點，可以理解為一個質點同時出現在不同位置概率的集合，就好比孫悟空一拔毛，吹出N個分身，處於不同位置，個個都能打，所有分身在邏輯上構成一個量子。

好了，現在讓這個孫猴子去做測量師，我們把它從直升機上扔下去，就相當於同時扔下了N個孫猴子，每一個猴子都可能隨機降落在不同的山谷里，然後報告自己的位置，那麼我們只要取其中一個最低值就是我們想要的結果。

現在，我們可以理解量子計算為什麼快了吧，但還剩一個理解障礙，那就是為什麼每一個分身就那麼SB，扔到哪裡就只報告自身位置，而不會像傳統測量師那樣到處走走，報告更多結果呢？

這就是量子世界與質點世界的區別，作為觀察者，我們人類活在一個質點構成的世界裡，量子只是活在我們的理論世界裡，我們只能看到這個理論世界給質點（客觀）世界帶來的結果，但我們無法進入量子（理論）世界操控量子世界裡反應過程。

這種不可操控性就像是你把一把燒紅的劍扔進冷水裡淬火，我們只看到劍作為質體，它剛性提高了，但我們無法去控制它內部晶體的反應過程（在極微觀尺度下，這種反應就是量子世界的事了），鋼鐵退火和淬火，只不過是冷卻溫度控制速度的區別，只是慣例上用了」量子退火「來形容量子計算過程。

通過控制冷卻溫度和速度，我們可以不同程度提高剛度，這種剛度其實就是量子世界反饋回來的信息，但我們不能直接從分身上獲得信息，只能通過一定的控制條件和特定的反饋信息檢測，控制孫猴子整體上去做我們想做的事，得到我們想要的答案。

所以量子計算雖然快，但也有很大的局限，除非我們能控制每一個分身，否則它無法取代傳統計算機，應用會非常的窄，如果我們能控制分身，那這又不是量子了，它的量子效應會消失，而變成傳統的質子。

給我的感覺就是，讓一塊燒紅的鐵，退到它該有的溫度。
計算機是，給你現在鐵的溫度，和周圍已知的環境溫度，讓你算出鐵應該降到什麼溫度，才是現實中鐵的正確溫度。
量子計算機是，給你現在鐵的溫度，和讓量子計算機去假設自己是任意溫度值（當然計算機是有局限的，不可能模擬出自然界的任意溫度值），然後通過這個任意溫度值和已知周圍環境溫度『作用』（作用不是代表計算，更像是一種預知，或者說是排除法，因為『正確』的溫度已經在量子計算機里，所以量子計算機只要找出這個正確的溫度值就行），從而得出，哪個溫度值才是自然鐵的溫度！

我倒覺得方法從邏輯和哲學上看，有點類比於一個看似風馬牛不相及的數學問題：「郵遞員最優路徑問題」。

一般的數學枚舉法，必須一條一條地把起點和終點之間的所有可能路徑的遍歷，最後求出這些和的最小值，即可對應最優路徑。然而，也有一種模擬方法，就是，按照原網路圖，用細線編製一個全模擬的網路，最後在起點和終點之間一拉。最優路徑就出來了，貌似大自然的選擇。整個過程中，量子退火的中終態能量最低原理，對應於細線網路物理上「最短路線一定最繃緊原理」。原來需要枚舉的所有常規態，在你拉直起始點網路的一瞬間，「坍塌了」，「退火了」。最緊繃這條要求，一瞬間就像量子糾纏處理一樣，排除了其他所有不緊繃的態，得出了最優解。

看我的這個解釋是否很適合用類比過程來理解呢？

只說一點，這裡的退火是冶金工業里的概念，

引用自百科:退火是一種金屬熱處理工藝，指的是將金屬緩慢加熱到一定溫度，保持足夠時間，然後以適宜速度冷卻。目的是降低硬度，改善切削加工性；消除殘餘應力，穩定尺寸，減少變形與裂紋傾向；細化晶粒，調整組織，消除組織缺陷。準確的說，退火是一種對材料的熱處理工藝

我的理解：如果一個問題有多個解，最優解相當於能量最低狀態（最穩定）。量子計算可以根據問題相關的參數，利用量子狀態的演化，獲得一個穩定的狀態。這個穩定狀態對應最優解。

有一種黏菌尋找最近路線有種天然直接的方法，不知道裡面有什麼道理，反正它就是找到最短的路線了。