量子計算機和量子演算法的出現會給機器學習領域帶來什麼樣的變革，為什麼會帶來這樣的變革？原理是什麼？

12-31

一直以來對量子計算和機器學習很感興趣，但是不知道這兩者之間能有什麼聯繫，總聽到人們說量子演算法與機器學習特別的情投意合，人們這樣說有什麼依據了？

首先, 量子計算機能不能給機器學習帶來巨大變革很難說. 量子計算機帶來的更多的是計算能力的提升, 而個人認為機器學習的變革還應該在於模仿人類的學習過程. (不是相關專業的, 能明白我的意思就好...) 現在的量子機器學習離應用還很遠. 沒有較好的加速或者是還不好造出來(qubit數目要求比較高)的toy model當然, 隨著實驗進展越來越快, 這個方向也會有越來越多的人感興趣. 恩，不過量子信息是否能給人工智慧帶來實質性的突破，感覺還很不好說。具體怎樣，我們具體看看就好了。

量子力學會和機器學習有比較深刻的關係. 比如 @Summer Clover 可能可以介紹一些關於如何用量子力學優化經典(相對量子的)演算法的內容?

我開始學習相關的文獻時間不長, 關於量子神經網路, 這個概念很早就有了, 我在這裡以及我的blog（Roger Luo"s Citadel）不定期地更一些我讀過的文章，來介紹一下量子機器學習，然後也算是順便記筆記了，還不太習慣知乎的打公式的功能，所以具體的式子和推倒可能會先在blog上出現。結構和順序也許後面會有調整，如果有修改意見以及問題可以評論or私信我。

最近主要看的是神經網路的，所以先更神經網路相關的部分。

大致打算從Nathan Weibe的深度學習往前介紹到量子神經網路（On the quantum neutral network）

1. Quantum Deep Learning (arxiv:1412.3489)

之前先更在blog了，有具體的演算法介紹，可能還有點亂（量子深度學習筆記/Notes on quantum deep learning）

Quantum Deep Learning 里其實是介紹的是Boltzman Machine(以後簡稱BM)的訓練方法, 用量子的訓練方法代替經典演算法中的CD-k(contrastive divergence，對比散度)演算法在時間複雜度上有了很好的提升, 使得大規模訓練全連接的BM有了可能. 作者也在後面模擬了用這兩個演算法訓練全連接網路。當然了, 並不能像Shor演算法一樣帶來令人振奮的指數加速...但是這個複雜度的優化應該也是很好的了。

首先先簡單介紹一下BM來湊個字數吧。玻爾茲曼機是一種概率型神經網路，它的目標是使得這個函數最小

$O_{ML} := frac{1}{N_{train}}sum_{vin train}log(sum_{h=1}^{n_h}P(v,h))-frac{lambda}{2}omega^Tomega$

（v,h）代表這個系統的某個狀態（每個unit的某一種賦值），這裡P是某個狀態出現的概率。

傳統的演算法是想辦法或得這個梯度然後用類似於梯度下降的方法來達到極值，量子演算法的思路也差不多。用量子比特來表示玻爾茲曼機思路上並不複雜，因為玻爾茲曼機實際上來自於物理中的Ising模型，所以利用本身就是以一定概率出現0和1的量子比特來表示玻爾茲曼機的單元（unit）是再合適不過的了。

然後從Nathan的文章里盜個表出來, 看看到底優化到什麼程度吧.

解釋一下, 那個 $epsilon$ 和精度相關. $n_h$ 是指hidden unit的個數, $n_v$ 是指visible unit的個數， $l$ 是網路的層數，E是邊的數目. 這個演算法並沒有改BM的結構, 只是加速了訓練方法. 當然這個東西還跑不起來, 比特數要求有點高. 以後實驗上就很難做了。

這個演算法是在最原始的BM訓練方法Gibbs抽樣的基礎上改進的，並且CEQS和CEQAE兩種演算法都是exact的。也就是誤差（error）的來源只有抽樣（sampling），對比特數目和物理資源的需求也沒有出現指數增長。比較吸引人的一點可能在於演算法本身的時間複雜度與層數無關（沒有 $l$ ），所以在用來訓練深層網路的時候表現可能會很好，而常用的CD-k演算法的時間複雜度會隨著網路層數上升。當然目前這個演算法離實驗實現還很遠，比特數目還不夠用。

為什麼說沒有改變BM的結構呢。因為要優化的函數沒變還是上面的這個函數

$O_{ML} := frac{1}{N_{train}}sum_{vin train}log(sum_{h=1}^{n_h}P(v,h))-frac{lambda}{2}omega^Tomega$

但是我們的訓練目標是獲得這樣一個量子態

$sum_{v,h}sqrt{P(v,h)}|v angle|h angle$

而Nathan的演算法就是給出了一種近似計算出前面這個振幅的演算法。它可以被量子計算機在多項式時間內算出來。

待續的在專欄里寫了，就這樣哈，瞄～

更新一下, IQC 今年有篇很不錯的科普: Quantum Computational Intelligence

https://uwaterloo.ca/institute-for-quantum-computing/blog/post/quantum-computational-intelligence

----------------------------------------------------------

簡單的了解過一些, 我試著說說我知道的.

這兩年說比較多的大多是基於 HHL 演算法(Harrow et al, 2009; 求解稀疏, well-conditioned 矩陣的線性方程組), 作為過程或者基本思想, 應用到基於多元統計分析的一些現有的機器學習演算法上的結果(如 QPCA 和 QSVM). 比較全面的綜述可以看 Scott Aaronson 年初這篇(nature.com 的頁面), 講了 HHL 演算法的一些應用, 除了 Quantum Machine Learning 還有解 ODE/PDE 之類的. 這個回答涉及了一些這篇綜述的內容: 量子技術會給模擬電路帶來哪些進步？ - Climber.pi 的回答. 不過想看具體細節的話還是去看 HHL 的原始論文吧.

當然也有一些演示實驗, 比如: 如何解讀「量子計算應對大數據挑戰：中國科大首次實現量子機器學習演算法」？ - 中國科學技術大學. 可惜的是, 聽說主持這項工作的 phd(從 HHL 演算法解二元線性方程組, 到 QSVM 的演示實驗), 畢業之後轉行了.

除此之外, Microsoft Research QuArC Group 有一系列相關工作(比如那篇 Quantum Deep Learning), 可以看看 Nathon Wiebe 在 Waterloo IQC 的 talk (youtube 上有). 下面是年初 ASCR Workshop on Quantum Computing for Science 裡面 Nathon Wiebe 的一張 slide.

最近還有用以改進經典機器學習演算法的工作, 可以看看 QuArC Group 的主頁(Quantum Architectures and Computation (QuArC)).至於量子神經網路, 印象中是很早以前就有人在討論的東西. 個人並不是十分清楚和現在的 Quantum Deep Learning 的聯繫.

題主可以去看看量子神經網路

現在量子計算的物理基礎還不夠，所以quantum learning還只是在想像階段。

說上一些不負責的話吧，或許引入量子機制之後機器學習會有一些意向不到的效果，雖然不應該會是突破性的進展。比如會有一些違反常識的結論，類似於quantum random walk。

而在模擬經典學習的過程，會有一個明顯的提速。

題主說量子計算與機器學習契合，有來源么？

估計是因為量子計算是一種並行計算吧

要是真的有量子計算機，一切都是人工智慧，根本就是自由社會了，怎麼還需要被資本家剝削的碼農呢？談何機器學習？