量子算法与量子计算实验_刘亚杰

HUNANGUANGBODIANSHIDAXUEXUEBAO

湖南广播电视大学学报

量子算法与量子计算实验

QuantumAlgorithmandExperimentsofQuantumComputation

刘亚杰LIUYa-jie

内容摘要:本文介绍了量子计算纠缠和量子比特的基本概念,系统阐述了几种主要的量子算法:Shor算法)))大数质

因子分解的量子算法;Grover搜索)))无序数据库的搜索;Hogg搜索)))高度结构化搜索。在对量子计算基本理论和量子算法有一定认识的基础上,进一步介绍了在量子计算实验方面起重要作用的二种体系:核磁共振、腔与原子体系。

关键词:量子算法 量子计算 量子比特 纠缠

中图分类号:O413 文献标识码:A 文章编号:1009-5152(06)02-061-03Abstract:Inthisthesis,

severalbasicconceptionsofquantumcomputationareintroduced,suchasentanglement,quantumbit.Severalkinds

ofmainquantumalgorithmsareillustrated,suchasShoralgorithm-thequantumalgorithmforfactoring,Groversearch-thesearchforthedisorderingdatabase,Hoggsearch-highstructurizationsearch.Onthebasisofknowledgeofbasictheoriesofquantumcomputationcomputingandquantumalgo-rithm,twokindsofsystemswhichplayimportantroleintheexperimentofquantumcomputationwasintroduced,Nuclearmagneticresonanceandcav-ityatomsystem.

Keywords:

Quantumalgorithm Quantumcomputation Quantumbit Entanglement

作者简介:刘亚杰(1964) ),男,湘潭广播电视大学讲师。湖南湘潭 411000

量子计算是量子物理与计算机科学交汇而生的一门新兴学科。它的出现实质上是量子物理学向物质、能量和信息这三大领地的最后一块信息领域的进军。

量子比特|1>和|0>之间存在着许多中间态,即|1>和|0>的不同迭加态,例如

(|0>+|1>)表示一个两子比特同时

存储着0和1。因此,对于位数相同的n个比特,量子比特可以存储2n倍的经典比特所能存储的信息。

对于两个量子比特的体系,其完备基由四个布尔态|00>、|01>、|10>和|11>组成。考虑它们之间的迭加,我们可以发现,|10>+|11>=|1>á(|0>+|1>),这是由两个量子比特构成的直积空间。而|11>+|00>或|01>+|10>则不能再写成直积形式。后面这种情况就是前面提到的纠缠。对于一个处于纠缠状态的体系,我们不能确切地指出其中某一个量子比特是处于|1>还是|0>。更一般的纠缠态是处于2n个布尔态的n个经典比特组成的迭加态。

11,1

一、量子计算的基本理论1、纠缠

1935年,Schrdinger首先给出了纠缠态的定义:由空间分离的两个子系统构成的纯态,如果系统波函数不能分解为两个子系统波函数的乘积,那么这样的波函数表示的态称作两个粒子的纠缠量子态。

1935年,Einstein,Podolsky和Rosen首先讨论了一个具体的两粒子纠缠量子态。在这个著名的实验中,两粒子的纠缠量子态为:

|74=ED(a+b-c0)|a4|b4

a,b

其中a,b分别为粒子1和粒子2的位置或动量,C0为常数。这个纠缠态的一个最明显的特征是:其中任何一个子系统的物理量的观测值(位置或动量)都是不确定的。但是,如果其中的一个子系统的物理量的观测值处于一个确定的值,那么我们就可以确定另外一个子系统的相应物理量观测值。

|74=

x=00,0

ECx|x4

2

时,称为等幅迭加态。这种等幅迭加态在以下要介绍的各量子算法中经常被用作初态。从上式也能看出,|7>是一个2n维的Hilbert空间中的一个单位矢量。它所在空间的维数

其中Cx可以是复数并且满足E|Cx|=1。当Cx=x

2、量子比特

