摘要：介绍量子计算基本知识（量子比特、二进制表示、操作算符、量子电路图），算符操作（Hadamard门、Oracle算符、Toffoli门和NOT门、AND门和FANOUT门、受控门、相移门），介绍Deutsch-Jozsa算法、Simon's算法、量子傅里叶变换、相位估计算法、周期求解、Order求解、Shor算法、Gorver算法。

一、 基本知识

量子比特

在经典中，低电平状态对应比特|0\rangle，高电平状态对应比特|1\rangle，存储比特的系统称为寄存器。假设有n个比特的寄存器，由于每个比特有2种状态，并且各个比特之间无关联，因此该寄存器有2^n种状态，并且只能处于2^n种中的某一种。假设有3个比特的寄存器，寄存器状态为110，其对应的十进制为6，则可以标记这个寄存器的状态为|1\rangle|1\rangle|0\rangle=|1,1,0\rangle=|6\rangle，表明这个寄存器存着数字6。

在量子中，自旋向上状态对应量子比特|0\rangle=\begin{pmatrix}1\\0\end{pmatrix}，自旋向下对应量子比特|1\rangle=\begin{pmatrix}0\\1\end{pmatrix}，存储量子比特的系统称为量子寄存器。由于量子力学允许状态的叠加，因此量子比特的状态可以是|0\rangle和|1\rangle的叠加态|\psi\rangle=\begin{pmatrix}a\\b\end{pmatrix}，其中a和b满足归一化条件|a|^2+|b|^2=1。假设有n个量子比特的寄存器，当各个量子比特之间无关联时，与经典一样，有2^n种状态，这些状态是基态|i\rangle,i=0,\dots,2^n-1；当量子比特之间发生纠缠时，这n个量子比特就处于基态的叠加态|\psi\rangle=\sum_{i=0}^{2^n-1}c_i|i\rangle，其中c_i需满足\sum_{i=0}^{2^n-1} |c_i|^2=1。

二进制表示

对于数N，存储这个数所需的位数为

n=\begin{cases} 1& \text{if }x=0\\ \lfloor\log_2|N|\rfloor+2 & \text{if }x\neq 0 \end{cases} \\

设有n个量子比特处于基态，它们的状态分别为j_{n-1},j_{n-2},\cdots,j_0\in\{0,1\}，记

j_{n-1}j_{n-2}\cdots j_0=j_{n-1}2^{n-1}+j_{n-2}2^{n-2}+\cdots +j_02^0\\

那么N=j_{n-1}j_{n-2}\cdots j_0就是系统的二进制表示。二进制表示法还可以表示小数

0.j_{n-1}j_{n-2}\cdots j_0=\frac{1}{2^1}j_{n-1}+\frac{1}{2^2}j_{n-2}+\cdots +\frac{1}{2^n}j_0\\

有关系j_{n-1}j_{n-2}\cdots j_0=2^n\times 0.j_{n-1}j_{n-2}\cdots j_0，因此乘以2^n表示向左移n位，除以2^n表示向右移n位。寄存器的状态一般用整数二进制表示，而相位一般用小数二进制表示。

操作算符

量子力学要求操作算符（或逻辑门）为酉算符U，酉算符定义为

U^\dagger U=I\\

其中^\dagger符号是取共轭（或者对偶），即转置复共轭。根据定义，酉算符输入输出的量子比特数相等。经典中的逻辑和、逻辑或都不是酉算符，因为输入为2个量子比特，而输出为1个量子比特；需要增加辅位来使得逻辑和以及逻辑或为酉算符。

量子电路图

以下为常见的量子电路图器件符号。默认为左边为输入，右边为输出。

（1）黑箱门。由方块加文字表述，|a\rangle为输入，|b\rangle为输出。图中举例为Hadamard门，也可以为其他门，如O_f等。

（2）测量门。由圆形、\mathcal M字和双实线表述，|a\rangle为叠加态，|b\rangle为测量结果。

（3）扇出门。由黑色实点连接，|a\rangle为输入，|b\rangle和|c\rangle为输出，有|b\rangle=|c\rangle=|a\rangle，输出可以被|0\rangle态拉低。

（4）异或门。由十字圈连接的T形结构，|a\rangle和|b\rangle为输入，输出|c\rangle=|a\oplus b\rangle。异或门可以看成是简单的控制非门，即把其中一个输入看成控制位，那么这个控制位为真则数据位（另一个位）取反。

（5）非门。由十字圈连接的一形结构，|a\rangle为输入，|b\rangle为输出。非门可以看成是特殊的异或门，即控制位恒为真，使得数据位取反。

（6）受控非门（CNOT门)。|a\rangle为控制位，|b\rangle为数据位；与异或门不同在于，它输入输出量子比特数均为2.

（7）受控控制非门(Toffoli门或CCNOT门)，也可以采用黑箱表述。|a\rangle和|b\rangle为控制位，|c\rangle为数据位，输出为|c\oplus(a\wedge b)\rangle。与CNOT的不同在于，它仅有所有控制位均为真时，数据位才取反。

（8）相位估计系统。核心部分为一个刷子（所在为控制位|k\rangle）和一个黑箱U（所在为数据位|\psi\rangle）的结构，结果为作用k次U于|\psi\rangle。用公式表达即

\Lambda_m(U)|k\rangle|\psi\rangle=|k\rangle(U^k|\psi\rangle)

二、 操作算符

Hadamard门

哈达玛门是量子计算中最基本的门之一，其矩阵形式为

H=\frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\ 1 & -1 \end{pmatrix} \\

