核磁共振量子计算机与并行量子计算.pdf

专题讲座 核磁共振量子计算机与并行量子计算 龙桂鲁1 2 3 肖 丽1 2 1清华大学物理系 北京 100084 2量子信息与测量教育部重点实验室 北京 100084 3中国科学院理论物理所 北京 100083 收稿日期 2003242 29 NUCLEAR MAGNETIC RESONANCE QUANTUM COMPUTER AND PARALLEL QUANTUM COMPUTING Long Guilu1 2 Xiao Li1 2 1Department of Physics Tsinghua University Beijing 100084 2Key Laboratory for Quantum Information and Measurements Ministry of Education Tsinghua University Beijing 100084 摘 要 在本文 我们首先回顾了量子计算的发展历史 阐述了核磁共振量子计算的 原理 在叙述了利用有效纯态方法进行核磁共振量子计算之后 我们阐述了 利用混合态进行核磁共振的量子计算的方法 首先是刘维尔量子计算方法 它是由Madi Brushweiler Ernst等人1998年提出的 在这一模式中 可以对 搜索算法进行加速算法 Brushweiler提出了一个指数速度的搜索算法 我们 在3个比特的量子计算机中实现了这一搜索算法 我们在这一模式中提出了 一个只需要一次搜索即可找标记物的直接拿取算法 并且在7个比特的核磁 共振的量子计算机中实现了这一直接拿取算法 本文提出了在一个核磁共振量子计算机 或者更一般地一个系统量子计 算机中实现多个量子计算机的并行计算 我们着重对量子搜索算法和Shor 的大数分解算法进行了并行实现 在并行量子计算中 一部分量子比特处在 纯态 一部分量子比特处在混合态 如果所有的量子比特都处在纯态上 则就 是有效纯态量子计算 如果所有的量子比特都处在混合态上 则就是刘维尔 量子计算 在这两个极限中间 相当于2个到N 2个量子计算机的并行计 算 量子搜索方法可以很有效地进行并行计算 而Shor算法则只能在小的范 围内进行并行计算 1 量子计算 1 1 为什么要研究量子计算机 计算机在短短的四五十年里 已经在世 界家喻户晓 深入人们的工作和生活的方方 面面 取得了巨大的成功 但是 现在为什么 人们又开始研究其他种类的计算机呢 例如 DNA计算机及量子计算机等 我们从电子计 21物理与工程 Vol 13 No 3 2003 算机的发展 以及量子计算机的特点来回答 这个问题 原因1 随着科学技术的发展 电子计算机的集 成化程度越来越高 集成片的尺度越来越小 计算能力是越来越强 根据Moor定律 1 计 算机芯片的集成化度 每18个月增长一倍 也就是说 相同尺寸的存储器上的存储单元 数目每过18个月就增加一倍 按照这个趋 势 到2020年左右 将发展到用单个原子的 尺度 到那时 经典物理规律将不起作用 系 统将受量子规律支配 表现出波粒二相性 电 子计算机将无法工作 原因2 芯片集成化速度的飞跃发展 电子计算 机的运算功能比其初期提高了数百万倍 但 由于其运行速度不断增快 晶体管间距离愈 来愈近 将必然导致热力学问题的产生 这一 问题产生于计算过程中的不可逆操作 2 要 解决这一问题自然需要进入量子力学的领 域 因为量子计算机是可逆的 3 6 量子计算 机的可逆还意味着可以从输入得到输出 同 时可以从输出推出输入 原因3 费曼的研究表明 6 经典计算机不能有 效地模拟量子体系 但是 对于大量的量子体 系 能够精确求解的量子体系并不多 所以人 们希望能够用计算机来模拟真实量子体系 量子计算机或量子模拟器 7 8 是量子体系的 有效模拟工具 用量子计算机来模拟量子体 系的演化 9 验证量子物理规律 是量子物理 学本身发展的迫切需要的技术支持 量子计算机的概念早在20世纪80年代 初就由于费曼提出 6 量子力学和计算机结合 而萌芽 后来 Benioff 3 4 提出量子图灵机的 概念 1985年 Deutsch 10 提出量子计算机的 具 体 概 念 1992年 Brassard和Berthi2 aume 11 12 证明了量子图灵机理论上比经典 图灵机快 虽然早已有量子计算机的概念 但 是由于没有可以操作的实例进一步显示量子 计算机在解决实际问题时的实际功能 故在 很长一段时间它的发展很慢 1994年 P Shor 13 利用量子纠缠性和叠加性提出著名的 大数因子分解的量子算法 Shor算法 使 得公开RSA密钥系统受到巨大挑战 激发了 人 们 研 究 量 子 计 算 机 的 高 潮 1996年 Grover 14 提出了在无序库中搜索某些满足特 定条件的项目的算法 Grover量子搜索算 法 使得从没有排序的N个数据中搜索一个 确定的数据 只需 O N 次运算 而利用经 典计算机平均需用N 2次运算 1 2 量子计算机的原理和特点 量子计算机是相对经典计算机而言的 量子计算机并不是在通常的计算问题上取代 传统的电子计算机 而是针对特定问题完成 经典计算机难以胜任的高难度计算工作 它 是以量子力学为基础 实现量子计算的机器 量子理论是物理世界的数学模型 从量子假 设及实验结果可以得出许多奇特的性质 利 用这些奇特的量子特性 量子计算机具有比 经典计算机更强大的功能 量子力学的基本假设 1 微观系统的物理状态由希尔伯特空 间的一个矢量来描述 2 微观系统的物理量由希尔伯特空间 的厄米矩阵描述 物理量所能取的值 是相应 矩阵的本征值 物理量A在状态 中取各 值ai的概率 与态矢量 按A的归一化本 征矢量 ai 的展开式中 ai 的系数的复平 方成正比 即与下式中ci的复平方成正比 i ci ai ci ai 3 微观系统的状态 t 随时间的变 化规律由薛定谔方程来描述 i 5 5t t H t 式中哈密顿量H为p q的矩阵函数 有如经 典力学中哈密顿量H为p q变量的函数 或者可以认为 t e i t 0 即体系的状态变化由U矩阵e i Ht来刻画 4 测量与塌缩 假定体系处于力学量 A的本征矢 a1 和 a2 的叠加态c1 a1 c2 a2 c1 2 c2 2 1 然后我们对力学量 A进行测量 以 c1 2 c2 2 的概率获得结果 a1 a2 但是 一旦我们获得了确定的结果 体 系的状态也就确定为 a1 或 a2 而不再是 两者的叠加了 31 物理与工程 Vol 13 No 3 2003 量子计算机的特点 1 线性叠加性 与经典计算机相对应 量子计算机也由 存储器和运算器组成 其中运算器又由逻辑 门网络组成 但是量子计算机的存储内容和 逻辑门与经典计算机却有所不同 在经典计算机中 信息或者数据由二进 制数据表示 每一个二进制数据位的0或1 由电平的高低决定 在经典计算机中 每个数 据位要么是0 要么是1 两者必居其一 量子 计算机则不同 它的二进制数据位 我们称之 为量子位 qubit 的0或1由电子或原子的 自旋状态或二能级系统的基态和激发态决 定 由于量子力学中有叠加态 superposition 的存在 从基本假设 1 可以得到 所以数据 位可能是0 也可能是1 还可能同时是0或者 1 即量子计算机的二进制数据位是0和1的 任意叠加态 正因为如此 对于n个数据位的 存储器 经典计算机只能存储一个n位二进 制数 而量子计算机能同时存储2 n 个n位二 进制数 同样 对经典计算机来说 每一次操 作只能对一个n位二进制数实行处理 而量 子计算机能同时对2 n 个二进制数进行处理 正是由于量子力学叠加态的存在 大大提高 了量子计算的效率 实现了连续变量和真正 意义上的并行计算 虽然经典计算机也可以 利用并行性作用来减少某些算法所需要的时 间 但若要使所需要的时间呈指数量级地减 少 必须要指数量级地增加操作用的计算机 数目 相应地 所需的物理空间指数量级增 加 而在量子体系中 随着体系尺度的线性增 加 并行量则指数增加 即量子体系中并行量 的指数增加仅使物理空间线性增加 这是量 子并行与经典并行之间的差别 2 干涉性 量子干涉性可直接从态叠加原理中推导 出来 对于n个量子位 量子计算机的叠加态 可以表示为 2 n 1 i 0 ci i 1 这种叠加不是简单的几率相加 而是几 率幅相加 故量子态有相对位相差 在演化过 程中会出现干涉相长或相消 这是经典布尔 态所不具备的 干涉性在量子超快算法中被 应用 3 纠缠性 在量子体系中 不同的体系间可以存在 量子纠缠 量子纠缠是一种没有经典对应的 关联 它不是一种动力学效应 而完全是一种 量子效应 建立纠缠时需要相互作用 但一旦 量子纠缠建立了 撤消相互作用 量子纠缠仍 然保持 量子纠缠在量子通信 15 18 中有着举 足轻重的作用 4 不可克隆性 由于量子力学的态叠加原理和系统态的 演化遵从么正变换 使得任何量子体系的任 意未知量子态无法被完全复制 19 20 即无法 在不破坏原来未知态的情况下对之进行观察 和测量 我们无法克隆不可知的量子态是我 们进行密码通信的基础 量子计算除了并行性的特点外 还有另 一个特点就是量子计算的随机性 28 量子计 算机是一个 真 正 意 义 上 的 随 机 计 算 机 Williams 29 认为利用量子的随机性产生随机 数进行编码 可以在密码通信中加以利用 另 外 在某些算法中加入一些随机性 可以得到 更有效的算法 30 1 3 量子计算的基本概念 量子力学用于计算科学 产生了新的基 本概念 在前面涉及到量子位 qubit 和量子 逻辑门 logic gate 的概念 在此 将稍加详细 的进行讨论 1 量子位 量子位是量子信息的一个基本单位 21 任何一个两态的体系如自旋为1 2的核和两 能级原子都可以作为一个量子位 量子位和 经典位的区别在于 一个经典 下转第20页 41物理与工程 Vol 13 No 3 2003 d 8 2 0Rsin 2 14 由于场强的对称性 P点场沿径向 大小为 EP dEPcos d 8 2 0Rsin 2 cos 2 2 d sin 2 d 8 2 0Rsin 2 8 2 0R2 2 0 d 4 0R 15 按照功能关系来讨论 设柱面的半径由 R收缩到R dR 沿轴线取长度为l 外力克 服静电场力做功为 dW qERdR l ERdR 16 式中ER为柱面上的电场强度 当柱面的半径 减小 dR 后 距柱面的中心轴线为R以外区 域内的场强和静电能没有发生变化 则外力 做的功转变为 dR 范围内的静电能 因而有 dW d 1 2 0E2dV 1 2 0E 2 2 Rld R 17 式中E为柱面半径收缩为 R d R 时 距轴 线为R处的场强 由高斯定律得 E 2 0R 18 由 16 式 17 式和 18 式联立解得 ER 4 0R 19 参考文献 1 严济慈编 电磁学 北京 高等教育出版社 1988 2 赵凯华等编 电磁学 上 北京 人民教育出版社 1978 上接第14页 位只能取两个可能值 0 或 1 中的一个 而一 个量子位是一个二维希尔伯特空间 Hilbert space 的矢量 即量子位可以处在任意叠加态 0 1 中 其中 2 2 1 由于 均为复数 这样除去归一化条件外 还需三 个参数来描述一个量子比特 可是我们知道 对一个量子体系而言 一个整体的相位是不 可观测的 也就是说 和e i 描述同一 个物理的量子态 一 个 量 子 比 特 可 以 用 cos e i sin 来描述 如图1所示 一个经典比 特的拓扑不过是两个点 而一个量子比特的 拓扑却是一个球面 看起来似乎一个量子比 特可以比一个经典比特承载更多的信息 然 而根据基本假定 4 当一个量子比特被测量 时 和一个经典比特一样 其结果也只能是0 或者1 尽管如此 我们要看到 在测量之前 量子比特确实比经典比特承载了更多的信 息 或者说在运算过程中 一个量子比特是表 现为一个希尔伯特空间的矢量的 我们可以 利用这一性质 对之施加各种各各样的量子 门 来完成量