“耐量子计算机密码“

量子计算机将在10年或者20年内变成现实，那时现在所用的RSA等几种密码都将失效。最近听到一个名词叫“耐量子计算机密码“。

我不知道大家怎么理解这概念。

量子计算机

 武强



　　量子力学和计算机这两个看似互不相干的理论，其结合却产生了一门也许会从根本上影响人类未来发展的新兴学科――量子信息学，通常人们通俗地称之为“量子计算机”。本文将简要的介绍量子信息理论的基本概念和历史背景，量子计算机的研究进展，及对这一学科未来发展前景的展望。

 
　　在介绍量子信息论的专业知识之前，先谈谈量子计算机的提出及其产生过程。众所周知，20世纪后半页计算机技术大行其道，人类进入信息时代。随着计算机芯片的集成度越来越高元件越做越小，集成电路技术现在正逼近其极限，科学家们看到传统的计算机结构必将有终结的一天，而且尽管计算机的运行速度与日俱增，但是有一些难题是计算机根本无法解决的，例如大数的因式分解，理论上只要一个数足够大，这个难题够目前最快的计算机忙几亿年的。

　　几十年前，一些先驱者，如美国IBM公司的Charles H. Bennett等人就开始研究信息处理电路未来的去向问题，他们指出，当计算机元件的尺寸变得非常之小时，我们不得不面对一个严峻的事实：必须用量子力学来对它们进行描述。八十年代初期，一些物理学家证明一台计算机原则上可以以纯粹的量子力学的方式运行，之后很长一段时间，这一研究领域渐趋冷清，因为科学家们不能找到实际的系统可供进行量子计算机的实验，而且还尚不清楚量子计算机解决数学问题是否会比常规计算机快。

　　进入20世纪90年代，实验技术和理论模型的进步为量子计算机的实现提供了可能。尤其值得一提的是1994年美国贝尔实验室的Peter W. Shor证明运用量子计算机竟然能有效地进行大数的因式分解。这意味着以大数因式分解算法为依据的电子银行、网络等领域的RSA公开密钥密码体系在量子计算机面前不堪一击，几年后Grover提出“量子搜寻算法”，可以破译DES密码体系。于是各国政府纷纷投入大量的资金和科研力量进行量子计算机的研究，如今这一领域已经形成一门新型学科――量子信息学。

量子信息的存储――量子比特（q-bit）

　　量子计算机为什么会有这么大的威力呢？其根本原因在于构成量子计算机的基本单元――量子比特（q-bit），它具有奇妙的性质，这种性质必须用量子力学来解释，因此称为量子特性。为了更好地理解什么是量子比特，让我们看看经典计算机的比特与量子计算机的量子比特有什么不同。我们现在所使用的计算机采用二进制来进行数据的存储和运算，在任何时刻一个存储器位代表0或1，例如在逻辑电路中电压为5V表示1，0V表示0，如果出现其他数值计算机就会以为是出错了。

　　而量子比特是由量子态相干叠加而成，一个具有两种状态的系统可以看作是一个“二进制”的量子比特，对量子力学有了解的人都知道，在量子世界里物质的状态是捉摸不定的，如电子的位置可以在这里同时也可以在那里，原子的能级在某一时刻可以处于激发态，同时也可以处于基态。我们就采用有两个能级的原子来做量子计算机的q-bit。规定原子在基态时记为 |0〉，在激发态时原子的状态记为 |1〉 ，而原子具体处于哪个态我们可以通过辨别原子光谱得以了解。微观世界的奇妙之处在于，原子除了保持上述两种状态之外，还可以处于两种态的线性叠加，记为 |φ〉=a |1〉+ b |0〉 ，其中a，b分别代表原子处于两种态的几率幅。如此一来，这样的一个q-bit不仅可以表示单独的“0”和“1”（a=0时只有“0”态，b=0时只有“1”态），而且可以同时既表示“0”，又表示“1”（a,b都不为0时）。



三个量子比特的系统，点击放大
图片引自http://helios.hampshire.edu/lspector/aaai-99-www/sld033.htm


　　举一个简单的例子，假如有一个由三个比特构成的存储器，如果是由经典比特构成则能表示000，001，010，011，100，101，110，111这8个二进制数，即0~7这8个十进制数，但同一时刻只能表示其中的一个数。若此存储器是由量子比特构成，如果三个比特都只处于 |0〉或 |1〉则能表示与经典比特一样的存储器，但是量子比特还可以处于 |0〉与 |1〉的叠加态，假设三个q-bit每一个都是处于( |0〉+ |1〉) / (√2) 态，那么它们组成的量子存储器将表示一个新的状态，用量子力学的符号，可记做：

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

