Hadamard Test与SWAP Test¶

量子线路是一系列量子门操作的组合。众多量子线路中有一部分量子线路是在构造量子算法时会被反复使用，这些被高频调用的量子线路组件我们称之为量子算法基本线路，下面将介绍几种常用基本线路。

Hadamard Test¶

Hadamard Test量子线路的主要作用是对任给的幺正算符 \(U\) 和量子态 \(\psi\) ，可以给出该幺正算符在量子态上的投影期望 \(\left\langle\psi\left|U\right|\psi\right\rangle\) 。

Hadamard Test的量子线路图结构简单，如下所示。

整个量子线路可以视为对两个寄存器中量子比特组成的一个n+1维量子态 \(\left|0\right\rangle\left|\psi\right\rangle\) 进行量子门操作组合 \(Q=\left.(H\otimes I^{\otimes n})\left(C-U\right)(H\otimes I^{\otimes n}\right)\)，其中 \(C-U\) 表示基于幺正算符 \(U\) 的受控门。

输出结果及推导¶

对Hadamard Test量子线路的输出结果进行推导，有如下结论：

\[\begin{split}\begin{aligned} Q\left|0\right\rangle\left|\psi\right\rangle=\frac{\left|0\right\rangle+\left|1\right\rangle}{2} \ \left|\psi\right\rangle+\frac{\left|0\right\rangle-\left|1\right\rangle}{2}U\left|\psi\right\rangle \\ =\left|0\right\rangle\frac{\left|\psi\right\rangle+U\left|\psi\right\rangle}{2}+\left|1\right\rangle \ \frac{\left|\psi\right\rangle-U\left|\psi\right\rangle}{2}. \end{aligned}\end{split}\]

对输出的结果量子态进行测量得到 \(\left|0\right\rangle\)，\(\left|1\right\rangle\) 的概率为

\[\begin{aligned} P_0= \frac{1}{4}\left \| (I+U)\left|\psi \right\rangle \right \|^2 \ =\frac{1+Re(\left\langle\psi\left|U\right|\psi\right\rangle)}{2}, \ P_1 = 1- P_0. \end{aligned}\]

由公式推导可知，Hadamard Test的结果相应的测量概率均与 \(Re(\left\langle\psi\left|U\right|\psi\right\rangle)\) 即幺正算符 \(U\) 在量子态 \(\psi\) 上投影期望的实部相关。

将图中测量之前的 \(H\) 门换成 \(RX(\frac{\pi}{2})\) 门，则可以得到概率与投影期望虚部相关的结果量子态。

代码实例¶

取 \(\left|\psi\right\rangle=\frac{\left|0\right\rangle+\left|1\right\rangle}{\sqrt2},U=H\)，Hadamard Test的一个代码实例如下：

#!/usr/bin/env python

import pyqpanda as pq

if __name__ == "__main__":

        machine = pq.init_quantum_machine(pq.QMachineType.CPU)
        cqv = machine.qAlloc_many(1)
        tqv = machine.qAlloc_many(1)
        prog = pq.create_empty_qprog()

        # 构建量子程序
        prog.insert(pq.H(cqv[0])) \
                .insert(pq.H(tqv[0])) \
                .insert(pq.H(tqv[0]).control([cqv[0]]))\
                .insert(pq.H(cqv[0]))

        # 对量子程序进行概率测量
        result = pq.prob_run_dict(prog, cqv, -1)
        pq.destroy_quantum_machine(machine)

        # 打印测量结果
        for key in result:
                print(key+":"+str(result[key]))

输出结果应如下所示，分别以 \(\frac{1+\sqrt2/2}{2}\) 和 \(1-\frac{1+\sqrt2/2}{2}\) 的概率得到 \(\left|0\right\rangle\)和 \(\left|1\right\rangle\) ：

0:0.853553
1:0.146447

Hadamard Test有着多种形式和广泛用途，其中一种特殊形式是基本量子线路SWAP Test。

SWAP Test¶

任给两个维数相同的量子态，通过SWAP Test线路，可以得到两个量子态的保真度，反应了它们的重叠情况。

SWAP Test的量子线路图如下所示。

对SWAP Test的公式推导验证过程完全类似于Hadamard Test，结果量子态的第一个寄存器测量得到\(\left|0\right\rangle, \left|1\right\rangle\) 的概率均与给定的两个量子态的保真度相关。

\[\begin{aligned} P_0= \frac{1+\left|\left\langle\psi|\phi\right\rangle\right|^2}{2}, \ P_1 = 1- P_0. \end{aligned}\]

