量子计算机.pptx

量子计算机 早在六七十年代 人们就发现 能耗会导致计算机芯片的发热 影响芯片的集成度 从而限制了计算机的运行速度 Lan dauer最早考虑了这个问题 他考察了能耗的来源 指出 能耗产生于计算过程中的不可逆操作 例如 对两比特的异或操作 因为只有一比特的输出 这一过程损失了一个自由度 因此是不可逆的 按照热力学 必然会产生一定的热量 经典计算机模型 图灵机 经典计算机实际上就是一个通用图灵机 通用图灵机是计算机的抽象数学模型 它由两部分构成 具有无限多个存储单元的记录带 每个存储单元内容的变化是有限的 通常用二进制的 0 和 1 来表示 一个具有有限状态的读写头 每步操作中读写头可以在记录带上左移或右移一格或不动 图灵机在操作中 读写头根据其内态和当前存储单元的内容 按既定的规则 改变其状态和存储单元的内容 并决定下一步读写头的移动方向 经典计算机模型 图灵机 上述图灵机的模型是不可逆的 例如 对图灵机操作 写存储单元 左移一格 其逆就变成了 左移一格 写存储单元 该逆操作不再是一个有效的图灵机操作 摩尔定律 传统计算机的缺陷 不可逆运算造成自由度损失 不可避免地产生热量损耗 能耗问题计算机芯片的布线密度很大时 根据海森堡不确定性关系 电子位置的不确定量很小时 动量的不确定量就会很大 电子不再被束缚 会有量子干涉效应 这种效应甚至会破坏芯片的功能 摩尔定律的极限 传统计算机的缺陷 按照Landauer的观点 信息是一物理实体 计算是一物理过程 他证明一个不可逆的计算机 目前的计算机均是经典计算机 它们是不可逆的 在完成布尔逻辑运算时 一个bit操作所需最小能量为E kTln2 k是Boltzmann常量 T是系统的热力学温度 按此估计 在室温下花费1W功率 每秒可完成3 5 10 个bit操作 在高集成度下 若完成更大量的运算 所耗费的功会使芯片材料有可能出现局部融化 元件的散热能力有限 元件的集成度有上限 故计算机芯片单位体积的计算速度也就有上限 Hilbert空间中量子态的描述 一个量子系统包含若干粒子 这些粒子按照量子力学的规律运动 则称此系统处于态空间的某种量子态 系统的态空间由多个本征态构成 一般在系统中选取一个方便描述和方便观察的物理量 如能量 作为代表来表征该系统的本征态 以能量为代表的本征态称能量本征态 以能量本征态为例 系统能量最低时的能量称为系统的基态能量 相应的能量本征态称为基态 量子系统的态空间一般用有限维的Hilbert空间 复向量内积空间 表述 即Hilbert空间可以表述量子系统的各种可能的量子态 使用Hilbert空间而不用其它线性空间描述量子计算的原因是具有复向量内积 概率幅描述所需 的完备空间的性质仅为Hilbert空间所具备 量子计算机 量子位 在经典计算机中 信息单元用1个二进制位表示 它处于 0 态或 1 态 而在二进制量子计算机中 信息单元称为 量子位 它除了可以处于 0 态或 1 态外 还可处于一种叠加态 叠加态是 0 态和 1 态的任意线性叠加 它以一定的概率同时存在于 0 态和 1 态之间 量子叠加态通过测量或与其它物体发生相互作用而坍缩到特定的 0 态或者 1 态 量子计算机 量子位 传统 1比特 1bit 0 或者 1 量子 1量子位 1qubit 1 0其中a和b称为概率幅 皆为复数 2和 2分别表示为 为态 1和态 0的概率 且 2 2 1量子位为一双态量子系统 那么 对于两个量子位组成的空间 则叠加态为 00 01 10 11也就是说这个叠加态处于一个2 2维的Hilbert空间 其有四个相互正交的基本态 00 01 10 11 量子寄存器 因此 定义一个N位量子寄存器为N个量子位的有序集合 它的叠加态就有2 N个相互正交的基本态 这就意味着在量子计算机中 处于叠加态的N位量子寄存器中的数是从0到2 N 1的所有的数 它们各以一定的概率同时存在 因此 一个N位量子寄存器就可以保存2 N位二进制数 量子寄存器位数的线性增长使存储空间呈现指数增长 这是量子计算存储单元的基本特征 也是量子计算速度能大大超越经典计算速度的前提 量子计算的原理 从物理观点看 计算机是一个物理系统 计算过程是一个物理过程 量子计算机是一个量子力学系统 量子计算过程就是这个量子力学系统内量子态的演化过程 量子力学中与量子计算关系最为密切的两个特性是叠加态和纠缠态 由于量子态具有量子叠加和量子纠缠的性质 使得量子计算有许多不同于经典计算的特点 量子纠缠 即使相距遥远距离 一个粒子的行为将会影响另一个的状态 当其中一颗被操作 例如量子测量 而状态发生变化 另一颗也会即刻发生相应的状态变化 量子逻辑门对量子位的态进行变换 可以实现某些逻辑功能 变换所起的作用相当于逻辑门所起的作用 在一定的时间间隔内实现逻辑变换的量子装置称为量子逻辑门量子逻辑门在量子计算中是一系列的幺正变换 用算符表示 它将一个态演化为另一个态 十九世纪爱尔兰逻辑学家GeorgeBoole证明了任何复杂的逻辑任务和算术任务都可以通过非 NOT 门 复制 COPY 门和与 AND 门这三种简单操作的组合来完成 量子逻辑门也以三种简单逻辑门为基础 量子门可以没有经典对应 例如 12 0 1 即只将信息位翻转一半 量子逻辑门 量子逻辑门执行的运算可以由幺正矩阵表示 对单比特的操作可以由2 2的矩阵表示 双比特的操作由4 4的矩阵表示阿达马门阿达马门是只对一个一个量子比特进行操作的门 可以用阿达马矩阵表示 量子逻辑门 量子 非 门就是将信息位翻转 将0 演化为1 将一个原子从基态激发到激发态 或者反过来 即0 1 1 0 量子逻辑门 量子 与 门可由三原子堆中的原子之间的相互作用来操作 三个原子依次排列构成原子堆ABA B的基态和激发态之间的能级差是它左右两个A原子的状态的函数 设B处于基态 三原子堆可根据两个A原子的状态表示为11 00 10和01四种情况 若入射光子的能量等于11态的B原子的基态和激发态之间的能级差 则11态的B原子被激发 其他三种情况的B原子仍处于基态 即11 1 00 0 01 0 10 0 这就完成了一次量子与门的操作 量子复制门 量子 复制 门依靠两个原子之间的相互作用 例如由原子A和原子B组成的两个原子对 设B原子都处于基态 而第一对的A原子处于激发态 第二对的A原子处于基态 由于A原子所处的状态不同 对B原子的能级有影响 使这两个原子对中B原子的基态和激发态之间的能级差不同 若入射光子的能量等于第一个原子对中B原子的基态和激发态之间的能级差 B原子吸收光子从基态翻转为激发态 于是A B原子均处于激发态 而第二个原子对中的B原子不被激发 A B原子均处于基态 即1 11 0 00 这就完成了一次复制门操作 量子算法 通过基本的量子幺正变换可以构建一些特定的量子算法 虽然量子计算的输入 变换和输出都与经典计算有很大的不同 但通过合理构造幺正变换 量子门 和测量时机 可以构造出功效高于经典算法的量子算法 许多计算复杂度很高的问题 如NP问题 往往不能有效地在经典计算机上进行计算 由于量子计算的量子并行原理 可以使计算能力比经典计算具有指数级的加速 量子并行计算 在经典计算中 并行性的核心思想是将一个计算任务分配给多个处理器同时运行 要快于使用一个处理器来运行 在理想的情况下 将工作分配给K个处理器就应该使计算时间缩短为原来的1 K 但是Amdahl在1967年发现这种加速性有一个极限 当达到这个极限时 即使再增加处理器的数量 也不能使计算速度有所提高 这是因为在经典计算中并不是所有的运算都可以分给多个处理器来做 因为这些运算是具有连续性的 必须在得到上一个运算的结果之后才能开始下一步的运算 与经典计算中的并行性不同 由于量子计算的特点是数据的可叠加性质和操作的幺正变换本质 从而就决定了量子计算的语义特征是完全意义上的通过一次操作即可改变全部数据的并行计算 量子计算与经典计算的比较 量子计算 同时存储2 N个数字同时赋值2 N个数字同时对状态操纵2 N个数字函数计算通过幺正变换对1000位的大数进行因数分解需几分之一秒 经典计算 同时存储2N个数字同时赋值2N个数字同时对状态操纵2N个数字函数计算通过经典循环方法对1000位的大数进行因数分解需1025年 量子计算机的物理实现 量子计算机实现首先必须解决量子位和量子门组的物理实现问题 迄今已经提出的实现技术有 离子阱技术 核磁共振技术 高Q光学腔技术 等 已经发现用激光束操纵冷冻在其空阱中的离子串有希望实现少数量子位数百个逻辑门操作 1 S Lloyd Science26l 1993 1569 S Lloyd Science 263 1994 695 2 D DiVincenzo Science 270 1995 255 3 R bouer IBMJ Res Dev 5 1961 l83 4 C H Bennett IBMJ Res Dev 6 1973 525 5 P Benioff Phys Rev Lett 48 1982 1581 6 R P Feymann Int J Theor Phys 21 1982 467 7 D Deutsch R Jozsa Proc R Soc LondonA 439 1992 553 8 P W Shor inProcedeeingsofthe35thAnnualSymposiumofFo