量子支持矩阵机QSMM（三）

1. 量子支持矩阵机QSMM（一）
2. 量子支持矩阵机QSMM（二）
3. HHL算法学习笔记（一）
4. HHL算法学习笔记（二）
5. 量子奇异值阈值算法QSVT（二）
6. Swap test

在前两期，小编重点介绍了经典的支持矩阵机SMM的ADMM求解方法，以及量子算法实现ADMM的思路。今天简要介绍下设计量子支持矩阵机QSMM算法的思路。

  QSMM算法

回顾量子支持矩阵机QSMM（二）中的图2可知，求解QSMM的核心算法包括了用于加速学习算法的HHL算法，QSVT算法，以及用于加速分类算法的swap-test算法。这些量子算法的具体实现及其复杂度分析请参考文章顶部的往期回顾。其中，分类算法的思想比较简单，与量子支持向量机QSVM分类算法相似，这里不再赘述。

学习算法的流程思想其实与经典的ADMM算法思想相同，如图1所示。量子的HHL算法和QSVT算法分别对迭代过程中的两个核心步骤进行加速。

图1 QSMM设计思路

【创新点/贡献】该算法在求解方法上的创新点/贡献主要有两个：

1. HHL算法执行之前，通过最小二乘的方法对原始问题进行了转换；没有该转换，原始问题无法直接应用量子算法。
2. 设计了QSVT量子算法，整体算法虽然是基于HHL算法的思想，但旋转门的设计还是比较巧妙的。

在应用上，经典SMM的提出主要是用于图像分类；这种针对具体场景的量子算法的设计对未来量子算法的实际应用提供了理论研究基础。

【未解决问题】这里面有一个关键问题小编没有解决，即在这个迭代过程中，存在一个问题：HHL算法的输入如何提取出来作为QSVT算法的输出？

在整体的算法流程介绍中，小编采用了与其他论文相似的方法（即通过sample进行提取）。

但sample的时间复杂度是多少？

有没有可能不通过sample提取而直接通过改变量子态来实现这一步的转换呢？

关于这个问题，小编思考了很久，暂未解决。如果对这一问题有想法的，欢迎与小编一起讨论~

下一期，小编将拟介绍量子降维算法，敬请期待。

参考文献：

[1] Luo L, Xie Y, Zhang Z, et al. Support matrix machines[C]// International Conference on International Conference on Machine Learning. JMLR.org,               2015:938-947.
[2] Bojia Duan, Jiabin Yuan, Ying Liu and Dan Li. Quantum algorithm for support matrix machines. Phys. Rev. A. 96, 032301 (2017).

注：作者：Duan.Bojia (QubitLab)
编辑：Zoe
校对：量豆豆

本文原创，首发在《量子机器学习》微信公众号，欢迎关注。