奇异值分解（SVD）有哪些很厉害的应用？ 第1页

这篇打算简单叙述量子算法近年的主要进展 (之一), 即量子奇异值变换 (quantum singular value transform) ^[1]. 故事的起点是这么一件事: 给定某个随机算法, 我们总是可以通过多次重复运行它来提高成功概率. 那么, 我们能尽可能少的重复吗? 量子算法中著名的振幅放大 (amplitude amplification) 技术 ^[2] 可以提供平方时间加速, 这里技术的例子之一就是 Grover 算法 (或者说"无结构搜索"算法).

这个技术做得事情就是在某个圆周上做多次固定角度逆时针旋转, 以期在若干次后到达圆周的顶点. 但这么做有个问题, 就是如果我们并不知道"固定角度"到底是多少的话, 我们并不能直接通过连续多次旋转到达顶点附近 – 直到量子奇异值变换 (quantum singular value transform) 相关技术 ^[3] 的出现解决了这一问题, 方案有些出人意料: 只需要把圆周"撑成"球面, 然后在上面绕着某两个轴交替旋转, 可以证明这样的旋转会在球面的极点附近收敛. 这即是不动点振幅放大 (fixed-point amplitude amplification) ^[4] 技术.

为什么这跟奇异值分解有关呢? 简而言之, 上面所切换的两个旋转轴, 其实跟某个矩阵的奇异值分解 (singular value decomposition) 的左奇异矢量及其正交矢量张成的平面, 以及右奇异矢量及其正交矢量张成的平面有关.

本文亦发表于我的博客: 如何提高成功概率：量子奇异值变换简说.

下面开始正文.

以平面旋转来提高成功概率

给定某个成功概率为 的随机算法, 为了提高它的成功概率 (譬如说成功概率接近 ), 我们可以这么做: 将这个算法重复允许很多遍, 如果其中有一个拷贝是成功的话, 我们就认为这个新的随机算法是成功的. 不难证明, 如果我们重复允许这个算法, 直到某一次成功才停下来的话 (满足几何分布),那么期望重复次数是 .

我们能在其他模型下做的更好吗? Gilles Brassard 和 Peter Høyer 在 1997 年证明了^[2], 对于量子算法, 我们只需要"重复" 次. 对量子算法稍有些了解的读者不难意识到, 著名的 Grover 算法其实是这一问题的特殊情况^[5], 同样提供了关于时间复杂度的平方加速. 具体来说, 这一问题可以写作:

任务 1. 给定可逆量子算法 使得对于选定的初始态 和目标态 , 这一量子算法的成功概率是 . 那么我们可否构造一个 , 在尽可能少的调用 的情况下, 使得 非常接近 .

如果取 为 的话, 不难发现这个问题有个很漂亮的几何解释:

即 和 其实可以张成一个平面上的圆, 它们分别对应于圆上的两点; 而 当然也可以投影到这个圆上. 换而言之, 问题变成了, 我们能够设法使得从圆心指向 的矢量, 能够绕着圆心旋转到 ? 这里的量子算法 其实描述的就是这个旋转过程 -- 展开来说, 这里通常包括绕着两个轴 和 反射, 然后交替这两个反射过程, 即作用 Grover 算子 , 就会绕着圆心逆时针旋转.

但是上面的旋转算法有个问题, 为了计算需要旋转多少次, 我们需要知道 Grover 算子每次会在这个圆上逆时针旋转多少度. 但总有些时候我们并不知道旋转角度, 也就是说, 如果我们连续地用 Grover 算子作用在同一个圆上 (所谓 fixed-point) 转的话, 很可能总是会转过头的.

于是, 有更好的办法吗?

量子奇异值变换和分解定理

上面的振幅放大 (amplitude amplification ) 其实只考虑了二维的希尔伯特空间, 或者说一个量子比特. 令人惊讶的是, 在很多时候其实我们只需要考虑二维空间, 譬如说 Jordan 引理^[6]就告诉我们, 对于两个投影算子 , 他们所作用的希尔伯特空间可以被正交分解成一群一维不变子空间和一群二维不变子空间; 这些不变子空间的维度取决于他们对应的 的特征值是否为 或 , 如果都不是的话是二维, 否则是一维.

Jordan 引理可以用来做一些很神奇的事情, 譬如用同一个"证据"态 (witness state) 来做 的 error reduction^[7], 或者来对量子零知识证明来做 rewinding^[8]. 是的, 这些应用听起来很反直觉, 因为把量子线路作用到量子态后, 再做测量通常会把量子态弄得面目全非; 但这里的分解定理告诉我们, 在一些情况下, 量子态们只会在二维子空间里跳来跳去. 这也意味着我们可以设法重复利用这些量子态们.

