量子人工智能笔记之量子深度学习-阿里云开发者社区

这是系列文章的第一篇，主要介绍weibe 基于经典玻尔兹曼机的工作。 Quantum Deep Learning (arxiv:1412.3489)

原问题量子计算机和量子算法的出现会给机器学习领域带来什么样的变革，为什么会带来这样的变革？原理是什么？的回答以及后续更新就在这里写了。

之前有段时间在看实验实现有没有可能，找了老师讨论后来发现现在还做不了。Quantum Deep Learning 里其实是介绍的是Boltzman Machine(以后简称BM)的训练方法, 用量子的训练方法代替经典算法中的CD-k(contrastive divergence，对比散度)算法在时间复杂度上有了很好的提升, 使得大规模训练全连接的BM有了可能. 作者也在后面模拟了用这两个算法训练全连接网络。当然了, 并不能像Shor算法一样带来令人振奋的指数加速...但是这个复杂度的优化应该也是很好的了。

首先先简单介绍一下BM来凑个字数吧。BM是一种概率型神经网络，它来自于物理学中的Ising模型，是组成深度可信网络的单元。它在分类（比如用于Netflix的视频分类中有着比较好的效果 Restricted Boltzmann Machines for Collaborative Filtering）等领域里都有很好的应用。

最初利用类似于模拟退火的方法进行抽样来完成训练，它的目标是通过训练获得一种分布从而使得能量 $O_{ML}$ 最低，其中某一种状态（v，h）出现的概率为

$P(v,h) = e^{-E(v,h)}/Z$

其中

$E(v,h) = -\sum_{i} v_i b_i -\sum_{j} h_j d_j - \sum_{i,j}\omega_{i,j}^{vh}v_i h_j - \sum_{i,j}\omega_{i,j}^{v} v_i v_j -\sum_{i,j} \omega_{i,j}^{h} h_i h_j$

Z是配分函数，我们的训练目标是使得这个函数最小：

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

（v,h）代表这个系统的某个状态（每个unit的某一种赋值），这里P是某个状态出现的概率。

传统的算法是想办法或得这个梯度然后用类似于梯度下降的方法来达到极值，量子算法的思路也差不多。所以参数更新的公式就是

$\frac{\partial O_{ML}}{\partial \omega_{ij}} = \langle v_i h_j \rangle_{data} - \langle v_i h_j\rangle_{model}-\lambda \omega_{ij}$

最原始的方法是用类似于模拟Ising模型的方法（通过Gibbs抽样）来训练，但是这样的性能很差，后来有了CD-k，PCD算法。但是以上算法都因为性能原因无法非常有效地计算全连接的玻尔兹曼机。于是就有了RBM（受限玻尔兹曼机），就是将一些单元之间的连接人为地去掉，这样训练起来就快了不少。

用量子比特来表示玻尔兹曼机思路上并不复杂，因为玻尔兹曼机实际上来自于物理中的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_{v\in train}\log(\sum_{h=1}^{n_h}P(v,h))-\frac{\lambda}{2}\omega^T\omega$

但是我们的训练目标是获得这样一个量子态

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

而Nathan的算法就是给出了一种近似计算出前面这个振幅的算法。它可以被量子计算机在多项式时间内算出来。

上一次写到了经典的玻尔兹曼机。这一篇继续往下写。因为主要是定理什么的这一章感觉主要就是在翻译了，我稍微调整了一下顺序。欢迎讨论～

如何训练出目标的概率分布，也就是目标的量子态 $\sum_{v,h}\sqrt{P(v,h)}|v\rangle |h\rangle$ 呢？

首先想要直接获得 $\sum_{v,h}\sqrt{P(v,h)}|v\rangle |h\rangle$ 是很困难的，因为 $P = \frac{e^{-E(v,h)}}{Z}$ ，而下面这个Z，也就是配分函数是很难计算的（需要把可能的状态都加起来）。于是Nathan使用了平均场近似大法，来获得一个好算一些的分布函数Q，使得我们可以用其它量来近似计算目标量子态。

平均场近似是这样的(注意这里的 $v$ 和 $\upsilon$ 不是一个东西...一个是visible unit的值还有一个是平均场近似的参数)：

对分布

$Q(v,h)=(\prod_i \mu_i^{v_i}(1-\mu_i)^{1-v_i})(\prod_j \upsilon_j^{h_j}(1-\upsilon_j)^{1-h_j})$

其中 $\mu_i$ 和 $v_j$ 是使得下面这个式子（ $KL(Q||P)$ ）最小的数。参数 $\mu_i$ 和 $v_j$ 被称为平均场系数。