对于单个量子比特，有性质

H|0\rangle=|+\rangle,H|+\rangle=|0\rangle\\ H|1\rangle=|-\rangle,H|-\rangle=|1\rangle\\

其中加态|+\rangle=\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)，减态|-\rangle=\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)。性质总结为哈达玛门连续作用两次后量子比特不变。

对于n个量子比特|x\rangle，经过归纳总结，有性质

H^{\otimes n}|x\rangle=\frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}(-1)^{x\cdot y}|y\rangle\\

其中x\cdot y=x_1y_1+\cdots +x_ny_n(\mod 2)为模2内积（伽罗瓦域内积）。性质总结为哈达玛门可以使n量子寄存器从基态变为等振幅的叠加态，该性质常常用来作为量子计算的预处理。变为叠加态后，一个操作就可以对叠加态中的所有状态|y\rangle进行操作。

Oracle算符

Oracle算符（记为O_f，U_f或B_f）是一个函数黑盒（Black box），其定义为

O_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle\\

其中\oplus是按位异或。其作用是利用叠加态，使用一次Oracle算符就可以对大量基态进行运算。

当|y\rangle是|-\rangle态时，由于\textbf{phase kick-back}作用：|-\oplus x\rangle=(-1)^x|-\rangle，因此

O_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle\\

Toffoli门和NOT门

Toffoli门称为受控控制门，或CCNOT门；它有3位输入和输出；如果前两位都设置为1，则它反转第三位，否则所有位保持不变。Toffoli门和NOT门是构造量子电路的基本门。Toffoli门的定义为

T|a\rangle|b\rangle|c\rangle=|a\rangle|b\rangle|c\oplus(a\wedge b)\rangle\\

其中a,b,c\in\{0,1\}，符号\wedge是逻辑与，符号\oplus是按位异或。

NOT门称为非门，它是泡利矩阵的x分量\sigma_x，其矩阵形式为

NOT=\begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix} \\

AND门和FANOUT门

经典中的AND门和FANOUT门（扇出门，即复制一个量子态）都不是酉算符，因此需要添加辅位；我们用Toffoli门和NOT门来实现它们，如下图所示。

受控门

当为量子比特|0\rangle时，起响应的门是Z_0=\begin{pmatrix}1&0\\0&0\end{pmatrix}门；当为量子比特|1\rangle时，起响应的门是Z_1=\begin{pmatrix}0&0\\0&1\end{pmatrix}门；起响应是指作用到对应的状态时，量子态不变，作用到非对应状态时，量子态为零向量；这个性质用数学表达即Z_a|b\rangle=\delta_{a,b}|b\rangle，其中a,b\in\{0,1\}.

受控门的作用是当且仅当所有控制位为|1\rangle时，数据位才受到U门的作用。设前n个为控制位，分别记为j_1,j_2,\cdots,j_n，最后一个为数据位，则表达式为

C-U(j_1,j_2,\cdots,j_n)=\left( \bigotimes_{a=0}^{2^n-1} Z_{a_i}\right)\otimes U^{\delta_{a,2^n-1}}=\begin{pmatrix} I & 0\\ 0 & U \end{pmatrix} \\

当仅有一个控制位和数据位时，受控门表达式为

C-U(j_1)=Z_0\otimes I+Z_1\otimes U= \left( \begin{array}{c|c} \begin{matrix} 1&0\\ 0&1 \end{matrix}& \begin{matrix} 0&0\\ 0&0 \end{matrix} \\ \hline \begin{matrix} 0&0\\ 0&0 \end{matrix}& \large U \end{array} \right) \\

相移门

相移门可以使量子比特的|1\rangle移动\phi相位，而|0\rangle保持不变，其定义为

R_\phi=\begin{pmatrix} 1 & 0\\ 0 & e^{i\phi} \end{pmatrix} \\

在量子傅里叶变换里，使用的是它的某种特殊形式

R_k=\begin{pmatrix} 1 & 0\\ 0 & e^{2\pi i/2^k} \end{pmatrix} \\

如果考虑控制位为j_m\in \{0,1\}的受控相位门

R_\phi(j_m)=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&e^{i\phi}\end{pmatrix} \\

那么相移因子可以综合表达为\exp(i\phi j_m)，这个结论在量子傅里叶变换里使用到。

三、 Deutsch-Jozsa算法

Deutsch-Jozsa算法是第一个体现量子计算优越性的算法，但算法本身并没有实际用途。考虑一个函数映射f:\{0,1\}^n\to \{0,1\}，且已知这个函数只能是下面两种中的一种：

• 我们称f为\textbf{constant}的，是指\forall x\in\{0,1\}^n有f(x)\equiv 0或f(x)\equiv 1.
  
• 我们称f为\textbf{balanced}的，是指函数值为0和1的自变量个数相等，即|\{x\in\{0,1\}^n:f(x)=0\}|=|\{x\in\{0,1\}^n:f(x)=1\}|=2^{n-1} \\

我们的任务是判断一个函数是constant还是balanced的。

考虑经典的情况。假如这个函数是balanced的，则只要发现两个不同自变量的函数值不同，就可以断言这个函数是balanced的，最坏的情形需要查询函数2^{n-1}+1次；假如这个函数是constant的，则在2^{n-1}次查询以前，都不能断言这个函数是constant的（有可能是balanced的），因此最坏需要查询函数2^{n-1}+1次。故经典复杂度渐进下界为\Omega(2^n)。

考虑如上量子电路图。

|\psi_1\rangle=|0^n\rangle|1\rangle

