量子算法与量子计算实验
论文摘要:本文介绍了量子计算纠缠和量子比特的基本概念,系统阐述了几种主要的量子算法:Shor算法———大数质因子分解的量子算法;Grover搜索———无序数据库的搜索;Hogg搜索———高度结构化搜索。在对量子计算基本理论和量子算法有一定认识的基础上,进一步介绍了在量子计算实验方面起重要作用的二种体系:核磁共振、腔与原子体系。
Abstract:In this thesis,several basic conceptions of quantum computation are introduced,such as entanglement,quantum bit.Several kindsof main quantum algorit hms are illustrated,such as Shor algorit hm—t he quantum algorit hm for factoring,Grover search—t he search for t he disorderingdatabase,Hogg search—high structurization search.On t he basis of knowledge of basic t heories of quantum computation computing and quantum algo2rit hm,two kinds of systems which play important role in t he experiment of quantum computation was introduced,Nuclear magnetic resonance and cavi2ty atom system. Key words:Quantum algorithm Quantum computation Quantum bit Entanglement 量子计算是量子物理与计算机科学交汇而生的一门新兴学科。它的出现实质上是量子物理学向物质、能量和信息这三大领地的最后一块信息领域的进军。
一、量子计算的基本理论 1、纠缠 1935年,Schr dinger首先给出了纠缠态的定义:由空间分离的两个子系统构成的纯态,如果系统波函数不能分解为两个子系统波函数的乘积,那么这样的波函数表示的态称作两个粒子的纠缠量子态。1935年,Einstein,Podolsky和Rosen首先讨论了一个具体的两粒子纠缠量子态。在这个著名的实验中,两粒子的纠缠量子态为:|Ψ〉=∑a,bδ(a+b—c0)|a|b〉 其中a,b分别为粒子1和粒子2的位置或动量,C0为常数。这个纠缠态的一个最明显的特征是:其中任何一个子系统的物理量的观测值(位置或动量)都是不确定的。但是,如果其中的一个子系统的物理量的观测值处于一个确定的值,那么我们就可以确定另外一个子系统的相应物理量观测值。 2、量子比特 量子比特有微观体系表征,如原子、核自旋或光子等。|1和|0可以由原子的两个能级来表示,也可以由核自旋或光子的不同极化方向来表征。与经典比特显著不同的是,量子比特|1和|0之间存在着许多中间态,即|1和|0的不同迭加态,例如12(|0+|1)表示一个两子比特同时存储着0和1。因此,对于位数相同的n个比特,量子比特可以存储2n倍的经典比特所能存储的信息。对于两个量子比特的体系,其完备基由四个布尔态|00、|01、|10和|11组成。考虑它们之间的迭加,我们可以发现,|10+|11=|1(|0+|1),这是由两个量子比特构成的直积空间。而|11+|00或|01+|10则不能再写成直积形式。后面这种情况就是前面提到的纠缠。对于一个处于纠缠状态的体系,我们不能确切地指出其中某一个量子比特是处于|1还是|0。更一般的纠缠态是处于2n个布尔态的n个经典比特组成的迭加态。|Ψ〉=∑11…1x=00…0Cx|x〉其中Cx可以是复数并且满足∑x|Cx|2=1。当Cx=12n时,称为等幅迭加态。这种等幅迭加态在以下要介绍的各量子算法中经常被用作初态。从上式也能看出,|Ψ是一个2n维的Hilbert空间中的一个单位矢量。它所在空间的维数是随n呈指数型增长,这明显区别于经典体系中随n呈线性增长的态空间。在一个孤立的量子体系中,对态的操作应是幺正的、可逆的。因此,我们构造的量子逻辑门也应满足这个特征。
二、量子算法 1、Shor算法———大数质因子分解的量子算法 用经典计算机来进行大数质因子分解,随着N的增大,所需比特数(即内存)是呈指数倍的增长。按照组合数学理论,当计算规模随着问题的难度呈多项式型增长时,该问题为P(Polynomial)问题。对于P问题,我们在有限的时间内总能找到办法求得它的解。对于我们在有限的时间内不可能找到办法求得解的问题称之为NP(Non—Polynomial)问题。目前世界上应用最广也是最成功的加密方法—公开密钥RSA系统的核心思想就是利用大数在有限时间内不可有效质因子化这一结论。1995年,P.W.Shor提出一种量子算法,能将这一著名的NP问题化为P问题,矛头直指RSA方法,从而在全球掀起了量子计算的研究热浪。在Shor算法中,寻找一个大数的质因子问题被转化为寻找其余因子函数的周期。只要该周期被找到,并且为一个偶数,那么利用剩余定理,就能得到该大数的质因子。给定整数N,选取一个与N互质的数a(a。
3、Hogg搜索:高度结构化搜索 前面介绍过的NP问题中有一类名为可满足性问题(Satisfiability Problem,简称SA T问题)。一个典型的SA T问题是包括有n个变量的一个逻辑公式,要求给予其中每个变量一个赋值使逻辑公式为真。数学上已证明,解决SAT问题的代价是随着变量数的增加而呈指数型增长。然而对于某些简单的情况,人们可以利用问题中具有的规则结构来迅速准确地搜索出问题的解。例如对于1—SAT问题,用经典试探法进行搜索,找出解的代价为最多需用n步。对于量子计算而言,由于能进行量子并行计算,因而可以仅以一步的代价找出1—SAT问题的解。下面以有m个逻辑子句的1—SAT问题为例。与Grover搜索相似,我们先在n个量子比特上制备一个等幅迭加态作为初始态,即|Ψ〉=2—n/2∑n—1s=0|S〉。另外,我们需设计好两种幺正操作R和U,其中R为对角矩阵,其归一化对角元为Rss=2cos[(2c—1)π/4] m=偶数ic m=奇数。(3.3.1)式中的c(0。