$\begin{aligned} KL(Q||P) &= \sum_{v,h}-Q(v,h)\ln(P(v,h))+Q(v,h)\ln(Q(v,h))\\ &=\sum_{v,h}Q(v,h)(\sum_i v_i b_i +\sum_j h_j d_j +\sum_{i,j}\omega_{i,j}v_i h_j +\ln{Z})\\ &=\sum_{i}\mu_ib_i+\sum_{j}v_jd_j+\sum_{i,j}\omega_{i,j}\mu_i v_j+\ln(Z)\\ &\quad\quad\quad + \sum_i \mu_i\ln(\mu_i)+(1-\mu_i)\ln(1-\mu_i)+\sum_{j}v_j \ln(v_j)+(1-v_j)\ln(1-v_j) \end{aligned}$

这个函数的最小值在 $\mu_i = \sigma(-b_i-\sum_j \omega_{i,j}v_j)\\ v_j = \sigma(-d_j-\sum_i \omega_{i,j}\mu_i)$

处取到

定义一

于是有了Q，我们就可以定义由Q所得到的配分函数，定义

$Z_Q := \sum_{v,h} Q(v,h)\log(\frac{e^{E(v,h)}}{Q(v,h)})$

然后对和训练集连接的节点（也就是训练数据接入的那个节点），有

$Z_{x,Q}:=\sum_h(x,h)\log(\frac{e^{-E(x,h)}}{Q_x(x,h)})$

不过呢，为了用量子算法来通过平均场近似的分布函数Q获得真正的分布P，我们还需要知道这个配分函数带来的近似在Q中占的比例

定义二

记常数 $\kappa>0$ ，并且对所有可见和不可见的结构(configurations)(v,h)都有

$\frac{e^{-E(v,h)}}{Z_Q}\leq \kappa Q(v,h)$

同样还可以对训练集定义

定义三

记常数 $\kappa_x>0$ ，并且对所有的隐藏结构(hidden configurations) h 和 $x\in x_{train}$ 满足

$\frac{e^{-E(x,h)}}{Z_Q}\leq \kappa_x Q_x(x,h)$

从这几个定义可以推出这样几个引理，具体证明就不记了，证明也挺短的，对学物理的来说也许结论更有用一点

引理一

$P(v,h)\leq \frac{e^{-E(v,h)}}{Z_Q}\leq \kappa Q(v,h)$

引理二

玻尔兹曼机可以以 $\frac{Z}{\kappa Z_Q}$ 的概率制备出来。这个还是需要看一下证明的：

证明：

假设我们已经获得了平均场近似的参数 $\mu_i$ 和 $\upsilon _j$ 。那么就确定了平均场分布Q。通过一系列的单比特旋转，我们就可以获得这样一个量子态（Q可以用来获得P）

$|\psi_Q\rangle:= \prod_i R_y (2 \arcsin(\sqrt{\mu_i}))|0\rangle \prod_j R_y (2\arcsin(\sqrt{\upsilon_j}))|0\rangle = \sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle$

然后容易看出来

$\sum_{v,h}\sqrt{Q(v,h)\mathbf{P}(v,h)}|v\rangle|h\rangle = \sqrt{\frac{Z}{\kappa Z_Q}}\sum_{v,h}\sqrt{\frac{e^{-E(v,h)}}{Z}}|v\rangle|h\rangle=\sqrt{\frac{Z}{\kappa Z_Q}}\sum_{v,h}\sqrt{\mathbf{P}(v,h)}|v\rangle |h\rangle$

下面就剩下用rejection sampling (应该翻译成拒绝抽样？)，记(知乎上没找到打花体P的命令mathscr不能用的说，用加粗代替了...)

$\mathbf{P}(v,h) := \frac{e^{-E(v,h)}}{\kappa Z_Q Q(v,h)}$

因为 $Q$ 和 $Z_Q$ 都能被有效计算出来（参看前面，在量子计算机里都不是指数增长的操作数），所以这里的 $\mathbf{P}$ 也能被有效地计算出来。并且引理一也保证了 $0\leq \mathbf{P}(v,h)\leq 1$ 。然后思路大致就是增加一个辅助比特和一个寄存比特，假如能有 $\sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|\mathbf{P}(v,h)\rangle|0\rangle$ 那么就可以通过对最后的辅助比特做一个控制旋转操作（类似于CNOT的一个东西），就能得到

$\sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|\mathbf{P}(v,h)\rangle|0\rangle\rightarrow \sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|\mathbf{P}(v,h)\rangle(\sqrt{1-\mathbf{P}(v,h)}|0\rangle+\sqrt{\mathbf{P}(v,h)}|1\rangle)$

而后面那个东西就是我们要的东西咯，于是对辅助比特进行测量，扔掉结果为0的量子态，就可以获得目标的量子态了。而这个的成功概率就是 $\frac{Z}{\kappa Z_Q}$

然后类似地，我们也知道了如何获得(x,h)的玻尔兹曼机的目标量子态。

铺垫差不多结束了，下面是写具体的算法。

我们来看数据是具体怎么参与到它的训练中去的。这一章也有不少部分会翻译自Nathan的原始文献，如果觉得翻译的不好可以去读一下原文，然后给我留言。我会学习一下然后修改的，因为伪代码里有公式，并不能用知乎的代码格式，所以手机显示可能没有源码代码里的对齐。。。

