量子计算机的诞生

电子计算机的计算能力存在瓶颈 芯片所能集成的电子元件数量有限 摩尔定律


量子效应 芯片集成密度达到纳米级，出现量子效应
量子计算机的出现对密码学的影响
不可计算问题 密码学
Questions
量子计算机 （超级计算） 可计算问题
如何在所有问题基本上都是可计算的情况下，构建一个新的密码体制？
（现在的研究主要利用相位！）
假定Alice和Bob约定用线偏振量和圆偏振量的4个偏振态来实现量子密钥 分配，用
< > |
表示右旋圆偏振量； 表示左旋员偏振量； 表示水平线偏振量； 表示垂直线偏振量。
采用线偏振基（+）和圆偏振基（O）来测量光子的偏振态。规则如下：
1. Alices随机地发给Bob一组光子。 2. Bob随机的选择+、O接收光子，并测量光子的偏振态。（1/2选对，也 就是1/2测对。） 3. Bob得到光子的实际偏振方向，只有Bob知道！ 4. Bob告诉Alice自己选择的测量基，即上表（2）的偏振基序列。结果不告 诉Alice。Alice告诉Bob那些测量基是正确的，并保留下来，其余的去掉。 若超过m/10不正确，实验失败。 5. Aice和Bob仅保留了相同基时的态，即表中（4）。双方随机地公开其中 的一部分态，若存在不一致，就说明有窃听！若一致，剩下的态转换二 进制数序列。如< |表示1，> -表示0。这样就得到了量子密钥。
主要成果
２00５年，中科院郭光灿院士领导的课题小组 ， 150km的室内量子密钥分配，利用网通的实际通信光缆。 从河北香河到天津。长期误差率低于6%。这是国际上公开 的最长距离的实用光纤量子密码系统。 2002年，德国慕尼黑大学与英军合作，用激光实现了 23.4km的量子密钥分配。 （空气中） 2003年，日本三菱电机公司也宣布，该公司用防盗量 子密码技术与100公里的光纤成功地传送信息，其传递距离 长度可达到87公里，打破了美国洛斯阿拉摩斯国家实验室 (Los Alamos National Laboratory)创造48公里的记录。
安全性讨论：若存在第三方对光子的测量，那么根据测不准 原理，必然会导致光子极化态的改变，并影响Bob的测量结 果。这样在（5）的比对过程中，就会出现不一致，哪怕是 一个相同，都说明信道被窃听。 上述密钥分配的缺陷：光的偏振特性在长距离的光纤传输中 会逐渐退化，造成的误码率增加。现在解决的办法是基于量 子纠缠和EPR效应的。目前最主流的实验方案是用光子的相 位特性进行编码。研究上进展最快的是英国、瑞士和美国。
(应用)
量子密码协议：
Bennett（贝内特）和Brassard（布拉萨德）于 1984年最早提出了量子密码协议，现在被统称为BB84 协议。该密码术与经典密码最大区别是它能抵挡任何破 译技术和计算工具的攻击，原因在于它的安全性是由物 理定律来保证而不是靠某种高复杂的运算。
采用量子的偏振量来作为量子位元
现在不可计算的问题难道永远不可计算了吗？
(量子算法)
量子傅里叶变换(Quantum Fourier Transfer， QFT)。传统的FFT的计算量是O(Nlog2N)，而QFT只 要O(log2N) 。 Shor巧妙地把QFT与数论知识结合起来，提出了 因式分解，解离散对数两个问题的多项式时间算法。 1996年，IBM，Lov Grover提出了Grover’s Algorithm。在N（=2^n）个物品中，取出其中一个 的计算量是O(N^1/2) （原来是O(N) ）
(传统粒子和量子)
传统粒子
传统意义上，任何 粒子都处在一个明确的 状态，是否测量都不会 改变状态。
量子
同时处在不同的状态， 同时处在不同的状 态，只是这些状态各自有 只是这些状态各自有不同 不同的发生概率（量子叠 的发生概率（量子叠加 加性），但是一旦被测量， 性），但是一旦被测量， 状态就被确定（量子态的 坍缩）。
(计算能力)
n个量子位元，可以产生2^n个所有可能组合（n 位二进制数）。量子计算机的处理器有n个量子位元， 那么同一时间执行一次运算，就可以同时对所有2^n 个不同状态作运算。而传统的电子计算机一次只能处 理一个状态。例，按理论估算，一个有5000个量子 位元的量子计算机，用30s就可以解决因式分解问题， 而传统的计算值需要100亿年（地球的岁数是46亿年， 太阳还有50亿年，产生智能只要46亿年！）。
(实现的困境)
量子计算基本上必须用到量子的相干性，没有相干 性，就没有高速的计算能力。但在现实中，我们很难保 持量子的相干性。消想干（量子相干性的衰减），主要 来自于外界环境与系统间的相互影响，且量子位元也不 会是一个独立的系统，受到外部环境的影响。
量子密码：
应该叫做量子加密，它是使用量子的选择来阻止信 息被截取的方式。量子密码已经允许成为可选择的密码技 术。现在的应用以密钥分配为主 。
真正的随机性 量子纠缠态的非局域关联 测不准原理（量子不可克隆原理） 量子隐形传态原理
(量子纠缠态的非局域关联)
一个特殊晶体将一个光子割裂或者一对纠缠的光子， 这对纠缠的光子即使相距很远也相互联结。 设A、B两个自旋为1/2的粒子组成的相关体系处于自 旋单态，即总自旋为0，这对粒子称为EPR对，并且他们 朝相反方向自由运动。 若单独测A，则可能向上，也可能向下，概率1/2。 若已经测得B的自旋为向上，那么粒子A的自旋方向 不管测还是不测，都是向下的。 在测量的时候发生了量子态的坍缩。自旋态的构造 和坍缩都是非定域的，这就是处于纠缠态的粒子的非局 域关联性。（在统计上已经被证实二粒子态所呈现的非 局域关联性）。
(量子位元) 利用量子作出的单一位元，就称为量子位元 （Quantum Bit，Qubit）。
传统位元：任时刻，非0即1，确定的
(真正的随机性) 真正的随机性：
有1/2的概率为状态|0>和|1>。所以量子计算机可以 生成传统电子计算机头疼的真正随机数。
由于电子计算机的完全确定性，电子计算机不会产生 真正的随机数，它只能生成相对的随机数，即伪随机数， 也就是说产生的伪随机数遵守一定的规律。