1. Deutsch 算法
2. Deutsch-Jozsa 算法
3. Simon 算法
4. Grover 搜索算法
5. 量子傅里叶变换(QFT)
6. 量子相位估计
7. 量子逻辑门
   1. 单比特量子门
   2. 多比特量子门

Deutsch 算法

定义函数,若称为常值函数,若称为平衡函数,Deutsch问题是判断是常值函数还是平衡函数^[1]。假设量子算符可以实现下面量子操作:

利用经典算法,需要两次运算才能确定的类型。若利用量子叠加性构造量子算法,只需要一次运行就能得到结果,下面是Deutsch算法的量子线路模型:

量子态经过变换后得到:

若,则第一个量子位为,若则第一个量子位为,因此将第一个量子位投影到,即可以确定的类型。考虑量子变换,可知,即为平衡函数,构建如下的量子线路,判断的函数类别

初始量子比特制备在态上,经过量子线路的运行,测量第一个量子比特,以的概率得到,即可以判断为平衡函数。

Deutsch-Jozsa 算法

作为Deutsch问题的推广,定义二值函数,当是常值函数对所有都有,若是平衡函数,一半的给出,另外一般给出,问题同样是判断的函数类型。利用经典计算可以知道最坏的情况需要步数才能判断函数的类型。利用量子算法只需要一步就能判断的类型,下面是量子算法的步骤^[1] :

1. 初始化个q-bits到态.

2. 对每个q-bits进行Hadamard操作,变换完后的态为:
   

3. 考虑量子操作(oracle)包含个控制比特和单个受控比特,即,作用于得到:
   

4. 然后再作用Hadamada门于前个比特,得到:
   

   其中可以记为,这里。

5. 最后一步即测量,考虑态的权重为:
   

   若为常值函数,当时其权重为,时,由于有一半为一半为,求和后得到权重为零。若为平衡函数,当时,权重,由此得到态的叠加。即当测量得到时,可以判断为常值函数,反之可以判断为平衡函数。

下面给出了一个比特的Deutsch-Jozsa 算法,其中通过四个CNOT门实现,当二进制中含有偶数个时,否则,即为平衡函数。

通过运行上述的量子线路可以得到采样结果为,即可以判断为平衡函数,这是符合定义的。

Simon 算法

考虑函数,其中函数是的,且对任意存在周期,使得,现在问题是确定周期 。对于经典算法,需要尝试 个可能性才能确定周期。而量子Simon 算法则可以将求解复杂度减低到。以下是Simon算法的详细步骤^{[1] [2]} :

1. 将个量子比特制备到初始态,然后将Hadamard作用到前个比特的集合,得到：
   

2. 考虑量子操作(oracle)包含个控制比特和受控比特,经过变换后的量子态为:
   

3. 测量后个量子比特,若投影到一个确定的态,可以知道量子态塌缩到:
   

4. 紧接着对前个量子比特进行Hadamard变换得到:
   

   其中,代入,得到:

5. 最终再次测量前个比特,投影得到,满足,重复量子算法可以得到一系列,均满足,通过求解线性方程即可以得到周期。考虑到求解需要个线性独立的方程,最好的情况也需要次重复运行电路,但量子算法的时间复杂度仍是多项式的,相比于经典算法存在指数加速。

Grover 搜索算法

假设一个有条目的数据库,每条目由数字标记,搜索的任务是找出满足要求的条目。用数学语言表示即,函数定义为:

其中为搜索目标。经典算法需要搜索步数为,而Gover 算法可以通过放大量子态振幅的,降低其他量子态的振幅,将搜索步数减少到^[2]。

为了实现量子Grover算法,考虑一个量子Oracle ,相当于一个量子黑盒,可以执行如下幺正变换:

其中是比特量子态,是单比特量子态,若作辅助量子比特,经过量子Oracle 变换后为:

若仅考虑比特量子态,则量子变换为,或将变换记为:

利用量子Oracle可以构造量子搜索算法:

1. 首先制备初态,即等权叠加态():
   

   同时将辅助量子位制备到. 其中目标态振幅为,Gover算法的实质就是通过放大目标态的振幅抑制其他态的振幅从而实现目标搜索。