量子比特有微观体系表征,如原子、核自旋或光子等。|1>和|0>可以由原子的两个能级来表示,也可以由核自旋或光子的不同极化方向来表征。与经典比特显著不同的是,

是随n呈指数型增长,这明显区别于经典体系中随n呈线性增长的态空间。

在一个孤立的量子体系中,对态的操作应是幺正的、可逆的。因此,我们构造的量子逻辑门也应满足这个特征。

XANDAIJIAOYUJISHU

现代教育技术

二、量子算法

1、Shor算法)))大数质因子分解的量子算法

用经典计算机来进行大数质因子分解,随着N的增大,所需比特数(即内存)是呈指数倍的增长。按照组合数学理论,当计算规模随着问题的难度呈多项式型增长时,该问题为P(Polynomial)问题。对于P问题,我们在有限的时间内总能找到办法求得它的解。对于我们在有限的时间内不可能找到办法求得解的问题称之为NP(Non-Polynomial)问题。目前世界上应用最广也是最成功的加密方法-公开密钥RSA系统的核心思想就是利用大数在有限时间内不可有效质因子化这一结论。1995年,P.W.Shor提出一种量子算法,能将这一著名的NP问题化为P问题,矛头直指RSA方法,从而在全球掀起了量子计算的研究热浪。

在Shor算法中,寻找一个大数的质因子问题被转化为寻找其余因子函数的周期。只要该周期被找到,并且为一个偶数,那么利用剩余定理,就能得到该大数的质因子。

给定整数N,选取一个与N互质的数a(a<N),我们能得到余因子函数faa,n(x)=amod(N),其中x=0,1,2,fa,N(x)是a/N的余数。我们首先需要知道fa,N(x)的变化周期。例如N=15,a=7,如表1,有:

x

x

单调函数的根。运用量子并行计算可以将A所在态的相位旋转180b,其余各态保持不变。即当T[i]=A时,增加一个相位e。

»相对各态的振幅的平均值作翻转。这一操作由幺正矩阵k1,k2,knD完成,其表达式为Dij=

,Dij=-1+。

NN

¼以上º»两步可以反复进行,每进行一次,称为一次

iP

搜索。可以证明,最多只需搜索N次,便能以大于0.5的几率找到我们要找的数据项。

Grover算法提出之后,引起了众人极大的兴趣。Grover算法中的翻转方法不仅被证明是最优化的搜索方式,而且也是抗干扰能力极强的方法。

3、Hogg搜索:高度结构化搜索

前面介绍过的NP问题中有一类名为可满足性问题(SatisfiabilityProblem,简称SAT问题)。一个典型的SAT问题是包括有n个变量的一个逻辑公式,要求给予其中每个变量一个赋值使逻辑公式为真。

数学上已证明,解决SAT问题的代价是随着变量数的增加而呈指数型增长。然而对于某些简单的情况,人们可以利用问题中具有的规则结构来迅速准确地搜索出问题的解。例如对于1-SAT问题,用经典试探法进行搜索,找出解的代价为最多需用n步。

表1 余因子函数的变化周期

x7

x

011

177

2494

334313

41

57

64

......

240116807117649...

对于量子计算而言,由于能进行量子并行计算,因而可以仅以一步的代价找出1-SAT问题的解。下面以有m个逻辑子句的1-SAT问题为例。与Grover搜索相似,我们先在n个量子比特上制备一个等幅迭加态作为初始态,即|74=2

-n/2

n-1s=0

fa,n(x)

不难看出,fa,N(x)的变化是有规律的,其变化周期为r=4。知道了这个周期,就可以利用孙子定理:设A=a=a

r/2

r/2

+1,B

-1,其中r必须为偶数,且a

r/2

mod(N)X1。求出A、B

E|S4。另外,我们需设计好两种幺正操作R和U,

之后,再分别求A、N和B、N的最大公约数(gcd)。设C=gcd(A,N),D=gcd(B,N)那么一定有C@D=N,即N被成功地质因子化。

Shor算法的关键在于求出大数N的余因子 …… 此处隐藏：3607字，全部文档内容请下载后查看。喜欢就下载吧 ……