量子计算机详解课件

量子计算机林晓菲2004-05-14主要内容量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子算法举例—shor算法参考文献主要内容量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子算法举例—shor算法参考文献量子计算机的发展及现状三大热点

量子计算机

量子密码术量子通信量子计算机20世纪后半页计算机技术大行其道，人类进入信息时代。随着计算机芯片的集成度越来越高元件越做越小，集成电路技术现在正逼近其极限。原件小型化过程量子计算机从大规模集成电路的发展史看，单粒子晶体管似乎是必然趋势。当一个晶体管里包含的杂质电子数目只有一个或少数几个时，量子行为便为主要性质，这时计算方式必然要用量子力学才能正确处理。早在60年代,Landauer就已研究计算过程的可逆性与统计力学的关系。量子计算机的概念源于对可逆计算机的研究。量子计算机早期量子计算机，实际上是用量子力学语言描述的经典计算机，并没有用到量子力学的本质特性，如量子态的叠加性和相干性。Feynman，Fredkin，Toffoli

等人考虑由量子力学原理确定计算规则发生的现象后,发现计算理论与物理学规律密不可分。量子计算机Deutch

指出,这种以量子力学原理決定的计算过程

(即量子计算)很多方面体现出与经典计算非常不同的行为。八十年代初期，一些物理学家证明一台计算机原则上可以以纯粹的量子力学的方式运行之后很长一段时间，因为科学家们不能找到实际的系统可供进行量子计算机的实验，而且还尚不清楚量子计算机解决数学问题是否会比常规计算机快，这一研究领域渐趋冷清。量子计算机进入20世纪90年代，实验技术和理论模型的进步为量子计算机的实现提供了可能。要使量子计算成为现实，一个核心问题就是克服消相干。而量子编码是迄今发现的克服消相干最有效的方法。主要的几种量子编码方案是：量子纠错码、量子避错码和量子防错码。量子计算机目前已经提出的在实验上实现对微观量子态的操纵方案主要利用了原子和光腔相互作用、冷阱束缚离子、电子或核自旋共振、量子点操纵、超导量子干涉等。尤其值得一提的是1994年美国贝尔实验室的PeterW.Shor证明运用量子计算机能有效地进行大数的因式分解。量子计算机几年后Grover提出“量子搜寻算法”，可以破译DES密码体系。于是各国政府纷纷投入大量的资金和科研力量进行量子计算机的研究美，英，德，法，加拿大，日本，中国大陆，台湾，新加坡，印度等已先后成立专门研究量子计算机的研究群。量子密码术量子密码术是密码术与量子力学结合的产物，它利用了系统所具有的量子性质。首先想到将量子物理用于密码术的是美国科学家威斯纳。1970年，威斯纳提出，可利用单量子态制造不可伪造的“电子钞票”。但这个设想的实现需要长时间保存单量子态，不太现实。量子密码术贝内特和布拉萨德在研究中发现，单量子态虽然不好保存但可用于传输信息。1984年，贝内特和布拉萨德提出了第一个量子密码术方案，称为BB84方案，由此迎来了量子密码术的新时期。1992年，贝内特又提出一种更简单，但效率减半的方案，即B92方案。量子密码术量子密码术并不用于传输密文，而是用于建立、传输密码本。根据量子力学的不确定性原理以及量子不可克隆定理，任何窃听者的存在都会被发现，从而保证密码本的绝对安全，也就保证了加密信息的绝对安全。量子密码术最初的量子密码通信利用的都是光子的偏振特性，在长距离的光纤传输中，光的偏振性会退化，造成误码率的增加。目前主流的实验方案则用光子的相位特性进行编码。与偏振编码相比，相位编码的好处是对光的偏振态要求不那么苛刻。目前，在量子密码术实验研究上进展最快的国家为英国、瑞士和美国。量子通信量子通信系统的基本部件包括量子态发生器、量子通道和量子测量装置。按其所传输的信息分为两类：经典量子通信和量子通信。经典量子通信主要用于量子密钥的传输。量子通信量子通信可用于量子隐形传送和量子纠缠的分发。隐形传送指的是脱离实物的一种“完全”的信息传送。从物理学角度，可以这样来想象隐形传送的过程：先提取原物的所有信息，然后将这些信息传送到接收地点，接收者依据这些信息，选取与构成原物完全相同的基本单元，制造出原物完美的复制品。量子通信量子力学的不确定性原理不允许精确地提取原物的全部信息，这个复制品不可能是完美的。因此长期以来，隐形传送不过是一种幻想而已。

1997年，在奥地利留学的中国青年学者潘建伟与荷兰学者波密斯特等人合作，首次实现了未知量子态的远程传输。这是国际上首次在实验上成功地将一个量子态从甲地的光子传送到乙地的光子上。主要内容量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子算法举例—shor算法参考文献量子力学原理量子计算机以量子力学建立逻辑体系，与量子计算机有关的量子力学的原理，即量子状态的主要性质包括：

●状态叠加●干涉性

