量子计算与计算机科学

摘要：量子力学是研究物质微观特性及其运动规律的物理学分支，它与计算机科学的完美结合产生了一门新兴学科――量子计算信息学，即量子计算机科学。文章先介绍传统电子器件的两个发展极限，引出量子计算的研究背景，再阐述其工作原理和对传统密码学的冲击，最后介绍了近年来量子计算的研究成果与其发展前景。

关键词：量子比特；量子力学；量子相干性；并行运算

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物性科学研究所试制出新一代存储量子比特的新载体――“超导磁束量子位”。它可通过微波照射大幅度提高对量子比特自由度的控制，其量子态也相对容易保持。

4　结束语

尽管量子计算研究框架已经成型，各方面研究也有所突破，但最终要实现高速无误的并行运算还存在许多亟待解决的理论和技术问题。正如Bennett和Zoller教授所说，“现在的量子计算机只是一个玩偶，真正做到有实用价值也许要10、20年甚至是50年。我们相信，随着知识和科技的进步，量子计算的研究一定会取得最后的胜利，并对人类和社会发展起到巨大的推动作用。届时，半导体工业顺利完成其历史使命，软件行业也将因此改朝换代，人类将步入一个神奇而高效的量子计算时代。