量子深度学习笔记/Notes on quantum deep learning

2016-04-04

Nathan的这篇量子深度学习实际上是给出了两个训练玻尔兹曼机的方法.一个是CEQS,是一个基于量子抽样的梯度估计方法. 另外一个CEQAE是基于量子振幅估计的梯度估计方法.这两个算法主要是解决之前的一些算法并没有展现出很好的量子加速效应. 而在这个算法中,我们就可以看到,时间复杂度已经有一部分被变为多项式级了(相对于传统的CD-k的算法而言).

文章的出发点依然是之前研究过很多的量子玻尔兹曼机,以及从这篇文章中可以看出Nathan在去年的QIP(量子信息处理会议)上提出的训练全连接玻尔兹曼机的想法.

玻尔兹曼机

玻尔兹曼机是一种概率型的神经网络, 它的训练目标是使得能量E最低.

\[ 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 \]

然后训练的目标可以是将这个函数优化到极值:

\[ 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 \]

构造这样一个玻尔兹曼机主要的思路实际上并不复杂,用量子比特来表示处于0或者1状态的玻尔兹曼机神经元(unit),那么由于量子力学本身具有的特性,整个玻尔兹曼机就可以看做是一个量子态. 并且每一个状态都有一定的概率出现,观测后,这个量子态有可能按照制备出的概率塌缩至任一可能的玻尔兹曼机的状态.这样就恰好符合经典玻尔兹曼机的结构. 举个例子,比如可以这样表示玻尔兹曼机的某一个状态.

\[ \|0001110101\rangle\otimes\|0110101101\rangle \]

前面是visible unit的状态,后面是hidden unit的状态.而实际上整个量子态是按照某种概率分布的. 经过一些计算我们只需要制备出满足以下概率分布的量子态就可以得到某一个训练过的玻尔兹曼机.

\[ \sum_{v,h} \sqrt{Q(v,h)} \|v\rangle\|h\rangle\|P(v,h)\rangle(\sqrt{1-P(v,h)} \|0\rangle+\sqrt{P(v,h)} \|1\rangle) \]

然后作者给出了几种训练算法的时间复杂度和所需量子比特的个数.

算法 操作数 量子比特数
ML \(O(N_{training} 2^{n_v+n_k} )\) 0
CD-k \(O(N_{training} lEk)\) 0
CEQS \(O(N_{training} E(\sqrt{\kappa} +\max_{x} {\sqrt{\kappa_x} } ))\) \(O(n_h+n_v+\log{1/\epsilon} )\)
CEQAE \(O(\sqrt{N_{training} } E^2(\sqrt{\kappa} +\max_{x} {\sqrt{\kappa_x} } ))\) \(O(n_h+n_v+\log{1/\epsilon} )\)

记号:

  • Q是吉布斯分布\(P = \exp{-E} /Z\)的一个平均场近似
  • \(Q_x\)记做训练集中的样例x连接的visible unit的平均场近似

然后平均场近似的数学形式是这样的

\[ Z_Q = \sum_{v,h} Q(v,h)\log(\frac{e^{-E(v,h)} } {Q(v,h)} ) \]

这样我们就可以通过平均场近似将原先的配分函数\(Z\)近似为\(Z_Q\)

然后制备算法的伪代码是这样的:

首先通过网络的bias和连接的权重\(\omega\)确定出平均场近似的参数\(\mu\),\(v\).然后计算平均场近似后的分布函数\(Z_Q\)

制备态

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

再向其中添加寄存比特来记录能量值:\(\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\)

然后通过量子门来对每一个(第i个)visible unit进行这样的操作

\[ \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} ) \]

再对每一个(第j个)hidden unit: \[ \sum_{v,h} \sqrt{Q(v,h)} \|v\rangle\|h\rangle\|E(v,h)\rangle→\sum_{v,h} \sqrt{Q(v,h)} \|v\rangle\|h\rangle\|E(v,h)+h_jd_j+\ln(v_j^{h_j} (1-v_j)^{1-h_j} )\rangle \]

然后对于量子态的制备, 文中利用平均场近似给出了这样一个方法.

量子态的制备算法

定义 1: 记Q是吉布斯分布 \(P = \exp{-E} /Z\) 的近似就有 \[ Z_Q := \sum_{v,h} Q(v,h) \log(\frac{e^{-E(v,h)} } {Q(v,h)} ) \]

