量子通信和量子计算
陈雪祺
摘要：量子计算和量子计算机是现代信息科学的重大议题，量子的叠加性、纠缠性和相干性为量子计算提供一种创新的计算方法，在对信息的运算、保存和处理方面远超过经典运算。Shor算法通过量子傅里叶变换，有效地在多项式时间内解决大数质因子分解问题；以Grover算法为代表的量子搜索算法，极大地提高搜索效率；量子通信技术利用量子的纠缠态实现信息传递；量子并行计算可以弥补智能算法中的某些不足，量子智能算法将有很大的发展空间。
关键词：量子算法；Shor算法；Grover算法；量子通信；量子智能计算
【分类号】：TM743
1.概述
量子计算是计算机科学与量子力学相结合的产物，根据Moore定律可知：当计算机的存储单元达到原子层次时，显著地量子效应将会严重影响计算机性能，计算机科学的进一步发展需要借助新的原理和方法【1】，量子计算为这一问题的解决提供了一个可能的途径。
根据量子计算原理设计的量子计算机是实现量子计算的最好体现。量子计算机是利用微观粒子状态来进行存储和处理信息的计算工具【2】。其基本原理是通过物理手段制备可操作的量子态，并利用量子态的叠加性、纠缠性和相干性等量子力学的特性进行信息的运算、保存和处理操作，从本质上改变了传统的计算理念。
量子通信是量子理论与信息理论的交叉学科，是指利用量子的纠缠态实现信息传递的通讯方式。量子的纠缠态是指：相互纠缠的两个粒子无论被分离多远，一个粒子状态的变化都会立即使得另一个粒子状态发生相应变化的现象。量子通信主要包括两类：用于量子密钥的传输，和用于量子隐形传态和量子纠缠的分发。与传统的通信技术相比，量子通信具有容量大，传输距离远和保密性强的特点。
2.量子计算基础
2.1 量子位
计算机要处理数据，必须把数据表示成计算机能够识别的形式。与经典计算机不同，量子计算机用量子位来存储信息，量子位的状态既可以是0态或1态，也可以是0态和1态的任意线性叠加状态。一个n位的量子寄存器可以处于 个基态的相干叠加态 中，即可以同时存储 种状态。因此，对量子寄存器的一次操作就相当于对经典计算机的 次操作，也就是量子的并行性。
2.2.量子逻辑门
对量子位的态进行变换，可以实现某些逻辑功能。变化所起到的作用相当于逻辑门的作用。因此，提出了“量子逻辑门”【3】的概念，为：在一定时间间隔内，实现逻辑变换的量子装置。
量子逻辑门在量子计算中是一系列的酉变换，将酉矩阵作为算符的变换被成为酉变换。量子位的态 是希尔伯特空间（Hilbert空间）的单位向量，实现酉变换后希尔伯特空间，在希尔伯特空间内仍为单位向量。【4】
3.量子算法
量子算法的核心就是利用量子计算机的特性加速求解的速度，可以达到经典计算机不可比拟的运算速度和信息处理功能。目前大致五类优于已知传统算法的量子算法：基于傅里叶变换的量子算法，以Grover为代表的量子搜素算法，模拟量子力学体系性质的量子仿真算法，“相对黑盒”指数加速的量子算法和相位估计量子算法。
3.1基于傅里叶变换的量子算法
Shor于1994年提出大数质因子分解量子算法，而大数质因子分解问题广泛应用在RSA公开密钥加密算法之中，该问题至今仍属于NP难度问题。但是Shor算法可以在量子计算的条件下，在多项式时间内很有效地解决该问题。这对RSA的安全性有着巨大的挑战。
Shor算法的基本思想是：利用数论相关知识，通过量子并行特点，获得所有的函数值；再随机选择比自变量小且互质的自然数，得到相关函数的叠加态；最后进行量子傅里叶变换得最后结果。构造如下函数：
就目前而言，该算法已经相对成熟，对其进行优化的空间不大。目前研究者的改进工作主要是：通过对同余式函数中与N互质的自然数选择的限制，提高算法成功的概率。Shor算法及其实现，对量子密码学和量子通信的发展有着极重要的价值。[7]
3.2以Grover为代表的量子搜素算法
3.2.1 Grover算法
Grover算法属于基于黑箱的搜索算法，其基本思想为：在考虑含有 个数据库的搜索问题，其中搜索的解恰好有 个，将数据库中的每个元素进行量化后，存储在 个量子位中， 与 满足关系式 。【8】将搜索问题表示成从0到 的整数 ，其中函数 定义为：如果 是需要搜索的解， ；若不是需要搜索的解，那么 。【12】
具体算法如下：
（1）初始化。应用Oracle算子 ，检验搜索元素是否是求解的实际问题中需要搜索的解。
（2）进行Grover迭代。将结果进行阿达马门（Hadamard门）变换。
（3）结果进行 运算。
（4）结果进行阿达马门变换。【12】
4. 量子智能计算
自Shor算法和Grover算法提出后，越来越多的研究员投身于量子计算方法的计算处理方面，同时智能计算向来是算法研究的热门领域，研究表明，二者的结合可以取得很大的突破，即利用量子并行计算可以很好的弥补智能算法中的某些不足。
目前已有的量子智能计算研究主要包括：量子人工神经网络，量子进化算法，量子退火算法和量子免疫算法等。其中，量子神经网络算法和量子进化算法已经成为目前学术研究领域的热点，并且取得了相当不错的成绩，下面将以量子进化算法为例。
量子进化算法是进化算法与量子计算的理论结合的产物，该算法利用量子比特的叠加性和相干性，用量子比特标记染色体，使得一个染色体可以携带大数量的信息。同时通过量子门的旋转角度表示染色体的更新操作，提高计算的全局搜索能力。
目前量子进化算法已经应用于许多领域，例如：工程问题、信息系统、神经网络优化等。同时，伴随着量子算法的理论和应用的进一步发展，量子进化算法等量子智能算法有着更大的发展前景和空间。
参考文献
1.王书浩，龙桂鲁.大数据与量子计算
2.张毅，卢凯，高颖慧.量子算法与量子衍生算法
3.Deutsch D，Jozsa R.Rapid solution of problems by quanturm computation[C]//Proc Roy Soc London A，1992，439：553-558
4.吴楠，宋方敏。量子计算与量子计算机
5.苏晓琴，郭光灿。量子通信与量子计算。量子电子学报，2004，21（6）：706-718
6. White T.Hadoop： The Defintive Guide，California：OReilly Media，Inc.2009：12-14
7.王蕴，黄德才，俞攸红.量子计算及量子算法研究进展.
8.孙吉贵，何雨果.量子搜索算法.软件学报，2003，14（3）：334-344
9.龙桂鲁.量子计算算法介绍
10.解光军，范海秋，操礼程.一种量子神经计算网络模型
11.Han KH，Kim J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE Trans on EvoluntionaryComputation，2002，6（6）：580-593
12.张海雄.Grover量子搜索算法的改进及其在图像检索中的应用
