3.2.4 实验验证 12

3.3 Deutsch-Jozsa算法 12

3.3.1 常函数与平衡函数 14

3.3.2 Deutsch-Jozsa算法 14

3.3.3 实验验证 14

3.4 Shor算法 15

3.4.1 因式分解的复杂性 15

3.4.2 寻序问题 16

3.4.3 利用寻序问题解决因式分解问题 16

3.4.4 Shor算法 17

3.4.5 可逆经典算法 17

3.4.6 模态乘法的量子线路 19

3.4.7 控制门和相位估算 19

4   总结 20

5   致谢 21

A  式(5)的证明 23

1 引言

量子计算和量子信息是一个新兴的交叉学科，其最早是物理学家为了更好地理解和掌 握量子力学而提出的。在很多科学领域，对单量子体系的控制能很好地帮助人们认识基础 的物理规律，开发新的科学技术。而量子计算和量子信息正是完成这一任务的不二人选[1]。 对于量子计算和量子信息的研究已经产生了许多成果， 在理论方面， 除了早期的Shor算 法[2]，Gorver算法[3]，Deutsch算法[4]等，许多量子计算语言和量子算法也相继被开发出 来；在实验方面，IBM在2017年推出了网络量子计算平台IBM QX[5]，而中国科学技术大 学也于当年建立了本源量子计算平台[6]，各种小规模的量子计算机已经先后被研发出来。 在第2节中，我们首先对量子计算的基本概念和IBM QX这一量子计算平台的基本情况进行 了简要的介绍。然后在第3节中，我们对于量子算法，包括复合量子逻辑门、Grover算法、 Deutsch-Jozsa算法、Shor算法进行了详细的阐述和实验验证。

2 量子计算的理论基础和网络量子实验平台的介绍

本节中我们先来回顾一下量子计算的一些基础概念和我们所选用的网络量子计算平台

IBM  QX 的构造。

2.1    量子计算的理论基础

2.1.1    量子比特

经典计算信息元是比特，一个比特要么处在0态上，要么处在1态上，利用AND，OR，

NOT，NAND等逻辑门来进行运算，所得的结果是完全确定的。

而量子计算的信息元是量子比特，它可以同时处在|0)和|1)的叠加态上

对于n个量子比特，则可以同时处在2n个态的叠加态上。这意味着量子计算有这天生的并行 计算能力，但第2.1.3中会讲到，这一能力还有一些限制条件。量子比特还有纠缠这一奇特 的性质，当一个体系处于纠缠态时，它就不能分别用各个量子比特的态来表示，如

量子比特可以用矩阵的形式表示。如式(1)中所示的单个量子比特，可以表示为

其中第一行的元素表示态|0)的叠加系数，第二行的元素表示态|1)的叠加系数。对于多量子 比特，其各行元素分别表示其中各个基矢的叠加系数。例如，对于两量子比特，可以如下 示意 利用网络量子计算资源实现量子算法的研究(2):http://www.chuibin.com/wuli/lunwen_205793.html