量子判别分析QLDA（三）

在前两期中，咱们回顾了经典的LDA降维与分类，并介绍了量子LDA降维算法。今天，只分享一个内容，就是上一期介绍的Hermitian chain product这个定理的证明过程。

本期大纲

Hermitian chain product

Hermitian chain product

Hermitian chain product的证明思路与HHL算法相同，我们借助图1对这个证明过程进行详细的说明。

图1 一轮Hermitian chain product

算法流程

① 算法的输入为：

其中，rho_0是一个与单位矩阵I成比例的密度矩阵，在矩阵A1的特征空间上进行分解，有：

在这一步作者没有给出系数beta的值，小编理解该值为：

② 执行相位估计，提取出A1的特征值存储在图1里中间的寄存器中，此时得到的状态为：

这一步中，需要个A1的copy，如果考虑准备A1的时间为O(X)，则这一步的时间复杂度为：

③ 执行受控旋转门R，此时附加量子比特变为状态：

其中：

此时，量子系统状态为：

④ 执行逆相位估计运算，上式中蓝色部分回退到初值，此时去除第二寄存器，可以得到：

⑤测量附加量子比特，得到|1>

这一步运算的简易推导如下：

注意上式中省略了归一化因子。

到这里，可以实现一个f_1函数作用于一个输入矩阵A_1的情形。

为了能够实现Hermitian chain product，即将多个f_j函数作用于多个输入矩阵A_j，需要执行多次图1的线路，如图2所示：

图2 k轮Hermitian chain product

图2表示的是，将A1作为第一轮运算中相位估计的输入矩阵，rho_0作为输入的密度矩阵；通过一轮运算可以输出密度矩阵rho_1；随后将rho_1作为输入，采用同样的一轮运算可以输出rho_2，重复进行，直至最后得到输出rho_k：

这里注意顺序，一定是先执行f1(A1)，在依次执行f2(A2),....,直至fk(Ak)。

复杂度分析

【算法的成功概率】

复杂度的分析要考虑在第三步中，引入的常数C的取值。作为归一化因子，C的取值如下：

这个取值的选择依据在于的概率幅值小于1，即：

因此，测量附加量子比特得到|1>

即算法的成功概率为：

【算法的时间复杂度】

由于相位估计最为耗时，结合相位估计的时间与算法的成功概率，可以得到一轮算法的时间复杂度为：

从图2可以看出，经过k轮运算，算法的时间复杂度为：

在这里，第一轮运算是可以采用amplitude amplification提高算法的成功概率的（如图2所示）。小编认为，仅能用amplitude amplification提高第一轮（而不是所有轮）运算，是因为输入rho_0是可控的，而输出值rho_j (j>0) 均是未知的。此时，最终算法的时间复杂度可以有一丁点的提高，最终为：

定理1的证明就至此介绍完毕啦。

参考文献

[1] Iris Cong and Luming Duan. Quantum discriminant analysis for dimensionality reduction and classification. 2016 New J. Phys. 18 073011.

搜索公众号：量子机器学习

如果你希望在这个领域中深造，

欢迎加入学术QQ群：552304117

加群请备注学校-专业-姓名，谢谢！