[量子计算]相位估计算法

本文出自:【InTheWorld的博客】 (欢迎留言、交流)

量子相位估计算法

量子相位估计算法(Quantom Phase Estimation)也称作量子特征值估计算法,是一个比较基本的算法。它的作用直观说来就是来估计一个酉变换的特征值。由于酉矩阵拥有一个性质:酉矩阵的特征值都是模为1的复数。所以对酉矩阵而言,其特征值和相位基本是对等的(因为模长已经确定了)。

量子傅里叶变换

在量子相位估计算法中,需要使用到量子傅里叶反变换。因此,我们简单了解一下量子傅里叶变换的相关知识。经典的离散傅里叶变换作用于一个复向量(x_{0}, x_{1},\cdots,x_{N-1}),并把它映射到另一个向量(y_{0}, y_{1},\cdots,y_{N-1}),其映射关系如下:

y_{k}=\frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} {x_{j}e^{-2\pi ijk/N}}

与其相对应的傅里叶反变换为:

x_{j}=\frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} {y_{k}e^{2\pi ijk/N}}

与上面类似, 量子傅里叶变换作用在量子态上,记为{\displaystyle |x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle },并把它映射到量子态{\displaystyle \sum _{i=0}^{N-1}y_{i}|i\rangle }上,而其映射规则在基态上的定义为:

|j\rangle \longrightarrow \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi ijk/N}|k\rangle

量子傅里叶变换的张量积表示如下所示:

{\displaystyle QFT(|x_{1}x_{2}\ldots x_{n}\rangle )={\displaystyle \frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}(|0\rangle +e^{2\pi i[0.x_{j}x_{j+1}\ldots x_{n}]}|1\rangle )}

这个公式看起来其实挺直观的,量子傅里叶变换的作用就是根据输入,改变输出量子比特的相位。如果你觉得这个公式都不够简单,那QFT的量子线路应该会让你满意。

上图中的H就是Hadamard门,R_{m}叫做控制相位门。R_{m}对应于如下的酉变换:

R_{m} = \begin{bmatrix} 1 & 0 \\ 0 & e^{2\pi i/2^{m} } \end{bmatrix}

量子傅里叶反变换量子傅里叶变换的逆过程,考虑量子计算都是可逆过程,量子傅里叶反变换的过程其实也非常好理解了。事实上,量子傅里叶反变换的量子线路就是把QFT的量子线路反过来。

相位估计算法理论

首先给出量子相位估计算法的线路图如下所示:

相位估计算法的线路可以分为两个部分,量子傅里叶变换之前的部分和之后的部分(包含Inverse QFT)。

如前文所说,相位估计算法所解决的问题是这样的:U是一个作用于m个量子比特的酉算子,U存在一个特征向量\vert \psi \rangle,也即{\displaystyle U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle ,0\leq \theta <1} 。然后,我们想找到特征向量|\psi\rangle对应的特征值{\displaystyle e^{2\pi i\theta }},也等价于找到相位\theta。这也是该算法名字的由来。

以下是算法流程:

  1. \vert 0 \rangle^{\bigotimes n}\vert \psi \rangle; 初始化状态
  2. \longrightarrow\dfrac{1}{\sqrt{2^n}} \displaystyle\sum_{j=0}^{2^n-1} {\vert j \rangle} {\vert \psi \rangle} ; 使用Hadamard门生成叠加态
  3. \longrightarrow\dfrac{1}{\sqrt{2^n}} \displaystyle\sum_{j=0}^{2^n-1} {\vert j \rangle} {U^{j}} {\vert \psi \rangle} = \dfrac{1}{\sqrt{2^n}} \displaystyle\sum_{j=0}^{2^n-1} {e^{2\pi i j \theta}} {\vert j \rangle} {\vert \psi \rangle};
    这一步主要是通过”控制U变换”,并利用特征向量的性质。
  4. \longrightarrow {\vert \widetilde{\phi_{\psi}} \rangle} {\vert \psi \rangle};
    这一步主要是应用傅里叶反变换。
  5. \longrightarrow \widetilde{\phi_{\psi}}
    这一步就是测量上部分寄存器的值,估计出相位值\theta

关于估计误差的计算,这里先略过了,相关资料上都有过程,先偷个懒了。

相位估计算法实例

接下来基于IBM量子计算平台,来完成简单的算法验证。首先考虑如下这个U门,

U= \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}

这个矩阵实际就是对应于泡利-X门,它实现的就是逻辑非。容易计算,这个矩阵有两个特征值,一个是+1,一个是-1。特征值+1对应的标准化特征向量是 \frac {|0\rangle +|1\rangle} {\sqrt 2},特征值-1对应的标准化特征向量是 \frac {|0\rangle -|1\rangle} {\sqrt 2}

因此可以构建如下所示的量子线路:

这个量子线路的q[2]相当于第二个寄存器(和特征向量相关的),q[3]相当于第一个寄存器(和测量相关的)。初态|0\rangle 经过Hadamard门会变换为 \frac {|0\rangle +|1\rangle} {\sqrt 2},然后再经过泡利-Z 门,就变成了 \frac {|0\rangle -|1\rangle} {\sqrt 2}。所以,量子相位估计算法预期应该计算出-1这个特征值,对应于相位就是二进制0.1倍的2 \pi,也即\pi

然后揭晓答案吧!运算结果如下图所示:

q[3]为1的概率为81.9%,所以说量子计算机基本找到了对应的相位。虽然例子有点简单了,但是验证了算法的可行性。这篇文章就先到这了!

参考文献

【1】.《量子计算与量子信息》Michael A. Nielsen
【2】.《量子力学》列文.朗道
【3】.《量子力学原理》P.A.M. Dirac
【4】. IBM量子计算实验平台

仅有1条评论 发表评论

  1. d /

    Good!wawu

发表评论