PDF《量子算法与量子计算实验》

第21 卷第2期物理学进展Vol.

21 ,No.

2 2001 年6月PROGRESS IN PHYSICS J un. ,2001 文章编号 :1000Ο

0542 (2001) 02Ο 0183Ο

33 收稿日期 :2000Ο 09Ο

23 ;

修收日期 :2001Ο 02Ο

23 基金项目 :国家自然科学基金、 中国科学院和国家科技部基础性研究特别资助 量子算法与量子计算实验 赵志 冯芒 詹明生 (中国科学院武汉物理与数学研究所 波谱与原子分子物理国家重点实验室 ,武汉 430071) 摘要: 从量子体系的基本特性出发 ,介绍了量子计算的基本概念和物理背景 ,系统阐述 了几种主要的量子算法以及量子计算在实验方面的发展现状.对比经典计算机 ,讨论了量子 计算机的优越性、 实现量子计算的困难和以期克服的途径. 关键词 : 量子算法 ;

量子计算 ;

纠缠 ;

相干 中图分类号 : O365 文献标识码 : A

1 引言当代计算机的理论基础是 Turing[1 ] 、 Church[2 ] 等人在三十年代提出的关于可计算函 数和不可计算函数之区分的一些纯数学的命题.其核心是通用 Turing 机理论 ,即用 Turing 机可模拟任何计算过程.尽管这些数学命题与物理毫不相干 ,但当人类第一台计 算机建成之时 ,计算便成了通过计算机这种物理装置完成的一个实实在在的物理过程. 物理学的发展使计算机日新月异 ,而物理学的规律同时也给了计算机以本质上的约束. 统计表明 ,近五十年来 ,尽管计算机的速度平均每两年翻一番 ,但其元件尺寸却平均每两 年缩小一倍.这种微型化的趋势正使得计算机发展逐渐逼近经典物理学的极限.当人们 终将面对尺寸仅为纳米量级的超微型电脑元器件时 ,计算机信息的储存、 传输和处理都将 在原子层面上按照量子力学的原理进行.另一方面 ,对比用宏观客体状态表示数和按照 经典物理定律运行的现有的经典计算机 ,人们自然联想到用微观体系状态表示数和按照 量子力学定律运行的新型计算机.由此引申出近年来科学前沿的一个热门课题 :量子计 算与量子计算机[3 ] . 早在半个世纪之前 ,量子力学的先驱者们就试图通过研究简单的量子门操作和数个 量子位的纠缠( Entanglement) 过程 ,弄清经典与量子世界的界限.八十年代初 ,美国阿贡 国家实验室的 Benioff 证明[4 ] ,一台计算机原则上可以纯粹的量子力学方式运行.随后 , 英、 美及以色列的科学家们开始对量子计算机进行研究 ,以期弄清它们同人们正广泛使用 的经典计算机的区别.著名物理学家、 诺贝尔物理学奖得主 Feynman 教授曾对这一问题 表现出极大的关注 ,并就此作了一次精采的专题演讲[5 ] .到目前为止 ,尽管我们还不敢 肯定量子计算机在解决所有问题时一定都比经典计算机快 ,但它所具备的以下特性 ,却是 经典计算机不能比拟的 : (1) 量子计算能真正模拟一个量子系统的演化 ,因为它本身的运 算方式就是严格依照量子力学的原理进行 ;

(2) 量子计算的操作对象是量子迭加态和纠缠 态.如果以纯态表示数 ,迭加态则表示多个数.对量子迭加态的操作 ,意味着对多个数同 时多路操作运算 ,即所谓 量子并行计算 .因此 ,它能快速有效地解决许多特殊问题. 正是有了这些特性 ,量子计算与经典计算有了很大的不同.在本文中 ,我们将介绍各 种量子算法.通过了解这些算法 ,我们将能体会到量子计算的巨大威力. 1.