|\psi_2\rangle=H^{\otimes n}|0^n\rangle \otimes H|1\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}|x\rangle|-\rangle

|\psi_3\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}B_f|x\rangle|-\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{f(x)}|x\rangle|-\rangle

|\psi_4\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in \{0,1\}^n}(-1)^{f(x)}H^{\otimes n}|x\rangle=\sum_{y\in\{0,1\}^n}\left(\frac{1}{2^n}\sum_{x\in\{0,1\}^n}(-1)^{f(x)+x\cdot y} \right)|y\rangle

我们考虑测量结果为|0^n\rangle的情形，计算概率

P\left(|y\rangle=|0^n\rangle\right)=\left|\frac{1}{2^n}\sum_{x\in\{0,1\}^n}(-1)^{f(x)}\right|^2

当函数为balanced的，则概率P=0，表明不可能观测到|y\rangle=|0^n\rangle态，表明观测到的|y\rangle中至少有一个量子比特为|1\rangle.
当函数为constant的，则概率P=1，表明观测到的必然为|y\rangle=|0^n\rangle态。

因此，只需要一次测量就可以断言函数是balanced的还是constant的：当观测到|0^n\rangle时，函数必然为constant的，否则为balanced的。

四、Simon's算法

Simon's Algorithm是比Deutsch-Jozsa算法更接近真实世界问题的算法，它是一个搜索算法。给定一个函数映射f:\{0,1\}^n\to \{0,1\}^n，并且我们已知这个函数必然为以下其中一种：

• f是单射函数。
  
• f不是单射函数，且存在串s\neq 0^n，对于满足x\oplus y=s的\forall x,y\in \{0,1\}^n，有f(x)=f(y).
  

我们的任务是判断f是否为单射函数，若不是，则返回串s。

考虑经典做法。由于串s的长度为n，因此串s的搜索空间为\{0,1\}^n，我们使用某k个自变量x_1,\cdots,x_k\in\{0,1\}^n张起的集合\{x_i\oplus x_j:i,j\in\{1,\cdots,k\}\}来覆盖\{0,1\}^n集合，因此有

\begin{pmatrix}k\\2\end{pmatrix}\geq 2^n \\

解得需要查询k\sim \mathcal O(\sqrt{2^n})次。这里是哪k个自变量x_1,\cdots,x_k，有特定的算法可以找到，不影响查询复杂度。

类似Deutsch-Jozsa算法，考虑如上量子电路图。

|\psi_1\rangle=|0^n\rangle|0^n\rangle

|\psi_2\rangle=H^{\otimes n}|0^n\rangle|0^n\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|0^n\rangle

|\psi_3\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}B_f|x\rangle|0^n\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle|f(x)\rangle

|\psi_4\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}H^{\otimes n}|x\rangle|f(x)\rangle=\sum_{y\in\{0,1\}^n}|y\rangle\left(\frac{1}{2^n}\sum_{x\in\{0,1\}^n}(-1)^{x\cdot y}|f(x)\rangle\right)

我们测量前n个量子比特。因为是部分测量，所以|y\rangle对应的系数为叠加态而不是常数。我们计算坍缩到|y\rangle态的概率。

先考虑f是单射函数的情形，因为x\neq y \Leftrightarrow f(x)\neq f(y)，因此\{|f(x)\rangle:x\in\{0,1\}^n\}构成了一组完备基，概率

P\left(|y\rangle \Big| s=0^n\right)=\sum_{x\in\{0,1\}^n}\left|\frac{1}{2^n}(-1)^{x\cdot y}\right|^2=\frac{1}{2^n} \\

