关键词：量子比特；量子力学；量子相干性；并行运算
0 引言
自1946年第一台电子计算机诞生至今，共经历了电子管、晶体管、中小规模集成电路和大规模集成电路四个时代。计算机科学日新月异，但其性能却始终满足不了人类日益增长的信息处理需求，且存在不可逾越的“两个极限”。
其一，随着传统硅芯片集成度的提高，芯片内部晶体管数与日俱增，相反其尺寸却越缩越小(如现在的英特尔双核处理器采用最新45纳米制造工艺，在143平方毫米内集成2.91亿晶体管)。根据摩尔定律估算，20年后制造工艺将达到几个原子级大小，甚至更小，从而导致芯片内部微观粒子性越来越弱，相反其波动性逐渐显著，传统宏观物理学定律因此不再适用，而遵循的是微观世界焕然一新的量子力学定理。也就是说，20年后传统计算机将达到它的“物理极限”。
其二，集成度的提高所带来耗能与散热的问题反过来制约着芯片集成度的规模，传统硅芯片集成度的停滞不前将导致计算机发展的“性能极限”。如何解决其发热问题?研究表明，芯片耗能产生于计算过程中的不可逆过程。如处理器对输入两串数据的异或操作而最终结果却只有一列数据的输出，这过程是不可逆的，根据能量守恒定律，消失的数据信号必然会产生热量。倘若输出时处理器能保留一串无用序列，即把不可逆转换为可逆过程，则能从根本上解决芯片耗能问题。利用量子力学里的玄正变换把不可逆转为可逆过程，从而引发了对量子计算的研究。
1 量子计算的基本原理
1.1 传统计算的存储方式
首先回顾传统计算机的工作原理。传统电子计算机采用比特作为信息存储单位。从物理学角度，比特是两态系统，它可保持其中一种可识别状态，即“1”或者“()”。对于“1”和“0”，可利用电流的通断或电平的高低两种方法表示，然后可通过与非门两种逻辑电路的组合实现加、减、乘、除和逻辑运算。如把0～0个数相加，先输入“00”，处理后输入“01”，两者相“与”再输入下个数“10”，以此类推直至处理完第n个数，即输入一次，运算一次，n次输入，n次运算。这种串行处理方式不可避免地制约着传统计算机的运算速率，数据越多影响越深，单次运算的时间累积足可达到惊人的数字。例如在1994年共1600个工作站历时8月才完成对129位(迄今最大长度)因式的分解。倘若分解位数多达1000位，据估算，即使目前最快的计算机也需耗费1025年。而遵循量子力学定理的新一代计算机利用超高速并行运算只需几秒即可得出结果。现在让我们打开量子计算的潘多拉魔盒，走进奇妙神秘的量子世界。
1.2 量子计算的存储方式
量子计算的信息存储单位是量子比特，其两态的表示常用以下两种方式：
(1)利用电子自旋方向。如向左自转状态代表“1”，向右自转状态代表“0”。电子的自转方向可通过电磁波照射加以控制。
(2)利用原子的不同能级。原子有基态和激发态两种能级，规定原子基态时为“0”，激发态时为“1”。其具体状态可通过辨别原子光谱或核磁共振技术辨别。
量子计算在处理0～n个数相加时，采用的是并行处理方式将“00”、“01”、“10”、“11”等n个数据同时输入处理器，并在最后做一次运算得出结果。无论有多少数据，量子计算都是同时输入，运算一次，从而避免了传统计算机输入一次运算一次的耗时过程。当对海量数据进行处理时，这种并行处理方式的速率足以让传统计算机望尘莫及。
1.3 量子叠加态
量子计算为何能实现并行运算呢?根本原因在于量子比特具有“叠加状态”的性质。传统计算机每个比特只能取一种可识别的状态“0”或“1”，而量子比特不仅可以取“0”或“1”，还可同时取“0”和“1”，即其叠加态。以此类推，n位传统比特仅能代表2n中的某一态，而n位量子比特却能同时表示2n个叠加态，这正是量子世界神奇之处。运算时量子计算只须对这2n个量子叠加态处理一次，这就意味着一次同时处理了2n个量子比特(同样的操作传统计算机需处理2n次，因此理论上量子计算工作速率可提高2n倍)，从而实现了并行运算。
量子叠加态恐怕读者一时难以接受，即使当年聪明绝顶的爱因斯坦也颇有微词。但微观世界到底有别于我们所处的宏观世界，存在着既令人惊讶又不得不承认的事实，并取得了多方面验证。以下用量子力学描述量子叠加态。
现有两比特存储单元，经典计算机只能存储00，01，10，11四位二进制数，但同一时刻只能存储其中某一位。而量子比特除了能表示“0”或“1”两态，还可同时表示“0”和“1”的叠加态，量子力学记为：
lφ〉＝al1〉＋blO〉
其中ab分别表示原子处于两态的几率，a＝0时只有“0”态，b＝0时只有“1”态，ab都不为0时既可表示“0”，又可表示“1”。因此，两位量子比特可同时表示4种状态，即在同一时刻可存储4个数，量子力学记为：
1.4 量子相干性
量子计算除可并行运算外，还能快速高效地并行运算，这就用到了量子的另外一个特性――量子相干性。
量子相干性是指量子之间的特殊联系，利用它可从一个或多个量子状态推出其它量子态。譬如两电子发生正向碰撞，若观测到其中一电子是向左自转的，那么根据动量和能量守恒定律，另外一电子必是向右自转。这两电子间所存在的这种联系就是量子相干性。
可以把量子相干性应用于存储当中。若某串量子比特是彼此相干的，则可把此串量子比特视为协同运行的同一整体，对其中某一比特的处理就会影响到其它比特的运行状态，正所谓牵一发而动全身。量子计算之所以能快速高效地运算缘归于此。然而令人遗憾的是量子相干性很难保持，在外部环境影响下很容易丢失相干性从而导致运算错误。虽然采用量子纠错码技术可避免出错，但其也只是发现和纠正错误，却不能从根本上杜绝量子相干性的丢失。因此，到达高效量子计算时代还有一段漫长曲折之路。
2 对传统密码学的冲击
密码通信源远流长。早在2500年前，密码就已广泛应用于战争与外交之中，当今的文学作品也多有涉猎，如汉帝赐董承的衣带诏，文人墨客的藏头诗，金庸笔下的蜡丸信等。随着历史的发展，密码和秘密通讯备受关注，密码学也应运而生。防与攻是一个永恒的活题，当科学家们如火如荼地研究各种加密之策时，破译之道也得以迅速发展。
传统理论认为，大数的因式分解是数学界的一道难题，至今也无有效的解决方案和算法。这一点在密码学有重要应用，现在广泛应用于互联网，银行和金融系统的RSA加密系统就是基于因式难分解而开发出来的。然而，在理论上包括RSA在内的任何加密算法都不是天衣无缝的，利用穷举法可一一破解，只要衡量破解与所耗费的人力物力和时间相比是否合理。如上文提到传统计算机需耗费1025年才能对1000位整数进行因式分解，从时间意义上讲，RSA加密算法是安全的。但是，精通高速并行运算的量子计算一旦问世，萦绕人类很久的因式分解难题迎刃而解，传统密码学将受到前所未有的巨大冲击。但正所谓有矛必有盾，相信届时一套更为安全成熟的量子加密体系终会酝酿而出。
3 近期研究成果
目前量子计算的研究仍处于实验阶段，许多科学家都以极大热忱追寻量子计算的梦想，实现方案虽不少，但以现在的科技水平和实验条件要找到一种合适的载体存储量子比特，并操纵和观测其微观量子态实在是太困难了，各界科学家历时多年才略有所获。
(1)1994年物理学家尼尔和艾萨克子利用丙胺酸制出一台最为基本的量子计算机，虽然只能做一些像1＋1＝2这样简单的运算，但对量子计算的研究具有里程碑的意义。
(2)2000年8月IBM用5个原子作为处理和存储器制造出当时最为先进的量子计算机，并以传统计算机无法匹敌的速度完成对密码学中周期函数的计算。
(3)2000年日本日立公司成功开发出“单电子晶体管”量子元件，它可以控制单个电子的运动，且具有体积小，功耗低的特点(比目前功耗最小的晶体管约低1000倍)。
(4)2001年IBM公司阿曼顿实验室利用核磁共振技术建构出7位量子比特计算机，其实现思想是用离子两个自转状态作为一个量子比特，用微波脉冲作为地址。但此法还不能存储15位以上的量子单元。
(5)2003年5月《Nature》杂志发表了克服量子相关性的实验结果，对克服退相干，实现量子加密、纠错和传输在理论上起到指导作用，从此量子通信振奋人心。
(6)2004年9月，NTT物性科学研究所试制出新一代存储量子比特的新载体――“超导磁束量子位”。它可通过微波照射大幅度提高对量子比特自由度的控制，其量子态也相对容易保持。
【关键词】量子计算；量子计算机；量子算法；量子信息处理
1、引言
在人类刚刚跨入21山_纪的时刻，！日_界科技的重大突破之一就是量子计算机的诞生。德国科学家已在实验室研制成功5个量子位的量子计算机，而美国LosAlamos国家实验室正在进行7个量子位的量子计算机的试验。它预示着人类的信息处理技术将会再一次发生巨大的飞跃，而研究面向量子计算机以量子计算为基础的量子信息处理技术已成为一项十分紧迫的任务。
2、子计算的物理背景
任何计算装置都是一个物理系统。量子计算机足根据物理系统的量子力学性质和规律执行计算任务的装置。量子计算足以量子计算目L为背景的计算。是在量了力。4个公设（postulate）下做出的代数抽象。Feylllilitn认为，量子足一种既不具有经典耗子性，亦不具有经典渡动性的物理客体（例如光子）。亦有人将量子解释为一种量，它反映了一些物理量（如轨道能级）的取值的离散性。其离散值之问的差值（未必为定值）定义为量子。按照量子力学原理，某些粒子存在若干离散的能量分布。称为能级。而某个物理客体（如电子）在另一个客体（姻原子棱）的离散能级之间跃迁（transition。粒子在不同能量级分布中的能级转移过程）时将会吸收或发出另一种物理客体（如光子），该物理客体所携带的能量的值恰好是发生跃迁的两个能级的差值。这使得物理“客体”和物理“量”之问产生了一个相互沟通和转化的桥梁；爱因斯坦的质能转换关系也提示了物质和能量在一定条件下是可以相互转化的因此。量子的这两种定义方式是对市统并可以相互转化的。量子的某些独特的性质为量了计算的优越性提供了基础。
3、量子计算机的特征
量子计算机，首先是能实现量子计算的机器，是以原子量子态为记忆单元、开关电路和信息储存形式，以量子动力学演化为信息传递与加工基础的量子通讯与量子计算，是指组成计算机硬件的各种元件达到原子级尺寸，其体积不到现在同类元件的1%。量子计算机是一物理系统，它能存储和处理关于量子力学变量的信息。量子计算机遵从的基本原理是量子力学原理：量子力学变量的分立特性、态迭加原理和量子相干性。信息的量子就是量子位，一位信息不是0就是1，量子力学变量的分立特性使它们可以记录信息：即能存储、写入、读出信息，信息的一个量子位是一个二能级（或二态）系统，所以一个量子位可用一自旋为1/2的粒子来表示，即粒子的自旋向上表示1，自旋向下表示0；或者用一光子的两个极化方向来表示0和1；或用一原子的基态代表0第一激发态代表1。就是说在量子计算机中，量子信息是存储在单个的自旋’、光子或原子上的。对光子来说，可以利用Kerr非线性作用来转动一光束使之线性极化，以获取写入、读出；对自旋来说，则是把电子（或核）置于磁场中，通过磁共振技术来获取量子信息的读出、写入；而写入和读出一个原子存储的信息位则是用一激光脉冲照射此原子来完成的。量子计算机使用两个量子寄存器，第一个为输入寄存器，第二个为输出寄存器。函数的演化由幺正演化算符通过量子逻辑门的操作来实现。单量子位算符实现一个量子位的翻转。两量子位算符，其中一个是控制位，它确定在什么情况下目标位才发生改变；另一个是目标位，它确定目标位如何改变；翻转或相位移动。还有多位量子逻辑门，种类很多。要说清楚量子计算，首先看经典计算。经典计算机从物理上可以被描述为对输入信号序列按一定算法进行交换的机器，其算法由计算机的内部逻辑电路来实现。经典计算机具有如下特点：
a）其输入态和输出态都是经典信号，用量子力学的语言来描述，也即是：其输入态和输出态都是某一力学量的本征态。如输入二进制序列0110110，用量子记号，即10110110>。所有的输入态均相互正交。对经典计算机不可能输入如下叠加Cl10110110>+C2I1001001>。
b）经典计算机内部的每一步变换都将正交态演化为正交态，而一般的量子变换没有这个性质，因此，经典计算机中的变换（或计算）只对应一类特殊集。
相应于经典计算机的以上两个限制，量子计算机分别作了推广。量子计算机的输入用一个具有有限能级的量子系统来描述，如二能级系统（称为量子比特），量子计算机的变换（即量子计算）包括所有可能的幺正变换。因此量子计算机的特点为：
a）量子计算机的输入态和输出态为一般的叠加态，其相互之间通常不正交；
b）量子计算机中的变换为所有可能的幺正变换。得出输出态之后，量子计算机对输出态进行一定的测量，给出计算结果。由此可见，量子计算对经典计算作了极大的扩充，经典计算是一类特殊的量子计算。量子计算最本质的特征为量子叠加性和相干性。量子计算机对每一个叠加分量实现的变换相当于一种经典计算，所有这些经典计算同时完成，并按一定的概率振幅叠加起来，给出量子计算的输出结果。这种计算称为量子并行计算，量子并行处理大大提高了量子计算机的效率，使得其可以完成经典计算机无法完成的工作，这是量子计算机的优越性之一。
4、量子计算机的应用
量子计算机惊人的运算能使其能够应用于电子、航空、航人、人文、地质、生物、材料等几乎各个学科领域，尤其是信息领域更是迫切需要量子计算机来完成大量数据处理的工作。信息技术与量子计算必然走向结合，形成新兴的量子信息处理技术。目前，在信息技术领域有许多理论上非常有效的信息处理方法和技术，由于运算量庞大，导致实时性差，不能满足实际需要，因此制约了信息技术的发展。量子计算机自然成为继续推动计算速度提高，进而引导各个学科全面进步的有效途径之一。在目前量子计算机还未进入实际应用的情况下，深入地研究量子算法是量子信息处理领域中的主要发展方向，其研究重点有以下三个方面；
（1）深刻领悟现有量子算法的木质，从中提取能够完成特定功能的量子算法模块，用其代替经典算法中的相应部分，以便尽可能地减少现有算法的运算量；
（2）以现有的量子算法为基础，着手研究新型的应用面更广的信息处理量子算法；
（3）利用现有的计算条件，尽量模拟量子计算机的真实运算环境，用来验证和开发新的算法。
5、量子计算机的应用前景
目前经典的计算机可以进行复杂计算，解决很多难题。但依然存在一些难解问题，它们的计算需要耗费大量的时间和资源，以致在宇宙时间内无法完成。量子计算研究的一个重要方向就是致力于这类问题的量子算法研究。量子计算机首先可用于因子分解。因子分解对于经典计算机而言是难解问题，以至于它成为共钥加密算法的理论基础。按照Shor的量子算法，量子计算机能够以多项式时间完成大数质因子的分解。量子计算机还可用于数据库的搜索。1996年，Grover发现了未加整理数据库搜索的Grover迭代量子算法。使用这种算法，在量子计算机上可以实现对未加整理数据库Ⅳ的平方根量级加速搜索，而且用这种加速搜索有可能解决经典上所谓的NP问题。量子计算机另一个重要的应用是计算机视觉，计算机视觉是一种通过二维图像理解三维世界的结构和特性的人工智能。计算机视觉的一个重要领域是图像处理和模式识别。由于图像包含的数据量很大，以致不得不对图像数据进行压缩。这种压缩必然会损失一部分原始信息。
作者简介：
Mirco A.Mannucci The University of Queensland,Australia
Quantum Computing for
Computer Scientists
2008, 384pp.
Hardcover
ISBN 9780521879965
N.S.扬诺夫斯基等著
量子计算是计算机科学、数学和物理学的交叉学科。在跨学科研究领域中,量子计算开创了量子力学的许多出人意料的新方向,并拓展了人类的计算能力。本书直接引领读者进入量子计算领域的前沿,给出了量子计算中最新研究成果。该书从必要的预备知识出发,然后从计算机科学的角度来介绍量子计算,包括计算机体系结构、编程语言、理论计算机科学、密码学、信息论和硬件。
全书由11章组成。1.复数,给出了复数的基本概念、复数代数和复数几何;2.复向量空间,以最基本的例子Cn空间引入,介绍了复向量空间的定义、性质和例子,给出了向量空间的基和维数、内积和希尔伯特空间、特征值和特征向量、厄米特矩阵和酉矩阵、张量积的向量空间;3.从古典到量子的飞跃,主要内容有古典的确定性系统、概率性系统、量子系统、集成系统;4.基本量子理论,主要有量子态、可观测性、度量和集成量子系统;5.结构框架,主要包括比特和量子比特、古典门、可逆门和量子门;6.算法,包括Deutsch算法、Deutsch-Jozsa算法、Simon的周期算法、Grover搜索算法和Shor因子分解算法;7.程序设计,包括量子世界的程序设计、量子汇编程序设计、面向高级量子程序设计和先于量子计算机的量子计算;8.理论计算科学,包括确定和非确定计算、概率性计算和量子计算;9.密码学,包括古典密码学、量子密钥交换的三个协议(BB84协议、B92协议和EPR协议)、量子电子传输;10.信息论,主要内容有古典信息和Shannon熵值、量子信息和冯•诺依曼熵值、古典和量子数据压缩、错误更新码;11.硬件,主要包括量子硬件的目标和挑战、量子计算机的实现、离子捕集器、线性光学、NMR与超导体和量子器件的未来。最后给出了5个附录,附录A量子计算的历史,介绍了量子计算领域中的重要文献;附录B习题解答;附录C 使用MATLAB进行量子计算实验;附录D 了解量子最新进展的途径:量子计算的网站和文献;附录E选题报告。
本书适合计算机科学的本科学生和相关研究人员,也适合各级科研人员自学。
陈涛,硕士
(中国传媒大学理学院)
Chen Tao,Master
自1982年理查德·费曼（Richard Feynman）提出“量子计算机”的概念之后，人们对它颇为关注，众多研究机构更是试图借此开辟计算机时代的新纪元。但是，任凭人们千呼万唤、前赴后继，都没能够彻底揭开量子计算机的面纱。那么，量子计算机到底发展到了什么样的阶段？遇到了什么障碍？此次诺贝尔奖会对量子计算机的研发起到什么推动作用？量子计算机一旦面世，随之而来的会是什么？
量子计算机是大势所趋
所谓量子计算机，简单来说就是利用量子携带信息、存储数据，遵循量子算法进行高速的数学和逻辑运算的物理设备。我们熟知的传统计算机的“心脏”依赖的是硅芯片，但是一个芯片的面积总是有限的。
硅晶体管作为在芯片上传输信息、处理信息的微型开关，每年都在缩小，但是，由于硅的特性和物理原理，尺寸缩小（现已达到纳米级）将限制性能的提升。所以，对晶体管进行传统的尺寸的扩展和收缩操作，不能再产生行业已经习惯的更低功耗、更低成本、更高速度的处理器的效果。虽然英特尔的22纳米处理器已经面世，还计划于2013年推出14纳米处理器，对于10nm、7nm以及5nm的制程研发路线图也已敲定，但是，只要粒子的尺度到了10的负10次方米以下，就会明显出现量子特性，所以大部分物理学家坚持认为，摩尔定律不可能无限维持。
为了突破这道瓶颈，
IBM一直致力于研发碳纳米管芯片，其研究人员在一个硅芯片上放置了1万多个碳纳米晶体管，从而能够获得比硅质器件更快的运行速度。IBM声称这一成果有望让摩尔定律在下一个十年中继续生效。但是，如何获得高纯度的碳、如何实现完美的制造工艺又是不可避免的问题。
因为量子计算机是利用量子携带信息的，所以，传统计算机面临的挑战恰恰是量子计算机的优势所在。量子计算机中的每个数据由不同粒子的量子状态决定，根据量子力学原理，粒子的量子状态是不同量子状态的叠加。所以，量子计算机计算时采用的量子比特在同一时间内能够呈现出多种状态——既可以是1也可以是0，传统计算机在运算中采用的传统比特在特定时间内只能代表一个状态——1或者0。这就是量子计算机与传统计算机最大的不同之处。由于量子叠加状态的不确定性，量子计算可以同时进行大量运算，它的潜在应用包括搜索由非结构化信息构成的数据库，进行任务最优化和解决此前无法解答的数学问题。所以，量子计算机是大势所趋。
实现方案众多
量子计算机以其独特的运算逻辑和强大的运算性能吸引了无数研究机构和科学家对其进行研究，也相继取得了一些成果。量子计算机以处于量子状态的原子作为中央处理器和内存，所以研制量子计算机，关键在于成功操控单个量子。相信大家一定对“薛定谔的猫”这一理论并不陌生，关在密闭笼子里的猫，由于量子状态的不确定性，人们永远不知道它是活着还是死亡。所以，处于宏观世界的我们如何才能够有效操控微观世界的粒子，是极大的难题。从理论上讲，量子计算机有几十种体系，从实验上也有十几种实现方法。
阿罗什带领他的团队利用微米量级的高反射光学微腔实现了单个原子辐射光子的操作；瓦恩兰的团队则利用可结合激光冷却技术，在离子阱中实现了单个离子的囚禁；IBM的托马斯·沃森研究中心组建了一支庞大的研究团队，依赖耶鲁大学和加州大学圣巴巴拉分校过去几年在量子计算领域取得的进展，意欲基于微电子制造技术实现量子计算；美国普林斯顿大学物理副教授杰森·培塔表示，他和加州大学圣巴巴拉分校的科学家利用电子的自旋特性，寻找到了操控电子的方法；利用声波和超导材料，也可以实现量子计算机的拓展；总部位于加拿大的D-Wave公司的量子芯片使用了特殊的铌金属（元素符号Nb，一种类似于银，柔软的、可延展的金属）材料，在低温下呈超导态，其中的电流有顺时针、逆时针以及顺逆同时存在的混合状态，而这正可以用来实现量子计算。
众多方法中，最值得一提的便是阿罗什和瓦恩兰的做法。阿罗什构造了一个腔，把单个光子囚禁在光腔里，实现量子的操控，再往腔里放入单个原子，使原子和光子相互作用，通过腔的损耗来调控它们的状态。瓦恩兰捕获离子的方法，是用一系列电极营造出一个电场囚笼，离子如被装进碗里的玻璃球，而后，用激光将离子冷却，最终，最冷的一个离子安静地待在碗底。他们独立发明并优化了测量与操作单个粒子的实验方法，而且单个粒子在实验过程中还能保持量子的物理性质。
中国科学院院士郭光灿这样评价阿罗什和瓦恩兰的成就：量子计算这个领域已经取得了飞速发展，现在的技术已经超过当初的技术，但是起点是他们。我们现在关注的不是单个离子，而是多个离子的纠缠，比如两个腔怎么连在一起，这是将来要做的，此外，还会有各种各样的腔，比如光学腔、物体腔和超导腔等。现在做量子计算机，实际上就是做芯片，把很多离子纠缠在一起，分到各个区里面，如果这一步能实现，量子计算机有希望在这方面实现实质性突破。
过程艰难 但前景乐观
自“量子计算机”的概念提出到现在的30年间，科学家们纷纷涉足，不管是在理论方面，还是实践方面，都取得了一些不可忽视的成就。
近几年来，量子计算机的领域更是全面开花，量子计算机不再是人们“只闻其名，不见其形”的概念型产品。英国布里斯托尔大学等机构以奥布赖恩为领导的研究人员更是在新一期美国《科学》杂志上宣布，成功研发出一种可用于量子计算的硅芯片。奥布赖恩表示，利用这种芯片技术，10年内可能就会研制出超越传统计算机的量子计算机。
想要研制出实用的量子计算机，需要面临科学技术方面的多重挑战，其中最主要的两大障碍就是：如何让粒子长时间保持量子状态，即保持相干性；如何让尽量多的粒子实现共同计算，即实现量子纠缠。阿罗什和瓦恩兰给出的实验方法均成功地打破了这些障碍，实现了基础性的突破。近几年来，研究人员以他们的研究成果为出发点，不断探索，取得了快速进展，可谓前景乐观。
需要注意的是，量子计算机的出现会将网络安全置于非常危险的境地，给现有的社会和经济体系以及国防带来潜在威胁。目前大部分的网络保密是使用“RSA公开码”的密码技术。想要破译这种密码，就要对大数分解质因子，这是极其困难的。按照现有的理论计算，分解一个400位数的质因子，用目前最先进的巨型计算机也需要用10亿年的时间，而人类的历史才不过几百万年。然而，量子计算机能够借助其强大的运算功能瞬间完成密码破译，这严重动摇了RSA公共码的安全性。
目前，量子计算机给人们的印象不过类似于一个玩具，娱乐价值似乎更高一些，但是在不久的将来，它一定能够引领计算机世界的潮流。
相关链接
量子计算机发展简史
1982年，诺贝尔奖获得者理查德·费曼（Richard Feynman）提出“量子计算机”的概念。
1985年，英国牛津大学的D. Deutsch进一步阐述了量子计算机的概念，并且证明了量子计算机比经典图灵计算机具有更强大的功能。
1994年，贝尔实验室的专家彼得·秀尔（Peter Shor）证明量子计算机能够完成对数运算，而且速度远胜传统计算机。
2005年，世界第一台量子计算机原型机在美国诞生，它基本符合了量子力学的全部本质特性。
2007年2月，加拿大D-Wave系统公司宣布研制成功16位量子比特的超导量子计算机。
2009年，世界第一台通用编程量子计算机在美国国家标准技术研究院诞生。
2010年1月，美国哈佛大学和澳洲昆士兰大学的科学家利用量子计算机准确算出了氢分子所含的能量。
2010年3月，德国于利希研究中心发表公报：该中心的超级计算机JUGENE成功模拟了42位的量子计算机。
计算机技术主要的发展成果有：巨型计算机、神经网络计算机、分子计算机、生物计算机、量子计算机、光计算机和纳米计算机等。下面本文将从这几方面对计算机技术的发展趋势进行阐述。
1.1巨型计算机巨型计算机的特点是：运算速度极快、存储空间巨大、功能强大。通常情况下，巨型计算机可以达到每秒百亿次以上的运算速度，其内存容量可达几百兆。巨型机是现阶段计算机技术发展水平的代表之一，在地质勘测、航空航天、国防、卫星、气象等领域有广泛应用，对这些领域的发展具有重要的影响作用。巨型计算机是未来计算机发展趋势之一，对其技术的研究能够有力推动计算机软硬件的应用技术的发展。
1.2神经网络计算机神经网络计算机是通过模仿人脑神经高效的运算功能而研究出的计算机技术。神经网络技术可以通过神经网络算法对较为复杂的信息进行处理、综合和判断，最后得出处理结果，其数据信息都是储存在神经节点中的，避免了由于各种因素而造成的神经元断裂、数据丢失或泄露等现象的发生。
1.3分子计算机分子计算机是使用分子方式对数据信息进行运算的，主要是使用分子晶体吸收信息电荷，并对其进行有组织的排列，从而达到更有效、更快捷的运算。分子计算机的特点是：存储信息时间长、存储量大、运算速度快、耗能少、体积小等。
1.4生物计算机生物计算机使用的是“蛋白质分子”构成的芯片取代了半导体硅片上原有的晶体管而研制成的计算机，它的特点是：运算速度快、存储量大、耗能低。生物计算机最主要的缺点是从其中提取信息比较困难，这一缺点也使得其使用率较低。不过在计算机技术未来的发展中，会通过不断创新和改进技术，使生物计算机扬长补短、发挥所长。
1.5量子计算机量子计算机是应用量子力学规律，并通过对量子信息进行高速的逻辑运算、数学运算、存储等处理过程的新技术。也就是说，当一台计算机使用的算法是量子算法，处理的信息是量子信息时，这台计算机就是量子计算机。量子计算机比普通计算机的运算速度快很多，且对信息的存储量要远比普通计算机大。量子计算机很有可能在不远的将来普及到千家万户。
1.6光计算机通过利用光替代电流或电子，可以极大的提高计算机的信息速度，可在同一时间处理大容量的信息，且耗电量微乎其微。光计算机技术是使用光内连技术和空间光调制器来实现的，通过光技术将存储部分和运算部分连接在一起，运算部分可以直接对存储部分进行存取。由于光的物理特性比电子的物理特性更适合传输，所以使用光传输，其传输速度更快、稳定性更强，不易出错。
1.7纳米计算机纳米技术是一种新兴的技术。一纳米相当于原子大小的四倍，比单个细菌略长些。纳米计算机是将纳米技术融入到传统的计算机技术中，而发展出来的一种新计算机技术。是通过将纳米元件集成的芯片应用到计算机系统中而形成的数据处理系统，其中纳米元件包括有计算机的电动机、处理器和传感器等。纳米元件可以很好的提升计算机的可靠性，使其导电性能大大增强。
2总结
关键词: 信息安全;密码学;量子计算;抗量子计算密码
中图分类号:TP 183 文献标志码:A 文章编号:1672-8513(2011)05-0388-08
The Challenge of Quantum Computing to Information Security and Our Countermeasures
ZHANG Huanguo, GUAN Haiming, WANG Houzheng
（Key Lab of Aerospace Information Security and Trusted Computing of Ministry of Education, Computer School, Whan University, Wuhan 430072, China）
Abstract: What cryptosystem to use is a severe challenge that we face in the quantum computing era. It is the only correct choice to research and establish an independent resistant quantum computing cryptosystem. This paper introduces to the research and development of resistant quantum computing cryptography, especially the signature scheme based on HASH function，lattice-based public key cryptosystem，MQ public key cryptosystem and public key cryptosystem based on error correcting codes. Also the paper gives some suggestions for further research on the quantum information theory，the complexity theory of quantum computing，design and analysis of resistant quantum computing cryptosystems .
Key words: information security; cryptography; quantum computing; resistant quantum computing cryptography
1 量子信息时代
量子信息技术的研究对象是实现量子态的相干叠加并对其进行有效处理、传输和存储，以创建新一代高性能的、安全的计算机和通信系统.量子通信和量子计算的理论基础是量子物理学.量子信息科学技术是在20世纪末期发展起来的新学科，预计在21世纪将有大的发展［1］.
量子有许多经典物理所没有的奇妙特性.量子的纠缠态就是其中突出的一个.原来存在相互作用、以后不再有相互作用的2个量子系统之间存在瞬时的超距量子关联，这种状态被称为量子纠缠态［1］.
量子的另一个奇妙特性是量子通信具有保密特性.这是因为量子态具有测不准和不可克隆的属性，根据这种属性除了合法的收发信人之外的任何人窃取信息，都将破坏量子的状态.这样，窃取者不仅得不到信息，而且窃取行为还会被发现，从而使量子通信具有保密的特性.目前，量子保密通信比较成熟的技术是，利用量子器件产生随机数作为密钥，再利用量子通信分配密钥，最后按传统的“一次一密”方式加密.量子纠缠态的超距作用预示，如果能够利用量子纠缠态进行通信，将获得超距和超高速通信.
量子计算机是一种以量子物理实现信息处理的新型计算机.奇妙的是量子计算具有天然的并行性.n量子位的量子计算机的一个操作能够处理2n个状态，具有指数级的处理能力，所以可以用多项式时间解决一些指数复杂度的问题.这就使得一些原来在电子计算机上无法解决的困难问题，在量子计算机上却是可以解决的.
2 量子计算机对现有密码提出严重挑战
针对密码破译的量子计算机算法主要有以下2种.
第1种量子破译算法叫做Grover算法［3］.这是贝尔实验室的Grover在1996年提出的一种通用的搜索破译算法，其计算复杂度为O(N).对于密码破译来说，这一算法的作用相当于把密码的密钥长度减少到原来的一半.这已经对现有密码构成很大的威胁，但是并未构成本质的威胁，因为只要把密钥加长1倍就可以了.
第2种量子破译算法叫做Shor算法［4］.这是贝尔实验室的Shor在1997年提出的在量子计算机上求解离散对数和因子分解问题的多项式时间算法.利用这种算法能够对目前广泛使用的RSA、ECC公钥密码和DH密钥协商体制进行有效攻击.对于椭圆曲线离散对数问题，Proos和Zalka指出：在N量子位(qbit)的量子计算机上可以容易地求解k比特的椭圆曲线离散对数问题［7］，其中N≈5k+8(k)1/2+5log 2k.对于整数的因子分解问题，Beauregard指出：在N量子位的量子计算机上可以容易地分解k比特的整数［5］，其中N≈2k.根据这种分析，利用1448qbit的计算机可以求解256位的椭圆曲线离散对数，因此也就可以破译256位的椭圆曲线密码，这可能威胁到我国第2代身份证的安全.利用2048qbit的计算机可以分解1024位的整数，因此也就可以破译1024位的RSA密码，这就可能威胁到我们电子商务的安全
Shor算法的攻击能力还在进一步扩展，已从求广义解离散傅里叶变换问题扩展到求解隐藏子群问题(HSP)，凡是能归结为HSP的公钥密码将不再安全.所以，一旦量子计算机能够走向实用，现在广泛应用的许多公钥密码将不再安全，量子计算机对我们的密码提出了严重的挑战.
3 抗量子计算密码的发展现状
抗量子计算密码（Resistant Quantum Computing Cryptography）主要包括以下3类：
第1类，量子密码；第2类，DNA密码；第3类是基于量子计算不擅长计算的那些数学问题所构建的密码.
量子保密的安全性建立在量子态的测不准与不可克隆属性之上，而不是基于计算的［1,6］.类似地，DNA密码的安全性建立在一些生物困难问题之上，也不是基于计算的［7-8］.因此，它们都是抗量子计算的.由于技术的复杂性，目前量子密码和DNA密码尚不成熟.
第3类抗量子计算密码是基于量子计算机不擅长的数学问题构建的密码.基于量子计算机不擅长计算的那些数学问题构建密码，就可以抵御量子计算机的攻击.本文主要讨论这一类抗量子计算密码［9］.
所有量子计算机不能攻破的密码都是抗量子计算的密码.国际上关于抗量子计算密码的研究主要集中在以下4个方面.
3.1 基于HASH函数的数字签名
1989年Merkle提出了认证树签名方案(MSS)［10］. Merkle 签名树方案的安全性仅仅依赖于Hash函数的安全性.目前量子计算机还没有对一般Hash函数的有效攻击方法, 因此Merkle签名方案具有抗量子计算性质.与基于数学困难性问题的公钥密码相比,Merkle签名方案不需要构造单向陷门函数,给定1个单向函数(通常采用Hash函数)便能造1个Merkle签名方案.在密码学上构造1个单向函数要比构造1个单向陷门函数要容易的多,因为设计单向函数不必考虑隐藏求逆的思路, 从而可以不受限制地运用置换、迭代、移位、反馈等简单编码技巧的巧妙组合,以简单的计算机指令或廉价的逻辑电路达到高度复杂的数学效果.新的Hash标准SHA-3［11］的征集过程中,涌现出了许多新的安全的Hash函数,利用这些新的Hash算法可以构造出一批新的实用Merkle签名算法.
Merkle 签名树方案的优点是签名和验证签名效率较高，缺点是签名和密钥较长,签名次数受限.在最初的Merkle签名方案中, 签名的次数与需要构造的二叉树紧密相关.签名的次数越多,所需要构造的二叉树越大,同时消耗的时间和空间代价也就越大.因此该方案的签名次数是受限制的.近年来,许多学者对此作了广泛的研究,提出了一些修改方案，大大地增加了签名的次数, 如CMSS方案［12］、GMSS方案［13］、DMSS方案等［14］.Buchmann, Dahmen 等提出了XOR树算法［12,15］,只需要采用抗原像攻击和抗第2原像攻击的Hash函数,便能构造出安全的签名方案.而在以往的Merkle签名树方案中,则要求Hash函数必须是抗强碰撞的.这是对原始Merkle签名方案的有益改进.上述这些成果,在理论上已基本成熟,在技术上已基本满足工程应用要求, 一些成果已经应用到了Microsoft Outlook 以及移动路由协议中［16］.
虽然基于Hash函数的数字签名方案已经开始应用，但是还有许多问题需要深入研究.如增加签名的次数、减小签名和密钥的尺寸、优化认证树的遍历方案以及如何实现加密和基于身份的认证等功能，均值得进一步研究.
3.2 基于纠错码的公钥密码
基于纠错码的公钥密码的基本思想是: 把纠错的方法作为私钥, 加密时对明文进行纠错编码，并主动加入一定数量的错误, 解密时运用私钥纠正错误, 恢复出明文.
McEliece利用Goppa码有快速译码算法的特点, 提出了第1个基于纠错编码的McEliece公钥密码体制［17］.该体制描述如下, 设G是二元Goppa码［n;k;d］的生成矩阵,其中n=2h;d=2t+1;k=n-ht,明密文集合分别为GF(2)k和GF(2)n.随机选取有限域GF(2)上的k阶可逆矩阵S和n阶置换矩阵P,并设G′=SGP,则私钥为,公钥为G′.如果要加密一个明文m∈GF(2)k,则计算c=mG′+z,这里z∈GF(2)n是重量为t的随机向量.要解密密文c, 首先计算cP-1=mSGPP-1+zP-1=mSG+zP-1,由于P是置换矩阵, 显然z与zP-1的重量相等且为t,于是可利用Goppa的快速译码算法将cP-1译码成m′= mS,则相应明文m= m′S-1.
1978年Berlekamp等证明了一般线性码的译码问题是NPC问题［18］，McEliece密码的安全性就建立在这一基础上.McEliece密码已经经受了30多年来的广泛密码分析,被认为是目前安全性最高的公钥密码体制之一.虽然McEliece 公钥密码的安全性高且加解密运算比较快, 但该方案也有它的弱点, 一是它的公钥尺寸太大，二是只能加密不能签名.
1986年Niederreiter提出了另一个基于纠错码的公钥密码体制［19］. 与McEliece密码不同的是它隐藏的是Goppa码的校验矩阵.该系统的私钥包括二元Goppa码［n;k;d］的校验矩阵H以及GF(2)上的可逆矩阵M和置换矩阵P.公钥为错误图样的重量t和矩阵H′=MHP.假如明文为重量为t 的n 维向量m, 则密文为c=mH′T .解密时,首先根据加密表达式可推导出z(MT )-1=mPTHT,然后通过Goppa码的快速译码算法得到mPT,从而可求出明文m .1994年我国学者李元兴、王新梅等［20］证明了Niederreiter密码与McEliece密码在安全性上是等价的.
McEliece密码和Niederreiter密码方案不能用于签名的主要原由是,用Hash算法所提取的待签消息摘要向量能正确解码的概率极低.2001年Courtois等提出了基于纠错码的CFS签名方案［21］.CFS 签名方案能做到可证明安全, 短签名性质是它的最大优点. 其缺点是密钥量大、签名效率低，影响了其实用性.
因此, 如何用纠错码构造一个既能加密又签名的密码, 是一个相当困难但却非常有价值的开放课题.
3.3 基于格的公钥密码
近年来,基于格理论的公钥密码体制引起了国内外学者的广泛关注.格上的一些难解问题已被证明是NP难的，如最短向量问题(SVP)、最近向量问题(CVP)等.基于格问题建立公钥密码方案具有如下优势:①由于格上的一些困难性问题还未发现量子多项式破译算法，因此我们认为基于格上困难问题的密码具有抗量子计算的性质.②格上的运算大多为线性运算,较RSA等数论密码实现效率高,特别适合智能卡等计算能力有限的设备.③根据计算复杂性理论,问题类的复杂性是指该问题类在最坏情况下的复杂度.为了确保基于该类困难问题的密码是安全的，我们希望该问题类的平均复杂性是困难的，而不仅仅在最坏情况下是困难的.Ajtai在文献［22］中开创性地证明了:格中一些问题类的平均复杂度等于其最坏情况下的复杂度.Ajtai和Dwork利用这一结论设计了AD公钥密码方案［23］.这是公钥密码中第1个能被证明其任一随机实例与最坏情况相当.尽管AD公钥方案具有良好的安全性, 但它的密钥量过大以及实现效率太低、而缺乏实用性.
1996年Hoffstein、Pipher和Silverman提出NTRU(Number Theory Research Unit)公钥密码［24］. 这是目前基于格的公钥密码中最具影响的密码方案.NTRU的安全性建立在在一个大维数的格中寻找最短向量的困难性之上.NTRU 密码的优点是运算速度快，存储空间小.然而, 基于NTRU的数字签名方案却并不成功.
2000年Hoffstein等利用NTRU格提出了NSS签名体制［25］, 这个体制在签名时泄露了私钥信息,导致了一类统计攻击,后来被证明是不安全的.2001年设计者改进了NSS 体制,提出了R-NSS 签名体制［26］,不幸的是它的签名仍然泄露部分私钥信息.Gentry 和Szydlo 结合最大公因子方法和统计方法,对R-NSS 作了有效的攻击.2003年Hoffstein等提出了NTRUSign数字签名体制［27］.NTRUSign 签名算法较NSS与R-NSS两个签名方案做了很大的改进,在签名过程中增加了对消息的扰动, 大大减少签名中对私钥信息的泄露, 但却极大地降低了签名的效率, 且密钥生成过于复杂.但这些签名方案都不是零知识的,也就是说,签名值会泄露私钥的部分相关信息.以NTRUSign 方案为例,其推荐参数为(N;q;df;dg;B;t;N)= (251;128;73;71;1;"transpose";310),设计值保守推荐该方案每个密钥对最多只能签署107 次,实际中一般认为最多可签署230次.因此，如何避免这种信息泄露缺陷值得我们深入研究.2008 年我国学者胡予濮提出了一种新的NTRU 签名方案［28］，其特点是无限制泄露的最终形式只是关于私钥的一组复杂的非线性方程组，从而提高了安全性.总体上这些签名方案出现的时间都还较短，还需要经历一段时间的安全分析和完善.
由上可知，进一步研究格上的困难问题，基于格的困难问题设计构造既能安全加密又能安全签名的密码，都是值得研究的重要问题.
3.4 MQ公钥密码
MQ公钥密码体制, 即多变量二次多项式公钥密码体制(Multivariate Quadratic Polynomials Public Key Cryptosystems).以下简称为MQ密码.它最早出现于上世纪80年代,由于早期的一些MQ密码均被破译,加之经典公钥密码如RSA算法的广泛应用,使得MQ公钥算法一度遭受冷落.但近10年来MQ密码的研究重新受到重视,成为密码学界的研究热点之一.其主要有3个原因:一是量子计算对经典公钥密码的挑战;二是MQ密码孕育了代数攻击的出现［29-31］,许多密码(如AES)的安全性均可转化为MQ问题,人们试图借鉴MQ密码的攻击方法来分析这些密码,反过来代数攻击的兴起又带动了MQ密码的蓬勃发展;三是MQ密码的实现效率比经典公钥密码快得多.在目前已经构造出的MQ密码中, 有一些非常适用于智能卡、RFID、移动电话、无线传感器网络等计算能力有限的设备, 这是RSA等经典公钥密码所不具备的优势.
MQ密码的安全性基于有限域上的多变量二次方程组的难解性.这是目前抗量子密码学领域中论文数量最多、最活跃的研究分支.
设U、T 是GF(q)上可逆线性变换(也叫做仿射双射变换),而F 是GF(q)上多元二次非线性可逆变换函数,称为MQ密码的中心映射.MQ密码的公钥P为T 、F 和U 的复合所构成的单向陷门函数,即P = T•F•U,而私钥D 由U、T 及F 的逆映射组成,即D = {U -1; F -1; T -1}.如何构造具有良好密码性质的非线性可逆变换F是MQ密码设计的核心.根据中心映射的类型划分,目前MQ密码体制主要有:Matsumoto-Imai体制、隐藏域方程(HFE) 体制、油醋(OV)体制及三角形(STS)体制［32］.
1988年日本的Matsumoto和Imai运用"大域-小域"的原理设计出第1个MQ方案,即著名的MI算法［33］.该方案受到了日本政府的高度重视,被确定为日本密码标准的候选方案.1995年Patarin利用线性化方程方法成功攻破了原始的MI算法［34］.然而,MI密码是多变量公钥密码发展的一个里程碑,为该领域带来了一种全新的设计思想,并且得到了广泛地研究和推广.改进MI算法最著名的是SFLASH签名体制［35］,它在2003年被欧洲NESSIE 项目收录,用于智能卡的签名标准算法.该标准签名算法在2007年美密会上被Dubois、Fouque、Shamir等彻底攻破［36］.2008年丁津泰等结合内部扰动和加模式方法给出了MI的改进方案［37-38］.2010年本文作者王后珍、张焕国也给出了一种SFLASH的改进方案［39-40］，改进后的方案可以抵抗文献［36］的攻击.但这些改进方案的安全性还需进一步研究.
1996年Patarin针对MI算法的弱点提出了隐藏域方程HFE(Hidden Field Equations)方案［41］.HFE可看作为是对MI的实质性改进.2003 年Faugere利用F5算法成功破解了HFE体制的Challenge-1［42］.HFE主要有2种改进算法.一是HFEv-体制,它是结合了醋变量方法和减方法改进而成,特殊参数化HFEv-体制的Quartz签名算法［43］.二是IPHFE体制［44］,这是丁津泰等结合内部扰动方法对HFE的改进.这2种MQ密码至今还未发现有效的攻击方法.
油醋(OilVinegar)体制［45］是Patarin在1997年利用线性化方程的原理,构造的一种MQ公钥密码体制.签名时只需随机选择一组醋变量代入油醋多项式,然后结合要签名的文件,解一个关于油变量的线性方程组.油醋签名体制主要分为3类:1997年Patarin提出的平衡油醋(OilVinegar)体制, 1999年欧密会上Kipnis、Patarin 和Goubin 提出的不平衡油醋(Unbalanced Oil and Vinegar)体制［46］以及丁津泰在ACNS2005会议上提出的彩虹(Rainbow)体制［47］.平衡的油醋体制中,油变量和醋变量的个数相等，但平衡的油醋体制并不安全.彩虹体制是一种多层的油醋体制,即每一层都是油醋多项式,而且该层的所有变量都是下一层的醋变量,它也是目前被认为是相对安全的MQ密码之一.
三角形体制是现有MQ密码中较为特殊的一类,它的签名效率比MI和HFE还快,而且均是在较小的有限域上进行.1999年Moh基于Tame变换提出了TTM 密码体制［48］,并在美国申请了专利.丁津泰等指出当时所有的TTM实例均满足线性化方程.Moh等随后又提出了一个新的TTM 实例,这个新的实例被我国学者胡磊、聂旭云等利用高阶线性化方程成功攻破［49］.目前三角形体制的设计主要是围绕锁多项式的构造、结合其它增强多变量密码安全性的方法如加减(plus-minus) 模式以及其它的代数结构如有理映射等.
我国学者也对MQ密码做了大量研究，取得了一些有影响的研究成果.2007年管海明引入单向函数链对MQ密码进行扩展,提出了有理分式公钥密码系统［50］.胡磊、聂旭云等利用高阶线性化方程成功攻破了Moh提出的一个TTM新实例［51］.2010年本文作者王后珍、张焕国给出了一种SFLASH的改进方案［39-40］.2010年王后珍、张焕国基于扩展MQ，设计了一种Hash函数［52-53］，该Hash函数具有一些明显的特点.同年，王后珍、张焕国借鉴有理分式密码单向函数链的思想［52］，对MQ密码进行了扩展，设计了一种新的抗量子计算扩展MQ密码［54］.这些研究对于扩展MQ密码结构，做了有益的探索.但是这些方案提出的时间较短，其安全性有待进一步分析.
根据上面的介绍,目前还没有一种公认安全的MQ公钥密码体制.目前MQ公钥密码的主要缺点是:只能签名,不能安全加密(加密时安全性降低)，公钥大小较长，很难设计出既安全又高效的MQ公钥密码体制.
3.5 小结
无论是量子密码、DNA密码，还是基于量子计算不擅长计算的那些数学问题所构建的密码，都还存在许多不完善之处，都还需要深入研究.
量子保密通信比较成熟的是，利用量子器件产生随机数作为密钥，再利用量子通信分配密钥，最后按“一次一密”方式加密.在这里，量子的作用主要是密钥产生和密钥分配，而加密还是采用的传统密码.因此，严格说这只能叫量子保密，尚不能叫量子密码.另外，目前的量子数字签名和认证方面还存在一些困难.
对于DNA密码，目前虽然已经提出了DNA传统密码和DNA公钥密码的概念和方案，但是理论和技术都还不成熟［9-10］.
对于基于量子计算不擅长计算的那些数学问题所构建的密码，现有的密码方案也有许多不足.如，Merkle树签名可以签名，不能加密；基于纠错码的密码可以加密，签名不理想；NTRU密码可以加密，签名不理想；MQ密码可以签名，加密不理想.这说明目前尚没有形成的理想的密码体制.而且这些密码的安全性还缺少严格的理论分析.
总之，目前尚未形成理想的抗量子密码.
4 我们的研究工作
我们的研究小组从2007年开始研究抗量子计算密码.目前获得了国家自然科学基金等项目的支持，并取得了以下2个阶段性研究成果.
4.1 利用多变量问题，设计了一种新的Hash函数
Hash 函数在数字签名、完整性校验等信息安全技术中被广泛应用.目前 Hash 函数的设计主要有3类方法:①直接构造法.它采用大量的逻辑运算来确保Hash函数的安全性. MD系列和SHA系列的Hash函数均是采用这种方法设计的.②基于分组密码的Hash 函数，其安全性依赖于分组密码的安全性.③基于难解性问题的构造法.利用一些难解性问题诸如离散对数、因子分解等来构造Hash 函数.在合理的假设下，这种Hash函数是可证明安全的，但一般来讲其效率较低.
我们基于多变量非线性多项式方程组的难解性问题，构造了一种新的Hash 函数［54-55］.它的安全性建立在多变量非线性多项式方程组的求解困难性之上.方程组的次数越高就越安全，但是效率就越低.它的效率主要取决多变量方程组的稀疏程度，方程组越稀疏效率就越高，但安全性就越低.我们可以权衡安全性和效率来控制多变量多项式方程组的次数和稠密度，以构造出满足用户需求的多变量Hash 函数.
4.2 对MQ密码进行了扩展，把Hash认证技术引入MQ密码，得到一种新的扩展MQ密码
扩展MQ密码的基本思想是对传统MQ密码的算法空间进行拓展. 如图1所示, 我们通过秘密变换L将传统MQ密码的公钥映G:GF(q)nGF(q)n, 拓展隐藏到更大算法空间中得到新的公钥映射G′:GF(q)n+δGF(q)n+μ, 且G′的输入输出空间是不对称的, 原像空间大于像空间(δ＞|μ|), 即具有压缩性, 但却并未改变映射G的可逆性质. 同时, 算法空间的拓展破坏了传统MQ密码的一些特殊代数结构性质, 从攻击者的角度, 由于无法从G′中成功分解出原公钥映射G, 因此必须在拓展空间中求解更大规模的非线性方程组G′, 另外, 新方案中引入Hash认证技术, 攻击者伪造签名时, 伪造的签名不仅要满足公钥方程G′、 还要通过Hash函数认证, 双重安全性保护极大地提升了传统MQ公钥密码系统的安全性. 底层MQ体制及Hash函数可灵活选取, 由此可构造出一类新的抗量子计算公钥密码体制.这种扩展MQ密码的特点是，既可安全签名，又可安全加密［56］.
我们提出的基于多变量问题的Hash函数和扩展MQ密码，具有自己的优点，也有自己的缺点.其安全性还需要经过广泛的分析与实践检验才能被实际证明.
5 今后的研究工作
5.1 量子信息论
量子信息建立在量子的物理属性之上，由于量子的物理属性较之电子的物理属性有许多特殊的性质，据此我们估计量子的信息特征也会有一些特殊的性质.这些特殊性质将会使量子信息论对经典信息论有一些新的扩展.但是，具体有哪些扩展，以及这些新扩展的理论体系和应用价值体现在哪里？我们尚不清楚.这是值得我们研究的重要问题.
5.2 量子计算理论
这里主要讨论量子可计算性理论和量子计算复杂性理论.
可计算性理论是研究计算的一般性质的数学理论.它通过建立计算的数学模型，精确区分哪些是可计算的，哪些是不可计算的.如果我们研究清楚量子可计算性理论，将有可能构造出量子计算环境下的绝对安全密码.但是我们目前对量子可计算性理论尚不清楚，迫切需要开展研究.
计算复杂性理论使用数学方法对计算中所需的各种资源的耗费作定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和基本性质.它是密码学的理论基础之一，公钥密码的安全性建立在计算复杂性理论之上.因此，抗量子计算密码应当建立在量子计算复杂性理论之上.为此，应当研究以下问题.
1） 量子计算的问题求解方法和特点.量子计算复杂性建立在量子图灵机模型之上，问题的计算是并行的.但是目前我们对量子图灵机的计算特点及其问题求解方法还不十分清楚，因此必须首先研究量子计算问题求解的方法和特点.
2） 量子计算复杂性与传统计算复杂性之间的关系.与电子计算机环境的P问题、NP问题相对应, 我们记量子计算环境的可解问题为QP问题, 难解问题为QNP问题.目前人们对量子计算复杂性与传统计算复杂性的关系还不够清楚，还有许多问题需要研究.如NP与QNP之间的关系是怎样的？ NPC与QP的关系是怎样的？NPC与QNP的关系是怎样的？能否定义QNPC问题？这些问题关系到我们应基于哪些问题构造密码以及所构造的密码是否具有抗量子计算攻击的能力.
3） 典型难计算问题的量子计算复杂度分析.我们需要研究传统计算环境下的一些NP难问题和NPC问题，是属于QP还是属于QNP问题？
5.3 量子计算环境下的密码安全性理论
在分析一个密码的安全性时，应首先分析它在电子计算环境下的安全性，如果它是安全的，再进一步分析它在量子计算环境下的安全性.如果它在电子计算环境下是不安全的，则可肯定它在量子计算环境下是不安全的.
1） 现有量子计算攻击算法的攻击能力分析.我们现在需要研究的是Shor算法除了攻击广义离散傅里叶变换以及HSP问题外，还能攻击哪些其它问题？如果能攻击，攻击复杂度是多大？
2) 寻找新的量子计算攻击算法.因为密码的安全性依赖于新攻击算法的发现.为了确保我们所构造的密码在相对长时间内是安全的，必须寻找新的量子计算攻击算法.
3) 密码在量子计算环境下的安全性分析.目前普遍认为, 基于格问题、MQ问题、纠错码的译码问题设计的公钥密码是抗量子计算的.但是，这种认识尚未经过量子计算复杂性理论的严格的论证.这些密码所依赖的困难问题是否真正属于QNP问题？这些密码在量子计算环境下的实际安全性如何？只有经过了严格的安全性分析，我们才能相信这些密码.
5.4 抗量子计算密码的构造理论与关键技术
通过量子计算复杂性理论和密码在量子计算环境下的安全性分析的研究，为设计抗量子计算密码奠定了理论基础，并得到了一些可构造抗量子计算的实际困难问题.但要实际设计出安全的密码，还要研究抗量子计算密码的构造理论与关键技术.
1) 量子计算环境下的单向陷门设计理论与方法.理论上，公钥密码的理论模型是单向陷门函数.要构造一个抗量子计算公钥密码首先就要设计一个量子计算环境下的单向陷门函数.单向陷门函数的概念是简单的，但是单向陷门函数的设计是困难的.在传统计算复杂性下单向陷门函数的设计已经十分困难，我们估计在量子计算复杂性下单向陷门函数的设计将更加困难.
2） 抗量子计算密码的算法设计与实现技术.有了单向陷门函数，还要进一步设计出密码算法.有了密码算法，还要有高效的实现技术.这些都是十分重要的问题.都需要认真研究才能做好.
6 结语
量子计算时代我们使用什么密码，是摆在我们面前的重大战略问题.研究并建立我国独立自主的抗量子计算密码是我们的唯一正确的选择.本文主要讨论了基于量子计算机不擅长计算的数学问题所构建的一类抗量子计算的密码，介绍了其发展现状，并给出了进一步研究的建议.
参考文献:
［1］张镇九,张昭理,李爱民.量子计算与通信保密［M］.武汉:华中师范大学出版社,2002.
［2］管海明. 国外量子计算机进展、对信息安全的挑战与对策［J］.计算机安全,2009(4):1-5.
［3］GROVER L K. A fast quantum mechanical algorithm for database search［C］// Proceedings of the Twenty-Eighth Annual Symposium on the Theory of Computing. New York: ACM Press, 1996.
［4］SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer ［J］. SIAM J Computer, 1997(26) :1484-1509.
［5］HANKERSON D, MENEZES A, VANSTONE S. 椭圆曲线密码学导论［M］.张焕国,译.北京:电子工业出版社,2005.
［6］曾贵华. 量子密码学［M］.北京:科学出版社,2006.
［7］来学嘉, 卢明欣, 秦磊, 等. 基于DNA 技术的非对称加密与签名方法［J］. 中国科学E辑:信息科学, 2010, 40(2): 240-248.
［8］卢明欣,来学嘉,肖国镇,等. 基于DNA技术的对称加密方法［J］. 中国科学E辑:信息科学, 2007(2): 175-182.
［9］BERNSTEIN D J, BUCHMANN J A, DAHMEN E. Post-quantum cryptography ［M］. Berlin:Springer, 2009.
［10］MERKLE R C. A certified digital signature［C］//Advances in Cryptology-CRYPTO 1989 Proceedings, LNCS. Berlin:Springer, 1989,435:218-238.
［11］NIST. Plan for new cryptographic hash functions［EB/OL］. ［2010-12-30］..
［49］DING J, HU L, NIE X Y, et al. High order linearization equation (HOLE) attack on multivariate public key cryptosystems［C］//Proceedings of PKC 2007. Berlin: Springer-Verlag, 2007: 233-248.
［50］管海明.有理分式公钥密码体制［C］//第五届中国信息与通信安全学术会议（CCICS’2007）论文集.科学出版社,2007:135-141.
［51］胡磊,聂旭云.多变量公钥密码的研究进展［C］//中国密码学发展报告.北京：电子工业出版社, 2007: 235-254.
［52］王后珍,张焕国.多变量Hash函数的构造理论与方法［J］.中国科学:信息科学版,2010,40(10):1299-1311.
［53］WANG H Z, ZHANG H G. Design theory and method of multivariate hash function［J］.SCIENCE CHINA:Information Sciences, 2010, 53(10):1 917-2 158.
［54］王后珍, 张焕国.一种新的轻量数字签名方法［J］.通信学报,2010(11):25-29.
收稿日期:2011-04-20.
5月3日，这台计算机的研制方――中国科学院量子信息与量子科技创新研究院在这里宣布，中国科学技术大学潘建伟院士及同事陆朝阳、朱晓波等，联合浙江大学王浩华研究组，构建了这台基于单光子的量子计算机，这是世界上第一台超越早期经典计算机的光量子计算机。
一时间评价纷至沓来：“中国科学家再次站在了创新的前沿”“量子计算将彻底改变人类未来的应用前景”……就连这次成果的焦点人物潘建伟也提到，“量子计算研究就像雨后春笋，到了爆发式发展的关键时刻。”那么这台中国造的量子计算机究竟能有何能耐，又将为我们带来什么？
计算速度加快2.4万倍
量子计算机是指利用量子相干叠加原理，理论上具有超快的并行计算和模拟能力的计算机。计算能力随可操纵的粒子数呈指数增长，可为经典计算机无法解决的大规模计算难题提供有效解决方案。
曾有人打过一个比方：如果现在传统计算机的速度是自行车，量子计算机的速度就如同飞机。例如，使用亿亿次的天河二号超级计算机求解一个亿亿亿变量的方程组，所需时间为100年，而使用一台万亿次的量子计算机求解同一个方程组，仅需0.01秒。
因为计算能力的革命性突破，如同蒸汽机之于工业文明，量子计算机将成为未来科技的引擎。实验测试表明，该原型机的取样速度不仅比国际同行类似的实验加快至少2.4万倍，同时，通过和经典算法比较，也比人类历史上第一台电子管计算机和第一台晶体管计算机运行速度快10倍到100倍。“这是历史上第一台超越早期经典计算机的基于单光子的量子模拟机，为最终实现超越经典超级计算能力的量子计算这一国际学术界称之为‘量子称霸’的目标奠定了坚实的基础。”潘建伟指出。
计划年底实现20个光量子比特的操纵
多粒子m缠的操纵作为量子计算的核心资源，一直是国际角逐的焦点。在光子体系，潘建伟团队在多光子纠缠领域始终保持着国际领先水平，并于2016年底把纪录刷新至十光子纠缠。在此基础上，团队此次利用自主发展的综合性能国际最优的量子点单光子源，通过电控可编程的光量子线路，构建了针对多光子“玻色取样”任务的光量子计算原型机。
“量子计算领域有几个大家共同努力的指标性节点：第一，展示超越首台电子计算机的计算能力；第二，展示超越商用CPU的计算能力；第三，展示超越超级计算机的计算能力。我们实现的只是其中的第一步，也是一小步，但同时是重要的一步。”潘建伟说。
曾经有科学家预测，除非量子计算机操控的比特数超过50个，量子计算机才能超过现有的经典计算机。此次，中国科学家的成果为10个超导量子比特，超过了之前由谷歌、美国航天航空局和加州大学圣芭芭拉分校公开报道的9个超导量子比特的纪录。
但也有分析称，尽管欧美等国公开报道的成果是9个，但谷歌之前已经放话，要在今年底之前把超导量子计算做到50个比特。因此，这一领域的竞争还远未结束。更何况即使获得了量子计算霸权，让其真正具备解决问题的能力也是路途漫漫。
在潘建伟看来，谷歌、IBM等公司拥有人才优势。尤其是谷歌，目前仍可以算是量子计算机领域的领头羊。但这次研究团队通过高精度脉冲控制和全局纠缠操作实现10比特量子态的成果，使中国在超导体系量子计算机研究领域也进入世界一流水平行列。
根据计划，潘建伟的研究团队将在今年底实现大约20个光量子比特的操纵，20个超导量子比特样品的设计、制备和测试，量子计算机的速度将会成指数增长。也许到时一张闪亮的国家名片又将出现。
量子技术未来将极大改变生活
随着大数据时代的到来，对计算能力的需求可以用“贪得无厌”来形容。同时，计算能力的强弱也对社会的发展起着至关重要的作用。当人们能把有效的数据结果都通过计算给提取出来，每一个数据才会成为真正的财富。
谈到量子计算机未来的应用前景，潘建伟充满信心：“量子通信主要是用在保密方面，它可以大大提高信息安全水平。除此之外，量子计算可能很快在某些特定计算方面超越目前传统的超级计算。这些技术在医学检测、药物设计、基因分析、各种导航等方面也将起到巨大的作用，会给人们的生活带来极大改变。”
5月16日，谷歌宣布成立了一个量子计算研究所。次日，谷歌宣布购买全球第二台 D-Wave 量子计算机。3月30日，洛克希德·马丁公司（美国航空航天制造商，也是国防工业承包商）向D-Wave公司购买首台商用量子计算机。我们有理由相信，人类文明正跨入量子计算新时代。
量子概要
如果将磁场中的原子自旋视为一个量子，这个原子在同一时刻的状态是自旋轴向上和自旋轴向下同时存在的总和，即自旋轴向上的同时也自旋轴向下（量子叠加）。虽然目前物理学还无法解释其中的原因，但理论推导和实验观测都是如此。
在量子世界，不管两个有共同来源的粒子距离多么遥远，一个粒子的变化立即就能影响到另外一个粒子，是为量子相干。譬如两电子发生正向碰撞，若其中一电子是向左自转的，那么另外一电子必是向右自转。一旦量子系统与外部环境发生相互作用，会导至量子相干性的衰减，即消相干或退相干（即薛定谔猫）。
任何对量子状态的测量都会发生退相干。这是一个困扰物理学界的难题。法国物理学家阿罗什和美国物理学家维因兰以其独立发明的方法，在不退相干的情况下实现了对量子状态的测量，从而获得2012年诺贝尔物理奖。
量子计算
在磁场下，如果原子自旋轴向上为“0”，自旋轴向下为“1”，那么量子比特（qubit，昆比特）在同一时刻可代表2个状态：“0”和“1”。 一个量子比特有两个状态，N个量子比特就能存入2N个二进制数。维因兰称：“通常，有N个量子比特的计算机可以同时对2N个数值进行操作。300个量子比特所能存储的数值就会比宇宙中的粒子总数还要多。”
假设磁场中的一串原子，各自有初始的自旋状态；一束激光照射过来，激光束会改变一些原子的旋转状态。如果能测量激光束进入前后的差异，就能完成量子“计算”。 阿罗什和维因兰的成就在于攻克退相干难题，使量子测量得以实现。其成就的意义正如瑞典皇家科学院所说，“他们的突破性方法向着建造基于量子物理的新型超快计算机迈出了关键一步”。
量子计算机
中科院院士、中科院量子信息重点实验室主任郭光灿指出，量子存储器的能力是传统存储器的2N倍，对其操作一次，可以同时将其存储的2N个数据变换成新的2N个数据，这就是量子计算机独有的使效率大幅提高的并行运算模式。在量子计算机面前，电子计算器就是一把算盘。
购物车(0)
