在前两期中,咱们回顾了经典的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
加群请备注学校-专业-姓名,谢谢!
领取专属 10元无门槛券
私享最新 技术干货