SWAP Test作为Hadamard的一种特殊形式，它对两个给定量子态给出了其保真度相关的测量结果，具有重要应用意义。在量子态的内积相关研究中有着重要作用。

如果将受控SWAP门替换为一般的受控门F那么可以还原得到一般形式的Hadamard Test的结果量子态

\[\begin{aligned} \frac{\left|0\right\rangle}{2}(I+F)\left|\phi\right\rangle \ \left|\psi\right\rangle+\frac{\left|1\right\rangle}{2}(I-F)\left|\phi\right\rangle\left|\psi\right\rangle. \end{aligned}\]

代码实例¶

SWAP Test的代码实例与Hadamard Test有细微区别。

取 \(\left|\phi\right\rangle=\frac{\left|0\right\rangle+\left|1\right\rangle} \ {\sqrt2},\left|\psi\right\rangle=\left|1\right\rangle\)，SWAP Test的一个代码实例如下：

#!/usr/bin/env python

import pyqpanda as pq

if __name__ == "__main__":

    machine = pq.init_quantum_machine(pq.QMachineType.CPU)
    cqv = machine.qAlloc_many(1)
    tqv = machine.qAlloc_many(1)
    qvec = machine.qAlloc_many(1)
    prog = pq.create_empty_qprog()

    # 构建量子程序
    prog.insert(pq.H(cqv[0])) \
        .insert(pq.H(tqv[0])) \
        .insert(pq.X(qvec[0])) \
        .insert(pq.SWAP(tqv[0],qvec[0]).control([cqv[0]]))\
        .insert(pq.H(cqv[0]))

    # 对量子程序进行概率测量
    result = pq.prob_run_dict(prog, cqv, -1)
    pq.destroy_quantum_machine(machine)

    # 打印测量结果
    for key in result:
        print(key+":"+str(result[key]))

输出结果应如下所示，分别以 \(0.75\) 和 \(0.25\) 的概率得到 \(\left|0\right\rangle\)和 \(\left|1\right\rangle\) ：

0:0.75
1:0.25

HHL算法¶

HHL算法是一种求解线性方程组的量子算法，线性方程组在许多领域中都有着广泛的实际应用。

问题描述¶

不失一般性地，我们假设 \(A\) 为自共轭矩阵，否则取

\[\begin{split}\begin{aligned} C_A=\begin{bmatrix} 0 & A \\ A^H & 0 \end{bmatrix}, C_b=\begin{bmatrix} b \\ 0 \end{bmatrix}, C_x=\begin{bmatrix} 0 \\ x \end{bmatrix}, \end{aligned}\end{split}\]

则有 \(C_A为自共轭矩阵，且C_A\vec{C_x}=\vec{C_b}\) ，依然满足条件且可以还原得到原方程的解.

以下默认 \(A\) 为自共轭矩阵.

将向量 \(\vec{b},\vec{x}分别归一化后采用编码到振幅上的方式映射到量子态|b\rangle,|x\rangle\) ，则原问题转化为

\[\begin{aligned} A|x\rangle=|b\rangle. \end{aligned}\]

对矩阵A进行谱分解有

\[\begin{aligned} A=P\Lambda P^{-1}=\sum\limits_{j=0}^{N-1}\lambda_j|u_j\rangle\langle u_j|,\lambda_j\in\mathbb{R}. \end{aligned}\]

其中 \({(\lambda_j,u_j)}为矩阵A的特征值和特征向量组成的特征对. 此自共轭矩阵A满秩可逆，A的N\) 个特征向量线性无关.

将 \(|b\rangle以A\) 的特征向量为基展开，即

\[\begin{aligned} |b\rangle=\sum\limits_{j=0}^{N-1}b_j|u_j\rangle,b_j\in\mathbb{C}. \end{aligned}\]

于是原方程组的解可表示为

\[\begin{aligned} |x\rangle=A^{-1}|b\rangle=\sum\limits_{j=0}^{N-1}\lambda_j^{-1}b_j|u_j\rangle. \end{aligned}\]

因此，算法目标就是构造如上式所示的量子态.

问题背景概述¶

线性方程组问题可定义为：给定矩阵 \(A\in C^{N\times N}\) 和向量 \(\vec{b}\in C^N\) ，找到 \(\vec{x}\in C^N\) 满足 \(A\vec{x}=\vec{b}\)。

如果矩阵A每行或每列最多具有s个非零元，则将线性方程组称为s-稀疏线性方程组。用经典算法（共轭梯度法）来解决N维的s-稀疏线性方程组，需要的时间复杂度为 \(O\left(Nsk\log{\left(\frac{1}{\varepsilon}\right)}\right)\)，这里 \(\ k\) 表示系统的条件数， \(\varepsilon\) 表示近似的精度。HHL是一种量子算法，当A是自共轭矩阵时，用HHL算法解线性方程组的时间复杂度为 \(O\left(\log{\left(N\right)}s^2\frac{k^2}{\varepsilon}\right)\)。

