量子计算机 林晓菲 2004-05-14

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

量子计算机的发展及现状 三大热点 量子计算机 量子密码术 量子通信

量子计算机 20世纪后半页计算机技术大行其道，人类进入信息时代。随着计算机芯片的集成度越来越高元件越做越小，集成电路技术现在正逼近其极限 。 原件小型化过程

量子计算机 从大规模集成电路的发展史看，单粒子晶体管似乎是必然趋势。当一个晶体管里包含的杂质电子数目只有一个或少数几个时，量子行为便为主要性质，这时计算方式必然要用量子力学才能正确处理。 早在60年代, Landauer就已研究计算过程的可逆性与统计力学的关系。量子计算机的概念源于对可逆计算机的研究 。

量子计算机 早期量 子计算机，实际上是用量子力学语言描述的经典计算机，并没有用到量子力学的本质特性，如量子态的叠加性和相干性。 Feynman，Fredkin，Toffoli 等人考虑由量子力学原理确定计算规则发生的现象后,发现计算理论与物理学规律密不可分。

量子计算机 Deutch 指出,这种以量子力学原理決定的计算过程 (即量子计算) 很多方面体现出与经典计算非常不同的行为。 八十年代初期，一些物理学家证明一台计算机原则上可以以纯粹的量子力学的方式运行 之后很长一段时间，因为科学家们不能找到实际的系统可供进行量子计算机的实验，而且还尚不清楚量子计算机解决数学问题是否会比常规计算机快，这一研究领域渐趋冷清。

量子计算机 进入20世纪90年代，实验技术和理论模型的进步为量子计算机的实现提供了可能。 要使量子 计算成为现实，一个核心问题就是克服消相干。而量子编码是迄今发现的克服消相干 最有效的方法。主要的几种量子编码方案是：量子纠错码、量子避错码和量子防错码。

量子计算机 目前已经提出的在实验上实现对微观量子态的操纵方案主要利用了原子和光腔 相互作用、冷阱束缚离子、电子或核自旋共振、量子点操纵、超导量子干涉等。 尤其值得一提的是1994年美国贝尔实验室的Peter W. 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个数，并且在某一时刻，只能表示其中的一个数 000 001 010 011 100 101 110 111

量子寄存器 若此寄存器器是由量子比特构成 ，每个量子比特可以处于|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门 量子网路 将量子门按某种方式连接，构成量子网路，以进行复杂的运算。 利用XOR门与转动门构成的Toffolli门

量子网路 K-位寄存器上作分离（快速）傅立叶变换的量子网路

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

shor算法 1994年，Peter Shor提出利用量子计算机将大数的素因子分解从NP问题简化为P问题。 Shor算法使双密钥系统土崩瓦解（如RSA算法），是量子计算机理论的里程碑。

RSA算法 以发明者的名字命名 Ron Rivest, Adi Shamir ， Leonard Adleman

RSA算法 Private Key（p，q，r） 其中：p, q 是两个相异的质数 r 是与 (p-1)(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)

c == br mod pq (0 <= c < pq) r 是与 (p-1)(q-1) 互质的数 RSA算法 c == br mod pq (0 <= c < pq) r 是与 (p-1)(q-1) 互质的数 n = pq

RSA算法 求数N 的因子等效于求余因子函数的周期 余因子函数 f a, N ( x) = axmod N ,

RSA算法 设该函数的周期为r 当r 为偶数，且r mod N != + 1时 C = gcd ( ar/ 2 - 1 , N) , D = gcd ( ar/ 2 + 1 , N) C 和D 即为N 的两个因子

RSA算法 举例： 取 p=3，q=5，r=7 则 m=7 n=15 取 a=2 则 b=8

RSA算法 对n=15进行分解 余因子函数f a, N ( x) = axmod N a可取 2 ,4 ,7 ,8 ,11 ,13 ,14 1 ,7 ,4 ,13 ,1 ,7 ,4 ,13 ,1 ,7 , . . .

RSA算法 可见周期r=4 且满足r为偶数， ar/ 2 mod N ≠±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) j = 0, 1, 2, ⋯, A，A ≈ 22L/r。 测量后，输入寄存器的状态为

Shor算法 测量周期 r 对输入寄存器进行傅里叶变换

Shor算法 若 r 可整除 22L, 有 A = 22L/r – 1, 故 方括号内的函数，仅当c 为 22L/r 的倍数时有非零值 22L/r

Shor算法 这一步的意义是：周期为 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 ≤L 2 当L > 5 ,则2L > L 2 设经典计算机的运算速度约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 +| 3〉| 13〉+| 4〉| 1〉+| 5〉| 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，即 r= 4

主要内容 量子计算机的发展及现状 从计算机科学表述的量子力学原理 量子计算基础 量子算法举例—shor算法 参考文献

参考文献 书籍

参考文献 人物

参考文献 杂志文章

参考文献 杂志文章

参考文献 杂志文章

参考文献 其它文章 Quantum Computation, Physics World, 1992, David Deutsch A quantum leap in secret communications. William Bown, New Scientist 30/1/93 Tight Bounds on Quantum Searching, M. Boyer, G. Brassard, P. Hoyer, A. Tapp Quantum Cryptoanalysis introduction, Artur Ekert Weirdest Computer of All, The Economist, 28 Sept. 1996

参考文献 其他文章 Is the universe a computer?. Julian Brown, New Scientist 14/6/1990 It takes two to tangle - in the quantum world. Ben Stein, New Scientist, 28/9/96 Quantum communication thwarts eavesdroppers. David Deutsch, New Scientist, 9/12/89 Quantum leap in code cracking computers. Mark Ward, New Scientist, 23/12/95 Quantum Code-breaking, The Economist, 30 Apr. 1994 Physical Revue Letters. (Vol. 78 p3414).

参考文献 网页

谢谢！