量子计算的优势特征算法和物理实现

　　摘要：量子计算表现出的并行性是其相对于经典运算的优势特征。目前已知的最为成功的两类量子算法是基于Shor的量子Fourier变换算法和基于Grover的量子搜索算法。量子计算和量子算法理论的基本框架已经成型，各方面研究进展日新月异，但最终实现实用价值的量子计算，还需要解决众多问题。其中，何种物理系统最终适用于量子计算机迄今尚无定论，尽管如此，坚信实现量子计算已不存在不可逾越的障碍的信念正激励着学术界的巨大研究热情。
　　关键词：量子计算；量子算法；优化；实现困难
　　随着人类在信息量处理速度方面的需求越来越高，当前计算机性能的提升速度满足不了人类在信息处理速度方面的需求。十九世纪初提出并建立的量子力学理论带来计算机的革命性发展了新的解决办法，量子独有的相干性和纠缠性等特性为量子计算带来了完全不同于经典计算的独特运算方式。经过近一个世纪的发展，2009年美国国家标准技术研究院研制的世界上首台通用编程量子计算机面世。量子计算是应用量子力学原理来进行有效计算的新颖计算模式，它利用量子叠加性、纠缠性和量子的相干性实现量子的并行计算。量子计算从本质上改变了传统的计算理念。
　　一、量子计算的优势特征
　　1982年美国物理学家费曼（R。P。Feynman）提出量子计算概念，但由于量子态的测不准原则以及量子系统容易受噪声干扰，量子运算很容易出错。直到1994年美国计算机专家Shor证明了量子计算机能快速分解大因数，并实现了第一套量子算法编码，量子计算以及量子计算机的研究才进入实验时代。
　　经典比特具有0和1两种状态。量子比特与经典比特的不同之处在于：一个量子比特除了可以像经典比特一样处于0和1这样的状态之外，还可以处于既非0又非0的状态上，这个中间状态称为叠加态（Superposition）。量子叠加态是决定量子计算不同于经典计算的关键特性之一，也是量子并行计算的理论基础。相同位数的寄存器，量子计算机可以记录的信息量是传统计算机的指数倍，它的运算速度和信息处理能力是经典计算机所无法比拟的。因此，量子并行计算体现了量子计算最重要的优越性。
　　二、量子算法
　　量子算法作为量子计算科学的重要部分，在过去的十几年中得到了广泛的发展并取得了一系列惊人的成就。目前已知的最为成功的两类量子算法是基于Shor的量子Fourier变换算法和基于Grover的量子搜索算法。1989年，Deutsch首次提出了Deutsch量子算法。该算法第一次很好的展示了量子计算机的并行性。1994年，Shor提出大数质因子分解量子算法并实现了该算法的量子编码，此后，Grover算法、量子智能算法等量子算法相继被提出，量子算法的研究工作也得到了各国研究者的关注。
　　（一）Shor大数质因子分解算法
　　1994年，Shor提出了离散对数问题和大整数质因子分解问题的量子算法，证明了这两个重要且复杂的问题属于BQP类，极大地促进了量子计算的发展，使人们第一次清楚地看到了量子计算独具优势的重要应用前景。从此，世界众多研究小组加入了该研究行列，量子计算研究领域取得了许多重大进步，
　　Shor的另一项同样重要的成果是率先提出了量子纠错码〔18，19〕，这使得容错的量子计算成为可能〔19〕。量子计算在密码学领域也取得了迅速的发展，这就意味着目前广泛应用于政府、军事以及金融机构等重要方面的RSA公钥密码体系的安全性可能面临着致命的威胁，仅这一点就足以引起人们对量子算法研究的极大关注。
　　Shor算法本身已经相当成熟，对其改进和优化的空间不大。Shor算法是目前为止已经提出的最好的量子算法，该算法不但具有传统算法无法比拟的优势，而且其巧妙的理论构思以及表现出的实际应用价值，都是十分宝贵的。Shor算法及其模拟实现，对量子通信和量子密码学的发展都具有极其重要的参考价值。
　　（二）Grover数据库搜索算法
　　对于无序数据库，搜索的规模随着数据库规模的增长而成线性增长。Grover提出量子搜索算法，将搜索问题完成时间缩小，对经典问题起到了二次加速的作用。
　　Grover算法适宜于解决在无序数据库中搜索某一个特定数据的问题。Grove：算法利用量子并行性，并没有像Shor算法一样实现问题的指数加速，然而搜索算法的广泛应用性却很好的弥补了这一点。现实中有许多问题，如最短路径问题、图的着色问题、排序问题及密码的穷举攻击问题等，都可以将Grover算法视为通用算法求解。事实上，目前Grover算法已经在核磁共振和光学系统中得到实现。
　　Grover算法是目前最经典的量子算法之一，然而它也存在着某些缺陷。对Grover算法的改进研究也成为了目前量子算法方面的一个热门研究领域。
　　（三）量子智能算法
　　自Shor算法和Grover算法提出以后，量子计算方法表现出的独特计算方式以及在信息处理方面展现的巨大潜力引起了研究者的广泛关注。自Shor因子分解算法和Grover搜索算法提出后，虽然众多研究者在量子算法领域进行了大量的研究，但迄今为止并没有取得重大突破。而智能算法向来是算法研究领域的一个热点，量子智能计算将量子理论原理与智能计算相结合，利用量子并行计算特性很好的弥补了智能算法中的某些不足之处，如：加快算法的收敛速度及避免早熟现象等。
　　目前己有的量子智能算法研究包括：量子进化算法、量子免疫计算、量子退火计算、量子神经网络和量子聚类算法等。其中，量子进化算法和量子神经网络成为目前学术研究的热点并取得了相当不错的成绩。
　　目前量子进化算法的应用研究领域也很有限，量子进化算法的研究还不够成熟，很多理论和应用的研究还需要深化和推广，进一步研究的空间还很大。
　　三、量子计算的物理实现
　　量子计算和量子算法理论的基本框架已经成型，各方面研究进展日新月异，但最终实现实用价值的量子计算，还需要解决众多问题。其中，量子计算的前提是量子计算的物理实现，但量子计算机技术上的实现却遇到严重的困难，何种物理系统能最终适用于量子计算机迄今尚无定论，尽管如此，坚信实现量子计算已不存在不可逾越的障碍的信念正激励着学术界的巨大研究热情去推进相关研究进展。
　　参考文献：
　　〔1〕首次在国际上实现量子分解算法。中国科学院院刊，2008，23（1）：7676。
　　〔2〕彭卫丰，孙力。SHOR量子算法的优化及应用研究。计算机应用与软件，2009，26（5）：239246。
　　〔3〕李士勇，李盼池。量子计算与量子优化算法。哈尔滨：哈尔滨工业大学出版社，2009。
　　〔4〕周正威，黄运锋，张永生等。量子计算的研究进展〔J〕。物理学进展，2005，25（4）：368385。