　　不难看出，上面这个公式表示8种状态的叠加，既在某一时刻一个量子存储器可以表示8个数。

量子信息的运算――量子算法

　　接下来我们看看量子计算机如何对这些态进行运算。假设现在我们想求一个函数f(n)，(n＝0~7)的值，采用经典计算的办法至少需要下面的步骤：

　　存储器清零→赋值运算→保存结果→再赋值运算→再保存结果……

　　对每一个n都必须经过存储器的赋值和函数f(n)的运算等步骤，而且至少需要8个存储器来保存结果。如果是用量子计算机来做这个题目则在原理上要简洁的多，只需用一个量子存储器，把各q-bit制备到( |0〉+ |1〉) / (√2)态上就一次性完成了对8个数的赋值，此时存储器成为态 |φ〉，然后对其进行相应的幺正变换以完成函数f(n)的功能，变换后的存储器内就保存了所需的8个结果。这种能同时对多个态进行操纵，所谓“量子并行计算”的性质正是量子计算机巨大威力的奥秘所在。

　　可能有人会还担心我们怎么把所需要的数据从8个或更多个结果中挑选出来呢？对具体的问题这就要要采用相应的量子算法，例如Shor提出的大数因式分解算法，和Grover的量子搜索算法漂亮地解决了两类问题。按照Shor算法，对一个1000位的数进行因式分解只需几分之一秒，同样的事情由目前最快的计算机来做，则需1025年！而Grover的搜索算法则被形象地称为“从稻草堆中找出一根针”！尽管量子算法已经很多了，但是到目前为止真正的量子计算机才只做到5个q-bit，只能做很简单的验证性实验。

　　除了最基本的量子位，量子计算，量子超空间传送等概念，在量子计算机的研究中还有许多有趣的现象和新的概念，如量子编码，量子逻辑门和量子网络，量子纠缠交换等。

量子计算机能做什么

　　量子计算机可以进行大数的因式分解，和Grover搜索破译密码，但是同时也提供了另一种保密通讯的方式。在利用EPR对进行量子通讯的实验中中我们发现，只有拥有EPR对的双方才可能完成量子信息的传递，任何第三方的窃听者都不能获得完全的量子信息，正所谓解铃还需系铃人，这样实现的量子通讯才是真正不会被破解的保密通讯。此外量子计算机还可以用来做量子系统的模拟，人们一旦有了量子模拟计算机，就无需求解薛定愕方程或者采用蒙特卡罗方法在经典计算机上做数值计算，便可精确地研究量子体系的特征。



图片引自http://www.amd1.com/quantum_computers.html


展望

　　现在用原子实现的量子计算机只有5个q-bit，放在一个试管中而且配备有庞大的外围设备，只能做1+1=2的简单运算，正如Bennett教授所说，“现在的量子计算机只是一个玩具，真正做到有实用价值的也许是5年，10年，甚至是50年以后”，我国量子信息专家中国科技大学的郭光灿教授则宣称，他领导的实验室将在5年之内研制出实用化的量子密码，来服务于社会！科学技术的发展过程充满了偶然和未知，就算是物理学泰斗爱因斯坦也决不会想到，为了批判量子力学而用他的聪明大脑假想出来的EPR态，在六十多年后不仅被证明是存在的，而且还被用来做量子计算机。

量子计算机将在10年或者20年内变成现实，那时现在所用的RSA等几种密码都将失效。

我觉得10年或者20年是不可能做到的，至多只能说使得RSA的密钥变得更长，但不会从根本上在多项式时间内分解大素数。因为大素数分解问题是NP难解问题，这个问题解决，所有的NP完全问题都可以多项式时间解出，这在现在是不可想象的。

我喜欢对事情保持低调,但是暂时没必要担心量子计算机的问题,我的根据是计算机这门学科现在大家开始探讨它的体系(冯.络伊曼)的缺陷,但是,现在计算机的三大方向(系统结构,人工智能,形式语言)都还处在理论不完备的状态,要使现在的计算机在理论基础上更坚实,都还有那么多路要走,毕竟现在计算机的整个大量的研究予应用也才半个世纪,对于量子计算机的理论基础就更不要有太高奢望了,研究领域的前瞻性是必不可少的,但是从应用来讲有很长的路要走,这只是我的个人看法:)如果对量子计算机充满信心的兄弟不要怪我喔