2. 构造对称操作,可以通过以下三步完成^[2] ：

   • 将量子态进行Hadamard 操作。
   • 进行相位变换,即。
   • 再对量子态进行 Hadamard 操作。
     即。

   现在可以构造Grover算法迭代的线路:

Grover 算法的迭代过程可以通过几何方法理解,其中的作用是将任意态以镜像翻转,而是以做镜像翻转。每一次迭代,往态方向旋转角度为,如下图所示:

因此经过次迭代后的振幅为:

可以看到目标态的振幅在迭代过程中变大,考虑迭代结束应该以非常高的概率得到,即,若非常大,即可以得到迭代次数,也就是说Grover算法相比于经典算法具有级加速。

通常对于一个搜索任务来说,可能存在多个满足要求的条目,此时Grover 算法仍然能实现搜索任务,初始态可以写为:

同样可以使用Grover迭代,只是每次的旋转角度,搜索次数为。当热搜索结束后得到的是目标态的等权叠加态,因此任然需要多次投影测量才能得到所有的目标态。

构建一个的量子线路,其中由两个翻转门和一个Toffoli门构成,即。由,得到,即只需要迭代一次就能完成搜索任务,因此可以构建如下的线路实现Grover 算法^[4] :

将初始态制备到,经过模拟得到输出的结果为,即实现了对目标的搜索。

量子傅里叶变换(QFT)

与离散傅里叶变换相同,量子傅里叶变换(QFT)可以定义为如下变换^[2] :

QFT就是要通过量子线路实现 的幺正变换,矩阵元 。考虑,将进行二进制展开:

可以计算,可以忽略包含的项,这些项对无贡献,即:

考虑任意态矢量的傅里叶变换即:

接下来要构建量子线路实现上述量子傅里叶变换,首先考虑一个简单的例子即单比特QFT,可以由Hadamard门完成即:

对于多比特QFT,需要利用到控制相位门,即第个比特控制第个比特做相位变换:

可以称为门,单比特的情形为Hadamard门。仅通过以上两种门和SWAP门即可以构建QFT的量子线路:

考虑到线路的分别对应,因此需要使用SWAP门调整输出后的顺序。若不考虑SWAP门,可知线路需要个Hadamard 门以及 个门,因此线路规模为,而经典离散傅里叶变换需要的逻辑门为呈指数增长。这里还需要说明的是,虽然QFT只需要一次就能得到结果,但要确定输出的态却需要重复运行线路进行测量,因此只有一些特定的问题才能利用QFT加速。

考虑一个比特QFT的例子,输入态为,可以构建如下的量子线路:

运行此线路次并进行投影测量,可以得到线路的采样结果为:

线路运行10000次,做投影测量,每个态出现的次数

考虑一个比特QFT的例子,其中输入态为方脉冲,如图所示,左侧为输入方脉冲,右侧为进行QFT后的输出结果。

输入态采样后概率分布

输出态采样后概率分布

量子相位估计

假设幺正算符存在本征态以及对应的本征值,即,其中是未知量,相位估计问题就是要得到精确到位的值。

为了实现量子估计算法,假设能够制备态,以及实现 操作即,其中为前面所定义的幺正变换。

量子相位估计算法需要两个寄存器,第一个寄存器存放相位估计结果,初始化为,第二个寄存器为辅助位,初始化为算子的本征态。如下图所示为相位估计算法的线路图:

1. 对第一个寄存器的个比特进行操作,然后对第二个寄存器进行控制门操作,其中的幂次依次为,操作完成后第一个寄存器量子态变换为:
   

   由于,可以将其二进制展开到小数点第位即:

代入可以得到:

可以发现具有傅里叶变换后的形式即:

其中。

2. 由上面可知,接下来便是执行QFT的逆变换即。

3. 对第一个寄存器的所有量子位做投影测量,可以确认目标态,从而得到位相估计结果。

以上的计算都是基于可以精确展开位二进制小数,此时可以精确地给出位相。若 不能精确展开为位二进制数,此时只能概率性地得到地近似值^[5]。考虑为近似到位的最好估计,即,可以得到测量末态的概率,因此总可以通过扩大量子位数目来达到需要的精度^[4][5]。

考虑一个单比特相位门,令,即,可知。为了估计相位值,可以构建如下量子线路: