在上期量子奇异值阈值算法QSVT(一)中,小编简单介绍了经典奇异值阈值算法的一些概念和应用场景。

本期将介绍量子奇异值阈值算法。

 本期导读

  1. QSVT problem
  2. QSVT algorithm

QSVT problem

在经典和量子SVT的输入/输出之间,存在了一种对应关系,如图1所示(图1中各个表达式均省略了归一化因子)。

量子奇异值阈值算法QSVT(二)-量子客

图1 经典SVT和量子SVT的输入和输出

【经典输入】假设经典输入矩阵为$A_0$,具有奇异值分解:

$A_0=\sum\limits_{k=1}^r\sigma_k{u_k}v_k^t$

【经典输出】回忆上期量子奇异值阈值算法QSVT(一)关于SVT的定义可知,输出矩阵S为:

$S=\sum\limits_{k=1}^r{(\sigma_k-\tau)_+{u_k}v_k^T}$

即S的左右奇异向量与$A_0$的相同,S的奇异值为$A_0$的奇异值减去超参$\tau$(若得到的值小于0,则置为0)。

经典和量子之间通过一个什么转换呢?

【向量化】:即图1中的Vectorization,即将一个m*n维矩阵转换成一个mn*1的列向量。

经过向量化之后的矩阵具有一个什么特点呢?

如图1中第二行所示,输入$\vec{A_0^T}$可以表示为$A_0$的各个左奇异向量和右奇异向量的张量积乘以奇异值之后的和:

$\vec{A_0^T}=\sum\limits_{k=1}^r\sigma_k{u_k}⊗v_k$

输出$\vec{S^T}$有同样的特点:

$\vec{S_0^T}=\sum\limits_{k=1}^r(\sigma_k-\tau)_+{u_k}⊗v_k$

通过Vectorization,可以将经典矩阵和量子态(向量表示)之间建立一种关系。

【量子输入】输入的量子态具有Schmidt分解(关于Schmidt分解可参考Quantum Computation and Quantum Information一书中P109):

$\mid\psi_{A_0}〉=\sum\limits_{k=1}^r\sigma_k\mid{u_k}〉\mid{v_k}〉$

【量子输出】同样,输出的量子态为:

$\mid\psi_s〉=\sum\limits_{k=1}^r(\sigma_k-\tau)_+\mid{u_k}〉\mid{v_k}〉$

可以看出,量子态输入$\mid{\psi_{A_0}}〉$与$\vec{A_0^T}$相等,量子态输出$\psi_S〉$与$\vec{S^T}$相等。

综上所述,QSVT求解的问题为:

$\vec{S^T}=D_{\tau}(\vec{A_0^T})$

其中,$D_{\tau}$为奇异值阈值算子。

QSVT algorithm

在QSMM论文中,小编有介绍QSVT算法的流程,这个流程和HHL的非常相似,这里小编通过量子线路模型对这个过程进行简单的回顾,如图2所示。

量子奇异值阈值算法QSVT(二)-量子客

图2 QSVT量子线路

线路的具体过程如下:

【1】初始状态的制备

$\mid\psi_1〉=\mid 0〉\mid 0〉^L\mid 0〉^C\mid\psi_{A_0}〉^B$

【2】执行Phase estimation,得到

$\mid\psi_2〉=\frac{1}{\sqrt{N_1}}\mid 0〉\mid 0〉^L\sum\limits_{k=1}^r\sigma_k\mid\delta_k^2〉^C\mid{u_k}〉\mid{v_k}〉^B$

Note:在这一步小编要重点解释下关于维度的问题。

首先回顾下HHL解决的问题是$A_x=b$的问题(其中A作为相位估计中受控酉算子的输入源,b作为相位估计中量子态的输入源)。而QSVT的输入变量只有$A_0$,QSVT算法的设计要求是相位估计的输入量子态和受控酉算子均由输入$A_0$产生,这是与HHL算法不同之处。