●纠缠

●不可复制性与不确定性●状态变化

量子力学原理状态叠加設{|n>}為可能的量子状态,則{∑iaik|k}也是一个可能的量子状态。对应于量子计算,这表示量子计算机可以代表经典计算机的很多状态。它使得大规模的量子并行存储成为可行,如n能阶系統至少可存2n个数据,由于理论上n无上限。因此,可以利用此特性作大规模的存储。又由于各状态之间有相位相干,存储过程是平行的。量子力学原理干涉性状态叠加时，依各状态间的相位关系可能出现相长或相消的状态，这是经典计算机的布尔状态所不具备的特征。状态变化

量子依照幺正变换法则，有系统的汉密尔顿算子决定其变化。量子力学原理

干涉性，状态变化这两个性质是量子并行计算的基础，因为系统的各个状态按照幺正变换同时变化，故一次量子计算可以同时作用在多个数据上。量子计算机的优越性主要体现在量子并行计算上量子力学原理纠缠整体的状态波函数不变并不一定表示各成份状态的波函数不变,这说明各成分波函数间有非定域的关联性。不可复制性与不确定性

不能精确的复制一个状态，也不能在不打扰该状态的情况下观察此状态量子力学原理纠缠，不可复制性与不确定性是量子加密，密码术，量子通信的基础。借助于纠缠性质，原则上可以实现超距的重生-灭体过程。量子状态的不可复制性与不确定性是的量子通信免于被窃听或者即使被窃听也无法解读。主要内容量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子算法举例—shor算法参考文献量子计算基础量子比特量子寄存器量子门量子网路量子比特在经典计算机中，运算的基本单元是比特（bit），它的基本状态是二值布尔逻辑状态（0或1）在量子计算机中，运算的基本单元是量子比特（q-bit），它的基本状态是两种状态的叠加。

量子比特规定原子在基态时记为|0〉，在激发态时原子的状态记为|1〉。原子除了保持上述两种状态之外，还可以处于两种态的线性叠加，记为

|φ〉=a|1〉+b|0〉

a和b分别代表原子处于两种态的几率幅

量子比特量子比特一种典型的量子比特—量子点

它基本上是一个被困在原子牢笼中的单一电子。当量子点暴露在刚好合适波长的激光脉冲下并持续一段时间，电子就会达到一种激发态：而第二次的激光脉冲又会使电子衰落回它的基态。电子的基态和激发态可以被视为量比的0和1状态，而激光在将量比从0状态撞击到1状态或从1撞击到0的应用，能够被看成是一种对取非功能的控制。

量子比特一种典型的量子比特—量子点如果激光持续时间只有取非功能要求的一半，那么电子将同时处于基态和激发态的重叠中，这也等价于量比的连贯性状态。而更多复杂的逻辑功能可以通过使用成对的安排好的量子点被模拟出来。因此，看起来量子点是一个合适的建造量子计算机的候选人。

量子寄存器存储一系列量子比特的体系称为量子寄存器假如有一个由三个比特构成的寄存器在经典计算机中，可以表示0~7共8个数，并且在某一时刻，只能表示其中的一个数

000001010011100101110111量子寄存器

若此寄存器器是由量子比特构成，每个量子比特可以处于|0〉或|1〉或

|0〉与|1〉的叠加态，既在某时刻一个量子存储器可以表示8个数。

0〉|0〉|0〉+|0〉|0〉|1〉+|0〉|1〉|0〉+|0〉|1〉|1〉+|1〉|0〉|0〉+|1〉|0〉|1〉+|1〉|1〉|0〉+|1〉|1〉|1〉

量子寄存器3个量子比特的系统量子寄存器3个量子比特的系统可以同时表示8个传统状态量子门在经典计算机中，逻辑判断是按真值表进行任何逻辑运算均可以归类于3项基本的布尔操作：非（NOT），与（AND），或（OR）这些基本的逻辑运算称为门量子门与经典计算机的门相对应的，量子计算机中的量子门由幺正变换实施。量子门的真值表较经典的真值表要广泛得多。量子门是实现量子并行计算的基石。

量子门可以作为实现量子计算的通用逻辑门的Fredkin

门和Toffoli门Fredkin门的真值表量子门Toffoli门及其真值表量子门异或（XOR）门及其对应操作量子网路将量子门按某种方式连接，构成量子网路，以进行复杂的运算。

利用XOR门与转动门构成的Toffolli门量子网路K-位寄存器上作分离（快速）傅立叶变换的量子网路主要内容量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子算法举例—shor算法参考文献shor算法1994年，PeterShor提出利用量子计算机将大数的素因子分解从NP问题简化为P问题。Shor算法使双密钥系统土崩瓦解（如RSA算法），是量子计算机理论的里程碑。RSA算法以发明者的名字命名RonRivest,

Adi

Shamir

，

LeonardAdleman

RSA算法是第一个能同时用于加密和数字签名的算法，也被认为是目前最优秀的公钥方案之一。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明RSA算法PrivateKey（p，q，r）

