本期导读

上一篇小编简单的介绍了相位估计的算法过程,特别强调了在量子算法设计中蕴含的一个小技巧:在相位估计中,通过QFT算法的逆运算,将量子态的概率幅值存储到基态中,以便通过后续测量得到相位值。
今天的算法介绍主要围绕着由Michael A. Nielsen和Isaac L. Chuang所著的《Quantum Computation and Quantum Information》中相位估计的算法分析(见5.2.1节)进行解读。

今天小编将用三张图共两部分带大家来解读相位估计的分析。

1. 相位估计的输出形式

2. 相位估计的算法分析

相位估计的输出形式

图1简单的介绍了相位估计的输出形式。上一篇内容已经介绍了相位估计算法的过程,现在我们就把它看作是一个黑箱,如图1左边的Phase estimation的方框所示。

【算法分析】 相位估计 | Phase Estimation-量子客

图1 相位估计的输出

这个黑箱涉及了两个寄存器:上面的第一寄存器(用横线和斜线组成)的输入是基态$|00…0>$,一共有$t$个量子比特,用于存储我们期望得到的相位;下面的第二寄存器存储的是输入矩阵$U$的一个特征向量$|u>$,经过这个黑箱之后,第二寄存器不发生变化。

黑箱操作完成后,对第一寄存器进行测量,我们就可以得到一串二进制数,如图1右上方框所标注。用这一串二进制数除以$2^t$,相当于将小数点向左移动$t$位,就可以得到如图1右中方框所标注的$\phi$,这个$\phi$就满足了图1右下等式。

我们简单回顾下这个等式的含义:输入酉矩阵$U$,$U$的特征向量为$|u>$,对应的特征值为$e^{2 \pi i\phi}$。相位估计算法就是依托于这个等式来实现的。

【划重点】相位估计算法的输出值和输入矩阵U的特征值$e^{2 \pi i\phi}$之间存在如下关系:相位估计算法依托于$U|u>= e^{2 \pi i\phi} |u>$这个等式实现,最终通过测量我们得到的是一串二进制数,这串二进制数除以$2^t$就可以得到上述等式中的$\phi$值。

相位估计的算法分析

在理想情况下,$t$比特能够表示精确的$\phi$值;但在很多实际情况下,$t$比特只能表示$\phi$的一个估计值。下面我们来分析如何以高概率得到一个较好的$\phi$估计值。如图2左上所示,我们将输出的$t$比特的二进制串进行隔断,分为红色和蓝色部分,红色部分包含$n$个比特,蓝色部分包含$t-n$个比特(冗余部分)。

【算法分析】 相位估计 | Phase Estimation-量子客

图2 算法分析(a)

如图2右下方框所示,其中m表示相位估计算法的实际输出值,$b$是假设的一个最优估计值, $\phi$是真实值(即表示U的特征值$e^{2 \pi i\phi}$中的$\phi$)。可以看到$m$和$b$的取值范围均为$[0,2^{t-n}-1]$。

我们的目标是确定$p(|m-b|>e)$的一个bound(界),其中$p$表示输出$m$的概率;$e$是评价误差的一个正整数:当$m$和$b$的前$n$个比特值不同时,有$|m-b|>e(e=2^{t-n}-1)$。这里将$p(|m-b|>e)$记为$\epsilon$。

在英文版小黄书中的P224页介绍了整个数学推导过程(需要深入理解的小伙伴还是要认认真真看书的)。$p(|m-b|>e)$的概率是通过量子态的概率幅$\alpha$来求得的,通过推导可以得到$p(|m-b|>e)=\epsilon<=1/[2(e-1)]$(如图3左上方框所示)。由这个等式可以得到$\epsilon$与$t$的关系,如图3左下方框所示。

【算法分析】 相位估计 | Phase Estimation-量子客

图3 算法分析(b)

图3左下方框的等式蕴含了一个小黄书上没有明确解释的一个关系。我们来回顾下,$t$是相位估计算法所实际输出的比特数,$n$是我们需要的一个精度(即$n$个比特就可以满足我们的精度需求),另外的$t-n$比特数(如图中两条红色直线标出的部分)相当于是冗余部分(即$n$个比特可以满足我们的精度需求,但实际算法中我们还采用了额外的$t-n$个比特)。那这$t-n$个冗余比特的作用是什么?量子算法虽然在执行过程中能够实现指数级的加速效果,但在得到最终结果时,是概率性的。因此在算法分析时常常需要分析成功输出结果的概率。根据图3左下所示,冗余比特越多,算法成功输出好的相位估计值的概率就越大。因此$t-n$个冗余比特的作用是为了提高成功输出好的相位值的概率。

【划重点】相位估计算法的量子线路在设计时包含了冗余的输入比特,这个冗余比特数越大,算法输出好的相位估计值的概率就越大。

小结

今天的内容更偏向于学术讨论,数学分析一直是让小编头大的部分,因此这部分内容单独拿出来聊一聊。希望今天的分享对大家理解相位估计的算法分析能提供一些帮助。


注:本文首发在公众号上,此栏目是作者的量子客专栏,最新文章推送请详情关注“量子机器学习”。

【算法分析】 相位估计 | Phase Estimation-量子客