通用量子计算机：理论、组成与实现PDF高清在线下载

【文章介绍】

通用量子计算机：理论、组成与实现是吴 楠，宋方敏， Xiangdong Li 发表在计算机学报的一篇专业论文。这篇论文结合国内外在上述各方面研究的最新进展以及作者自身的研究结果，从计算机系统的角度尝试为通用量子计算机的研究和研制绘制一幅蓝图，并详细阐述其中的困难与努力方向。

【作者介绍】

WU Nan was born in 1981. He received his BSc and Ph.D. from the Department of Computer Science, Nanjing University,China in 2004 and 2009,respectively.Currently, he is an assistant professor at the department of computer science and technology in Nanjing University. His research interest includes quantum computing, quantum computer architecture and quantum information. He was a research scholar at the Graduate School of the City University of New York between 2008 and 2009. He is a member of ACM, IEEE, SPIE and CCF.

SONG Fang-Min received his BSc, MSc and Ph.D. from the Department of Mathematics and Department of Computer Science at Nanjing University, China in 1982, 1985 and 1988,respectively. He took the position of postdoc research fellow at ETH and CTH in 1993 and 1994, respectively. Currently, he is a full professor at the department of computer science and technology in Nanjing University. His research mainly focus on the symbolic logic, quantum algorithm and quantum computation. He is a member of CCF.

LI Xiang-Dong received his M.S. in Computer Information Science from CUNY Brooklyn College in 1997, and Ph.D. in physics from the CUNY Graduate School in 2000. He is an associate professor at the Department of Computer Systems Technology in New York City College of Technology, CUNY. He is a faculty member of both Ph.D. programs in Computer Science and Physics at the CUNY Graduate School. His research fields include information security and quantum information. He is a member of APS.

【PDF高清截图】

【内容摘要】

翻开二十世纪的物理学史册，正如仰望深邃浩渺的夜空，群星璀璨，其中最闪亮的几颗新星之一当属量子力学的提出与发展。 而同在二十世纪，电子计算机的诞生同样深刻地改变了世界。 量子力学和计算机科学与技术在二十世纪八十年代开始结合并诞生了一个多学科交叉与融合的新型学科方向：量子计算，它在备受关注中快速发展，并有可能由此产生足以改变传统计算模式从而对人类文明产生巨大推动的计算工具——量子计算机。

研究和制造量子计算机的主要动因是经典电子计算机的局限性。 电子计算机是一种以超大规模集成电路为物理基础的计算设备。 从数学角度看，电子计算机所进行的是依赖于布尔代数逻辑的通用计算。 计算的通用性在电子计算机诞生之前的1930 年代由Turing 等人研究[1]，其中最著名的结论之一当属Church-Turing 论题：

论题1：一切直觉可计算的问题均可由图灵机模拟[1,2]。

所谓“直觉可计算”在当时有许多描述方式，如递归函数或者可计算函数等，随着后来计算机科学的发展，这个提法逐渐被计算理论中的“算法”所取代，即：图灵机是可以实现任何算法的通用“计算机”。 有了 Turing 和 Church 所绘制的蓝图，在1940 年代，随着布尔逻辑和数字逻辑电路的发展，可以实现任何算法的通用电子计算机诞生了。 计算机的研究与发展逐渐成为现代科学、技术和工业的重要目标，并无所不在地改变着社会面貌和人类生活。

然而，在经历了电子计算机沿着“摩尔定律[3]”的轨迹快速发展的近40 年后，人们逐渐认识到电子计算机的发展终究无法突破物理极限，这包括集成电路的密度、电子的量子效应、元器件的热效应等；另一方面，一些现有算法的时间复杂度过高，使得在输入规模较大时很难在可被接受的时间范围内解出。 为解决上述两个问题的探索直接导致了一种新的计算模式——量子计算和一种新的计算设备——量子计算机的提出。

1980 年， Benioff 提出用量子力学中哈密顿量模型来表示图灵机[4]；1982 年， Feynman 在Benioff的工作基础上提出，要解决传统计算机面对大规模量子系统模拟的难题的有效途径应该是用量子系统本身模拟另一个量子系统[5]，甚至可以用量子系统模拟其它复杂的物理系统——因为量子力学被认为是当前支配宇宙中所有物理现象的最基本的力学系统——这首次提出了用量子设备处理信息的想法。 1985 年，Deutsch 将Feynman 的思想具体化并证明用量子计算机有效模拟在经典计算机尚不能有效模拟的系统是可能的[6]。

对比基于经典图灵机和布尔逻辑系统的经典计算，量子计算具有一些前者难以比拟的优势。 这可归纳为以下2 个方面：

第一，信息的表示与存储。 在经典计算中，信息和数据是以二进制数值的形式表示和储存的，比特是经典信息的基本度量单位，它可视为一个取值为的随机变量，这便意味着一个比特在任一确定的时刻必为“0”或“1”，且不可得兼。 不论在数值的表示还是存储方面，布尔逻辑的表示空间都是实线性空间，该空间中的1 个比特可视为模2 整数加群上的一维向量。 当希望通过扩展二进制数值的位数来增加信息和数据的表示和存储能力时，带来的效果只能是线性增长。 与之不同，由于量子态的叠加性（superposition，见于量子力学第一公设[7]），任一量子态可表示和储存为“0”（即量子基态）和“1”（即量子基态）的线性叠加（即量子态， ）。 这样，量子信息和量子数据便可表示和储存为上述量子态的形式，显然这不是实线性空间，而是Hilbert 空间[8]。 故在量子计算中，量子信息的度量单位是以上述单量子态为存储单位的量子位（qubit），它在表示和储存方面带来的优势是随着量子位的增加，量子信息的表示空间和存储空间将以指数规模拓展。

第二，信息的处理。 在计算理论中，信息处理的能力涉及两方面：一是数据的表示能力，二是问题的求解空间。 上文已提及，基于图灵机的经典计算是通用的，任何经典算法都可看做一个接受不同规模参数输入的可计算函数，函数的输出就是该算法对应的问题的解。 由于数据的表示空间是线性的，所以当求解问题的代价与输入数据的规模呈指数关系时，用确定性函数计算输入数据就需要指数规模的代价（时间或空间）。 而在Hilbert 空间中由于量子态的叠加性，量子算法处理的问题表示和求解空间均为输入的指数规模，所以某些特定的函数便可以在线性时间内处理指数规模的输入，这种特性现已被诸多量子算法应用。

【下载地址】

链接：https://pan.baidu.com/s/1CLL2RoF5QT_6xA4-O2fumA 提取码：3qgk