学习
实践
活动
专区
工具
TVP
写文章

量子判别分析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

加群请备注学校-专业-姓名,谢谢!

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180423G0ECNO00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

同媒体快讯

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券