András Gilyén, Guang Hao Low, 宿愿和 Nathan Wiebe 在 2018 年的工作^[1]把上述 Jordan 引理推广到了更一般的情形, 即

如果在投影算子 和 之间再插一个酉算子 U 的话, 它们所作用的希尔伯特空间还是可以分成一群一维不变子空间, 和一群二维不变子空间.

有趣的是, 这里的不变子空间的维度, 跟它们对应的 的奇异值分解中对应的奇异值是否为 0 或 1 有关: 如果都不是的话, 那么不变子空间的维度是二维.

展开来说, 考虑 的奇异值分解, 即 , 其中 , 并且 和 . 对于奇异值满足 的情形, 分别可以定义 的正交矢量 , 以及 的正交矢量 , 其中奇异值 . 也就是说左奇异矢量对应是不变子空间是 , 右奇异矢对应的不变子空间是 ; 而 则是从 跳到 , 同时作用旋转矩阵 .

于是我们可以重新审视上一节中的 Grover 算子 . 其实它可以被推广为下述形式: , 其中 等于先作用 , 然后在控制量子比特上作用 , 然后再作用 . 注意到 的时候, 我们有 ; 即旋转角度 都取 的时候, 就是振幅放大 (amplitude amplificatio) 算法. 这意味着我们有一些额外的自由度, 来控制这样的量子算法的表现.

现在, 让我们聚焦到量子奇异值变换中的分解定理导出的那些二维不变子空间们. 注意到左奇异值矢量及其正交矢量可以张成一个平面 (右奇异值矢量及其正交矢量相同), 在这两个平面上我们同样可以考虑他们类似振幅放大算法中的圆; 但是这里我们可以在在这两个不同的平面上绕着圆心旋转 (即作用 或 ), 并且可以通过作用 和 来交替切换平面. 那么有没有办法来控制不同的平面的旋转角度呢? 或者说, 给定一组旋转角度, 我们能有办法知道这一系列操作最终做了什么吗?

Isaac Chuang 和 Guang Hao Low 更早的工作^[3]给出了二维不变子空间中的答案. 事实上上述操作序列可以看成量子信号处理 (quantum signal processing); 换而言之, 次不同平面上的交替旋转操作, 相当于对奇异值 作用了某个 -次多项式 , 即 . 更进一步, 借助量子奇异值变换给出的分解定理, 我们可以对所有不变子空间都做类似的操作, 即 .

下面我们将给出量子奇异值变换的一个具体应用, 即怎么解决不动点振幅放大 (fixed-point amplitude amplification) 问题.

以球面旋转来提高成功概率

回忆一下, 第一节提到的可逆量子算法 的形式是 . 换而言之, 的奇异值分解一定会得到对应于左奇异矢量 和右奇异矢量 的奇异值. 此时这一可逆量子算法的成功概率 满足 , 其中 . 也就是说, 为了放大这一可逆量子算法的成功概率, 我们需要下述奇异矢量变换:

任务2. 构造一个奇异矢量变换 , 使得对于任何喂进去的左奇异矢量, 都能吐出对应的右奇异矢量.

对于任务 2, 我们需要某个函数, 使得所有奇异值都能被替换为 . 又注意到奇异值变换中的奇异值都是非负的 (因为 的奇异值变换是用 定义的), 看起来 sign 函数正好能满足我们的需求:

Sign 函数即对于所有大于零的输入输出 1, 对于所有小于零的输入输出 -1. 而在上一节的讨论中, 我们知道每个奇异值变换的一系列旋转操作最终对应于某个多项式函数. 也就是说, 我们需要做的是找到某个多项式函数, 使得其能够很好地近似 sign 函数.

幸运的是, 选取合适参数的高斯误差函数 就能很好地近似 sign 函数, 而高斯误差函数亦能很好地用多项式函数近似. 即我们可以找到能在 区间内以 误差近似 sign 函数的次数为 的多项式. 这意味着我们可以通过这一具体的多项式, 选择量子奇异值变换中所需要的一系列旋转角度. 再注意到 , 其中 , 从而我们给出了任务 2 所需要的构造. 即我们找到了某种基于量子算法的神奇"重复方式", 使得我们最终得到的结果矢量总是很接近目标矢量, 不管我们到底重复了多少次.

这样的做法有什么几何解释吗? 从上一节中我们知道, 量子奇异值变换可以看成现在某个平面上 (对应于某法向量) 以选定角度旋转; 再跳转到另一个平面 (对应于另一个法向量) 上, 以另一个选定角度旋转; 以此类推. 有趣的是, 在 Isaac Chuang 等人的综述^[9]中指出下述几何解释:

