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

今天咱们继续来聊QSVT算法吧～喜欢碎片化阅读的小伙伴们可以选择每期跟读，喜欢系统性阅读的小伙伴们可以选择等一个专题更新完毕后再阅读。

咱们先来简单的回顾一下前两期内容。

前期回顾

在量子奇异值阈值算法QSVT（一）中，介绍了经典奇异值阈值算法SVT的概念和应用场景，其中还介绍了低秩的概念及其应用。

在量子奇异值阈值算法QSVT（二）中，介绍了量子奇异值阈值QSVT问题及QSVT算法，主要包括经典SVT是如何通过转换变成量子算法能够求解的问题；以及QSVT量子算法的流程。

本期导读

相信有些朋友和我一样，喜欢从具体的实例入手来进一步理解算法。本期将介绍一个QSVT的具体实例，通过一步一步的说明来帮助大家更好的理解QSVT算法。

QSVT实例

在该例中，要求矩阵$A_0$的两个奇异值分别是2和1，且奇异值阈值参数$\tau$设置为1/2。

满足上述要求的所有输入矩阵$A_0$均可以通过图1的线路实现奇异值阈值的计算。

Note: 大家有兴趣可以思考下“为什么”满足上述要求的所有输入矩阵$A_0$均可以通过图1的线路实现奇异值阈值的计算。

如果输入有不同的变动，线路又应该如何设计和调整？

图1 QSVT算法实例的量子线路

在下面具体的实验说明中，选择的矩阵如下：

输入矩阵$A_0$是一个2*3的矩阵，因此矩阵A0的向量化表示为一个6*1的向量b。

Note: 2*3的维度并非上述线路所必需的要求，选择2*3只是想尝试下非方阵的输入。

以上是该例的前提，下面介绍算法流程。

算法流程

根据图1的线路和量子奇异值阈值算法QSVT（二）中QSVT算法的流程，我们来看一下这个实例是一步一步如何演化的。

（1）量子系统的初态为：

$\mid\psi_1〉=\mid 0000b〉$

其中|$\mid b〉$表示$\mid\psi_{A_0}\rangle$，即A0的向量化表示。因为$A_0$的两个奇异值分别为2和1，即$\sigma_1=2$，$\sigma_2=1$，因此有：

$\mid b〉=\frac{1}{\sqrt{N_1}}\sum\nolimits_{k=1}^{2}\sigma_k\mid{u_k}〉\mid{v_k}〉=\frac{1}{\sqrt{5}}(2\mid{u_1}〉\mid{v_1}〉+\mid{u_2}〉\mid{v_2}〉)$

其中，

$N_1=\sum\nolimits_{k=1}^{2}\sigma_k^2=5$

（2）图1中的$U_{PE}$表示相位估计运算（有关相位估计算法可以回顾文章入门量子机器学习领域，也许可以从解读Phase Estimation算法开始）。

算法中受控U运算中涉及的矩阵A满足：

$A=A_0A_0^++\sum\nolimits_{k=1}^{r}\sigma_k^2\mid{u_k}〉〈u_k\mid$

Note: 在量子奇异值阈值算法QSVT（二）中关于这一步有解释过，由于矩阵A是一个2*2的矩阵，而输入向量$\mid b〉$是一个6*1维向量，因此需要扩大矩阵的维度，即通过张量乘一个3维的单位向量，使其成为6*6矩阵：$e^{iAt}⊗I_n$

上述式子中的n=3。在图1中因为空间限制的原因，在线路图中省略了$⊗I_n$。

此时可以理解为，矩阵A作用在了$\mid{u_k}〉$子空间上，单位矩阵作用在了$\mid{v_k}〉$子空间上。因此经过相位估计运算之后：

$\mid\psi_2〉=\frac{1}{\sqrt{N_1}}\sum\nolimits_{k=1}^{2}\sigma_k\mid\sigma_k^2〉\mid{u_k}〉\mid{v_k}〉=\frac{1}{\sqrt{5}}(2\mid 100〉\mid{u_1}〉\mid{v_1}+\mid 001〉\mid{u_2}〉\mid{v_2}〉)$

Note: 这里做一点进一步的说明。我们考虑最小矩阵A为2*2维矩阵。此时$A_0$的奇异值分别为2和1，即用两个比特可以完全精确的表示这两个奇异值。

此时对应矩阵A的特征值则为4和1，即至少需要三个比特才能精确的表示这两个特征值。

也就是在这个线路的设计中，Reg.C的最小比特数为3。

