今天咱们继续来聊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的概率来评估执行一次算法的成功概率。

  • 在该例中,$\mid{\psi_{\hat{S}}}\rangle$和$\mid{\psi_S}\rangle$的内积为:0.9962。
  • 算法执行一次成功得到$\mid{\psi_{\hat{S}}}\rangle$的概率为:0.9499。

因此可以说,在该例中,通过执行一次图1所示的量子线路,能够以94.99%的成功概率得到保真度为99.62%的输出。不过请注意,这里的保真度并非物理实验中表示的保真度,而是评价理论值和线路输出值内积的一个表示。

细心的朋友有没有发现,这个保真度和概率的值都很高。如果你有做过HHL算法的实验,你会发现通过一次实验很难使两者同时保持较高的值。那为什么这个实例做到了呢?

如果你对这个问题感兴趣,敬请期待下期解说~

小结

今天介绍一个简单的例子,大家可以自己动手计算一下,对理解QSVT算法会有很大的帮助。如果你对这个算法感兴趣,还可以在matlab上编程实验下,一定会有有趣的发现。

下期我们来聊一聊在这个例子中参数alpha的取值问题,敬请期待。

注:

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

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

入门量子机器学习领域,也许可以从解读Phase Estimation算法开始

发表评论

后才能评论