换而言之, 这里的构造相当于考虑两顶点分别为 和 的 Bloch 球面, 从顶点 附近的球面上的点 出发, 在球面上环绕接近 , 并最终停留在 附近. 这也就是为什么基于量子奇异值变换的构造能避免转过头 (即 overshooting) 的直观原因.

参考

1. ^ ^{a b} Gilyén, András, Yuan Su, Guang Hao Low, and Nathan Wiebe. "Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics." In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193-204. 2019.
2. ^ ^{a b} Brassard, Gilles, and Peter Hoyer. "An exact quantum polynomial-time algorithm for Simon's problem." In Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, pp. 12-23. IEEE, 1997.
3. ^ ^{a b} Low, Guang Hao, and Isaac L. Chuang. "Optimal Hamiltonian simulation by quantum signal processing." Physical review letters 118, no. 1 (2017): 010501.
4. ^ Yoder, Theodore J., Guang Hao Low, and Isaac L. Chuang. "Fixed-point quantum search with an optimal number of queries." Physical review letters 113, no. 21 (2014): 210501.
5. ^ 准确地说, Grover 算法给出了 OR 函数的查询复杂度上界, 而 Brassard 和 Hoyer 的工作则是为了在一些情形下给出精确振幅放大 (exact amplitude amplification).
6. ^ Regev 的讲义中有很清晰地表述: Regev, O. "Witness-preserving QMA amplification." Quantum Computation Lecture notes, Spring (2006).
7. ^ Marriott, Chris, and John Watrous. "Quantum arthur–merlin games." computational complexity 14, no. 2 (2005): 122-152.
8. ^ Watrous, John. "Zero-knowledge against quantum attacks." SIAM Journal on Computing 39, no. 1 (2009): 25-58.
9. ^ Martyn, John M., Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. "A grand unification of quantum algorithms." arXiv preprint arXiv:2105.02859 (2021).

SVD的最重要应用就是找出数据中的主成分，从而做到数据压缩。看到这个问题时，想到之前写过一篇关于目标检测Fast R-CNN的文章，其中有一个用到SVD的地方，我觉得可以作为对这个问题的回答。

在Fast R-CNN中，类别预测与位置预测均通过全连接层实现，全连接操作的本质为向量的线性变换

其中，和分别为全连接层的输出和输入，其维度分别为和。为全连接层参数，其维度为，这也是上述线性变换所需的计算量（这里指乘法运算次数。 的每个行向量与列向量 计算內积，需要进行次乘法运算，矩阵有行，故总共需要次乘法运算）。例如在上述代码示例中，针对单个RoI，上式中的代表该RoI特征，其维度为4096。在类别预测的位置预测分支的全连接层中，上式中的分别代表类别分布和包围框位置变换参数，其维度分别为21和84。设RoI的个数为 ，则全连接运算计算量会被放大 倍，而在实际应用中，产生的RoI数量往往是非常可观的。例如产生的RoI数量为2000个（参考R-CNN中选择性搜索得到的区域建议个数），用于位置预测分支全连接层的乘法计算量将超过6.8亿次（具体为次），如此大规模的计算需要大量的时间开销，严重限制了目标检测的速度。所以为了提高目标检测速度，Fast R-CNN采用基于SVD的技巧降低上述运算量。SVD的定义为

其中为一个矩阵，由左奇异向量（singular vector）组成，为一个矩，由右奇异向量组成。为一个对角矩阵，除了主对角线上的元素以外全为0，对角线元素为矩阵由大到小排列的奇异值（singular value）。下图为SVD的图形示意。

在矩阵中，奇异值由大到小排列，排名靠前的很少几个奇异值（在很多情况10%甚至1%）之和就占了整个奇异值之和的绝大比例。这就意味着可以用少量几个大的奇异值来近似描述矩阵。具体方法为，取W的最大个奇异值构造对角阵，分别取对应的个左、右奇异向量构造和，从而得到 的近似SVD

近似SVD的图形示意如下图所示，可以看出在近似SVD中，参与运算的矩阵元素个数大幅减少。

在中用替代，有

从上式可以很容易的看出，近似SVD等价于用两个全连接层近似替代一个全连接层，两个全连接层的参数分别为。当选择一个很小的（）时，替换后的计算量降低到。

在Fast R-CNN中，首先在训练阶段完成单个全连接层参数 的训练。在测试阶段，用上述近似方法将 近似分解为，并表达为两个全连接层以降低计算量。实践表明，Fast R-CNN利用该方法，以MAP损失0.3%的代价换来30%的速度提升，可以说这一“买卖”是划算的。