考虑f不是单射函数，记f的值域Z。对于\forall z\in Z，\exists x,x'\in\{0,1\}^n,x\neq x'，满足f(x)=f(x')=z，因此x、x'和z三者一一对应；又由于s\oplus x=x'\Leftrightarrow s\oplus x'=x，因此s\oplus是单射；因此存在集合\{x_i\}和\{x'_i\}，满足\{x_i\}\cup\{x'_i\}=\{0,1\}^n,\{x_i\}\cap\{x'_i\}=\emptyset且|\{x_i\}|=|\{x'_i\}|，集合Z的大小为|Z|=|\{z_i\}|=|\{x_i\}|=2^{n-1}。由于\{|z\rangle\}是完备基，因此概率

\begin{aligned} P\left(|y\rangle\Big|s\neq 0^n\right) &=\left| \frac{1}{2^n}\sum_{z\in Z}\left((-1)^{x\cdot y}+(-1)^{x'\cdot y}\right)|z\rangle\right|^2\\\\ &= \sum_{z\in Z}\left|\frac{1}{2^n}\left((-1)^{x\cdot y}+(-1)^{(s\oplus x)\cdot y}\right)\right|^2\\\\ &=\sum_{z\in Z}\left| \frac{1}{2^n}(-1)^{x\cdot y}\left(1+(-1)^{s\cdot y}\right)\right|^2\\\\ &= \begin{cases} 2^{-(n-1)}& \text{if }s\cdot y=0\\ 0& \text{if }s\cdot y=1 \end{cases} \end{aligned} \\

结合两种情况，记\delta\approx2^{-n}>0

P(|y\rangle)= \begin{cases} \delta& \text{if }s\cdot y=0\\ 0 & \text{if }s\cdot y=1 \end{cases} \\

表明测量|y\rangle，只能得到与s正交的y。我们测量n-1次，得到y_1,\cdots,y_{n-1}，意味着得到一个线性方程组，只不过这里的内积为模2内积。

\begin{cases} \begin{aligned} y_1\cdot s&=0\\ y_2\cdot s&=0\\ &\vdots\\ y_{n-1}\cdot &s=0 \end{aligned} \end{cases} \\

若y_1,\cdots,y_{n-1}恰好是线性无关的，则解这n-1个方程可得到s的一个非零解s'。我们取x=0^n，因此x'=s'\oplus x=s'；若f(0^n)=f(s')，表明f不是单射，因此s'就是所求的串s；若f(0^n)\neq f(s')，则f是单射，因此s=0^n。

下面我们计算测量n-1次得到线性无关的y_1,\cdots,y_{n-1}的概率。显然我们不希望y=0^n，因为这对于方程组来说是无意义的；因此第一次有效测量的概率是P_1=\frac{2^n-1}{2^n}；对于第二次测量，我们不希望再得到0^n和y_1，因此P_2=\frac{2^n-2}{2^n}；对于第三次测量，我们不希望y_3与\{y_1,y_2\}线性相关，即y_3\notin span\{y_1,y_2\}，由于|span\{y_1,y_2\}|=2^2，因此P_3=\frac{2^n-2^2}{2^n}；……；对于第n-1次测量，y_{n-1}\notin span\{y_1,\cdots y_{n-2}\}，|span\{y_1,\cdots y_{n-2}\}|=2^{n-2}，因此P_n=\frac{2^n-2^{n-2}}{2^n}；因此测量n-1次得到线性无关的y_1,\cdots,y_{n-1}的概率为

P=\prod_{i=1}^{n-1}P_i=\prod_{i=1}^{n-1}\left(1-\frac{1}{2^{n-i+1}}\right)>2\prod_{i=1}^{\infty}\left(1-\frac{1}{2^k}\right)=0.57758 \\ 可以估算，重复12次的n-1次的测量，可以使得线性独立的概率提高到99.996\%以上，因此西蒙斯算法的复杂度为\mathcal O(n)。

五、 量子傅里叶变换

经典傅里叶变换的计算采用的是变换系数的方式，而量子傅里叶变换（对应经典的IDFT而不是DFT）采用的是变换基底的方式。假设有量子态|\psi\rangle=\sum_j f(j)|j\rangle，经过傅里叶变换后的态为|\widetilde\psi\rangle=F|\psi\rangle=\sum_k\widetilde f(k)|k\rangle，记\omega=e^{\frac{2\pi i}{N}}，则变换系数的方式为

|\widetilde{\psi}'\rangle=F'|\psi\rangle=\sum_kF'[f(j)]|k\rangle=\frac{1}{\sqrt{N}}\sum_k\left( \sum_j \omega^{jk}f(j)\right)|k\rangle\\

变换基底的方式为

|\widetilde{\psi}\rangle=F|\psi\rangle=\sum_jf(j)F[|j\rangle]=\frac{1}{\sqrt{N}}\sum_jf(j)\left(\sum_k\omega^{jk}|k\rangle \right)\\

可以发现|\widetilde{\psi}'\rangle=|\widetilde{\psi}\rangle，即变换系数方式和变换基底方式本质上相同。由于F是线性操作，因此可以实线对叠加态|\psi\rangle一次操作来实现经典需要的n次操作；量子傅里叶变换的核心是实线F[|j\rangle]操作，我们先用二进制k_{n-1}k_{n-2}\cdots k_0表示k，然后用二进制j_{n-1}j_{n-2}\cdots j_0表示j得到

\begin{aligned} F[|j\rangle]=&\frac{1}{\sqrt{2^n}}\sum_{k_{n-1}=0}^1\sum_{k_{n-2}=0}^1\cdots \sum_{k_{0}=0}^1 \omega^{j(k_{n-1}2^{n-1}+k_{n-2}2^{n-2}+\cdots+k_02^0)}|k_{n-1}\rangle||k_{n-2}\rangle\cdots|k_0\rangle\\\\ =&\left(\frac{1}{\sqrt{2}}\sum_{k_{n-1}=0}^1\omega^{jk_{n-1}2^{n-1}}|k_{n-1}\rangle\right)\otimes\left(\frac{1}{\sqrt{2}}\sum_{k_{n-2}=0}^1\omega^{jk_{n-2}2^{n-2}}|k_{n-2}\rangle\right)\otimes\cdots\otimes\left(\frac{1}{\sqrt{2}}\sum_{k_{0}=0}^1\omega^{jk_{0}2^{0}}|k_{0}\rangle\right)\\\\ =&{\bigotimes_{i=n-1}^{0}} \frac{1}{\sqrt{2}}\left( |0\rangle+e^{\frac{2\pi i}{2^n}j2^i}|1\rangle\right)\\\\ =&\bigotimes_{i=n-1}^0\frac{1}{\sqrt{2}}\left( |0\rangle+e^{2\pi i\times j_{n-1}\cdots j_{n-i}\cdot j_{n-i-1}\cdots j_{0}}|1\rangle\right)\\\\ =&\bigotimes_{i=0}^{n-1}\frac{1}{\sqrt{2}}\left( |0\rangle+e^{2\pi i\times 0\cdot j_i\cdots j_{0}}|1\rangle\right) \end{aligned}

上式表明量子傅里叶变换后的各个量子比特之间不相互纠缠，因此可以分别制备各个量子比特来实现量子傅里叶变换。以制备|0\rangle+e^{2\pi i\times 0\cdot j_i\cdots j_0}|1\rangle态为例，由于有性质

\frac{1}{\sqrt{2}}\left(|0\rangle+e^{2\pi i\times 0\cdot j_i}|1\rangle\right)=\frac{1}{\sqrt{2}}\left(|0\rangle+(-1)^{j_i}|1\rangle\right)=H|j_i\rangle\\

因此

\begin{aligned} \frac{1}{\sqrt{2}}\left(|0\rangle+e^{2\pi i\times 0\cdot j_i\cdots j_0}|1\rangle\right)= &|0\rangle+\prod_{k=2}^{i+1} \exp\left(\frac{2\pi i}{2^k}j_{i+1-k}\right)(-1)^{j_i}|1\rangle\\\\ =&R_{i+1}(j_0)R_i(j_1)\cdots R_2(j_{i-1})H|j_i\rangle \end{aligned} \\

根据上式，i=0对应原最高位，傅里叶变换后的此位需要|j_0\rangle制备，QFT的量子电路实现如下图所示；寄存器|j\rangle的顺序和寄存器|k\rangle的最高位到最低位的顺序相反，如果要对应起来，最后应当使用交换电路。

由于第i(i=0,1,\cdots,n-1)个量子比特需要i+1个逻辑门，因此总共需要的逻辑门数量为

1+2+\cdots+n=\frac{n(n+1)}{2}\\

由上式可知，量子QFT仅需要\mathcal O(n^2)次操作，对比经典DFT需要\mathcal O(n2^n)次操作，可知量子傅里叶变换相比经典傅里叶变换有指数级优势。

值得一提的是，量子傅里叶变换得出的往往是叠加态|\widetilde\psi\rangle=\sum_k\widetilde f(k)|k\rangle，因此我们不可直接获取结果；此外，由于输入一般也是叠加态|\psi\rangle=\sum_j f(j)|j\rangle，因此往往也难以制备输入。

六、 相位估计算法

phase-estimation的目的是求操作算符U的本征值\lambda（给定本征态|\psi\rangle），由于U是幺正算符，不难证明\lambda^*\lambda=1，因此本征值可以写成\lambda=e^{i 2\pi\theta}的形式，其中\theta\in \mathbb R称为本征值\lambda的相位，我们把\theta写成j/2^m，相位估计就是求j\in\{0,1\}^m.

相位估计中用到\Lambda_m(U)算符（就是|\psi_2\rangle到|\psi_3\rangle的变换），其定义为

\Lambda_m(U)|k\rangle|\psi\rangle=|k\rangle(U^k|\psi\rangle)\\

\Lambda_m(U)算符可以用多个受控U^{2^j},j=0,1,\cdots,m-1门实现。量子电路如下图所示，其中|\psi\rangle为算符U的本征态，即满足U|\psi\rangle=e^{i2\pi \theta}|\psi\rangle。记\omega=e^{2\pi i/2^m}

|\psi_1\rangle=|0^m\rangle|\psi\rangle

|\psi_2\rangle=H^{\otimes m}|0^m\rangle|\psi\rangle=\frac{1}{\sqrt{2^m}}\sum_{k=0}^{2^m-1}|k\rangle|\psi\rangle

|\psi_3\rangle=\frac{1}{\sqrt{2^m}}\sum_{k=0}^{2^m-1}\Lambda_m(U)|k\rangle|\psi\rangle=\frac{1}{\sqrt{2^m}}\sum_{k=0}^{2^m-1}e^{i2\pi k\theta}|k\rangle|\psi\rangle

|\psi_4\rangle=\frac{1}{\sqrt{2^m}}\sum_{k=0}^{2^m-1}\omega^{jk}F^\dagger|k\rangle=\frac{1}{2^m}\sum_{k'=0}^{2^m-1}\sum_{k=0}^{2^m-1}\omega^{k(j-k')}|k'\rangle=\sum_{k'=0}^{2^m-1}\delta_{j,k'}|k'\rangle=|j\rangle

其中\frac{1}{N}\sum_ke^{2\pi i\frac{k(j-k')}{N}}=\delta_{j,k'}是因为当j\neq k'时，环\mathbb Z_N上生成的理想\langle j-k' \rangle=\{k(j-k'):k\in \mathbb Z_N\}是主理想整环，因此求和为零；当j=k'时显然；因此得证。

通过测量|\psi_4\rangle就可以测量j的数值，然后通过\theta=j/2^m计算相位。但上述过程是假设\theta=j/2^m,j=0,1,\cdots,2^m-1得出的，若\theta不符合这个假设，则需要分析这个假设带来的影响，此时

|\psi_4'\rangle=\frac{1}{\sqrt{2^m}}\sum_{k=0}^{2^m-1}e^{2\pi ik\theta}F^\dagger|k\rangle=\frac{1}{2^m}\sum_{k=0}^{2^m-1}\sum_{k'=0}^{2^m-1}e^{2\pi ik(\theta-k'/2^m)}|k'\rangle=\sum_{k'=0}^{2^m-1}\left(\frac{1}{2^m}\sum_{k=0}^{2^m-1}e^{2\pi ik(\theta-k'/2^m)} \right)|k'\rangle\\

记\varepsilon=\theta-k'/2^m，由于\theta的最小间隔为\frac{1}{2^m}，因此\varepsilon\leq |\frac{1}{2^{m+1}}|。由于\theta\neq j/2^m,j\in \mathbb Z_{2^m}，因此\varepsilon \notin \mathbb Z，故\sum_ke^{2\pi ik\varepsilon}是等比级数。

P_{k'}(\varepsilon,m)=\left|\frac{1}{2^m}\sum_{k=0}^{2^m-1}e^{2\pi ik(\theta-k'/2^m)} \right|^2=\left| \frac{1}{2^{m}}\frac{e^{2\pi i\varepsilon 2^m}-1}{e^{2\pi i\varepsilon}-1}\right|^2=\left| \frac{1}{2^m}\frac{\sin (\pi \varepsilon 2^m)}{\sin (\pi \varepsilon)}\right|^2 \\

可以证明，P_{k'}(\varepsilon,m)随两个自变量都单调递减，且显然有下界0，因此P_{k'}(\varepsilon,m)有下确界

\lim_{m\to \infty}P_{k'}(\frac{1}{2^{m+1}},m)=\frac{4}{\pi^2}\approx 0.405285>0 \\ 此外，P_{k'}(\varepsilon,m)有上确界

\lim_{\varepsilon\to 0}P_{k'}(\varepsilon,1)=1 \\

以上结果表明，无论\theta服从什么分布，均有较高概率以2^{-(m+1)}为误差容限得到相位\theta的估计值。

七、 周期求解

周期求解问题，即给定一个周期函数f:\{0,1\}^n\to \{0,1\}^m，已知f自变量x_i和因变量y_i，求函数f的周期r。

算法的核心是利用傅里叶变换获得周期，量子电路图如下图所示。

|\psi_1\rangle=B_fH^{\otimes n}|0^n\rangle|0^m\rangle=\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle|f(x)\rangle\\

设第一次测量测得寄存器的值为f(x_0)，由于函数周期为r，因此有d=N/r个点的函数值为f(x_0)，设这些点中自变量最小的为x_0，因此这些点分别为f(x_0+jr),j=0,1,\cdots,d-1.由于为部分测量，因此结果应当归一化。

|\psi_2\rangle=\mathcal M |\psi_1\rangle=\frac{\sum_{j=0}^{d-1}|x_0+jr\rangle|f(x_0)\rangle}{\left\| \sum_{j=0}^{d-1}|x_0+jr\rangle|f(x_0)\rangle\right\|}\\

丢弃第二个寄存器，对第一个寄存器进行量子傅里叶变换。记N=2^n为自变量个数，由于

\begin{aligned} F[|x_0+jr\rangle]=&\frac{1}{\sqrt r}\sum_{k=0}^{r-1}\exp{\left(2\pi i\frac{(x_0+jr)k}{r}\right)}\large|k\frac{N}{r}\rangle\\\\ =&\frac{1}{\sqrt r}\sum_{k=0}^{r-1}\exp{\left(2\pi i\frac{x_0k}{r}\right)}\large|k\frac{N}{r}\rangle \end{aligned} \\

即傅里叶变换的结果与j无关，因此

|\psi_3\rangle=\frac{\sum_{j=0}^{d-1}F[|x_0+jr\rangle]}{\left\|\sum_{j=0}^{d-1}|x_0+jr\rangle\right\|}=\frac{1}{\sqrt r}\sum_{k=0}^{r-1}\exp{\left(2\pi i\frac{x_0k}{r}\right)}\large|k\frac{N}{r}\rangle \\

以上结果表明，第二次测量得到的值符合kN/r,k=0,1,\cdots,r-1分布，并且每个可能的值是等概率的，分布与第一次测量的值无关。假设测量得到的值为c，则有

\frac{c}{N}=\frac{k}{r} \\

由于r

因此测量t次得到c_i,i=1,2,\cdots,t，计算出c_i/N的约化分数，记这些约化分数的分母为r_i，则所求周期r=\max (r_i)。

下面进一步分析需要测量多少次才能保证算法的正确性。

记\phi(n)为Euler's totient function，其定义为小于n的且与n互质的正整数的个数，则有性质（Hardy and Wright 1979, Theorem 328）

\phi(n)/n>\delta/\log \log n为某一常数

\phi(r)/r代表k/r为约化分数的概率，即c/N的约化分数的分母为r的概率，此概率P\sim 1/\log \log r.

只需测量1/P\sim \mathcal O(\log \log r)次，即可保证有较高的概率取样得到r，因此周期求解算法的复杂度为\mathcal O(\log \log r)。

八、 Order求解

记\mathbb Z_N^\star=\{z\in \mathbb Z_N:\gcd(z,N)=1\}，对于a\in Z_N^\star，考虑模N指数函数f(n)=a^n(\text{mod} N),n\in \mathbb N，因为a^n(\text{mod} N)\in \mathbb Z_N且f(0)=1，因此必然存在最小的r\in \mathbb N^+使得f(r)=f(0)，又由于a^{r+s}(\text{mod} N)=(nN+1)a^s(\text{mod} N)=a^s(\text{mod} N)，因此r是f(n)的最小正周期。

称满足a^r\equiv 1(\text{mod} N)的最小正整数r为a在模N运算下的Order.

我们使用周期求解的方法来求f(n)的最小正周期r。最重要的是要获取|\psi_1\rangle态

|\psi_1\rangle=\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle|a^x(\text{mod} N)\rangle \\

因为有性质a^n(\text{mod} N)=a*a^{n-1}(\text{mod} N)，因此关键算符是

M_a|x\rangle=|ax(\text{mod} N)\rangle\\

将M_a作用k次到|1\rangle态来得到|a^k(\text{mod} N)\rangle，这个可以使用\Lambda(M_a)算符来实现。获取|\psi_1\rangle态的过程为

\begin{aligned} \Lambda(M_a)H^{\otimes n}|0\rangle|1\rangle=&\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\Lambda(M_a)|x\rangle|1\rangle\\\\ =&\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle (M_a^x|1\rangle)\\\\ =&\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle |a^x(\text{mod} N)\rangle \end{aligned} \\

给定数N，对于数a\in \mathbb Z_N^\star，可以通过上述算法计算a在模N下的Order。

记寄存器的位数为l，则Schnhage-Strassen算法进行乘法运算的复杂度为\mathcal O(l\log l\log\log l)，即M_a运算的复杂度为\mathcal O(l\log l\log\log l)，而\Lambda(M_a)由\mathcal O(l)个M_a^{2_j}门组成，因此电路单次运算的需要\mathcal O(l^2\log l\log\log l)次运算，又由于周期求解复杂度为\mathcal O(\log\log r)< \mathcal O(\log l)，因此Order求解复杂度为\mathcal O(l^2(\log l)^2\log\log l).

九、 Shor算法

Shor算法是量子计算中最重要的算法之一，它可以在多项式复杂度下进行质因数分解，因此撼动了密码学的根基，研究量子计算机的主要目的之一就是质因数分解。质因数分解的典型思路为：

给定待分解的整数N，寻找它的因子u，使得N分解为u和v=N/u的乘积，然后对u和v进行分解……直至最后不可分解。

上述算法的关键是寻找N的因子u，而辗转相除法是求公因子的有效算法，它的复杂度仅为\mathcal O(\log n)。因此我们需要随机选取一个数a\in\{2,3,\cdots,N-1\}，计算d=\gcd (a,N)，若d>1有因子d，否则表明a\in \mathbb Z_N^\star；因此我们可以计算a在模N下的Order，记为r，此时有N \big| (a^r-1)；若r为偶数，则进一步有N\big|(a^{r/2}+1)(a^{r/2}-1)，由于r是最小的正周期，因此不可能有N\big|(a^{r/2}-1)；记s=\gcd(a^{r/2}-1,N)，若s=1，则表明a^{r/2}-1不包含N的因子，此时分解完全；若s>1即是N的因子。

综上，算法的步骤为

Randomly choose a\in\{2,3,\cdots,N-1\}

Compute d=\gcd (a,N)

If d>1 then

Return u=d and v=N/u

Else

Compute r=Order(a)

If r is even

Compute s=\gcd(a^{r/2}-1,N)

If s>1

Return u=s and v=N/u

Else

Return

在上述算法中，辗转相除法的复杂度为\mathcal O(\log N)=\mathcal O(l)，Order求解复杂度为\mathcal O(l^2(\log l)^2\log\log l)<\mathcal O(l^3)，因此Return一次的复杂度为\mathcal O(l^3)，Shor算法的复杂度为\text{polynomial}(l)。

十、 Gorver算法

给定映射f:\{0,1\}^n\to \{0,1\}，记集合A=\{x\in\{0,1\}^n:f(x)=1\}，记集合B=\{x\in\{0,1\}^n:f(x)=0\}，Gorver算法的目的是求出集合A。由于为无结构化数据，经典算法需要\mathcal O(2^n)的复杂度，而Gorver算法使用了量子并行搜索的策略，它的复杂度仅为\mathcal O(\sqrt{2^n})，在n较大的情况下，Gorver算法加速效果显著。

Gorver算法是在空间\text{span}(|B\rangle,|A\rangle)进行的，其中

|A\rangle\equiv \frac{1}{\sqrt{|A|}}\sum_{x\in A}|x\rangle,\quad |B\rangle=\frac{1}{\sqrt{|B|}}\sum_{x\in B}|x\rangle\\

记等权全叠加态为|S\rangle，则有

|S\rangle\equiv H^{\otimes n}|0^n\rangle=\frac{1}{\sqrt{2^n}}\sum_{x\in\{0,1\}^n}|x\rangle=\sqrt{\frac{|A|}{N}}|A\rangle+\sqrt{\frac{|B|}{N}}|B\rangle\\

因此Gorver算法需要实现变换M:|S\rangle\to |A\rangle，由于波函数是归一的，因此这种变换是旋转变换。为表述方便，我们使用与\text{span}(|B\rangle,|A\rangle)同构的复平面空间，将实部对应到|B\rangle，虚部对应到|A\rangle，则

M=e^{i(\pi/2-\theta)},\quad \theta=\sin^{-1}\sqrt{\frac{|A|}{N}}\\

由于有性质B_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle，因此对于x\in A有B_f:|x\rangle\to -|x\rangle，而对于x\in B仍保持B_f:|x\rangle\to |x\rangle，这表明B_f变换对应了复共轭变换，复共轭变换是以|B\rangle为对称的镜像变换，即B_f:e^{i\varphi}\to e^{-i\varphi}。

假设关于|S\rangle有一镜像变换D，那么D:e^{i\varphi}\to e^{i(2\theta-\varphi)}。由于DB_f:e^{i\varphi}\to e^{i(\varphi+2\theta)}，表明DB_f=e^{i2\theta}，又由于|A|\ll N，因此\theta\approx \sqrt{\frac{|A|}{N}}为一小量，表明我们可以使用\lfloor\frac{\pi}{4\theta}\rfloor个DB_f变换来近似M变换。

所谓镜像变换，即平行于镜面的分量保持不变，而垂直于镜面的分量反号。记一般的镜像变换为\mathcal D，镜面为矢量|S_{//}\rangle，镜面法向量为|S_{\perp}\rangle，则有\mathcal D[\alpha|S_{//}\rangle+\beta|S_{\perp}\rangle]=\alpha|S_{//}\rangle-\beta|S_{\perp}\rangle，因此得到

\begin{cases} \mathcal D|S_{//}\rangle=|S_{//}\rangle \\ \mathcal D|S_{\perp}\rangle=-|S_{\perp}\rangle \end{cases}\quad \Rightarrow \mathcal D=|S_{//}\rangle\langle S_{//}|-|S_{\perp}\rangle\langle S_{\perp}| \\

又由于I=|S_{//}\rangle\langle S_{//}|+|S_{\perp}\rangle\langle S_{\perp}|，因此\mathcal D=2|S_{//}\rangle\langle S_{//}|-I，故D的具体表达式为

\begin{aligned} D=&2|S\rangle\langle S|-I\\ =&2(H^{\otimes n}|0^n\rangle\langle 0^n|H^{\otimes n})-H^{\otimes n}IH^{\otimes n}\\ =&H^{\otimes n}(2|0^n\rangle\langle 0^n|-I)H^{\otimes n} \end{aligned}\\

如果|A|已知，那么M\approx (DB_f)^{\lfloor\frac{\pi}{4\theta}\rfloor}，由M近似引起的误差阈值为\Delta k_M=\theta，因此获得正确|A\rangle的概率P\left( |A'\rangle=|A\rangle \right)>\cos\theta

如果|A|估计出现偏差\Delta A，满足\Delta A\ll |A|\ll N，根据误差传递\Delta k_A=\frac{\pi\Delta \theta}{4\theta^2}=\frac{\pi\Delta A}{8\theta A}，进一步假设\Delta A\gg \theta^2 |A|，则可以认为|A|估计引起的误差远大于M近似引起的误差，因此\Delta k=\sqrt{(\Delta k_A)^2+(\Delta k_M)^2}\approx \frac{\pi\Delta A}{8\theta A}，因此获得正确|A\rangle的概率P\left( |A'\rangle=|A\rangle \right)>\cos\left(\frac{\pi\Delta A}{8A}\sqrt{\frac{N}{A}}\right)

如果|A|未知，则k无法计算，由于P\left( |A'\rangle=|A\rangle \right)=\sin^2\left(\left(2k+1\right)\theta\right)，不同的k会导致概率值不同，不好的k值甚至会使概率达到零，因此需要依次尝试不同的k值。由于k\in\{1,2,\cdots,\lfloor\frac{\pi}{4}\sqrt{N}\rfloor\}，因此原则上最多需要运行\Omega(\sqrt N)次Grover算法，最多查询\Omega (N)次B_f，与经典相同。为了使得最多只有\Omega (\sqrt N)次查询B_f，我们依次取k=\lfloor\frac{\pi}{4}\sqrt{\frac{N}{2^m}}\rfloor,m=0,1,2,\cdots,k\geq 1，因此最多有\frac{\pi}{4}\sqrt{N}\left(1+\frac{1}{\sqrt{2}}+\frac{1}{2}+\cdots\right)=\frac{\pi}{4}\sqrt{N}(2+\sqrt 2)次B_f查询。由于失误率P_{err}=\cos^2((2k+1)\theta)，因此获得正确|A\rangle的概率至少为

\text{minP}(N)=\min_{\theta\in[0,\pi/2]} \left(1- \prod_{k=\lfloor\frac{\pi}{4}\sqrt{\frac{N}{2^m}}\rfloor, m=0,1,2,\cdots}^{k\geq 1} \cos^2\left((2k+1)\theta\right)\right)\\

令x=\log_2N，绘制\text{minP-x}图像，如下图所示。

根据数值计算结果，当N\approx 16000时（14个量子比特），P\left( |A'\rangle=|A\rangle \right)\geq 0.998，表明在N较大（万以上的量级）时这种k取法有效。

以|A|未知时为例，算法流程为

Compute H^{\otimes n}|0^n\rangle on n-qubit quantum register X

Init m=0

While k=\lfloor\frac{\pi}{4}\sqrt{\frac{N}{2^m}}\rfloor\geq 1

Apply to the register X the transformation

G=H^{\otimes n}(2|0^n\rangle\langle 0^n|-I)H^{\otimes n}B_f

\quad k times.

m=m+1

Clone register X and measure enough times.

主要参考文献

[1] Bennet, C. H. (1998). Quantum Information and Computation. Lecture Notes. Nature (London), 404(March). Retrieved from https://cs.uwaterloo.ca/~watrous/LectureNotes/CPSC519.Winter2006/all.pdf

[2] Benenti, G., Casati, G., & Strini, G. (2010). Principles of Quantum Computation and Information - Volume I: Basic Concepts. Retrieved from http://www-reynal.ensea.fr/docs/iq/PrinciplesOfQuantumComputation1.pdf

[3] Topics, S. (n.d.). Principles of Quantum Computation and Information Volume II: Basic Tools and Special Topics. Retrieved from http://www-reynal.ensea.fr/docs/iq/PrinciplesOfQuantumComputation2.pdf

[4] Childs, A. M. (2017). Lecture Notes on Quantum Algorithms. (May). Retrieved from https://www.cs.umd.edu/~amchilds/qa/qa.pdf

[5] Melkebeek, I. D. Van. (n.d.). Lecture5 : More Elementary Quantum Algorithms Simon ’ s Problem. 2(2), 1–7. Retrieved from http://pages.cs.wisc.edu/~dieter/Courses/2010f-CS880/Scribes/05/lecture05.pdf

[6] de Wolf, R. (2019). Quantum Computing: Lecture Notes. Retrieved from https://arxiv.org/pdf/1907.09415.pdf

[7] 佐川弘幸, 吉田宣章. (2007). 突破经典信息科学的极限——量子信息论.