输入向量:输入矩阵$A_0$为m*n维,展开成向量维度为mn*1,即图2中Reg.B的维度为mn。

受控酉算子:相位估计中受控酉算子的矩阵$A=A_0*A_0^T$为m*m维。

此时可以看到,m*m维的矩阵无法直接作用在mn维的向量上

因此,在受控酉算子的设计上,需要将算子$e^{iAt}$张量乘以一个n维的单位矩阵,扩展到mn*mn维之上,即:

$e^{iAt}⊗I_n$

【3】执行受控旋转操作

在算法的表达中,这一步需要实现的操作是,若$\sqrt{z}>\tau$,则执行:

$\mid 0〉\mid z〉\rightarrow{(\frac{r(\sqrt{z}-\tau)}{\sqrt{z}}\mid 1〉+\sqrt{1-\frac{r^2(\sqrt{z}-\tau)^2}{z}}\mid 0〉)\mid z〉}$

其中,第一个比特是附加量子比特,第二是Reg.C中输出的值。

这一步骤在量子线路设计中被分为了两步:

第一步,计算:

$y_k=(1-\tau/{\sigma_k})_+\in{[0,1)}$

并将值$y_k$存储在寄存器的基态中:

$\mid\psi_3〉=\frac{1}{\sqrt{N_1}}\mid 0〉\sum\limits_{k=1}^r\sigma_k\mid y_k〉^L\mid \sigma_k^2〉^C\mid{u_k}〉\mid{v_k}〉^B$

第二步,计算:

$\mid 0〉\mid{y_k}〉\rightarrow(y_k\mid 1〉+\sqrt{1-y_k^2}\mid 0〉)\mid{y_k}〉$

将$y_k$从基态$|y_k〉$中提取到附加量子比特基态|1〉前面的系数中:

$\mid\psi_4〉=\frac{1}{\sqrt{N_1}}\sum\limits_{k=1}^r\sigma_k[\sin(y_k\alpha)\mid 1〉+\cos(y_k\alpha)\mid 0〉]\mid{y_k}〉^L\mid\sigma_k^2〉^C\mid{u_k}〉\mid{v_k}^B$

再回顾一遍HHL算法学习笔记(一)中提到的设计思想,即先计算所求的值将其存储到基态中,再通过受控旋转操作将基态中的值提取到概率幅中。通过后处理过程(即测量)就可以将这个概率幅值参与到后续计算之中。

关于这两步的展开设计:第一步可以采用牛顿迭代法实现,第二步一般通过Pauli-Y近似得到。这里就不做延伸了。

【4】执行U逆:

$\mid\psi_5〉=\frac{1}{\sqrt{N_1}}\sum\limits_{k=1}^r\sigma_k[\sin(y_k\alpha)\mid 1〉+\cos(y_k\alpha)\mid 0〉]\mid{u_k}〉\mid{v_k}〉^B$

Note:在量子算法中,这里的逆运算指的是逆phase estimation。在量子线路中,这里的逆运算指的是Ry之前的所有运算,即包含了图中$U_{\sigma,\tau}$的逆运算。即在量子算法和量子线路中,这里的逆运算涉及的酉算子有所不同。

【5】测量附加量子比特得到1,最终得到:

量子奇异值阈值算法QSVT(二)-量子客

至此,我们得到QSVT算法的输出。

Note:以上所有式子中的N均表示归一化因子。

小结

  • 本期小编简单的介绍了经典SVT和量子SVT输入输出之间的关系,以及算法的流程。
  • 下一期小编将举一个相当简单的例子,以便能更好的理解这个算法。
  • 关于这个算法有什么好的建议和意见,欢迎大家留言。

注:

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

本文原创,首发在《量子机器学习》微信公众号,欢迎关注。最后感谢Zoe在量子客对本文的再次整理、校验与编辑。

量子奇异值阈值算法QSVT(二)-量子客