论文： An efficient quantum algorithm for generative machine learning
论文地址：https://arxiv.org/abs/1711.02038
量子计算领域的一个核心任务是找到量子计算机可以提供超越传统计算机实现指数级加速的应用场景。机器学习是一个量子计算机可以在其多个应用层面提供大幅加速的重要领域。针对机器学习的判别式模型，基于线性代数问题的有效求解，人们已发现了多种量子算法，在假设能从量子随机访问存储器中获取有效输入的情况下可实现运算的指数级加速。
在机器学习中，生成式模型则代表了另一个大类，其被广泛用于监督学习和非监督学习。此文中，我们首先提出了量子生成式模型（Quantum Generative Model, QGM）的概念，模型通过测量一系列处于多体纠缠态下的可观测算符来表示用于描述数据间关系的概率分布。生成式模型最显著的特征是其表征能力和从数据中学习模型参数的能力，以及对任意变量之间的复杂关系进行推断的能力。对于表征能力，我们证明我们提出的 QGM 可以高效地表示任何因子图（factor graph），其中包括了所有实际应用的经典生成式模型，即经典生成式模型只是 QGM 的特例。此外，通过证明至少存在一些特定的概率分布，可以被 QGM 表示，但不能被任何使用多项式量级的变量的因子图进行表示，我们表明 QGM 相对于因子图具备指数量级的表征能力（前提是计算复杂度理论中一个被广泛接受的猜想成立的话，即多项式分层作为 P vs NP 问题的泛化，是不塌缩的）。
具备表征能力和泛化能力只是量子生成式模型（QGM）的一个方面，另一方面我们需要可用于训练和推断的有效算法。我们提出了一种通用的学习算法，该算法利用对多体纠缠量子态构建的母哈密顿系统（parent Hamiltonian）进行量子相位估计（quantum phase estimation）进行学习。虽然不能期待这种量子算法在所有情况下都能在多项式时间内有效地实现，我们证明了至少存在一些我们的量子算法相对于所有经典算法有指数量级的加速效果的场景。（因为如果可以证明我们的量子算法在所有情况下都可行，那就意味着量子计算机能高效解决所有 NP 问题，这显然不太可能）同时这个结论依赖于量子计算机不能被经典计算机高效地模拟这个现在广为接受的假设。
我们算法中的指数加速效果可以直观地理解为：机器学习生成式模型的目的是通过寻找潜在的概率分布，对自然界中任意的数据生成过程进行建模。由于自然界是受量子力学定律支配的，所以用经典生成式模型中的概率分布对现实世界中的数据进行建模，是很有局限性的。然而，在我们的量子生成式模型中，我们使用一个多体纠缠量子态的概率幅对数据中的相互关系进行参数化。也正是因为由于量子概率幅的相干性会产生比经典概率模型复杂得多的现象，我们的量子生成式模型也许的确能在特定情况下取得显著的性能提升。
图 1：经典和量子生成模型。a，因子图（factor graph）图示；b，张量网络状态（tensor network state）图示；c，量子生成模型（quantum generative model）定义。
图 2：通过量子生成模型可以有效表示因子图。
我们的 QGM 用图态 |G> 表示，由 m 个量子比特与图 G（graph G）组成。我们引入下面的变换：
其中 M_i 表示应用在量子比特 i 的 Hilbert 空间上的可逆（通常是非么正的）2×2 矩阵。从图 G 的 m 个顶点，我们选择一个 n 个量子比特的子集作为可见的单元，并在计算基态 {| 0>;| 1>} 上计算该子集。
从 n 个二元变量 {x_i,i = 1,2, ...,n} 的概率分布 Q（{x_i}）中得到计算结果样本（其他 m×n 个隐藏的量子比特只用来给出低密度矩阵）。给定图 G 和可见顶点的子集，概率分布 Q（{x_i}）定义了由矩阵 Mi 中的参数有效参数化的 QGM。
状态| Q>可以写成一个特定的张量网络状态（见图 1）。我们用这种形式来表示我们的模型，原因有二点：首先，概率分布 Q（{x_i}）需要具备足以包含所有因子图的泛化能力; 第二，如果状态| Q>采取特定的形式，这个模型中的参数可以方便地通过量子算法在数据集上进行训练。
现在我们证明任何因子图都可以看成是 QGM 的一个特例，其定理如下：
定理 1： 上面定义的 QGM 可以任意高精度地有效表示任何常数度（degree，即节点连接的边的数量）的因子图的概率分布。
定理 2： 如果计算复杂性理论中关于多项式分成的泛化假设不塌缩，那么存在可以被 QGM 高效表示但不能被任何来自由经典生成模型简化后的因子图的条件概率有效甚至近似地表示的概率分布。
图 S1：因子图和 QGM 的参数空间。a，两种模型都有多项式量级的参数的一种情况。在这种情况下，因子图不能代表 QGM 中的一些分布（如蓝色圆圈所示处）。b，为了表示 QGM 中的蓝色圆圈的分布，因子图必须包含指数级的参数。在这种情况下，参数空间将膨胀到一个非常大的规模。
图 3：关于 QGM 的训练算法示意图。
a ，QGM 的训练和推断过程被简化到在|Q(z)>状态下对某些特定操作的测量。因此量子算法的关键步骤是获取状态|Q(z)>，具体通过针对已构建的母哈密顿系统进行递归的量子相位估计的方法制备。
由指定值组成的集合 z 中的变量被称为条件变量，而其他标记二元物理索引的变量则被称为无条件变量。我们将变量分组，使得每个组只包含一个无条件变量和一些通过少量固定数量的边连接的不同的组（表示虚拟索引或隐藏变量）。然后每个组使用一个物理索引（用 p 表示）和少量固定数量的虚拟索引（在图中用 i，j，k 表示）定义一个张量。
b ，|Q(z)>的张量网络表示，其中为 a 中每个指定的组定义一个局部张量。
c ，|Q(t)>的张量网络表示，其中|Q(t)>是从|Q(z)>简化的一系列状态。每一次简化会移出一个局部张量。移出的局部张量用未填充的圆圈表示，每个圆圈的物理索引设置为 0. 对于剩余张量网络和移出张量之间的边，我们将相应的虚拟索引设置为 0（由未填充的圆圈表示）。
d ，母哈密顿量（parent Hamiltonian）的构建。该图显示了如何在母哈密顿算子中构造一个项，该项对应于一组相邻的局部张量，例如 c 中的虚线框中的那些。在压缩组内所有虚拟指标之后，我们得到一个张量 L_pqr,ij，其定义了从虚拟指标 i，j 到物理指标 p，q，r 的线性映射 L. 由于指标 i，j 取所有可能的值，该映射 L 的范围跨越物理指标 p，q，r 的希尔伯特空间 H_p,q,r 中的子空间范围（L）。该子空间在 H_p,q,r 内部有用 comp（L）表示的互补的正交子空间。
投影到子空间 comp（L），然后在母哈密顿系统中定义一个项，由此定义|Q_t>位于该投影的核空间中。我们用一组相邻的张量构造每个局部项。每个局部张量可以涉及几个哈密顿量项（如虚线框和虚线框中的 c 所示），因此一些相邻组具有非空重叠，并且产生一般不交换的项。通过这种方法，可以构造母哈密顿系统，用其基态来定义状态|Q_t>。
e ，在母哈密顿系统中使用的量子相位估计方法从|Q_t-1>到|Q_t>的演化过程中的状态的示意图。|Q_t-1> *，|Q_t> *分别表示在|Q_t-1>和|Q_t>所跨越的二维子空间内正交于|Q_t-1>，|Q_t>的状态。|Q_t>和|Q_t-1>之间的角度由重叠部分η_t= | <Q_t | Q_t-1> | ^ 2 确定。
f ，通过量子相位估计算法的递归应用得到的状态演化过程。演化过程的每一个分支都是从状态|Q_t-1>开始，在状态|Q_t>结束，其中η_t 和 1-η_t 表示相关输出的概率。
定理 3： 存在计算条件概率和KL 散度的梯度到附加误差 1/poly(n) 的实例，使得（i）我们的算法可以在多项式时间内得到计算结果;（ii）任何经典算法都不能在多项式时间内完成计算，除非经典计算机能够高效地模拟量子计算。
