量子奇异值阈值算法QSVT（二）

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

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

图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}$为奇异值阈值算子。

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

图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算法的输出。

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

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

注：

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

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