量子计算机_量子算法与物理实现.pdf

量子计算机 量子算法与物理实现 方 粮 刘汝霖 汤振森 隋兵才 池雅庆 国防科学技术大学计算机学院 湖南 长沙 摘 要 量子算法与物理实现是量子计算机研究中的两个基本问题 本文首先总结了相关领域的主 要进展 并讨论了有代表性的量子算法 特别介绍了用于求解线性方程组的量子算法 分析了影响新量子 算法提出的因素 然后 探讨了物理实现的迪文森佐判据 并介绍了典型的实现方案及性能比较 同时 也关注了对量子计算机研究持有异议的观点 最后 对量子计算机的新研究方向作了探讨 关键词 量子计算机 量子算法 量子比特 离子阱 量子随机游走 费米子 拓扑量子计算 中图分类号 文献标识码 引言 量子计算机是一类遵循量子力学规律存储量 子信息 实现量子计算的物理装置 它的特点可归 结为 量子计算机的输入态和输出态为一般的叠 加态 其相互之间通常非正交 量子计算机中的变换为所有可能的幺正变 换 量子计算机对输出态进行一定的测量 给 出计算结果 量子计算机的输入用一个具有有限能级的量 子系统来描述 如二能级系统 称为量子比特 即 量子比特 可以是 态和 态的任意组合 其中 和 分别代表相干 叠加态中的比例系数 基于量子相干效应 满足 条件的系数取值有无穷多组 因此量子 比特所代表的信息得以大大丰富 量子比特的构 成可以利用光子的偏振 也可以利用被捕获离子 或原子 的能级 还可以利用超导线路 其中包括 对 以及与环流方向相关的左 右旋环流的 收稿日期 修订日期 基金项目 国家自然科学基金创新研究群体科学基金资助项目 通讯地址 湖南省长沙市国防科学技术大学计算机学院 计算机工程与科学 年第 卷第 期 文章编号 叠加态 量子叠加性和量子相干性是量子计算最本质 的特征 量子计算机对每一个叠加分量实现的变 换相当于一种经典计算 所有这些经典计算同时完 成 并按一定的概率振幅叠加起来 给出量子计算 机的输出结果 因此 量子计算是一种并行计算 在此并行条件下能够在多项式时间内解决经典计 算机指数时间内才能解决的问题 例如 量子计算 机可在几秒钟之内将一个 位的大数分解为两 个质数的乘积 而当前的计算机完成此项工作需耗 时 万年 若研制出量子计算机 就可破译目前 通用的 密码体系 后果不堪设想 鉴于量子计算非凡的能力 引起了来自数学 物理学 化学和计算机科学等不同领域的研究人员 的极大兴趣 也引起了政府部门和商界的高度重 视 因而 研究量子计算机的势头有增无减 目 前 在 等顶级期刊上 量子计算相 关的文章都在以每月数篇的规模增长 特别是由 于量子计算机潜在巨大能力 美国国防部甚至联合 等公司和相关高校 整合各方力量启动 了 微型曼哈顿计划 希望率先研制出实际可用的 大型量子计算机 以占领先机 量子计算机的研究主要可分为量子算法和物 理实现两大分支 量子计算机的近代研究可追溯 到 年美国的 提出的有可能把量子 力学和计算机结合起来的设想 年 英国 牛津大学的 进一步阐述了量子计算机的 概念 并且证明了量子计算机比经典图灵计算机具 有更强大的功能 年 美国的 利用量 子计算机理论证明 一个 位大数的质因子分 解只需用 的多项式时间 而不是以前的 的指 数次时间 这无疑说明了量子计算机会对现有的社 会和国民经济以及国防产生潜在的威胁 年 美国的 证明在无序数据库搜索问题上 量子计算机比经典计算机优越 年 英国 大学的 等人提出了一个新的量子 算法 把求解线形方程组的复杂度由 降低到 这是第一个解决科学和工程中最常见问 题的量子算法 相对于量子算法而言 量子计算机的物理实现 研究可谓严重落后 的 认为 实 现量子计算机功能的该物理系统必须满足某些特 定的条件 即所谓的 判据 该判据 与量子计算相关的共有五条 且各条之间难以协 调 物理实现非常困难 年 奥地利茵斯布鲁 克大学的 和 首次提出量子计算物理 实现理论模型 他们建议在线性离子阱体系中 实现量子计算 此后 物理学家从理论上提出了十 几种物理系统和操控模式 试图达到物理实现量子 计算的基本要求 基于纠缠光子随机游走的方 案 拓扑量子计算机以及基于 费米子的 量子计算机实现方案是当前的研究热点 量子算法与物理实现是量子计算机实现研究 中的两个最基本问题 本文结合国内外最新的研 究成果 总结了量子算法和物理实现研究的主要进 展 讨论了量子算法的类型和提出量子算法的影响 因素 探讨了物理实现的 判据 介绍了 典型的实现方案及性能比较 同时 也关注了对量 子计算机研究持有异议的观点 最后 对量子计算 机的新研究方向作了探讨 量子算法 实用的量子算法大致可分为三类 第一类是 以 算法为代表的基于量子 变换方法 寻找周期性的问题 进一步又可归结为阿贝尔隐含 子群问题 凡是能归结为 的公钥密码 将不再安全 而 算法构建了基于概率幅放大方法的 一类问题的基本框架 包括改进的 算法 碰撞问题 量子遗传算法 量子模拟退火算法 量子 神经网络等 第三类是属于模拟或解决量子物理问题的算 法 包括 提出的用量子计算机加速量子 物理仿真的原创性设想 近期有基于量子随机游 走 尤其是连续时间量子随机游走的算法 这其中 就有 和 提出的 树的布尔 逻辑计算算法等 算法 年发现的 算法是一个针对整数分 解的量子算法 它解决的题目如下 给定一个整数 找出它的质因子 在一个量子计算机上面 要 分解整数 算法的运行需要多项式时间 更精确地说 这个算法花费 的时间 算法中 把寻找一个大数的质因子问题 转化为寻找其余因子函数的周期 只要该周期 被找到 并且为一个偶数 那么利用剩余定理 就能 得到该大数的质因子 给定整数 选取一个与 方 粮等 量子计算机 量子算法与物理实现 互质的数 使得 以 为 例 先选 分别计算 得 到一个重复序列 不难看出 变化周期为 它也满足 有了这个周期 就可以利用孙子定理 设 其中 必须为偶数 且 求出 之后 再分别求 和 的最大公约数 设 那么一定有 即 被成功地质 因子化 本实例中 即 把 分解为 算法的关键在于求出大数 的余因子 函数的周期 不过 由于余因子函数的周期 不 能在量子计算中被有效测出 因此在 算法中 需借助量子离散傅立叶变换 考虑 维向量 对于经典 的情况 其傅里叶变换 为 槡 针对量子情况 对任意给定的态 其傅里叶变换通过幺正变换 实现 其中 槡 如果单独作 用某 个 基 矢 则 量 子 变 换 可 以 表 示 为 槡 这里的 和 即为量子 变换对 离散 变换将余因子函数的周期换成 另一个可测的周期 理论上可以证明 在量子计算机上进行的基于 变换的 量子算法对因子分解是有效 的 即对正整数的因子分解所需要的计算时间随着 计算的数 的位数增加以多项式方式增长 当 的位数很大时 以位数的指数方式增长与以位数 的多项式方式增长在计算量上有巨大的差别 算法重要性在于 若使用量子计算机的 话 我们可以用来破解已被广泛使用的公开密钥加 密方法 也就是 加密算法 算法的基础 在于假设了我们不能很有效率地分解一个已知的 整数 就目前所知 这假设对传统的 也就是非量 子 计算机为真 没有已知传统的算法可以在多项 式时间内解决这个问题 然而 算法展示了 因子分解这问题在量子计算机上可以很有效地解 决 所以一个足够大的量子计算机可以破解 这也是推动量子计算机的物理实现研究和量子算 法研究的强大动力 在 年 的一个小组展示了 算 法的实验 使用 核磁共振 实现的量子计算 机 以其 个量子比特 将 分解成 然而 对 的实验是否是量子计算的真实展示 则有 一些疑虑出现 因为没有纠缠现象被发现 算法 算法的实现基于概率幅放大 对许多 计算问题的传统算法都有平方加速 由于振幅放 大是量子算法的基础 因而引起了极大的关注 这 包括对误差和修正的健壮性的研究 算法是面向无序数据库的搜索算法 对于一个无结构的数据库 最优经典算法的搜索复 杂度为 用概率图灵机搜索的期望次数为 步 算法的搜索复杂度为 槡 这就是说该算法能够在量子计算机上搜索 比特 的数据比在经典计算机上搜索槡 比特的数据还 要快或相当 并且 搜索算法是一种对空间 进行完全搜索的优化算法 现实中许多问题都可归结为搜索问题 如最 短路径问题 排序问题 图着色问题 数据库搜索问 题及密码中的穷举攻击问题等均属于这类问题 算法对经典对称密码的攻击非常有 效 年美国国家标准局 公布了数据加 密的标准算法 其有效密钥长度为 比特 由于计算技术和密码理论的发展 比特密钥的 已远远不能对付当前的攻击 特别是密码的 穷举攻击 为了增加密码的安全性 美国国家标 准技术研究所 又经过了 年的广泛征 集和严格筛选 并于 年公布了新的高级加密 标准算法 其密钥长度可取为 比特 比特和 比特 目前欧洲又在征集序列密码的 标准加密算法 其气势更盛于 不过从现在 所提供的 个算法看 其种子密钥长度都在 比特以上 因而 可以说经典私钥密码的安全性 在算法没有安全漏洞的条件下 就是靠增加密钥 长度来保证的 目前序列密码和分组密码 如 设计中以 增加密钥长度来保证密码的安全性 在量子计算 机上亦不再安全 因而量子 攻击对经典私 钥密码可以成功地实施攻击 虽然 算法并 计算机工程与科学 不能在指数量级上优于经典算法 但由于其未来 应用的广泛性 因而仍具有重要意义 求解线形方程组的量子算法 求解线形方程组的量子算法由 等人 于 年提出 该算法的主要思想如下 给定一个厄米特 矩阵 一个单位向 量珗 假定我们要求珝 以满足 珝 珗 首先 该算 法把珗 表示为量子态 然后 为 实现不同时间的叠加 用哈密尔顿仿真技术把 施加到 用相位估计理论 把对 的取幂运算 转换成在 的本征基上分解 以求解相应的特 征值 这一步完成后 系统的状态接近 其中 是 的特征向量基 再进行线性映射 其中 是归一化常数 由于该操作并不唯 一 因此有一定的失败概率 成功后 再计算 寄存器 留下的状态与 成比例 在矩阵求反算法执行中的关键因素是 的条 件数 即 的最大和最小特征值之比 随着条件 数的增加 逐步趋向于不能求反的矩阵 解就变 得更不稳定 这样的矩阵称为 条件差的 该算 法一般假定 的奇异值在 和 之间 在这种 情况下 运行时间随 而变 其中 是输 出态 中的附加误差 因此 该算法最好情况发 生在 和 均为 的多项式量级时 此时 可获得指数级的加速比 等人也研究了 对 条件差的 矩阵的处理方法 该算法可产生珝 的所有分量 但是 有时人们 可能只对其中某些期望值珝 珝 感兴趣 此处 是某种线性算子 该算法对非线性算子也适用 把 映射到量子力学算子 执行与 相关的量子 测量 可得到期望的值 珝 珝 用 这种方法可获得珝 的多种特性 如归一化 状态空 间中不同部分的权重 矢量矩等 在实际的科学研究和工程计算中 我们遇到最 多的问题是与解线性方程组相关 而且遇到的大部 分线性方程组都是稀疏的和高维的 为解决该问 题 传统的算法做出了长期的努力 但现在最优的 算法复杂度是 该量子算法的结果表明 若 使用量子计算机来解高维的线性方程组 最好的加 速比将达到指数级 因此 该算法可以求解高维的 线性方程组 这有可能解决以前难以解决的问题 如长期天气预报 更加有效的网络检索处理等 问 题是 真正实用的量子计算机何时问世 为什么没有更多的量子算法 发现大数分解算法后 研究了这样一个 问题 为什么没有发现更多的量子算法 给出了两种可能的解释 同时提出了可能导致发现 更多量子算法的研究思路 认为 第一个可能的理由是 量子计算机 的运行方式与传统计算机完全不同 使得我们原有 的设计算法的技巧以及理解运算过程的直觉不再 适用 第二个理由是 量子计算机只能对少数问题 提供显著加速比 而我们也许已经发现许多或所有 重要的构造量子算法的技巧 用传统的直觉很难理解量子计算机 物理学 家已经花费了数十年的时间使量子力学现象直观 化 而计算机科学家考虑量子算法仅一 二十年的 时间 所有具有明显加速的量子算法都涉及量子 干涉 而传统计算机科学家对此所知不多 因而 有可能仍有些重要的量子算法有待发现 值得一试的研究领域是 对在传统计算机上已 有多项式时间可解的问题 探索更快的量子算法 该方法限于获得多项式因子的加速比 这虽然没 有像发现超多项式加速比的量子算法那样令人激 动 而且实用价值也可能不大 但是可以获得设计 量子算法的新技巧 任何对进一步开发量子算法 有潜在价值的新技巧都值得一试 物理实现 按照 判据 要实现量子计算机 相 应的物理系统必须满足如下要求 具有可伸缩的 特性良好的量子比特位 能够初始化量子比特到某个基准态 如 具有足够长的相干时间 要比完成量子门 操作的时间长得多 具有一套通用的量子门 能够实现对特定量子比特位的测量 为在物理上实现量子计算机 研究人员依照 判据 主要在以下两大方向展开了广 泛深入的研究 基于固态电磁电路的量子计算机 包括自 旋 系统 超导 系统 量子 点 系统 核磁共振 系统等 方 粮等 量子计算机 量子算法与物理实现 实现方案 基于量子光学系统的量子计算机 包括离 子阱 腔量子电动力学 系 统 线性光学系统 光子晶体和光学晶格束缚冷原 子体系等实现方案 基于固态电磁系统的方法可集成性好 目前已 能够制备和操控几个 十几个量子比特的演示系 统 若能实现规模集成 就有望实现复杂的量子运 算 但是 固态系统容易受外界环境干扰 退相干 问题相当严重 而基于量子光学方案的量子相干 性较好 易于实现单量子比特位和两量子比特位的 幺正变换 但是 量子光学系统体系的可集成性较 差 描述实验系统的主要性能参数为 退相干时间 秒 运算时间 秒 以及不同物理实现的最大 操作次数 表 为各物理实现 系统的性能比较 从表 可以看出 和 两种 方案的最大操作次数有可能达到 而 方案可达 前景看好 表 物理实现系统的性能比较 下面分别讨论三种典型的量子计算系统 即量 子点量子计算 离子阱量子计算和超导量子计算 同时介绍了基于光子随机游走的实现方案 量子点量子计算 自 提出用电场阵列限制量子点中 电子数目及自旋方向来制备量子比特的方案以 来 实现量子计算芯片的基本条件 量子比 特位 逻辑门 量子相干和测量都已经在实验中成 功实现 半导体量子点的实现方式被认为是最有 可能实现大规模量子计算机的候选方案 同时 由 于与当前半导体工艺的良好兼容性 半导体量子点 也成为量子计算研究领域发展最快的分支之一 束缚在量子点中运动的电子 就像在原子中的 电子一样 具有类似抛物线型的限制势 电子的能 谱是一系列分立的能级 因此量子点就像一个 人 造原子 与通过测量原子光谱获得电子的状态类 似 量子点中的电子能级可以通过电学测量手段得 到 量子点通过两个可以让电子隧穿的势垒连接 到源极和漏极 并通过电容耦合与一个或多个栅极 连接 栅极可以调节量子点与源漏电极之间的电 势差 通过测量电子的隧穿电流和电极上电压 就 可以得到量子点的相关信息 当量子点中只包含一个电子时 整个系统可以 用氢原子的波函数进行描述 当该量子点置于外 磁场中或者使用极化光激发时 由于自旋的存在 轨道劈裂成二能级结构 其基态是与磁场平行方 向的自旋向上态 而激发态则是与磁场方向相反的 自旋向下态 大学 小组在 年将量 子点放在稀释制冷器中 外加 的强磁场 量 子点的塞曼能达到了 大于 的热 能 但小于轨道能级间隔和充电能 将劈裂的二能 级作为希尔伯特空间的一组基 就形成了一个量子 比特 这是首次在半导体器件中实现自旋量子比 特 图 为量子比特中自旋到电荷的转换的 图 表示金属电极 表示施加在二 维电子气表面的磁场 图 量子比特中自旋到电荷的转换 年 小组制备了栅极调节的碳纳 米管量子点 如图 所示 接触提供了高 电导率的金属 纳米管接口 在低温下不会形成隧 穿势垒 长度约 的纳米管与 接触时的栅 极响应 如图 所示 制备的 顶栅 在 下用 的交流信号激励 在该器件 中 电压大于 时 所有栅极都会抑制电导 该 结构易于在一个纳米管上实现多量子点的精确调 控 可作为基于纳米管的量子系统设计范例 为了读出量子点中的信息 通常在量子点附近 计算机工程与科学 图 栅极调节的碳纳米管量子点 有一个专门制作的读出结构 称为量子点接触 如 图 所示 量子点接触中的电子隧穿通过势垒 形成电流 由于量子点上的电子与量子点接触中 的电子存在比较强的库仑相互作用 当量子点上的 电子数目发生改变时 就会影响到量子点接触上的 势垒 从而改变量子点接触中的电流 加上外磁场 后 量子点中自旋向上和自旋向下的电子分别带有 不同的能量 调节电极之间的电势差 使得量子点 形成不同的分布 量子点接触则通过感应量子点中 的电流变化读出信息 图 一种量子点结构的 图样 它把电子束缚在 纳米的区域内范围 其 中 分别为左 中 右电极 而 为量子点 间的遂穿势垒 左侧的量子点接触 被用于检 测器件电流 用于控制读取量子点中的信息 尽管利用半导体量子点的自旋进行量子信息 处理已经获得许多令人瞩目的进展 但是要成为真 正的量子芯片还有很多困难需要克服 半导体量 子点体系受周边环境的影响比较严重 控制其退相 干 维持其量子相干状态遇到了更大的挑战 许多 研究人员开始探索利用 和石墨烯等新型半 导体材料制备量子点 在这些新材料中没有核自 旋 所以自旋量子比特具有较长的量子相干时间 初步的实验发现退相干时间可以达到秒的量级 自 旋弛豫时间甚至可以达到数小时 这些进展已引起 国际上广泛关注 也为半导体量子点作量子芯片的 研究开辟了一个全新的思路 离子阱量子计算 年 和 首次提出在线性离子 阱体系中实现量子计算 并于同年在实验室中实现 了该方案 在该体系中 是束缚在线性离 子阱中单个离子的两个内能级 如图 所示 单 的幺正变换可以通过寻址激光束与单个 离子的共振相互作用来完成 个 的受控幺 正变换需要利用失谐的激光束先后照射两个需要 相互作用的离子 借助与整体离子串的声子相互作 用来完成 初态制备可以利用激光冷却来完成 而 末态测量则可以通过观测单个离子的荧光光谱来 完成 由于过程需要大量离子的参与 操作过程更 易受到外电场等退相干因素的影响 同时导致量子 操作的效率也非常低 离子阱作为实现小规模量 子计算机的强力候选被广泛关注 图 线性离子阱示意图 为了提高量子比特的集成数目 解决方法之一 是采用复杂的阱结构使得离子之间相互独立 这可 以通过设置阱电极来实现 如图 所示 另一 种增加离子阱比特数的方式是通过光子相互作用 耦合小的库仑离子团 采用这种方法使得离子可 以实现微米尺度的纠缠 通过重复调用的量子电 路形成稳定的量子存储网络实现长距离通信 该 方法也有望成为大型分布式量子计算系统的基本 单元 图 多级线性离子阱芯片 图示放大区域的白色斑点为 方 粮等 量子计算机 量子算法与物理实现 晶格离子阱方案也备受关注 其基本结构是 平面上电或磁的离子阱晶格阵列 每个离子阱中仅 仅束缚单个离子 不同的离子阱间隔较远 可以忽 略掉它们之间的相互作用 对照线性离子阱的方 案 增大并行操作的效率 由于平面上不同离子阱 之间是互不影响的 因此也易于集成 中性原子形成量子比特的形式与离子相似 一个中性冷原子阵列可以通过交叉激光束被束缚 在自由空间 形成光格点 由激光作用产生斯塔克 效应并形成有效的对原子的外部势场 选择合适 的激光光束 可以在三维空间形成特定模式的势 阱 如图 所示 中性原子被限制在势垒区内 类似 晶格中原子 图 多维光学格子示意图 通过调整外部激光束的尺寸 极化方向 能量 密度可以精确控制光学格点的维度 深度 形式 位 置等参数 采用光栅格子最重要的问题在于如何 实现原子量子比特的初始化 相互作用和测量 对 于阱中的离子和原子 相干时间远高于纠缠制备 操控和测量的时间 挑战主要来自如何保持在向 着更高集成度扩展时仍然拥有较高的高保真度 图 为光子中介的离子阱方案 每个独立 的离子阱中束缚有两个不同类型的离子 由于两 个离子不相同 就可以采用不同频率的激光照射该 节点 从而控制单 的幺正变换 不需要激光 对这两个离子分别寻址 图 基于光子中介的离子阱方案原理图 超导量子计算 超导量子计算的核心单元是一种 超导体 绝 缘体 超导 体 三 层 结 构 的 约 瑟 夫 森 结 电 子 器 件 其中间绝缘层的厚度不超过 形成一 个势垒 库珀对能够隧穿该势垒形成超导电流 世纪 年代 在约瑟夫森结电路中观测到 宏观量子相干现象 这种宏观量子相干现象 表现为大量电子集团运动的相干叠加 即宏观薛定 谔猫态 年代中期 量子信息与量子计算的兴起使 小电容约瑟夫森结器件成为量子计算领域的研究 热点 应用超导的宏观量子特性 以约瑟夫 森结为基本器件来控制超导宏观波函数的自由度 目前有三种形式的 基本结构 分别为超导电 荷 超导磁通 和超导相位 与天然的量子体系相比 超导量子电 路的能级结构可通过对电路的设计进行定制 或通 过外加电磁信号进行调控 而且 基于现有的集成 电路工艺 约瑟夫森量子电路还具有天然量子体系 无法比拟的可扩展性 这些优点使超导量子电路 成为实现可扩展量子计算最有前景的物理方案之 一 单 逻辑门操作已经在不同种类的约瑟 夫森器件上成功实现 最近 人们在超导传 输线腔 等介观谐振子器件 方面都取得了 很有意义的进展 超导量子计算存在的主要问题是固体体系中 大量不易操控的自由度给约瑟夫森量子电路带来 强烈的消相干 其中最典型的消相干过程是由 具有低频特性的电荷型或磁通型偏置噪声所导致 的退相干 已知的各种约瑟夫森量子电路消 相干时间大约为各自单 操作时间的 倍 这与实现量子纠错编码所需的 次单 操作的阈值还存在较大差距 近年来 超导量子计算取得了新的重要进展 年 德国 的 等 实现了超导电荷 如图 所示 超导电荷 是一块尺寸在亚微米量级的超导金属块 通 过由两个相同的约瑟夫森结组成超导量子干涉器 件 外加的偏置电压通过偏置电容来控 制 的工作点 而在超导量子干涉器件的有效 约瑟 夫 森 耦 合 能 年 美 国 耶 鲁 大 学 的 小组提出并实现了 个电荷 与 超导传输线腔谐振子之间的强耦合 该实验不 仅在固体体系中模拟了量子光学过程 还展示了利 用固体谐振腔作为数据总线来实现 之间可 计算机工程与科学 控耦合的可能性 图 约瑟夫森电荷 示意图 年 美国麻省理工学院 等提出 基于磁通自由度的持续电流 磁通 的结构是一个包含 个约瑟夫森结的闭合回 路 的 和 分别对应环路内顺时针和逆 时针的超导电流 年 小组实现了持续 电流 与 谐 振 子 的 耦 合 年 日本 实验室的 等实现了 个磁 通 之间的可控耦合 光子随机游走 量子随机游走最初是在 年由物理学家提 出的 然而 正是由于对量子计算机关注的升温才 促使了人们对是否能够将这种随机游走的特性用 于计算的思考 经典随机游走位置的标准差是步 数的函数 大致在槡 量级 相比之下 量子随机 游走的位置的标准差为步数 的线性函数 这一 差异表明对于量子算法而言 其对空间的搜索速度 是经典算法的二次方 这也是基于量子随机游走的 量子算法的优势之一 其中一个重要应用是图的 游历 如图 所示 图 图的游历 对于这样一个由两个完全二进制树相交叉形 成的图 求从起点到终点的最短路径所需时间 对 于经典随机游走 所需时间为二进制树深度 的指 数函数 相比之下 量子游走算法可以在多项式时 间完成 另一个关于量子随机游走的典型应用是布尔 表达式求值 对于一个 变量的布尔表达式 可 以表示为如下形式 使用由 门组成的 层 完全二进制树 其叶的个数为 每一个表示 为 或者 现欲求布尔表达式的值就相当于求 取二进制树根节点的值 如图 所示 图 经典二进制 逻辑树 对于经典算法 解决此类问题的时间复杂度为 的多项式函数 而通过 等人 发现 的量子算法 其时间复杂度可达到下限 槡 此外 量子游走在图同构 碰撞问题 游戏断言等算 法中也有广泛的应用 美梦还是噩梦 乐观者认为实用的量子计算机指日可待 满怀 信心地不惜投入巨资加紧研制 而悲观者对量子计 算机的前景似乎并不看好 发出了研制量子计算机 是美梦还是噩梦的感慨 悲观主义者的论点 量子计算的原理是将量子力学的叠加原理运 用到计算机运算上 量子计算已经成为物理学领 域的一个热点 二能级系统作为量子比特已获得广 泛的认同 而二能级系统之间的相互作用可以构建 量子逻辑门也成为业界的共识 原理上 一个量子逻辑门网络可以处理大量处 于叠加态的量子寄存器 实现大规模并行处理 从 而大大地降低时间复杂度 常规计算机进行大数 因子分解是非常复杂的 这使得大数因子分解问题 广泛运用于信息系统的安全加密 而 量子算 法的发现 在理论上表明在量子计算机上可以实现 大数因子分解多项式时间复杂度 如果量子计算机 成为现实 已有的加密系统将面临崩溃 尽管量子计算涉及到许多令人着迷的物理学 知识 已经超出了仅仅是计算速度快的世俗见解 但反对者认为 在可以预见的未来 实现大规模的 方 粮等 量子计算机 量子算法与物理实现 量子计算是一个不可能的梦想 法国 大学的 认为 量 子计算依赖在具有多个连续自由度的量子系统内 处理信息 这个概念的实际实现要求对多粒子 波函数的所有 个独立概率幅的完全控制 其中 的实际位数由两部分构成 一是超越 传统计算机所需存储的最大位数 二是纠错所需的 大量的量子比特位 运用专门设计的纠错码 每个 量子比特可容忍的噪声水平估计为 若没有 纠错 噪声水平要达到惊人的 量级 综合考 虑 需要 位 从实用的观点讨论了量子计算的原 理 认为高精度地操作一个 连续自由 度的多粒子物理系统 以实现量子计算的功能 需 要满足下列要求 必须能够对每个量子比特初始化 精度达 到 必须能够以相同的精度测量每一个量子比 特 必须具有通用的量子门 即能够通过系统 波函数的酉变换 将系统的任意态转换为所选的目 标态 除了量子门施加的变换以外 系统的任何 演化都必须避免 研究证明 在 的温度下 的磁场能 够使电子自旋极化向下 实现量子位的初始化 但 在 的磁场下 将会引起系统波函数的非期望演 化 而量子位的测量是通过基于自旋轨道或者与 环境的交换作用 这将难以满足要求 此外 对 量子位进行酉变换 要保证每个量子位不受其他量 子位操作的影响 综上所述 高精度操作一个具有连续自由度的 多粒子物理系统 完全控制 个幅值 是不可能的 一件事情 认为 在可预见的未来 不会 建造出可工作的量子计算装置 美梦还是噩梦 理想量子计算机的基本单元是具有两个相互 作用的量子比特的逻辑门 一个控制位 一个目标 位 如果控制位为 目标位不发生任何变化 如 果控制位为 目标位实现既定的变换 量子力学 允许存在其他操作 如果控制位处于 和 的叠加 态时 逻辑门的输出处于纠缠态 即控制位与目标 位处于不可分割的状态 类似于 佯谬中的一 对粒子 输入位的叠加和输出位的纠缠 是区分于 经典逻辑门的基本特征 在理论上 它打开了一个 更为广泛的计算范畴 用于检测量子理论观点的实验 最近已用于研 究量子逻辑门的操作 尽管操作一个简单的量子 逻辑门并无基本困难 但考虑一个需要大量逻辑门 联合的大型计算机的操作时 情况就不一样了 机 器不得不牵涉到大量经典路径量子干涉产生的量 子态叠加 这将需要一个与外部世界完全隔离的 机器 事实上 量子相干性对于坏境相当敏感 一 个松弛事件对处于激发态的量子状态的影响可能 破坏计算所需要的相干性 一个简单的推导可帮我们理解退相干问题的 严重性 如果 表示单个量子比特的弛豫时 间 表示一个逻辑门的操作时间 则 记为 量子计算机的一个衡量参数 为了使计算有合理 的成功概率 必须达到量子比特数与逻辑门操作 数乘积的数量级 在已有的最好的量子光学系统 中 运用 算法分解一个 的数需要对 个量子比特进行 个逻辑门操作 将会大 于 如果分解一个 的数 将达到 数量级 如果 为 那么弛豫时间 将要达到 年 为处理退相干问题 许多方案提出检测并重建 量子相干性 例如使量子比特处于纠缠态 事实 上 多粒子纠缠态的制备尚无成功的先例 即便技 术的发展 使得在未来实验室纠缠态的制备成为现 实 但是任何检测的失误都将引起相干性的遗失 任何操作的失误都会引起其他的错误 可以认为 除非在不可预见的未来 有新的物理学被发现 否 则一旦处理稍微多一点的逻辑门 纠错编码技术的 实现将会变得极其艰难 从这个角度来说 大规模 量子机器 尽管是计算机科学家的梦想 但是将会 成为实验科学家的噩梦 尽管 大规模的量子计算机不够现实 的 认为可以通过制造仅仅包含少数量子 比特的量子计算机 对多粒子的量子自旋系统进行 模拟 以计算和研究该量子系统的行为 但是 反 对者认为 如果仅仅考虑少量的粒子 经典计算机 完全能够胜任这项工作 制造量子计算机完全没有 必要 上述观点充分表明 研制实用的量子计算机的 道路还很漫长 任务还十分艰巨 虽然量子计算的 研究取得很多有益的进展 但量子计算机的物理实 现还十分困难 我们认为 少量量子比特的量子信 息处理机仍然是一个可能的实现的挑战性工作 这类量子计算机 原则上可以作为专用处理机 配 计算机工程与科学 合常规计算机对简单的量子系统进行模拟 研究方向 研制大规模 容错量子计算机的努力聚集了人 类多学科的智慧 在这种智力的结合点上 半导体 物理 结理论 弦理论 任意子以及量子霍尔效应等 知识交叉融合 合力攻克量子计算机研制难题 随着数学和物理学的发展 将会有新的量子算 法被提出 也会有新的物理实现技术被试验 研究方向 量子算法 除了 分类的基于量子 变换 基 于概率幅放大和基于量子物理模拟三类量子算法 外 还有其他种类的量子算法吗 在上述三类量子算法中 也许还有更多的算法 有待发现 研究方向 物理实现 量子拓扑计算 拓扑学研究几何形象在几何元素的连续变形 下保持不变的性质 如果构成 的元素是拓 扑不变的 基于这些 进行运算的结果也具有 拓扑不变性 由此构造的量子计算就很少受到干 扰 这种量子计算机具有内在的抗干扰能力 有文 献估 计 利 用 拓 扑 量 子 计 算 的 差 错 率 可 低 至 当前的问题是 如何找到具有拓扑不变性的物 理系统作为量子计算的数据位 目前理论 上有两种系统候选 一是任意子 系统 称 为拓扑量子计算 一是波函数的量子几何相位 也 叫几何量子计算 目前已知有实验性系统的 核磁共振 离子阱 微腔中的原子 超导约 瑟夫森结 量子点等 都可以实现量子几何相位 几何量子计算尚属一种改良的性质 只是把信 息落在几何相位 应用它对动力细节无关的稳定 性 拓扑量子计算则是建立在全新的计算思路 应 用任意子的交换相位 交换过程的 编辫 程