其中：p,

q

是两个相异的质数

r

是与

(p-1)(q-1)

互质的数Publickey（m，n）

其中：

m满足rm

==

1

mod

(p-1)(q-1)n

=

pq

RSA算法加密目标

对a加密，假设

a

<

n加密结果

b

==

am

mod

n,

(0

<=

b

<

n)解密过程

c

==

br

mod

pq

(0

<=

c

<

pq)

RSA算法

c

==

br

mod

pq

(0

<=

c

<

pq)

r

是与

(p-1)(q-1)

互质的数

n

=

pq

RSA算法求数N的因子等效于求余因子函数的周期余因子函数

fa,N(x)=axmod

N,

其中:a为与N互素的可随机选定的数

a<Nx=0,1,2,3,4,⋯RSA算法设该函数的周期为r当r为偶数，且rmodN!=+1时

C=gcd

(ar/2

-1,N),D=gcd

(ar/2

+1,N)C和D即为N的两个因子RSA算法举例：

取p=3，q=5，r=7

则m=7n=15

取a=2

则b=8RSA算法对n=15进行分解余因子函数fa,N(x)=axmod

Na可取

2,4,7,8,11,13,14

随机选a=7ax为1,7,49,343,2401,16807,...axmod15的值为

1,7,4,13,1,7,4,13,1,7,...

RSA算法可见周期r=4

且满足r为偶数，

ar/2modN≠±1于是，C=gcd

(ar/2

-1,N)=3

D=gcd

(ar/2

+1,N)=5

为N的两个质因子shor算法对N进行分解设数N

在二进制中位数为L取输入寄存器为2L位,输出寄存器为L位它们的初始状态均设为0,两个寄存器总初始态为|0〉|0〉利用“转动”门操作，将输入寄存器设置为

Shor算法将余因子函数作用于输出寄存器,使其成为对输出寄存器进行测量，若有s种可能的测量结果，则测量后与其他s-1种结果相关的态均不存在Shor算法设z=fl,N(x)是某个最小值l所对应的测量结果，周期性要求所有的测量结果应可以表达为fjr+l,N(x)

其中，r是余因子函数的周期

j=0,1,2,⋯,A，A≈

22L/r。测量后，输入寄存器的状态为Shor算法测量周期r对输入寄存器进行傅里叶变换

Shor算法若r可整除22L,有A=22L/r–1,故方括号内的函数，仅当c为22L/r的倍数时有非零值22L/rShor算法这一步的意义是：周期为r的状态函数的傅里叶变换得到周期为22L/r的状态函数将f(c)以及c=j*22L/r

代入得

Shor算法对此时的输入寄存器进行测量，可得到满足c/22L=k/r,(k=0,1,2,⋯)的c值将c/22L消到一个不可约的分数后，就可以得到r得值。已经证明，此算法重复O(㏒r)可得到所需的结果Shor算法Shor算法对于r不能整除22L的一般情况，情况比较复杂，可以通过一系列的数学和物理变化经过O(㏒N)次重复计算后，得到r的值Shor算法Shor算法Shor

算法为一种随机运算法，但因量子计算具有高度并行能力，每次运算可同时处理22L

个数据，故允许重复计算从恶热得到高几率的结果(~1)。卻又不至於影響計算的有效性。从上可知，以量子计算分解大数质因子所需的步数为㏒N的多项式，即将问题简化为P问题。shor算法经典因子分解与量子因子分解的比较因为L(L+1)/2≤L2

当L>5,则2L>L2

设L=200,2L/2=2100≈1030

设经典计算机的运算速度约1012

次/秒作1030

次运算需1018

秒,而宇宙的寿命约为1017秒在量子计算机上采用量子算法,

需要作的运算次数约为L2≈4×104

同样的运算速度,10-8

秒可完成shor算法举例：取N=15，a=7

15需要四位二进制表示，于是设置输入寄存器为8位，输出寄存器为4位。设置寄存器的状态，并用余因子函数对其作用后，两个寄存器的总状态为（余数共有1，4，7，13四个）

shor算法举例：取N=15，a=7

(1/16)(|0〉|1〉+|1〉|7〉+|2〉|4〉+|3〉|13〉+|4〉|1〉+|5〉|7〉+|6〉|4〉+|7〉|13〉+|8〉|1〉+|9〉|7〉+|10〉|4〉+|11〉|13〉+|12〉|1〉+|13〉|7〉+|14〉|4〉+|15〉|13〉)shor算法举例：取N=15，a=7

对输出寄存器进行测量，将随机得到1，4，7，13中的一个，假设测得的是7

则输入输出寄存器的状态为

shor算法举例：取N=15，a=7

(1/16)(|1〉|7〉+|5〉|7〉

+|13〉|7〉+|9>|7>)=(1/16)(|1〉+|5〉+|9〉+|13〉)|7〉shor算法举例：取N=15，a=7

对输入寄存器进行傅里叶变换，得到

c=64

将c/22L约分得1/4，即