HHL算法相对于经典算法有着指数级的加速，但经典算法可以返回精确解，而HHL算法只能返回近似解。

备注

HHL算法是一种纯量子算法，它和它的改进版的出现对于证明量子算法的实用性有着重大意义。

算法原理¶

在对线性方程组进行一定格式转换后可以以HHL算法进行求解，HHL算法主要包含了以下三大步骤，并需要使用右端项比特、存储比特和辅助比特总共三个寄存器；

构造右端项量子态，对存储比特及右端项比特进行参数含左端项矩阵的相位估计，将左端项矩阵的整数形式特征值全部转移到存储比特的基向量中；
进行一系列参数含特征值的受控旋转，过滤出所有的特征值相关量子态，将特征值从存储比特的基向量转移到振幅；
对特征存储比特及右端项比特进行逆相位估计，将存储比特振幅上的特征值合并到右端项比特上，当辅助比特测量得到特定状态时，在右端项比特上可得到解的量子态。

在进行算法具体步骤之前，需要对经典形式的线性方程组求解问题 \(A\vec{x}=\vec{b}\) 进行特定转换：

不失一般性地假设矩阵 \(A\) 为自共轭矩阵，否则取

\[\begin{split}\begin{aligned} C_A=\left[\begin{matrix}0&A\\A^H&0\\\end{matrix}\right], \vec C_b=\left[\begin{matrix}b\\0\\\end{matrix}\right], \vec C_x=\left[\begin{matrix}0\\x\\\end{matrix}\right], \end{aligned}\end{split}\]

使得 \(C_A\vec{C_x}=\vec{C_b}\) 成立且满足 \(C_A\) 自共轭。

以下内容中将默认A为自共轭矩阵。

将向量 \(\vec{b},\vec{x}\) 分别归一化后采用编码到振幅上的方式映射到量子态 \(\left|b\right\rangle,\left|x\right\rangle\) ，原问题转换为 \(A\left|x\right\rangle=\left|b\right\rangle\).

对矩阵 \(A\) 进行谱分解有

\[\begin{aligned} A=\sum_{j=0}^{N-1}\lambda_j\left|u_j\right\rangle\left\langle u_j\right|,\lambda_j\in R. \end{aligned}\]

其中 \({{\lambda}_j,u_j}\) 为矩阵A的特征对（特征值及相应的特征向量）。

将 \(\left|b\right\rangle\) 以特征向量基展开，得到

\[\begin{aligned} \left|b\right\rangle=\sum_{j=0}^{N-1}{b_j\left|u_j\right\rangle},b_j\in C. \end{aligned}\]

于是原方程组的解可表示为

\[\left|x\right\rangle=A^{-1}\left|b\right\rangle=\sum_{j=0}^{N-1}{\lambda_j^{-1}b_j\left|u_j\right\rangle.}\]

显而易见算法的基本思路应当是从右端项量子态 \(\left|b\right\rangle\) 出发构造解量子态 \(\left|x\right\rangle\) 。

通过QPE提取特征值¶

为了将矩阵 \(A\) 的特征值提取到解量子态的振幅，首先需要完成特征值的提取。由前文可知，QPE量子线路可以用于特征值提取。

对 \(\left|0\right\rangle^{\otimes n}\left|b\right\rangle\) 进行一次QPE操作，得到

\[\begin{aligned} {QPE(\left|0\right\rangle}^{\otimes n}\left|b\right\rangle)=\sum_{j=0}^{N-1}{b_j\left|\widetilde{\lambda_j}\right\rangle\left|u_j\right\rangle}. \end{aligned}\]

其中 \(\widetilde{\lambda_j}\) 是对应特征值 \(\lambda_j\) 的近似整数，细节参见QPE部分介绍。于是矩阵A的特征值信息存入到了基向量 \(\left|\widetilde{\lambda_j}\right\rangle\) 中。

通过受控旋转转移特征值¶

构造如下受控旋转 \(CR(k)\)