第一个算法是生成model state的算法

首先平均场近似的系数可以通过前面的方法算出来（参见平均场近似），然后就有Q：

$Q(v,h)=(\prod_i \mu_i^{v_i}(1-\mu_i)^{1-v_i})(\prod_j \upsilon_j^{h_j}(1-\upsilon_j)^{1-h_j})$

这样我们就可以计算引理里的 $Z_Q$ 。下面是获得模型态的伪代码：

# 输入是几个玻尔兹曼机的基本参数，模型的权重矩阵是omega,可见单元偏移(biases) b，隐藏单元的偏移 d，边集合E，和 $\kappa$
function qGenModelState( $\omega$ ,b,d,E, $\kappa$ )

# 通过输入的参数来计算平均场的系数
mu, v = gen_meanfield_para()
# 计算平均场近似后的配分函数
Z_Q = meanfield_partition(mu,v)
# 制备初态

$\sum_{v,h} \sqrt{Q(v,h)}|v\rangle|h\rangle := (\prod_{i=1}^{n_v} e^{-i\sqrt{\mu_i} Y}|0\rangle)(\prod_{j=1}^{n_h}e^{-i\sqrt{v_j}Y}|0\rangle)$

# 添加寄存比特用来寄存能量值，并且初始化为 0

$\sum_{v,h} \sqrt{Q(v,h)} |v\rangle |h\rangle \rightarrow \sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle |0\rangle$

# 后面一系列循环都是为了将来通过测量辅助比特来获得我们在引理里提到的要获得的玻尔 # 兹曼机态，注意他是怎么把概率幅给导出一个带有配分函数的形式的，最后要用到前文提 # 到的控制旋转，参见量子深度学习笔记（二）或者原文的Lemma 2，这里的辅助比特也 # 需要不止一个，所以实验上就很难做了

for i = 1 : $n_v$

$\sum_{v,h} \sqrt{Q(v,h)} |v\rangle |h\rangle |E(v,h)\rangle \rightarrow \sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle |E(v,h)+v_i b_i +\ln (\mu_i^{v_i} (1-\mu_{i})^{1-v_i})\rangle$

end

for j = 1: $n_h$

$\sum_{v,h} \sqrt{Q(v,h)}|v\rangle|h\rangle|E(v,h)\rangle \rightarrow\sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle |E(v,h)+h_j d_j +\ln (\mu_i^{v_i}(1-\mu_i)^{1-h_j})\rangle$

end

for $(i,j)\in E$

$\sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle|E(v,h)\rangle\rightarrow\sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|E(v,h)+v_i h_j \omega_{i,j}\rangle$

end

# 最后总的来讲我们最后制备出了这样一个态 $\sum_{v,h}\sqrt{Q(v,h)}|v\rangle|h\rangle|E(v,h)\rangle \rightarrow \sum_{v,h}\sqrt{Q(v,h)}|v\rangle |h\rangle|E(v,h)\rangle (\sqrt{\frac{e^{-E(v,h)}}{Z_{Q}\kappa}}|1\rangle+\sqrt{1-\frac{e^{-E(v,h)}}{Z_Q\kappa}}|0\rangle)$

end

然后对data state，也是用同样的方法(把 $\kappa$ 换成 $\kappa_x$ ，可见单元的值用ｘ代替即可)，我们叫这个函数为　qGenDataState

然后我们知道，梯度是这么算的：

$\frac{\partial O_{ML}}{\partial \omega_{i,j}} = \langle v_ih_j\rangle_{data}-\langle v_ih_j\rangle_{model}-\lambda\omega_{i,j}$

注意这个式子和经典的玻尔兹曼机完全一样，套用就好了，所以我们最终的训练算法是这样的

for i = 1:N_train

success = 0

while success = 0

$|\psi\rangle$ = qGenModelState( $\omega$ ,b,d,E, $\kappa$ )

# 测量辅助比特

success = measure_ancilla_qubit( $|\psi\rangle$ )

　end

modelVUnits[i] = 测量可见比特的结果

modelHUnits[i] = 测量隐藏比特的结果

success = 0

while success = 0

$|\psi\rangle$ = qGenDataState( $\omega$ ,b,d,E, $\kappa$ ,x[i])

success = measure_ancilla_qubit( $|\psi\rangle$ )　＃　测量的是最后一个辅助比特，那个前面带了分布函数的

end

dataVUnits[i] = 测量可见比特的结果

dataHUnit[i] ＝　测量隐藏比特的结果

end

最后逐个计算梯度

for (i,j) in v,h # 对每个可见和隐藏节点

gradMLw[i,j] = $r(\frac{1}{N_{train}}\sum_{k=1}^{N_{train}} (dataVUnits[k,i]dataHUnits[k,j]-modelVUnits[k,i]modelVUnits[k,i]modelHUnits[k,j]-\lambda\omega_{i,j})$