1、量子计算机量子计算机林晓菲2004-05-14主要内容主要内容量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子算法举例shor算法参考文献主要内容主要内容量子计算机的发展及现状量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子算法举例shor算法参考文献量子计算机的发展及现状量子计算机的发展及现状三大热点 量子计算机 量子密码术 量子通信量子计算机量子计算机20世纪后半页计算机技术大行其道，人类进入信息时代。随着计算机芯片的集成度越来越高元件越做越小，集成电路技术现在正逼近其极限 。原件小型化过程原件小型化过程量子计算机量子计算机从大规模集成电路的发展史看
2、，单粒子晶体管似乎是必然趋势。当一个晶体管里包含的杂质电子数目只有一个或少数几个时，量子行为便为主要性质，这时计算方式必然要用量子力学才能正确处理。早在60年代, Landauer就已研究计算过程的可逆性与统计力学的关系。量子计算机的概念源于对可逆计算机的研究 。量子计算机量子计算机早期量 子计算机，实际上是用量子力学语言描述的经典计算机，并没有用到量子力学的本质特性，如量子态的叠加性和相干性。 Feynman，Fredkin，Toffoli 等人考虑由量子力学原理确定计算规则发生的现象后,发现计算理论与物理学规律密不可分。量子计算机量子计算机Deutch 指出,这种以量子力学原理決定的计算过
3、程 (即量子计算) 很多方面体现出与经典计算非常不同的行为。八十年代初期，一些物理学家证明一台计算机原则上可以以纯粹的量子力学的方式运行之后很长一段时间，因为科学家们不能找到实际的系统可供进行量子计算机的实验，而且还尚不清楚量子计算机解决数学问题是否会比常规计算机快，这一研究领域渐趋冷清。量子计算机量子计算机进入20世纪90年代，实验技术和理论模型的进步为量子计算机的实现提供了可能。要使量子 计算成为现实，一个核心问题就是克服消相干。而量子编码是迄今发现的克服消相干 最有效的方法。主要的几种量子编码方案是：量子纠错码、量子避错码和量子防错码。 量子计算机量子计算机目前已经提出的在实验上实现对微
4、观量子态的操纵方案主要利用了原子和光腔 相互作用、冷阱束缚离子、电子或核自旋共振、量子点操纵、超导量子干涉等。 尤其值得一提的是1994年美国贝尔实验室的Peter W. Shor证明运用量子计算机能有效地进行大数的因式分解。量子计算机量子计算机几年后Grover提出“量子搜寻算法”，可以破译DES密码体系。 于是各国政府纷纷投入大量的资金和科研力量进行量子计算机的研究美，英，德，法，加拿大，日本，中国大陆，台湾，新加坡，印度等已先后成立专门研究量子计算机的研究群。量子密码术量子密码术量子密码术是密码术与量子力学结合的产物，它利用了系统所具有的量子性质。首先首先想到将量子物理用于密码术的是美国
5、科学家威斯纳威斯纳。1970年 ，威斯纳提出，可利用单量子态制造不可伪造的“电子钞票”。但这个设想的实现需要长时间保存单量子态，不太现实。量子密码术量子密码术贝内特和布拉萨德在研究中发现，单量子态虽然不好保存但可用于传输信息。 1984年，贝内特和布拉萨德提出了第一个量子密码术方案，称为BB84方案方案，由此迎来了量子密码术的新时期。1992年，贝内特又提出 一种更简单，但效率减半的方案，即B92方案方案。 量子密码术量子密码术量子密码术并不用于传输密文，而是用于建立、传输密码本。根据量子力学的不确定性原理以及量子不可克隆定理，任何窃 听者的存在都会被发现，从而保证密码本的绝对安全，也就保证了
6、加密信息的绝对安全。 量子密码术量子密码术最初的量子密码通信利用的都是光子的偏振特性，在长距离的光纤传输中，光的偏振性会退化，造成误码率的增加。 目前主流的实验方案主流的实验方案则用光子的相位特性进行编码。与偏振编码相比，相位编码的好处是对光的偏振态要求不那么苛刻。目前，在量子密码术实验研究上进展最快的国家为英国、瑞士和美国。 量子通信量子通信量子通信系统的基本部件基本部件包括量子态发生器、量子通道和量子测量装置。按其所传输的信息分为两类：经典量子通信和量子通信。 经典量子通信主要用于量子密钥的传输 。量子通信量子通信量子通信可用于量子隐形传送量子隐形传送和量子纠缠的分发。 隐形传送指的是脱离
7、实物的一种“完全”的信息传送。从物理学角度，可以这样来想象隐形传送的过程隐形传送的过程：先提取原物的所有信息，然后将这些信息传送到接收地点，接收者依据这些信息，选取与构成原物完全相同的基本单元，制造出原物完美的复制品。量子通信量子通信量子力学的不确定性原理不允许精确地提取 原物的全部信息，这个复制品不可能是完美的。因此长期以来，隐形传送不过是一种 幻想而已。 1997年，在奥地利留学的中国青年学者潘建伟与荷兰学者波密斯特等人合作，首次实现了未知量子态的远程传输。这是国际上首次在实验上成功地将一个量子态从甲地的光子传送到乙地的光子上。主要内容主要内容量子计算机的发展及现状从计算机科学表述的量子力
8、学原从计算机科学表述的量子力学原理理量子计算基础量子算法举例shor算法参考文献量子力学原理量子力学原理量子计算机以量子力学建立逻辑体系，与量子计算机有关的量子力学的原理，即量子状态的主要性质包括： 状态叠加状态叠加 干涉性干涉性 纠缠 不可复制性与不确定性 状态变化状态变化 量子力学原理量子力学原理状态叠加状态叠加設 |n為可能的量子状态,則iaik|k也是一个可能的量子状态。对应于量子计算,这表示量子计算机可以代表经典计算机的很多状态。它使得大规模的量子并行存储成为可行, 如 n 能阶系統至少可存 2n个数据, 由于理论上n无上限。 因此, 可以利用此特性作大规模的存储。又由于各状态之间有
9、相位相干,存储过程是平行的。量子力学原理量子力学原理干涉性干涉性 状态叠加时，依各状态间的相位关系可能出现相长或相消的状态，这是经典计算机的布尔状态所不具备的特征。状态变化状态变化 量子依照幺正变换法则，有系统的汉密尔顿算子决定其变化。量子力学原理量子力学原理 干涉性，状态变化这两个性质是量子并行计算的基础，因为系统的各个状态按照幺正变换同时变化，故一次量子计算可以同时作用在多个数据上。量子计算机的优越性主要体现在量子并行计算上量子力学原理量子力学原理纠缠纠缠 整体的状态波函数不变并不一定表示各成份状态的波函数不变,这说明各成分波函数间有非定域的关联性。不可复制性与不确定性不可复制性与不确定性
10、 不能精确的复制一个状态，也不能在不打扰该状态的情况下观察此状态量子力学原理量子力学原理纠缠，不可复制性与不确定性是量子加密，密码术，量子通信的基础。借助于纠缠性质，原则上可以实现超距的重生-灭体过程。量子状态的不可复制性与不确定性是的量子通信免于被窃听或者即使被窃听也无法解读。主要内容主要内容量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子计算基础量子算法举例shor算法参考文献量子计算基础量子计算基础量子比特量子寄存器量子门量子网路量子比特量子比特在经典计算机中，运算的基本单元是比特（bit），它的基本状态是二值布尔逻辑状态（0或1）在量子计算机中，运算的基本单元是量子
11、比特（q-bit），它的基本状态是两种状态的叠加。 量子比特量子比特规定原子在基态时记为 |0，在激发态时原子的状态记为 |1。原子除了保持上述两种状态之外，还可以处于两种态的线性叠加，记为 |=a |1+ b |0 a和b分别代表原子处于两种态的几率幅 量子比特量子比特量子比特量子比特一种典型的量子比特一种典型的量子比特量子点量子点 它基本上是一个被困在原子牢笼中的单一电子。当量子点暴露在刚好合适波长的激光脉冲下并持续一段时间，电子就会达到一种激发态：而第二次的激光脉冲又会使电子衰落回它的基态。电子的基态和激发态可以被视为量比的0和1状态，而激光在将量比从0状态撞击到1状态或从1撞击到0的应
12、用，能够被看成是一种对取非功能的控制。 量子比特量子比特一种典型的量子比特一种典型的量子比特量子点量子点 如果激光持续时间只有取非功能要求的一半，那么电子将同时处于基态和激发态的重叠中，这也等价于量比的连贯性状态。而更多复杂的逻辑功能可以通过使用成对的安排好的量子点被模拟出来。因此，看起来量子点是一个合适的建造量子计算机的候选人。 量子寄存器量子寄存器存储一系列量子比特的体系称为量子寄存器 假如有一个由三个比特构成的寄存器 在经典计算机中，可以表示07共8个数，并且在某一时刻，只能表示其中的一个数 000 001 010 011 100 101 110 111量子寄存器量子寄存器 若此寄存器器
13、是由量子比特构成 ，每个量子比特可以处于|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）这些基本的逻辑运算称为门量子门量子门与经典计算机的门相对应的，量子计算机中的量子门由幺正变换实施。量子
14、门的真值表较经典的真值表要广泛得多。量子门是实现量子并行计算的基石。 量子门量子门可以作为实现量子计算的通用逻辑门的Fredkin 门和Toffoli门Fredkin门的真值表门的真值表量子门量子门Toffoli门及其真值表门及其真值表量子门量子门异或（异或（XOR）门及其对应操作）门及其对应操作量子网路量子网路将量子门按某种方式连接，构成量子网路，以进行复杂的运算。 利用利用XOR门与转动门构成的门与转动门构成的Toffolli门门量子网路量子网路K-位寄存器上作分离（快速）傅立叶变换的量子网路主要内容主要内容量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子算法举例量子算
15、法举例shor算法算法参考文献shor算法算法1994年，Peter Shor提出利用量子计算机将大数的素因子分解从NP问题简化为P问题。Shor算法使双密钥系统土崩瓦解（如RSA算法），是量子计算机理论的里程碑。RSA算法算法以发明者的名字命名 Ron Rivest, Adi Shamir ， Leonard Adleman RSA算法是第一个能同时用于加密和数字签名的算法 ，也被认为是目前最优秀的公钥方案之一 。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明 RSA算法算法Private Key（p，q，r） 其中：p, q 是两个相异的质数 r 是与 (p-1
16、)(q-1) 互质的数 Public key（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=brmodpq(0=cpq)r是与是与(p-1)(q-1)互质的数互质的数n=pqRSA算法算法求数N 的因子等效于求余因子函数的周期余因子函数 f a, N ( x) = axmod N , 其中:a 为与N 互素的可随机选定的数 a 5 ,则2L L 2 设
17、L = 200 ,2 L / 2= 2100 1030 设经典计算机的运算速度约1012 次/ 秒 作1030 次运算需1018 秒,而宇宙的寿命约为1017秒在量子计算机上采用量子算法, 需要作的运算次数约为L 2 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 +|
18、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 对输入寄存器进
19、行傅里叶变换，得到 c=64 将c/22L 约分得1/4，即 r= 4 主要内容主要内容量子计算机的发展及现状从计算机科学表述的量子力学原理量子计算基础量子算法举例shor算法参考文献参考文献参考文献参考文献书籍书籍 参考文献参考文献人物人物 参考文献参考文献杂志文章杂志文章 参考文献参考文献杂志文章杂志文章参考文献参考文献杂志文章杂志文章参考文献参考文献其它文章其它文章 Quantum Computation, Physics World, 1992, David DeutschA quantum leap in secret communications. William Bown, Ne
20、w Scientist 30/1/93Tight Bounds on Quantum Searching, M. Boyer, G. Brassard, P. Hoyer, A. TappQuantum Cryptoanalysis introduction, Artur EkertWeirdest Computer of All, The Economist, 28 Sept. 1996参考文献参考文献其他文章其他文章 Is the universe a computer?. Julian Brown, New Scientist 14/6/1990It takes two to tangl
21、e - in the quantum world. Ben Stein, New Scientist, 28/9/96Quantum communication thwarts eavesdroppers. David Deutsch, New Scientist, 9/12/89Quantum leap in code cracking computers. Mark Ward, New Scientist, 23/12/95Quantum Code-breaking, The Economist, 30 Apr. 1994Physical Revue Letters. (Vol. 78 p3414). 参考文献参考文献网页网页
