本期导读

上一篇小编简单的介绍了相位估计的算法过程，特别强调了在量子算法设计中蕴含的一个小技巧：在相位估计中，通过QFT算法的逆运算，将量子态的概率幅值存储到基态中，以便通过后续测量得到相位值。

今天的算法介绍主要围绕着由Michael A. Nielsen和Isaac L. Chuang所著的《Quantum Computation and Quantum Information》中相位估计的算法分析（见5.2.1节）进行解读。

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

1. 相位估计的输出形式

2. 相位估计的算法分析

相位估计的输出形式

图1简单的介绍了相位估计的输出形式。上一篇内容已经介绍了相位估计算法的过程，现在我们就把它看作是一个黑箱，如图1左边的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$个比特（冗余部分）。

图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左下方框所示。

图3 算法分析（b）

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

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