（3）执行$U_{\sigma,\tau}$的运算。这一步线路设计完成的映射是：

$U_{\sigma,\tau}:\mid 100〉\rightarrow\mid 110〉and\mid 001〉\rightarrow\mid 100〉$

Note: 这个变换的结果是：$\mid 110〉=\mid 6〉, \mid 100〉=\mid 4〉$，观察下面这两个式子：

$2^3(1-\tau/{\sigma_1})=6$

$2^3(1-\tau/{\sigma_2})=4$

因此可以用$\mid 110〉$表示$\mid{1-\tau⁄{\sigma_1}}〉$，用$\mid 100〉$表示$\mid{1-\tau⁄{\sigma_2}}〉$。

我们再来解释下系数$2^3$。回忆HHL算法学习笔记（一）中介绍的“提取占比”的思想，因此在寄存器中，

二进制表示的$\mid 6〉$为：$\mid 110〉=2^3\mid{1-\tau⁄{\sigma_1}}〉$

二进制表示的$\mid 6/8〉$为：$\mid 0.110〉=\mid{1-\tau⁄{\sigma_1}}〉$

上述两者的区别只在于小数点位置的不同，但在量子计算中所起到的作用是等价的。因此，我们可以用$\mid 110〉$来表示$\mid {1-\tau⁄{\sigma_1}}〉$。

因此，经过$U_{\sigma,\tau}$之后，得到：

$\mid\psi_3〉=\frac{1}{\sqrt{N_1}}\sum\nolimits_{k=1}^{2}\sigma_k\mid{2^3(1-\tau/{\sigma_k})〉}=\frac{1}{\sqrt{5}}(2\mid 110〉\mid{u_1}〉\mid{v_1}+\mid 100〉\mid{u_2}〉\mid{v_2}〉)$

（4）执行Ry的运算。

在这里，采用一系列的Pauli Y矩阵来实现将基态$\mid 110〉$和$\mid 100〉$中的值提取到概率幅中。在这个过程中实现的是一个近似的提取效果：

$\mid\psi_4〉=\frac{1}{\sqrt{N_1}}\sum\nolimits_{k=1}^{2}{\sigma_k\{\sin[(1-\tau/{\sigma_k}\alpha]\mid 1〉+\cos[(1-\tau/{\sigma_k})\alpha]\mid 0〉\}}\mid{2^3(1-\tau/{\sigma_k})〉}\mid{u_k}〉\mid{v_k}〉\\=\frac{1}{\sqrt{5}}\{2[\sin(1.63905)\mid 1〉+\cos(1.63905)\mid 0〉]\mid 110〉\mid{u_1}〉\mid{v_1}+[\sin(1.0927)\mid 1〉+\cos(1.0927)\mid 0〉]\mid 100〉\mid{u_2}〉\mid{v_2}〉\}$

在上式中，存在一个参数$\alpha$，在这里的近似取值为$\alpha=2.0944$。至于为什么会取这个值，咱们下期再介绍。

（5）执行U逆运算。图1中所示的U逆运算包含了Ry之前所有线路的逆运算,即包括了U_sigma,tau的逆和$U_{PE}$的逆。因为$U_{PE}$在该例中是完美的执行的（即Reg.C能够完全精确的存储特征值），因此执行U逆运算之后，Reg.C的值恢复到初始态$\mid 000〉$。

然后测量第一个量子比特Anc.，测量结果得到1时，可以得到Reg.B为：

$\mid\psi_{\hat{S}}〉=\frac{1}{\sqrt{N_3}}[1.9999\mid{u_1}\rangle\mid{v_1}\rangle+0.8660\mid{u_2}\rangle\mid{v_2}\rangle]$

其中，

$N_2={1.9999}^2+{0.8660}^2=4.7495$

最后，我们来看理论上，我们希望算法能够输出的结果如下：

$\mid\psi_S\rangle=\frac{1}{\sqrt{N_2}}\sum\nolimits_{k=1}{2}(\sigma_k-\tau)\mid 1000\rangle\mid{u_k}\rangle\mid{v_k}\rangle=\frac{1}{\sqrt{10}}(3\mid{u_1}\rangle\mid{v_1}\rangle+\mid{u_2}\rangle\mid{v_2}\rangle)$

根据上述结果，我们可以通过保真度和概率这两个维度来评估该实例。

【保真度和概率】我们可以通过计算理论值和线路输出值的内积来评估算法的精度（保真度），并通过计算测量Anc.得到1的概率来评估执行一次算法的成功概率。