定义$Q_{x} \(是对x (\)xx_{training} $, $x_{training} $是训练的数据集)相连接的visible unit的平均场近似

\[ Z_{x,Q} := \sum_{h} Q_x(x,h)\log(\frac{e^{-E(v,h)} } {Q_x(x,h)} ) \]


为了从Q制备出P,我们需要估计出一个上界 (这里不太清楚为啥要知道一个上界?)

定义 2\(\kappa>0\)是一个对所有可能的 \((v,h)\) 都满足

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

这里\(Z_Q\)是对配分函数的一个近似


定义 3\(\kappa_x>0\) 是一个常数使得$xx_{training} $和所有的hidden unit都满足

\[ \frac{e^{-E(x,h)} } {Z_{x,Q} } \leq \kappa_x Q_{x} (x,h) \]

平均场近似

\[ Q(v,h) = (\Pi_{i} \mu_i^{v_i} (1-\mu_i)^{1-v_i} )(\Pi_j v_j^{h_j} (1-v_j)^{1-h_j} ) \]

这里\(\mu_i\)\(v_j\)是使得\(KL(Q\|\|P)\)最小的平均场参数.

\[ \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} \mu_i v_j +\ln(Z)) + Q(v,h)\ln(Q(v,h))\\\\ &= \sum_{i} \mu_i b_i +\sum_j v_j d_j +\sum_{i,j} \omega_{i,j} \mu_i v_j +\ln(Z)\\\\ &+\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} \]

\(KL(Q\|\|P)\)进行微分后,可以求得其取最小值时,\(\mu_i\)\(v_j\)的取值:

\[ \begin{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) \end{aligned} \]

这里\(\sigma(x) = 1/(1+\exp(-x))\)

实际上就有

\[ \log(Z_Q) = \log(Z) - KL(Q||P) \]


推论 1 对所有的hidden unit和visible unit都有

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

证明:

平均场近似可以用来估计配分函数的下界, 由Jensen不等式

\[ \log(Z) = \log(\sum_{v,h} \frac{Q(v,h)e^{-E(v,h)} } {Q(v,h)} )\geq\sum_{v,h} Q(v,h)\log(\frac{e^{-E(v,h)} } {Q(v,h)} ) = \log(Z_Q) \]

之前的定义是不是少了个log?因为\(Z_Q\)在之前被定义为

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

所以就有\(Z_Q\leq Z\), 所以

\[ P(v,h) = \frac{e^{-E(v,h)} } {Z} \leq \frac{e^{E(v,h)} } {Z_Q} \]

推论 2 Boltzmann机的吉布斯态可以以$ \(的概率成功制备. 同时与数据集相连的visible unit可以通过\) $的概率制备.

证明:

首先通过

\[ \begin{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) \end{aligned} \]

确定平均场近似的系数. 这些系数就唯一地确定了平均场分布Q,然后用它来近似配分函数\(Z\)\(Z_x\)

有了平均场近似的系数,可以通过一系列对单比特的旋转

\[ \|\psi_Q\rangle := \Pi_{i} R_y(2\arcsin(\sqrt{\mu_i} ))\|0\rangle\Pi_{j} R_y(2\arcsin(\sqrt{v_j} ))\|0\rangle = \sum_{v,h} \sqrt{Q(v,h)} \|v\rangle\|h\rangle \]

然后就需要通过reject sampling来获得\(\sum_{v,h} \sqrt{P(v,h)} \|v\rangle\|h\rangle\)的近似

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

\(\mathbf{P} (v,h)\)可以通过平均场系数有效地计算出来. 同时推论一也保证了\(\mathbf{P} (v,h)\)在(0,1)之间的

我们就可以将这个态

\[ \sum_{v,h} \sqrt{Q(v,h)} \|v\rangle\|h\rangle\|0\rangle \]

变为

\[ \sum_{v,h} \sqrt{Q(v,h)} \|v\rangle\|h\rangle\|\mathbf{P} (v,h)\rangle \]

然后我们可以通过增加一个辅助比特来获得目标的态

\[ \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) \]

然后对辅助比特测量, 就能以一定概率获得

\[ \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{P(v,h)} \|v\rangle\|h\rangle \]