\[\begin{split}\begin{aligned} CR(k)(\left|a\right\rangle\left|j\right\rangle)=\left\{\begin{matrix} RY(2\arcsin{\frac{C}{k}})\left|a\right\rangle\left|k\right\rangle,j=k,\\ \left|a\right\rangle\left|j\right\rangle,j\neq k, \end{matrix}\right. \end{aligned}\end{split}\]

式中 \(C\) 为 \(\widetilde{\lambda_j}\) 的归一化系数，有 \(C\le\smash{\displaystyle\min_{j}} {\left|\widetilde{\lambda_j}\right|}\)从而任意 \(\frac{C^2}{{\widetilde{\lambda_j}}^2}\le 1\)。对 \(\sum_{j=0}^{N-1}{b_j\left|0\right\rangle \left|\widetilde{\lambda_j}\right\rangle\left|u_j\right\rangle}\) 经过遍历式旋转量子门操作后可以得到

\[\begin{aligned} (\prod (CR(k)\otimes I))\sum^{N-1}_{j=0}b_j\left|0\right\rangle\left|\widetilde{\lambda_j}\right\rangle \left|u_j\right\rangle=\sum_{j=0}^{N-1}{(\sqrt{1-\frac{C^2}{{\widetilde{\lambda_j}}^2}}\left|0\right\rangle +\frac{C}{\widetilde{\lambda_j}}\left|1\right\rangle)b_j\left|\widetilde{\lambda_j}\right\rangle\left|u_j\right\rangle}. \end{aligned}\]

通过逆QPE输出结果量子态¶

理论上，受控旋转后的量子态已经可以通过测量得到解量子态 \(\left|x\right\rangle\) 。

但为了避免出现 \(\left|u_j\right\rangle\) 相同但\(\left|\widetilde{\lambda_j}\right\rangle\) 不同的需要合并的量子态\(\frac{C }{\widetilde{\lambda_j}}b_j\left|1\right\rangle\left|\widetilde{\lambda_j}\right\rangle\left|u_j\right\rangle\)，应当选择逆QPE操作来得到形如 \(\frac{C }{\widetilde{\lambda_j}}b_j\left|1\right\rangle\left|0\right\rangle\left|u_j\right\rangle\) 的结果量子态。

对旋转结果进行逆QPE，有

\[\begin{split}\begin{aligned} & (I\otimes{QPE}^{\dagger})\sum_{j=0}^{N-1}{(\sqrt{1-\frac{C^2}{{\widetilde{\lambda_j}}^2}}\left|0\right\rangle+\frac{C}{\widetilde{\lambda_j}} \left|1\right\rangle)b_j\left|\widetilde{\lambda_j}\right\rangle\left|u_j\right\rangle} \\ & =\sum_{j=0}^{N-1}{(b_j}\sqrt{1-\frac{C^2}{{\widetilde{\lambda_j}}^2}}\left|0\right\rangle\left|0\right\rangle\left|u_j\right\rangle+b_j \frac{C}{\widetilde{\lambda_j}}\left|1\right\rangle\left|0\right\rangle\left|u_j\right\rangle). \end{aligned}\end{split}\]

事实上即使是这种形式的结果量子态，由于误差的存在，依然无法在第一个和第二个量子寄存器分别为 \(\left|1\right\rangle,\left|0\right\rangle\) 的情况下以概率1得到解量子态 \(\left|x\right\rangle=\sum_{j=0}^{N-1}{\lambda_j^{-1}b_j\left|u_j\right\rangle}\) 。

备注

HHL算法充分利用了量子相位估计提取特征值信息的功能，巧妙构造了受控旋转门从存储比特的基向量中抓取特征值存入振幅，最后利用逆相位估计还原存储量子比特，从而得到了振幅含特征值的方程解。

量子线路图与参考代码¶

HHL算法的量子线路图如下所示

此处仅介绍QPanda-2.0中提供的几个HHL算法调用接口。

HHL(matrix, data, QuantumMachine)

HHL_solve_linear_equations(matrix, data)

第一个函数接口用于得到HHL算法对应的量子线路，第二个函数接口则可以输入QStat格式的矩阵和右端项，返还解向量。目前第一个函数接口返回的线路需要追加特殊后处理，得到的并不是直接求解的结果，一般推荐使用第二个函数接口HHL_solve_linear_equations。

选取 \(A=\bigl(\begin{smallmatrix} 1 & 0 \\ 0 & 1 \\ \end{smallmatrix}\bigr), b=\begin{pmatrix} 0.6,0.8\end{pmatrix}^T\) ，验证HHL的代码实例如下：

#!/usr/bin/env python

import pyqpanda as pq
import numpy as np

if __name__ == "__main__":
   A=[1,0,0,1]
   b=[0.6,0.8]
   result = pq.HHL_solve_linear_equations(A,b,1)

   #打印测量结果
   for key in result:
      print(key)

输出结果应该和右端项向量一样是 \([0.6,0.8]\)，虚数项参数为0。因为误差会出现较小的扰动：

(0.5999999999999998+0j)
(0.7999999999999994+0j)

Grover算法和量子计数算法¶

量子计数算法（Quantum Counting）与Grover算法都是基于集合元素二类划分问题衍生的算法。量子计数算法可以求得集合中两种类型元素的个数，Grover算法则可以求得指定类型的一个元素。

问题背景概述¶

前文中介绍了振幅放大量子线路的问题背景集合元素二类划分问题，即对于给定的有限集合和划分标准 \(\Omega,f\)，我们可以用如下量子态表示集合元素

\[\begin{aligned} \left|\psi\right\rangle=sin\theta\left|\varphi_1\right\rangle+cos\theta\left|\varphi_0\right\rangle, \ \left|\varphi_0\right\rangle=\left|\varphi_1^\bot\right\rangle. \end{aligned}\]

现在对此问题进行两种扩展。

量子计数问题¶

记 \(\left|\Omega\right|=N=2^n,\Omega\supseteq B, \left|B\right|=M\le N\)，且判别函数满足

\[\begin{split}\begin{aligned} \left\{\begin{matrix} f:\Omega\rightarrow\{0,1\},\\ f\left(x\right)=\left\{\begin{matrix} 1,x\in B,\\ 0,x\notin B. \end{matrix}\right. \end{matrix}\right. \end{aligned}\end{split}\]

求 \(M\)。

传统算法是简单地通过 \(O(N)\) 次的运算进行遍历计数，从而求得解的集合基数 \(M\)。量子计数算法的时间复杂度与QPE过程完全一致，均为 \(O\left(\left(\log_2{N}\right)^2\right)\)。

备注

将振幅放大算子应用到QPE线路中，可以起到类似于由特征量子态提取特征值的过滤提取作用。

解元素的搜索问题¶

集合 \(\Omega\) 中存在某个元素 \(\omega \in \Omega\) 为特定问题的解，判别函数的定义如下：

\[\begin{split}\begin{aligned} \left\{\begin{matrix} f:\Omega\rightarrow\{0,1\},\\ f\left(x\right)=\left\{\begin{matrix} 1,x=\omega,\\ 0,x \neq \omega. \end{matrix}\right. \end{matrix}\right. \end{aligned}\end{split}\]

求 \(\omega \in \Omega\) 。

Grover算法的过程与振幅放大量子线路的过程完全一致。Grover算法的时间复杂度为 \(O(\sqrt N)\)，相对于经典算法的O(N)有着极大加速。

备注

事实上，振幅放大得到振幅和基向量的近似求解的思想不局限于集合元素二类划分问题。

算法原理¶

两种算法需要预制备的集合元素量子态有着相似的如下形式：

但具体定义和需要求解的目标不同，因此基于振幅放大量子线路衍生出的算法原理也有所不同。

基于振幅放大算子的QPE过程¶

量子计数算法中的两个基量子态是基于集合和判别函数定义的，即：

\[\begin{aligned} \left|\varphi_0\right\rangle=\frac{1}{\sqrt{N-M}}\sum_{x\notin B}\left|x\right\rangle, \left|\varphi_1\right\rangle=\frac{1}{\sqrt M}\sum_{x\in B}\left|x\right\rangle. \end{aligned}\]

将问题转化到空间 \(\{\left|\varphi_0\right\rangle,\left|\varphi_1\right\rangle\}\) 上，不妨记 \(\sin{\theta}=\frac{\sqrt M}{\sqrt N}\) ，则需要求解 \(\theta\) 。

直接在空间 \(\{\left|\varphi_0\right\rangle,\left|\varphi_1\right\rangle\}\) 上定义振幅放大算子\(G=\left[\begin{matrix}\cos{2\theta}&-\sin{2\theta}\\\sin{2\theta}&\cos{2\theta}\\\end{matrix}\right]\)，满足

\[\begin{aligned} G(\cos{\theta}\left|\varphi_0\right\rangle+\sin{\theta}\left|\varphi_1\right\rangle) =\cos{3\theta}\left|\varphi_0\right\rangle+\sin{3\theta}\left|\varphi_1\right\rangle. \end{aligned}\]

振幅放大算子 \(G\) 的特征向量可以构成空间 \(\{\left|\varphi_0\right\rangle,\left|\varphi_1\right\rangle\}\) 的一组基向量，因此 \(\psi\) 可以拆解为 \(G\) 的特征向量的线性组合。

\(G\) 的特征值为 \(e^{\pm2i\theta}\)，借助在制备 \(\psi\) 的过程中使用的索引比特，可以准确区分出以 \(G\) 构造的QPE过程结果对应的特征子相位是 \(2\theta\) 或 \(2\pi-2\theta\)。

于是就可以通过基于 \(G\) 的QPE过程完成对 \(\theta\) 的求解，而 \(N\) 已知，于是完成了对 \(M\) 的求解。

备注

为什么可以判定振幅放大算子 \(G\) 的特征向量可以构成空间 \(\{\left|\varphi_0\right\rangle,\left|\varphi_1\right\rangle\}\) 的一组基向量？

基于镜像变换的振幅放大量子线路¶

对于给定的量子态 \(\left|\psi\right\rangle=sin\theta\left|\varphi_1\right\rangle+cos\theta\left|\varphi_0\right\rangle\)，可以直接参考振幅放大量子线路，给出Grover算子，从而得到 \(\left|\psi_k\right\rangle=\sin{(2k+1)\theta} \left|\varphi_1\right\rangle+\cos{(2k+1)\theta}\left|\varphi_0\right\rangle,\ (2k+1)\theta\approx\frac{\pi}{2}\)。

但直接通过镜像变换构造的Grover算子 \(G=-(I-2\left|\omega\right\rangle \left\langle\omega\right|) (I-2\left|\psi\right\rangle \left\langle\psi\right|)\) 在实际的编程实现和运算过程中计算量过大，因此需要考虑如何将其利用基础的普适量子门简单实现累乘。

将原问题转换到空间 \(\{\left|\omega\right\rangle,\left|\psi\right\rangle\}\) 上，不妨记 \(\left|\Omega\right|=N\) ，由 \(\left\langle\varphi\middle|\omega\right\rangle=\frac{1}{\sqrt N}, \left\langle\varphi\middle|\varphi\right\rangle=1\) 可知

\[\begin{split}\begin{aligned} U_\omega=(I-2\left|\omega\right\rangle\langle\omega|)=\left[\begin{matrix}-1&-\frac{2}{\sqrt N}\\0&1\\\end{matrix}\right], U_s=2\left|\varphi\right\rangle\langle\varphi|-I=\left[\begin{matrix}-1&0\\\frac{2}{\sqrt N}&1\\\end{matrix}\right]. \end{aligned}\end{split}\]

记 \(\sin{\theta}=\frac{1}{\sqrt N},a=e^{i\theta},\ \ \frac{1}{\sqrt N}=\frac{a-a^{-1}}{2i}\)，于是有

\[\begin{split}\begin{aligned} U_\omega U_s=\frac{1}{a^2+1}\left[\begin{matrix}-i&i\\a&a^{-1}\\\end{matrix}\right]\left[\begin{matrix}a^2&0 \\0&a^{-2}\\\end{matrix}\right]\left[\begin{matrix}i&a\\-a^2i&a\\\end{matrix}\right]. \end{aligned}\end{split}\]

记 \(Q=U_sU_\omega\) ，有 \(Q\left|\varphi\right\rangle=\frac{N-4}{N}\left|\varphi\right\rangle +\frac{2}{\sqrt N}\left|\omega\right\rangle\) ，且

\[\begin{split}Q^k = \frac{1}{a^2+1}\left[\begin{matrix}-i&i\\a&a^{-1}\\\end{matrix} \right]\left[\begin{matrix}a^{2k}&0\\0&a^{-2k}\\\end{matrix}\right]\left[\begin{matrix}i&a\\-a^2i&a\\\end{matrix}\right].\end{split}\]

对 \(\left|\varphi\right\rangle\) 执行量子门 \(Q^k\) 后，测量第一个寄存器得到解量子态 \(\left|\omega\right\rangle\) 的概率为 \(P(\omega)={\langle\omega|Q}^k\left|\varphi\right\rangle=\left[\begin{matrix}\left\langle\omega|\omega\right\rangle &\left\langle\omega|\varphi\right\rangle\\\end{matrix}\right]{{{(U}_sU}_\omega)}^k\left[\begin{matrix}0\\1\\\end{matrix}\right] =\frac{a^{2k+1}-a^{-\left(2k+1\right)}}{2i}=\sin{(\left(2k+1\right)\theta)}\)。

解 \(\left(2k+1\right)\theta=\frac{\pi}{2}\) 可知经过 \(k=[\frac{\pi}{4}\arcsin{\frac{1}{\sqrt N}}-\frac{1}{2}]≈O(N)\)次 \(Q\) 量子门操作后可以通过测量以逼近 \(1\) 的概率得到解 \(\left|\omega\right\rangle\)。

量子线路图与参考代码¶

量子计数算法和Grover算法的核心内容都是振幅放大算子，算法结构分别与QPE和振幅放大量子线路基本一致。

Quantum Counting算法的量子线路图如下所示

Grover算法的量子线路图如下所示

基于QPanda-2.0的实现量子计数算法的过程与QPE过程几乎没有区别，因此源码与Grover算法合并在一起，两种算法的程序实现可以参考 QPanda-2.0下Quantum Counting和Grover算法程序源码。

下面对Grover算法介绍基于QPanda-2.0的一个接口函数和一个样例代码实现。Quantum Counting算法的程序实例不再赘述，与QPE的代码实现没有本质区别。

备注

基于集合 \(\Omega\) 和判别函数 \(f\) 的试验态制备是两种算法共同的重要前置工作，与振幅放大算子一起构成了算法的核心组件。

Grover(data, Classical_condition, QuantumMachine, qlist, data)

输入参数分别为算法搜索空间、搜索条件、量子模拟机、输出结果存储比特以及迭代次数，返还一个可执行的Grover量子线路。 Grover算法还有其他的接口函数，此处不作赘述。

下面是一个一维Grover示例程序代码

#!/usr/bin/env python

import pyqpanda as pq
import numpy as np

if __name__ == "__main__":

   machine = pq.init_quantum_machine(pq.QMachineType.CPU)
   x = machine.cAlloc()
   prog = pq.create_empty_qprog()

   data=[3, 6, 6, 9, 10, 15, 11, 6]
   grover_result = pq.Grover_search(data, x==6, machine, 1)

   print(grover_result[1])

输出结果是查找列表中数值6所在的坐标，应当如下

[1,2,7]

Shor算法¶

Shor算法，又叫质因数分解算法，在破解RSA加密方面有着重要意义。

问题背景¶

已知一个大整数 \(N=pq\)，其中 \(p,q\) 均为未知的质数，求解 \(p,q\)。 Shor算法分为经典算法实现的公约数求解、将质因数分解转化为函数周期求解等部分，以及借助量子傅里叶变换等量子算法实现的函数周期求解共三个部分。

相对经典算法，Shor算法在计算资源耗费和计算时间复杂度两方面均有极大的降低，使经典算法无法求解的超大型质因子分解问题出现了量子算法求解的可能。

备注

Shor算法试图解决的极大比特数RSA问题使用经典算法在理论上所需的计算时间和空间资源是近乎无法满足的，它不再只体现了量子计算的相对优势，而是揭示了特定问题上量子计算的不可取代性和绝对优势。

算法原理¶

Shor分解算法的具体步骤如下：

\(\forall 1<x<N,\ x\in\mathbb{Z}\)；
\(gcd(x,N)\neq 1\)，结束；
求 \(r\) 使得 \(x^r mod N≡1\)；
\(r\ mod\ 2\equiv1\)，回到1取 \(\dot{x}≠x\)；
\(x^\frac{r}{2}\ mod\ N\equiv-1\)，回到1取 \(\dot{x}≠x\)；
\(gcd(x^\frac{r}{2}-1,N)gcd(x^\frac{r}{2}+1,N)=N\)。

式中 \(gcd\) 表示最大公约数（Greatest Common Divisor）。

以上步骤中，难点集中在第三步阶寻找问题。将第三步转化为如下问题，并采用量子算法求解：

记 \(f\left(x\right)=x^a\mathrm{\ mod\ N},f\left(a+r\right)=f\left(a\right)\)，求最小的 \(r\) 。

下面介绍阶寻找问题求解的量子算法的核心内容，主要有三个部分。

公式变形所需的前置引理。
构造出可用的模乘量子门操作以迭代完成阶寻找问题求解。
参考QPE对构造出的模乘求和形式的结果以逆量子傅里叶变换得到 \(x\) 模 \(N\) 的阶 \(r\) 。

限于篇幅，第一部分中的前置引理将只作介绍而不加以证明。

前置引理¶

定义

\[\begin{aligned} \left|u_s\right\rangle\equiv\frac{1}{\sqrt{r}}\Sigma_{k=0}^{r-1}e^{-\frac{2\pi\ iks}{r}}\left|x^k\ mod N\right\rangle,\ x^rmod\ N\equiv1. \end{aligned}\]

引理1：

\[\begin{aligned} \frac{1}{\sqrt{r}}\Sigma_{s=0}^{r-1}e^\frac{2\pi\ iks}{r}\left|u_s\right\rangle=\left|x^k\ modN\right\rangle. \end{aligned}\]

引理2：

\[\begin{aligned} \exists U,U\left|y\right\rangle=\left|xy\ modN\right\rangle,s.t.U\left|u_s\right\rangle=e^\frac{2\pi is}{r}\left|u_s\right\rangle. \end{aligned}\]

引理3：

\[\begin{aligned} \frac{1}{\sqrt{r}}\Sigma_{s=0}^{r-1}\left|u_s\right\rangle=\left|1\right\rangle. \end{aligned}\]

有了引理1、2和3，我们就可以将模指量子态、定义的特殊量子态 \(\left|u_s\right\rangle\)、基态 \(\left|1\right\rangle\) 以及阶 \(r\) 通过量子傅里叶变换/逆变换、\(\left|u_s\right\rangle\) 的定义变换/逆变换全部关联起来。

构造模乘量子门¶

定义量子门操作 \(U^j\left|y\right\rangle=\left|yx^j\ modN\right\rangle\)。

对任给整数 \(Z\)，对其进行 \(t\) 位数二进制展开可知

\[\begin{aligned} U^{2^{t-1}z_{t-1}}U^{2^{t-2}z_{t-2}}\cdots U^{2^0z_0}\left|1\right\rangle\approx\left|1\ast x^z\ modN\right\rangle. \end{aligned}\]

由上式可以利用模乘量子门来实现模指操作。

求解阶寻找问题¶

考察两个寄存器组成的量子态 \(\left|0\right\rangle^{\otimes t}(\left|0\right\rangle^{\otimes L-1} \left|1\right\rangle){=\left|0\right\rangle^{\otimes t}\left|1\right\rangle}_L\)，将第一个寄存器初始化为最大叠加态，有

\[\begin{aligned} (H^{\otimes t}{\otimes I^{\otimes L})(\left|0\right\rangle}^{\otimes t}\left|1\right\rangle_L) =\left|+\right\rangle^{\otimes t}\otimes\left|1\right\rangle_L. \end{aligned}\]

基于量子门操作 \(U^j\) 可以定义受控模乘量子门 \(C-U^j\)。取 \(\left|+\right\rangle^{\otimes t}\) 的第j项作为控制比特对 \(\left|+\right\rangle^{\otimes t}\otimes\left|1\right\rangle_L\) 执行 \(t\) 次 \(C-U^{2^{j-1}}\) 完成受控模指量子门操作，有

\[\begin{split}\begin{aligned} &\prod_{j=1}^{t}\left(C-U^{2^{j-1}}\right)\left(\left|+\right\rangle^{\otimes t}\otimes\left|1\right\rangle_L\right)\\ & =\frac{1}{{\sqrt2}^t}\sum_{j=0}^{2^t-1}\left|j\right\rangle\left|x^j\ modN\right\rangle \\ & =\frac{1}{\sqrt{r2^t}}{\Sigma_{j=0}^{2^t-1}\Sigma}_{s=0}^{r-1}e^\frac{2\pi\ ijs}{r} \left|j\right\rangle\left|u_s\right\rangle=:\left|\psi\right\rangle. \end{aligned}\end{split}\]

对第一个寄存器进行IQFT，有

\[\begin{aligned} ({\rm QFT}^{-1}\otimes I^{\otimes L})\left|\psi\right\rangle=\frac{1}{\sqrt r}\Sigma_{s=0}^{r-1} \left|\frac{2^ts}{r}\right\rangle\left|u_s\right\rangle. \end{aligned}\]

测量第一个寄存器得到任意一个非 \(\left|0\right\rangle\) 量子态，进而有最逼近实数 \(\frac{2^ts}{r}\) 的整数\([\frac{2^ts}{r}]\)，对实数 \(\frac{[\frac{2^ts}{r}]}{2^t}\) 进行连续分数展开得到 \(\frac{s}{r}\)，自然可以获得分母 \(r\)。

此处 \(L=n={[\log}_2N]\)，如果取 \(t=2n+1+[log(2+\frac{1}{2\varepsilon})]\)，那么可以得到二进制展开精度为 \(2n+1\) 位的相位估计结果，且测量得到该结果的概率至少为 \(\frac{1-\varepsilon}{r}\)。一般取 \(t=2n\)。

量子线路图与参考代码¶

Shor算法的量子线路图如下所示

基于QPanda-2.0的Shor算法源码参见QPanda-2.0下Shor算法程序源码，

下面是QPanda-2.0中提供的Shor算法调用接口。

Shor_factorization(int)

输入参数为被质因数分解的大数，返还一个2维list，内容为计算过程是否成功和分解后的质因子对list。

选取 \(N=15\) ，验证Shor的代码实例如下

#!/usr/bin/env python

import pyqpanda as pq

if __name__ == "__main__":

    N=15
    r = pq.Shor_factorization(N)
    print(r)

对 \(15\) 的质因子分解结果应该是 \(15=3*5\) ，所以应当返还算法成功标志和两个质因子 \(3\) 和 \(5\) 。

(True, (3, 5))