算法一的伪代码:

  • 先从\(\omega\),b,d计算平均场系数\(\mu\),\(v\)
  • 获得平均场配分函数\(Z_Q\)
  • 制备态: \(\sum_{v,h} \sqrt{Q(v,h)} \|v\rangle\|h\rangle:=(\Pi_{i=1} ^{n_v} e^{-i\sqrt{\mu_i} Y} \|0\rangle)(\Pi_{i=1} ^{n_h} e^{-i\sqrt{v_j} Y} \|0\rangle)\)
  • 添加一个寄存比特:

\[ \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 \]

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_ib_i+\ln(\mu_i^{v_i} (1-\mu_{i} )^{1-h_j} )\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)+v_i h_j\omega_{i,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_ih_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) \]

算法二

对算法一进行一些小的修改, 将\(Q\)替换为\(Q_x\),就可以用来训练出需要的\(\sum_i\sqrt{Q(x,h)} |x\rangle|h\rangle\)态,

function qGenDataState(\(\omega\),b,d,E,\(\kappa_x\),x)

计算平均场系数v

计算平均场近似的配分函数 $Z_{x,Q} $

for i=1:\(n_v\) \[ \sum_{h} \sqrt{Q(x,h)} \|x\rangle\|h\rangle\|E(x,h)\rangle\rightarrow \sum_{h} \sqrt{Q(x,h)} \|x\rangle\|h\rangle\|E(x,h)+x_ib_i\rangle \] end

for j=1:\(n_h\) \[ \sum_{h} \sqrt{Q(x,h)} \|x\rangle\|h\rangle\|E(x,h)\rangle\rightarrow\sum_{h} \sqrt{Q(x,h)} \|x\rangle\|h\rangle\|E(x,h)+h_jd_j+\ln(v_j^{h_j} (1-v_j)^{1-h_j} )\rangle \] end

for (i,j)\(\in\)E do \[ \sum_{h} \sqrt{Q(x,h)} |x\rangle|h\rangle|E(x,h)\rangle\rightarrow\sum_h\sqrt{Q(x,h)} |x\rangle|h\rangle|E(x,h)+x_ih_j\omega_{ij} \rangle \] end

return \[ \sum_h \sqrt{Q(x,h)} |x\rangle|h\rangle|E(x,h)\rangle(\sqrt{\frac{e^{-E(x,h)} } {Z_{x,Q} \kappa_x} } |1\rangle+\sqrt{1-\frac{e^{-E(x,h)} } {Z_{x,Q} \kappa_x} } |0\rangle) \] end

训练算法

这是用类Julia语言写的模拟这个量子算法的数值模拟算法伪代码, 这是对一个数据集进行一个epoch的训练过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 对每个训练样本进行训练(制备玻尔兹曼机态)
for i=1:n_train
success = 0
while success = 0
ψ = QuGenModelState(ω,b,d,E,κ)
# 这是测量的部分, 用蒙卡来模拟测量
dice = rand()
if dice < e^(-E)/(Z*κ_x)
success = 1
end
end
# modelVUnits 和 modelHUnits 都是矩阵, 用来对每个数据集的测量结果
modelVUnits[:,i] = measure_visible_unit(ψ)
modelHUnits[:,i] = measure_hidden_unit(ψ)
success = 0
while success = 0
# 用和visiable unit连接的数据生成Data model, 也就是算法 2
ψ = qGenDataState(ω,b,d,E,κ,x_train[i])
# 测量
dice = rand()
if dice < e^(-E/Z_xQ*κ)
success = 1
end
# dataVUnit 和 dataHUnit 是用来存储算法 2获得的态的测量结果(每一个数据集的)
dataVUnit[:,i] = measure_visible_unit(ψ)
dataHUnit[:,i] = measure_hidden_unit(ψ)
end
# 到这里制备和训练就结束了
# 然后计算用来优化训练目标函数的梯度
# 注意这里简写了两个for循环
for i in eachindex(v),j in eachindex(h)
gradMLw[i,j] = learning_rate*(sum_k(dataVUnit[i,k]*dataHUnit[j,k]-
modelVUnits[i,k]*modelHUnits[j,k]-λ*ω[i,j]))/n_train
###################
gradMLb[i] = learning_rate*(sum_k(dataVUnit[i,k]-modelVUnits[k,i]))
gradMLd[j] = learning_rate*(sum_k(dataHUnit[i,k]-modelHUnits[k,i]))
end

之后按照这个梯度更新b,d还有$_{ij} $即可