量子信息研究进展

第 us卷 第 w期 物 理 学 进 展 ∂ ²¯ qus o‘²qw usss年 ts月 °• ’ Š• ∞≥≥ Œ‘°‹ ≠≥Œ≤≥ ’¦·qousss 文章编号 }tsssΟsxwukussslswΟswszΟux 收稿日期 }usssΟs|Οsx 基金项目 }国家自然科学基金资助kt|{zwsxy oy|{z{suxl 量子信息研究进展 李传锋 郭光灿 k中国科学技术大学量子通信与量子计算开放实验室 o合肥 uvssuyl 摘 要 } 量子信息论是经典信息论与量子力学相结合的新兴交叉学科 ∀本文综述了量子 信息领域的研究进展 ∀即包括了为人们所熟知的量子通信与量子计算领域 o也包括了刚刚兴 起的但却有巨大潜力的量子对策论等领域 ∀本文以介绍量子信息论的基本理论框架为主 o同 时也介绍了量子信息领域的实验研究进展 ∀ 关键词 } 量子信息 ~量子通信 ~量子计算 ~量子对策论 中图分类号 } ’wtv 文献标识码 } „ s 引 言 纵观绝大多数科学领域的发展 o其过程类似盲人摸象 o开始先是领域中的独立现象的 研究 o然后是各种现象之间的联系 o再从千丝万缕的联系中找出这个领域的第一性原理 o 最后在第一性原理的指导下领域不断发展壮大 o又与其它领域交叉产生新的分支 ∀象相 对论那样平地起高楼的毕竟少之又少 ∀ 量子信息论的奠基者们的本意是用量子力学来辅助完成一些经典信息过程 o然而随 着研究的深入 o后来者们逐步把量子力学与经典信息论真正地结合起来 ∀在此过程中 o许 多重大问题k如消相干等l得到解决 o各种新的奇异现象被发现 o这使得研究者们越来越坚 定地相信量子信息论已成为一门独立的学科 ∀这一点可以体现在量子信息领域的两位权 威 …¨ ±±¨ ··和 ⁄¬∂¬±¦¨±½²最近在5自然6杂志上对量子信息所做的总结性上≈t  }从经 典信息到量子信息的推广 o就象从实数到复数的推广一样 ∀ 量子信息除了推广了经典信息中的信源与信道等概念外 o还引入了其特有的量子纠 缠 ∀量子信息可以说是经典信息与量子纠缠的互补 ∀经典信息可以被任意克隆 o但只能 从时空中的一点传到后面的一点 ∀量子纠缠不可以被克隆 o但可以把时空中的任意两点 联系起来k非局域性l ∀ 目前量子信息论中 o量子通信与量子计算领域已经做了广泛深入的研究 o新的领域如 量子对策等也在兴起 o而且其基础理论的研究也不断取得新的进展 ∀相比较而言 o实验进 展要小一些 ∀ t 量子信息基础理论 现有的经典信息以比特作为信息单元 o从物理角度讲 o比特是个两态系统 o它可以制 备为两个可识别状态中的一个 o如是或非 o真或假 os或 t ∀在数字计算机中电容器平板之 间的电压可表示信息比特 o有电荷代表 t o无电荷代表 s ∀量子信息的单元称为量子比特 k ∏´¥¬·l o它是两个逻辑态的叠加态 | Υ > = χs | s > + χt | t > , | χs | u + | χt | u = t (t) 经典比特可以看成量子比特的特例(χs € s或 χt € t) ∀用量子态来表示信息是量子 信息的出发点 o有关信息的所有问题都必须采用量子力学理论来处理 o信息的演变遵从薛 定谔方程 o信息传输就是量子态在量子通道中的传送 o信息处理k计算l是量子态的幺正变 换 o信息提取便是对量子系统实行量子测量 ∀ 在实验中任何两态的量子系统都可以用来制备成量子比特 o常见的有 }光子的正交偏 振态 !电子或原子核的自旋 !原子或量子点的能级 !任何量子系统的空间模式等 ∀ 信息一旦量子化 o量子力学的特性便成为量子信息的物理基础 o其主要的有 } tl 量子纠缠 }Νk大于 tl的量子比特可以处于量子纠缠态 o子系统的局域状态不是相 互独立的 o对一个子系统的测量会获取另外子系统的状态 ∀ ul 量子不可克隆 }量子力学的线性特性禁止对任意量子态实行精确的复制 o量子不 可克隆定理和不确定性质原理构成量子密码术的物理基础 ∀ vl 量子叠加性和相干性 }量子比特可以处在两个本征态的叠加态 o在对量子比特的 操作过程中 o两态的叠加振幅可以相互干涉 o这就是所谓的量子相干性 ∀ 量子相干性在各种量子信息过程中都起着至关重要的作用 o但是 o因为环境的影响 o 量子相干性将不可避免地随时间指数衰减 o这就是消相干 ∀消相干引起量子错误 o量子编 码的目的就是为了纠正或防止这些量子错误 ∀ t qt 量子纠缠 量子纠缠是存在于多子系量子系统中的一种奇妙现象 o即对一个子系统的测量结果 无法独立于对其它子系的测量参数 ∀虽然 o近些年来 o随着量子信息这一新兴领域的蓬勃 发展 o量子纠缠逐渐成为人们的热门话题 o但它并不是什么新生事物 o/纠缠0这一名词的 出现可以追溯到量子力学诞生之初 ∀ 因为量子力学描述的物理实在具有无法消除的随机性 o所以 o从它诞生之日起 o围绕 量子力学的争论就从未间断过 ∀其主要表现为以爱因斯坦为代表的经典物理学家和以玻 尔为代表的哥本哈根学派之间的冲突 ∀其间最著名的事例是在 t|vx 年爱因斯坦同 °²§²¯¶®¼和 • ²¶¨±一起提出的 ∞°• 佯谬≈u  ∀在此文中爱因斯坦等人第一次提出纠缠态 的想法 o其目的意在在承认局域性和实在性的前提下 o量子力学的描述是不完备的 ∀ 玻尔虽然对此做出了相应的回答 o但据玻尔的助手说 o∞°• 的文章对玻尔的影响是极为 重大的 ∀因为玻尔从中看到了 o在考虑多粒子时量子理论会导致纯粹的量子效应 ∀然而 o {sw 物 理 学 进 展 us卷 无论是玻尔还是爱因斯坦 o都没有洞悉他们所讨论的纠缠态的全部含义 o在经过了数十年 的努力之后 o这些含义才逐渐地被发掘出来≈v  ∀ 现在 o量子纠缠态已被应用到量子信息的各个领域 ∀对量子纠缠的深入研究无论是 对于量子信息的基本理论还是对未来潜在的实际应用都将产生深远的影响 ∀ 那么 o什么样的量子态才算是纠缠态呢 ‚对于一个由 Ν个子系统构成的复合系统 o 如果系统的密度矩阵不能写成各个子系统的密度矩阵的直积的线性叠加的形式 o则 o这个 复合系统就是纠缠的 ∀即 } Θ Ξ Ε ι πι Θ(t)ι Ä Θ(u)ι Ä , Ä Θ( Ν)ι (u) 这里 πt ∴s ,并且 Ει πι € t ∀ 目前实验上制备的最完美的纠缠态是利用参量下转换的办法产生的纠缠光子对≈w  ∀ 而最新进展则是在离子阱中制备出了四粒子纠缠态≈x  ∀ t qt qt …¨ ¯¯ 态 两态的两粒子体系的纠缠态中有如下四个 …¨ ¯¯ 基≈y  o它们构成特殊的表象 o | 5 ? > = tu(| ss > ? | tt > ) (v¤) | 7 ? > = tu(| st > ? | ts > ) (v¥) 每个 …¨ ¯¯ 基态都是双粒子体系最大纠缠态 o它们是四维空间中的正交完备基 o可用之对任 意二粒子态¿7  ΑΒ实施正交测量 o称为 …¨ ¯¯ 基测量 ∀ 每个 …¨ ¯¯ 态携带非局域的两比特信息 }°¤µ¬·¼ ¥¬·k宇称比特l }¿5  代表偶宇称 o ¿7 代表奇宇称 o°«¤¶¨ ¥¬·k相位比特l }分别由 n !p来表征 ∀ 对单个两态粒子可实施如下的局域幺正变换k用 °¤∏¯¬矩阵表征l } Ρt = s tt s , Ρu = s − ι ι s Ρv = t ss − t , Ι = t s s t (w) 若对处于 …¨ ¯¯ 基态的体系实施局域操作k如对粒子 „l o则可实现 …¨ ¯¯ 基之间的变换 ∀ Ρv 的作用是使¿s  Α和¿t  Α相对相位倒转 ,导致存储于纠缠态的相位比特倒转 | 5 + > ∴ | 5 − > , | 7 + > ∴ | 7 − > Ρt的作用是使自旋倒转(¿s  Α ∴¿t  Α) ,从而导致宇称比特倒转 | 5 + > ∴ | 7 + > , | 5 − > ∴ | 7 − > Ρt的作用等效于 Ρt Ρv功能 ,它使宇称比特和相位比特同时倒转 | 5 + > ∴ | 7 − > , | 5 − > ∴ | 7 + > 假定 „ ¬¯¦¨ 和 …²¥分别持有处于 …¨ ¯¯ 态的粒子 Α和 Β o那么他们可使用局域幺正变 换使某 …¨ ¯¯ 基变换到任意 …¨ ¯¯ 基 o但这种局域变换无法改变粒子 Α和 Β的状态 o它们的 约化密度算符始终为 ΘΑ € ΘΒ € tu Ι o换句话讲他们所操作的信息无法被局域地读出来 ∀ |sw w期 李传锋等 }量子信息研究进展 若 „ ¬¯¦¨ 和 …²¥对粒子 Α和 Β进行联合操作 o就可以获得 …¨ ¯¯ 态的宇称和相位比特 的信息 ∀ t qt qu 纠缠的度量 我们先来介绍由两子系构成的复合系统的纠缠定量化问题 ∀目前 o人们已广泛使用 四个 …¨ ¯¯ 态作为定量化两子系系统纠缠的标准 o每个 …¨ ¯¯ 态的纠缠度定义为 t o也称为一 个 ¥¨¬·k纠缠比特l ∀所谓纠缠度 o就是指所研究的纠缠态携带纠缠的量的多少 ∀纠缠度 的提出 o为不同的纠缠态之间建立了可比关系 ∀ 在给出具体的纠缠度定义之前 o我们先介绍定量纠缠度所遵从的原则 ∀最近荷兰科 学家 ‹²µ²§¨¦®¬父子将定义纠缠度的假定前提分成三组≈z  ∀k一l明显假定 }¤l非负性 o即 Ε(Θ) ∴s ~¥l当 Θ为非纠缠态 o则 Ε(Θ) € s ~¦l四个 …¨ ¯¯ 态的纠缠度为 t ∀k二l基本假定 } ¤l局域操作下的单调性 }如果仅对纠缠态 Θ的各个子系实施局域的量子操作 o以 πι的概 率获得量子态 Ρι o则纠缠的期望值不能增长 o即 Ε(Θ) ∴ 6 ιπιΕ(Ρι) , 6 ιπι € t ~¥l凸性k信 息抛除下的单调性l }Ε( 6 ιπιΘ) [ 6 ιπιΕ(Θι) , Θ€ 6ι πιΘι ∀k三l渐进性假定 }¤l部分可加 性 }Ε(ȍ ν) € νΕ(Θ) ~¥l连续性 }如果当 ν ψ ] 时  7  ν¿Θν¿7  ν  ψt o则 tν¿Ε( 7  ν) p Ε(Θν)¿ψs ,这里 Θν 为 ν对的联合态 ∀这三组假定是对目前所认识到的纠缠态规律的 一个概括性的总结 o带有相当普遍的意义 ∀ 目前 o对两子系复合系统中纯态的纠缠定量化已经完成 ∀它的纠缠度等于任一子系 统约化密度矩阵的 √²± ‘¨ ∏°¤±±熵≈{  ∀由于两子系复合系统可以进行 ≥¦«°¬§·分解≈|  o 所以两子系统的纠缠度相等 ∀对于混合态的纠缠度量则存在很大困难 ∀ …¨ ±±¨ ··等人提 出了生成纠缠和蒸馏纠缠的概念≈ts  ∀生成纠缠态 ΕΦ(ΘΑΒ)定义为 }通过局域操作和经典 通信过程 o为制备纠缠态 ΘΑΒ所消耗掉 …¨ ¯¯ 态的最小数目 o即如果制备 ΘΑΒ的 ν 份拷贝需 要 κ个 …¨ ¯¯ 态 o则生成纠缠 Ε∆(ΘΑΒl € ¬¯°ν ψ ] κχ°¬± ν ∀类似地 o蒸馏纠缠 Ε∆(ΘΑΒ)定义为 }通过 局域操作和经典通信过程 o可以从 ΘΑΒ中提取出的 …¨ ¯¯ 态的最大数目 o即 o有 ν份 ΘΑΒ的拷 贝 ,可从中提取 κχ个 …¨ ¯¯ 态 o则 Ε∆(ΘΑΒ) € ¬¯°ν ψ ] κχ°¤¬ ν ,生成纠缠和蒸馏纠缠的关系是 ΕΦ  Ε∆ ∀ 除此之外 o还有很多纠缠度的定义 o这里不在赘述 ∀迄今为止 o人们仍未放弃寻找物 理意义鲜明 o同时又简单 !易求解的纠缠度的定义 ∀ 多子系的纠缠态具有很多为两子系纠缠态所不具备的性质 o定量化非常困难 o目前对 其研究尚处于起步阶段 ∀现在 o人们认为多子系纠缠态的纠缠度应由一组数来描述 ∀ …¨ ±±¨ ··等人提出了最小可逆纠缠生成集的概念≈tt  ∀任何一个多子系纠缠态可由这组生 成集以渐进可逆的方式实现 o每个生成元都联系着一个纠缠度 ∀但是 o目前对这个生成集 的构成尚不十分清楚 ∀ t qt qv 纠缠态的判别及其分类 以上给出的纠缠态的定义非常形式化的 ∀一般情况下 o对一个具体的密度矩阵 o人们 stw 物 理 学 进 展 us卷 并不知道它是否具有子系密度矩阵的直积形式的分解 o也就是说 o不知道它是纠缠的还是 非纠缠k可分l的 ∀最先研究这个问题并取得重要进展的是 ° µ¨¨¶o他给出了判别两子系系 统的量子态为可分的必要条件≈tu  }两子系系统可分量子态 ΘΑΒ的部分转置矩阵 ΡΑΒ为半 正定 ∀这里 ΘΑΒ与 ΡΑΒ矩阵元的关系为 : ΡµΛ, νϖ = < µ Α | < ΛΒ | Ρ | νΑ > | ϖΒ > = < µ Α | < ϖΒ | Θ| νΑ > | ΛΒ > = Θµϖ, νΛ (x) 此条件可以作为判别纠缠态的充分条件 ∀即 o如果我们发现一个密度矩阵的部分转置矩 阵带有负的本征值 o我们就可以判定这个量子态为纠缠态 ∀人们将部分转置为负定的情 形简记为 ‘°× o相反 o部分转置为半正定则记为 °°× ∀ ‹²µ²§¨¦®¬等人随后证明了 o°°× 是 u ≅ u和 u ≅ v系统可分态的充分必要条件≈tv  o但若维度大于 u ≅ v o°°× 仅为必要条 件 ∀ 任何一个带有 °°× 特性的两子系复合系统的量子态 o即使生成纠缠不为零 o但蒸馏 纠缠为零 o即 o我们无法通过局域操作和经典通信的手段从中提取出 …¨ ¯¯ 态 ∀ ‹²µ²§¨¦®¬ 将这种态称为 }/束缚纠缠态0≈tw  ∀这直接导致了纠缠态的分类 o一般将束缚纠缠态以外 的纠缠态通称为/可蒸馏的纠缠态0 ∀最新的研究成果表明 o即使是 ‘°× 的纠缠态也存在 束缚纠缠态的情况≈tx  ∀ 由于无法从束缚纠缠态中蒸馏出 …¨ ¯¯ 态 o所以束缚纠缠态不能胜任 …¨ ¯¯ 态在量子通 信中的所扮演的角色 ∀但束缚纠缠态的存在 o提示了自然界更为深刻的一面 o即信息的不 可逆过程 o这很类似于热力学中的熵增加现象 ∀近来 o关于束缚纠缠态的研究逐渐展开 ∀ 人们发现在束缚纠缠态中存在一种/纠缠激活0的有趣现象≈ty  ∀即当两地分享某种可蒸 馏的纠缠态的同时也分享一定量的束缚纠缠态 o在这种情况下 o束缚纠缠态可以起到一定 的/泵浦0作用 o使可蒸馏纠缠态具有更强的隐形传态能力 ∀ t qu 量子不可克隆定理 t qu qt 量子不可克隆定理 t|{u年 o• ²²··¨µ¶和 ∏µ¨®在5自然6杂志上发表了一篇短文中提出这样一个问题 } 是否存在一种物理过程 o实现对一个未知量子态的精确复制 o使得每个复制态与初始量子 态完全相同 ‚该文证明 o量子力学的线性特性禁止这样的复制 o这就是量子不可克隆定理 的最初表述≈tz  ∀ 量子不可克隆定理的证明很简单 ∀以两态量子系统为例 o其基矢选为¿s 和¿t  o设 ¿σ代表此二维空间任意量子态 o量子克隆过程可以表示为 | σ > | Θ > ξ ψ | σ > | σ > Θ∗ σ > ξ (y) 式中右端¿σ ¿σ表示初始模和复制均处于¿σ态 ,¿Θ  ξ 和¿Θ∗ σ  ξ 分别为装置在复 制前后的量子态 ,复制后装置的量子态¿Θ∗ σ  ξ 可能依赖于输入态¿σ ∀假如存在(y)式 的变换 ,那么对基矢¿s 和¿t 应该分别有 | s > | Θ > ξ ψ | s > | s > | Θ∗ s > ξ (z¤) | t > | Θ > ξ ψ | t > | t > | Θ∗ t > ξ (z¥) ttw w期 李传锋等 }量子信息研究进展 现假定¿σ是一个任意的叠加态 o即 | σ > = Α| s > + Β | t > , | Α| u + | Β | u = t ({) 由 z式及量子操作的线性特征 o不难得到在操作后 o¿σ将演变为¿σ ¿Θ  ξ € (Α¿s  n Β¿t  )¿Θ  ξ ψ Α¿s  s  ¿Θ ∗ s  ξ n Β¿t  t  ¿Θ ∗ t  ξ)如果复制机的态¿Θ∗ s  ξ 与¿Θ∗ t  ξ 不恒等 ,那么上式给出的初始模和复制模均于¿s 与¿t 的混合态 ;如果态¿Θ∗ s  ξ 与¿Θ∗ t  ξ 恒等 ,则初始模和复制模将处于纠缠态 Α¿s  s  n Β¿t  t  ∀无论哪种情况 , 初始模和复制模都不可能处于直积态¿σ ¿σ ∀因此如果一个量子复制机能精确复制态 ¿s 和¿t  ,则它不可能复制两态的叠加态¿σ ,此即量子不可克隆定理的内容 ∀ 量子态不可克隆是量子力学的固有特性 o它设置了一个不可逾越的界限 ∀量子不可 克隆定理是量子信息科学的重要理论基础之一 ∀量子信息是以量子态为信息载体k信息 单元l ∀量子态不可精确复制是量子密码术的重要前提 o它确保了量子密码的安全性 o使 得窃听者不可能采取克隆技术来获得合法用户的信息 ∀鉴于这个定理的重要性 o近年来 人们对它作了进一步的研究 o揭示出更丰富的物理内涵 ∀ 在 • ϝ的证明中 o假设了输入态是完全未知的 ∀但在实际情况中 o我们往往知道输 入态属于一个确定的态集合 ∀例如在基于非正交态的量子密码术中 o输入态是两个非正 交态的其中之一 ∀ • ϝ的证明基于量子叠加原理 o该证明行之有效至少需要 v种可能的 输入态 o如上面的¿s  ,¿t 及 Α¿s  n Β¿t  o因此它没有排除克隆两个量子态的可能 性 ∀之后人们推广了量子不可克隆定理 o使之适用于两态情况 o指出如果克隆过程可以表 示为一幺正演化 o则幺正性要求两个态可以被相同的物理过程克隆 o当且仅当它们相互正 交 o亦即非正交态不可以克隆≈t{  ∀该结果在量子密码术中有重要应用 o我们知道 o一个简 单的量子密码就是随机地传送两个非正交的量子态 o正因为非正交态不可克隆 o所以 窃听者无法窃取信息 ∀ 适用于两态的量子不可克隆定理后来被进一步推广到混合态情况 o并证明了一个更 强的定理 o文献中称为量子不可播送定理≈t|  ∀设系统 Α处于两个可能的混合态{ Θs , Θt} 中的一个 , Θs , Θt为密度算符 o如果要将系统 Α的态克隆到系统 Β上 o则演化后系统 ΑΒ 的态应为 Θσ Θσ ,其中 σ€ s ,t ∀但量子播送的要求更弱些 o记演化后系统 ΑΒ的态为 Θ∗ σ o 量子播送只要求 ΤρΑ(Θ∗ σ) = Θσ , ΤρΒ(Θ∗ σ) = Θ∗ σ (|) 其中 ΤρΑ , ΤρΒ分别表示对系统 Α , Β求迹 ∀因此量子播送只要求系统 ΑΒ的约化态与演 化前系统 Α的态一致 ∀量子不可播送定理指出 o两个混合态经过幺正演化可以被量子播 送 o当且仅当它们相互对易 ∀该定理是量子不可克隆定理的强化 o当 Θs , Θt 表示纯态时 o 显然量子不可播送定理回到两态的量子不可克隆定理 ∀近来不可克隆定理又被推广到纠 缠态情况≈us  ∀ ²µ甚至指出复合系统的正交态不可以被克隆≈ut  o当然 o这种正交态的不 可克隆定理需要狭义相对论做基础 ∀ 量子不可克隆定理断言 o非正交态不可以克隆 o但它并没有排除非精确克隆即复制量 子态的可能性 ∀目前主要有两种克隆机 }普适克隆机和概率克隆机 ∀ utw 物 理 学 进 展 us卷 t qu qu 普适量子克隆机 文献中常用态的保真度来表征量子克隆机的性能 ∀设输入态为¿7 s  ,输入出态为 Θ,则保真度 Φ定义为 Φ = < 7 s | Θ| 7 s > (ts) 普适量子克隆机k…∏½¨ ®p ‹¬¯¯ µ¨¼克隆机l对于任意的量子态都适用 ∀其性能与输入态无 关 o两个输出态完全相同 o但不等于输入态 ∀这表明输入态在克隆过程中不可避免地遭到 破坏 o选择一组最佳参数可使得这种破坏达到最小程度 ∀业已证明 o对二维系统 o输入 !输 出态之间的保真度最高可以达到 xry≈uu  ∀ 以上考虑的是一到二的克隆机 ∀更一般的量子克隆机具有 Ν个相同的输入态和 Μ 个( ́ Ν)相同的输出态 ∀对于 Ν到 Μ的普适量子克隆机 o其保真度最高可达到≈uv ouw  ΦΝ , Μ = Μ( Ν + t) + ΝΜ( Ν + u) (tt) 显然 o当 Ν € t , Μ€ u时 o上式给出了单输入双输出的量子复制机的最佳保真度 xry ∀ …∏½¨ ®等人给出了普适克隆机的逻辑网络≈ux  o我们已经用光学的办法在实验上实现 了普适量子克隆机≈uy  ∀ t qu qv 概率量子克隆机 概率量子克隆机k段 p郭克隆机l≈uz ou{ 适用于线性无关的态集 ∀它把幺正演化和测 量过程相结合 o以确定的大于零的概率产生输出 o而且输出态一定是输入态的精确复制 态 ∀为构造概率量子克隆机 o测量和合适的幺正演化都是不可缺的 ∀如果只有幺正演化 o 显然非正交态不可以精确克隆 ~另一方面 o如果只有测量 o当输入态为非正交态时 o机器不 可能对其中任意一个输入态都以大于零的概率产生输出 o且输出态还应是输入态的精确 复制态 ∀因此构造概率量子克隆机的关键是要设计出合适的幺正演化并要联系测量过 程≈u|  ∀ 概率克隆机成功产生输出的概率 o定义为克隆效率 o它决定了该机器的性能 ∀显然 o 对于确定的输入态集合 o我们希望设计一种机器 o使得它具有最大效率 o且该效率不依赖 于具体的输入态 o此时该机器称为最佳概率量子克隆机 ∀业已证明 o如要输入态属于集合 {¿7 s  ¿7 t  } o则概率量子克隆机的最高效率为 Γ°¤¬ = tt + < 7 s | 7 t > (tu) 显然只有对于正交输入态 o该效率才能达到 t o这一点保证了基于传送两个非正交态的量 子密钥体系的安全性 ∀ t qv 消相干与量子编码 现在利用计算机进行复杂运算时 o我们不再为结果的可靠性担心 ∀但是在计算机概 念刚提出时 o曾经有人提出如下反驳 }在计算机这样一个复杂系统中 o噪声是不可避免的 o 只要噪声使得计算机中任一部件发生一次错误 o最后的运算结果都会变得面目全非 o因 vtw w期 李传锋等 }量子信息研究进展 此 o利用计算机进行复杂运算是不可能的 ∀这一困难后来是怎样克服呢 ‚编码在这过程 中起了关键性的作用 ∀什么是编码 ‚编码 o更准确地说 o信道编码 o指的是 o通过引入冗余 信息 o使得在一部分比特发生错误的情况下 o仍有可能按照一定的规则纠正这些错误 o以 实现无失真地传送和处理信息 ∀举一个最简的重复码为例 o我们可以将信号 s编码为 sss o信号 t编码为 ttt o这样如果最多只有一个比特发生错误 o譬如 osss变成了 sst o我 们可以按照少数服从多数的原则 o找出错误的比特k第三比特l o并纠正该错误 ∀ 以上是经典编码的基本概念 o为什么要引进量子编码呢 ‚这与量子信息论特别是量 子计算机的发展有关 ∀量子信息论中 o信息的载体为量子比特 ∀量子比特可以处于 s ot 两个本征态的任意叠加态 o而且在对量子比特的操作过程中 o两态的叠加振幅可以相互干 涉 o这就是所谓的量子相干性 o已经发现 o在量子信息论的各个领域 o量子相干性都起着本 质性的作用 o可以说 o量子信息论的所有优越性均为自于量子相干性 o但由于环境的影响 o 量子相干性将不可避免地随时间指数衰减 o这就是困扰整个量子信息论的消相干问 题≈vs  ∀消相干引起量子错误 o量子编码的目的就是为了纠正或防止这些量子错误 ∀虽然 量子编码和经典编码的基本想法类似 o即要以合适的方式引进信息冗余 o以提高信息的抗 干扰能力 o但量子码可不是经典码的简单推广 o在量子情况下 o编码存在着一些基本困难 o 表现在如下 v个方面 ∀ tl经典编码中 o为引入信息冗余 o需要将单比特态复制到多比特上去 o但在量子力学 中 o量子态不可克隆定理禁止态的复制 ∀ ul经典编码在纠错时 o需要进行测量 o以确定错误图样 o在量子情况下 o测量会引起态 坍缩 o从而破坏量子相干性 ∀ vl经典码中的错误只有一种 o即 s ot之间的跃迁 ∀而量子错误的自由度要大得多 ∀ 对于一个确定的输入态 o其输出态可以是二维空间中的任意态 ∀因此 o量子错误的种类为 连续统 ∀ 因为这些原因 o量子纠错比经典纠错困难得多 o事实上 o直到 t||x年底至 t||y年 o ≥«²µ≈vt 和 ≥·¨¤±¨ ≈vu 才独立地提出了最初的两个量子纠错编码方案 o量子纠错码通过一些 巧妙的措施 o克服了上面的 v个困难 o具体为 tl为了不违背量子态不可克隆定理 o量子编码时 o单比特态不是被复制为多比特的直 积态 o而是编码为一较复杂的纠缠态 ∀对于纯态而言 o纠缠态即指不能表示为直积形式的 态 ∀通过编码为纠缠态 o既引进了信息冗余 o又没有违背量子力学的原理 ∀ ul量子纠错在确定错误图样时 o只进行部分测量 o通过编码 o可以使得不同的量子错 误对应于不同的正交空间 o部分的量子测量k即只对一些附加量子比特 o而不是对全部比 特进行测量l使得态投影到某一正交空间 o在此正交空间 o信息位之间的量子相干性仍被 保持 o同时测量的结果又给出量子错误图样 ∀ vl量子错误的种类虽然为连续统 o但人们发现 o它可以表示为 v种基本量子错误k对 应于 v个 °¤∏¯¬矩阵l的线性组合 ∀只要纠正了这 v种基本量子错 o所有的量子错误都将 得到纠正 ∀ 自从发现了最初的两个量子编码方案 o各种更高效的量子码已被相继提出 ∀下面我 们介绍几种最重要的量子编码方案 ∀ wtw 物 理 学 进 展 us卷 t qv qt 量子编码方案 ktl量子纠错码 ∀ ≥«²µ≈vt 的第一个纠错方案为量子重复码 o它利用 |比特编码 t比 特信息 o可以纠正 t位错 o≥«²µ的方案简单 o而且与经典重复码有较直接的类比 o但它的 效率不高 ∀事实上 o≥·¨¤±¨ ≈vu 的编码方案对后来的量子纠错码影响更大 o在该方案中 o ≥·¨¤±¨ 提出了互补基的概念 o给出了量子纠错一些一般性的描述 o并具体构造了一个利用 z比特来编码 t比特纠 t位错的量子码 ∀紧接着 o≤¤¯§¨µ¥¤±®和 ≥«²µ≈vv 以及 ≥·¨¤±¨ ≈vw 提 出了一个从经典纠错码构造量子纠错码的方法 o该方法建立在群论语言之上 o纠 t位错的 最佳k效率最高l量子码也由两个小组独立地发现 o该方案利用 x比特来编码 t比特 o纠多 位错的量子码情况更复杂 o迄今为止 o只发现一些简单的纠多位错的量子码 ∀现有的各种 量子纠错码 o都可以被统一在群论框架之下 o该描述已由 Š²··¨¶°¤±≈vx 和 ≤¤¯§¨µ¥¤±® 等≈vy 给出 o但利用现有理论去构造新的量子纠错码 o仍然是一件非常艰巨的工作 o为了寻 求更高效的量子码 o人们往往需要逐步地摸索 ∀ 量子纠错码适用于独立消相干 o其优点为适用范围广 o缺点为效率不高 ∀ kul量子防错码 ∀量子防错码≈vz ov{ 利用了量子  ±¨²效应k看门狗效应l ∀量子  ±¨² 效应≈v| 是指 }如果以很高的频率对一个系统进行测量 o则系统不会发生演化 ∀那么 o如果 以很高的频率来观察一个量子系统是否发生消相干 o根据  ±¨²效应 o系统将总是不发生 消相干 ∀量子防错码的效率高 o但其缺点是测量的频率要求很高 o而且噪声的增长不能太 快 ∀ kvl量子避错码 ∀量子避错码基于消相干中的集体效应 ∀ °¤¯ °¤等≈ws 和我们课题 组≈wt 先后考察了量子比特消相干过程中的集体效应 o发现集体消相干和独立消相干具有 本质的不同 o最突出的一点是 o对于集体消相干 o存在相干保持态 ∀相干保持态是指一类 能在噪声环境下保持稳定的态 ∀量子避错码即是将一个任意输入态编码为一个较高维空 间的相干保持态 ∀对于实际中很重要的一类量子噪声 o我们设计了一个用二比特编码一 比特信息的量子避错码方案≈wu  o意大利的量子信息小组将该方案推广到更普遍的噪声模 型≈wv  o但相应地要求用四比特来编码一比特量子信息 ∀量子避错码的优点为效率很高 o 而且不需要进行测量和纠错操作 o其缺点为只能适用于克服集体消相干 ∀ 关于量子编码的实验进展 o目前已经在核磁共振中演示了纠相位错的三比特≈ww 和两 比特≈wx 纠错码 ∀ t qv qu 量子编码定理 量子编码定量研究的目标是要寻找经典 ≥«¤±±²±定理的量子对应 ∀ ≥«¤±±²±信源编 码定理确定了任一信源给出的信息的最大压缩率 o信道编码定理确定了信息在有噪信道 中无失真地传输的最大速率 o亦即信道容量 o≥«¤±±²±定理奠定了整个经典信息论的基 础 ∀对于量子信息论 o是否存在类似的定理 ‚能否引进信道容量的概念 ‚如何发展有效 的算法去计算量子信道容量 ‚这些问题显然都是量子信息论中的基本问题 ∀ 早在 t||v年 o≥¦«∏°¤¦«¨µ就证明了一个比较初步的量子信源编码定理≈wy  o该证明后 来经 ²½¶¤和 ‹²¯ √¨²的工作得到进一步的简化和推广 ∀量子信源以概率 πι 发送密度算 xtw w期 李传锋等 }量子信息研究进展 符为 Θι的量子态 , Θ€ 6 ι πιΘι表示信源的总密度算符 ∀量子信源编码定理要回答的是 o对 于这样的量子系统 o其信息最少可以用多少量子比特表征出来 ‚ ≥¦«∏°¤¦«¨µ的定理表 明 o如果所有 Θι均限制为纯态 o以 u为底的 ∂ ²±Ο‘¨ ∏°¤±±熵 Σ(Θ) € p τρ( Θ¯²ªuΘl确定了 所需的最小量子比特数 ∀熵是量子力学中的重要概念 ∀ ≥¦«∏°¤¦«¨µ的定理揭示出 o量子 力学和信息论这两个看起来互不相关的学科 o实际上却存在着内在的联系 ∀ ≥¦«∏°¤¦«¨µ 的定理后来经 ‹²¯ √¨²推广到 Θι 为混合态的情况 o此时相对 ∂ ²±Ο‘¨ ∏°¤±±熵 Σ(Θ) p 6 ι πιΣ(Θι)确定了所需的最小量子比特数 ∀ 在经典信息中 o信道容量只需要一个量即可表征 ∀但在量子信息中 o根据不同的辅助 资源和通信用途 o量子信道有几种不同的容量≈t  ∀包括 } tl 经典容量 oΧo等于通过此量子信道可靠地传送经典比特的最大速率 ∀ ul 量子容量 oΘ o指通过信道完全可靠地传送量子比特的最大速率 ∀ vl 经典辅助量子容量 oΘu o定义为在通信双方无限制的经典通信辅助下 o通过信道 完全可靠地传送量子比特的最大速率 ∀ wl 纠缠辅助经典容量 oΧΕ o定义为在通信双方拥有无限制的事先分享的量子纠缠的 辅助下 o通过此信道可靠地传送经典比特的最大速率 ∀ 对于所有已知的量子信道 o这些容量之间满足关系 Θ [ Θu [ Χ [ ΧΕ o这些容量各自 随着信道参数的变化而独立变化 o但是计算起来比较困难 ∀ u 量子通信 量子通信是量子信息中研究较早的领域 o比较典型的通信方式有 }量子密集编码≈wz  o 用量子信道传送经典比特 ~量子隐形传态≈w{  o用经典辅助的办法传送量子态 ∀量子通信 中还有一个很重要的分支是量子密码 o即信息的保密传送 ∀ u qt 量子密集编码 假定 „ ¬¯¦¨ 与 …²¥早已建立量子通道 o他们共享 …¨ ¯¯ 态¿5 n  ΑΒ o„ ¬¯¦¨ 对她的纠缠粒 子 Α可以施加四种可能的幺正变换{ Ι , Ρt , Ρu , Ρv} ∀她选择其中之一进行操作 o其作用是 编码进两个比特经典信息 ∀这个操作实际上是将 „ p …量子通道¿5 n  ΑΒ变换成下列四 种正交态中一个上 } | 5 + > ΑΒ ,(偶宇称 ,正相位) ,(s ,s) | 7 + > ΑΒ ,(奇宇称 ,正相位) ,(t ,s) | 7 − > ΑΒ ,(奇宇称 ,负相位) ,(t ,t) | 5 − > ΑΒ ,(偶宇称 ,负相位) ,(s ,t) 现在 „ ¬¯¦¨ 将她的粒子 Α发送给 …²¥o…²¥对两个粒子实行 …¨ ¯¯ 基测量k联合测量l o测量 结果可使 …²¥确认 „ ¬¯¦¨ 所做的变换 o于是他获得由 „ ¬¯¦¨ 传送给他们两个比特的经典信 息 ∀因此 o„ ¬¯¦¨ 仅送给 …²¥一个粒子 o便能成功地传送了两个比特的经典信息 o这就是所 谓的/密集编码0≈wx  ∀ ytw 物 理 学 进 展 us卷 量子密集编码有如下优点 } tl保密性强 ∀所传的量子比特 ΘΑ € tu Ι Α o不携带任何信息 o窃听者即使载获此量子 比特 o也无法破译 ∀所有信息均编制在 „Ο…之间关联上 o局域测量无法提取 ∀ ul量子通道可以在使用之前早就制备好 o在紧急时使用 o就可以更有效地传送信息 ∀ 量子密集编码已由 Œ±±¶¥µ∏¦®小组完成≈w|  o由于 …¨ ¯¯ 基识别的困难 o他们只实现了四 种操作中的三种 o即传送了 t qx{比特 ∀ u qu 量子隐形传态 在量子密集编码中 o量子纠缠可用来加速经典信息的传输 ∀那么 o我们可否使用经典 信息来实现量子信息传输 ‚ 现假定 „ ¬¯¦¨ 和 …²¥之间有 ∞°• 对¿5 n  ΑΒ o„ ¬¯¦¨ 有一粒子 Χ处于未知量子态 ¿7  Χ∀ „ ¬¯¦¨ 对 Χ和她拥有的 ∞°• 粒子 Α实施 …¨ ¯¯ 基测量 o这个测量将随机地把 Α  Χ投影到四个态¿5 ?  ΧΑ ,¿7 ?  ΧΑ当中的一个 ∀然后 „ ¬¯¦¨ 将测量结果k两比特的经 典信息l告诉 …²¥o后者按照这个信息对他所拥有的粒子 Β施加相应的操作k四种 °¤∏¯¬操 作之一l o这个作用可以使 Β的粒子变换到¿7  χ的精确复制态上 o这便实现了量子隐形 传态≈ww  ∀ „ ¬¯¦¨ 的测量结果与 …²¥应当实施的相应局域操作之间的对应关系如下 } | 5 + > ΧΑ ψ ΙΒ , | 7 + > ΧΑ ψ Ρ( Β)t | 7 − > ΧΑ ψ Ρ( Β)u , | 5 − > ΧΑ ψ Ρ( Β)v (tv) 量子隐形传态的特点是 o量子态¿7  Χ被传送给¿7  Β(从 Χψ Β) ,但粒子 Χ本身 不被传送 ∀应特别指出 tl事先 o粒子 Χ与 Β不纠缠 o„ ¬¯¦¨ 测量之后 o在 Α与 Χ之间建立了关联 ∀ ul„ ¬¯¦¨ 的测量输出是完全随机 o故这个测量无法获得任何关于 7  Χ的信息 ∀ vl从 „ ¬¯¦¨ 传送给 …²¥的两比特经典信息 o也给不出¿7  Χ信息 ∀ wl Α与 Β共享的 ∞°• 粒子对也给不出¿7  Χ信息 o它们早就存在了 ∀ xl这过程不是克隆¿7  Χ o因为在 „ ¬¯¦¨ 测量之后 o¿7  Χ已被破坏掉 ∀ yl¿7  Χ被分解为经典信息和量子信息两部分 o只有两者共同组合才能重新构造出 来 ∀ 下面用量子力学来描述上述的量子隐形传态过程 ∀设 | 7 > Χ = α | s > + β | t > , | α | u + | β | u = t (tw) 初始时 o粒子 Χ和 ∞°• 粒子对 „Ο…构成的整个系统 o其量子态为 | 7 > Χ  | 5 + > ΑΒ = tu | 5 + > ΧΑ | 7 > Β + tu | 7 + > ΧΑΡt | 7 > Β + tu | 7 − > ΧΑ(− ιΡu) | 7 > Β + tu | 5 − > ΧΑΡv | 7 > Β , (tx) 式中为¿5 ?  ΧΑ ,¿7 ?  ΧΑ粒子 Χ和 Α的 …¨ ¯¯ 基态 ∀ „ ¬¯¦¨ 对粒子 Χ和 Α的实施 …¨ ¯¯ 基测量 o会使 …²¥粒子 Β投影到相应的纯态上 o这个 纯态与¿7  Β之间为幺正变换 ∀ …²¥可按照 „ ¬¯¦¨ 经典通道传送来关于她测到那个 …¨ ¯¯ ztw w期 李传锋等 }量子信息研究进展 基态的信息 o采用式ktvl相应的幺正变换对粒子 Β实施操作 o粒子 Β便处式ktwl的量子 态上 ∀ 目前已有四个小组完成了量子隐形传态实验 ∀Œ±±¶¥µ∏¦®小组用了与密集编码相同 的装置实现了从一个光子的态传递到另一个光子上≈xs  ∀ • ²°¨小组则采用了一个更为简 单的办法 o把量子态从纠缠光子对中的一个光子传递到另一个光子上≈xt  ∀最近 ≤Œ× 小 组则根据 ∂¤¬§°¤±的方案≈xu 完成了连续变量的隐形传态≈xv  ∀还有一个实验是在 ‘ • k核磁共振l中实现的≈xw  o但是传递的距离很短 o把态从样品分子中的一个原子传递到另 一个原子上 ∀ u qv 量子密码术 现代保密通信的原理图如下 } „ ¬¯¦¨ 采用密钥 Κk随机数l将她要发送给 …²¥的明文通过某种加密规则变换成密文 o 然后经由公开的经典信息通道传送给 …²¥o后者采用密钥 Κχ通过适当的解密规则将密文 变换成为明文 ∀这个过程如果能够有效地防止任何非法用户的窃听 o那就是安全的保密 通信 ∀ 按照密钥 Κ和 Κχ是否相同 o密钥系统可分为对称密码k Κ € Κχl和非对称密码k Κ Ξ Κχl ∀数学上证明存在有不可破译的对称密钥 o即 ∂ µ¨±¤°密码或一次性便笺式密码 o它 要求密钥应与明文一样长 o而且仅能使用一次 ∀这种体系需要用户双方拥有庞大的相同 密码k随机数l o因此密钥的传送 !保管等都极不安全 o不宜广泛使用 ∀目前广泛用于网络 ! 金融行业的是非对称密码 o它是一种公开密钥 o加密和解密法则 !加密的密钥 Κ均是公开 的 o只是解密的密钥 Κχ不公开 o只有接收者 …²¥本人知道 ∀这种密钥的安全性基于大数 因子分解这样一类不易计算的单向性函数 ∀数学上虽没能严格证明这种密钥不可破译 o 但现有经典计算机几乎无法完成这种计算 ∀ ≥«²µ量子算法证明 o采用量子计算机可以轻而易举地破译这种公开密钥体系 ∀这就 对现有保密通信提出了严峻挑战 ∀解决这个问题的有效途径是量子密码术 ∀它采用量子 态作为信息载体 o经由量子通道传送 o在合法用户之间建立共享的密钥k经典随机数l ∀ 量子密码的安全性由量子力学原理所保证 ∀所谓绝对安全性是指窃听者智商极高 o 采用最高明的窃听策略 o使用一切可能的先进仪器 o在这些条件下 o密钥仍然是安全的 ∀ 窃听者的基本策略有两类 }一是通过对携带着经典信息的量子态进行测量 o从其测量的结 果来获取所需的信息 ∀但是量子力学的基本原理告诉我们 o对量子态的测量会干扰量子 {tw 物 理 学 进 展 us卷 态本身 o因此 o这种窃听方式必然会留下痕迹而被合法用户所发现 ∀二是避开直接量子测 量而采用量子复制机来复制传送信息的量子态 o窃听者将原量子态传送给 …²¥o而留下复 制的量子态进行测量以窃取信息 o这样就不会留下任何会被发现的痕迹 ∀但是量子不可 克隆定理确保窃听者不会成功 o任何物理上可行的量子复制机都不可能克隆出与输入量 子态完全一样的量子态来 ∀因此 o量子密码术原则上可以提供不可破译 !不可窃听的保密 通信体系 ∀ 首先想到将量子力学用于密码术的是美国的 • ¬¨¶±¨ µo他在 t|zs年提出用共轭编码 制造不可伪造的/银行支票0等 ∀因为他的想法太新奇 o被拒绝刊登 o直到 t|{v年才 得以在会议录上发表≈xx  ∀ 目前 o量子密码的方案主要有四种 } tl 基于两种共轭基的四态方案 o其代表为 ……{w协议≈xy  ~ ul 基于两个非正交态的两态方案 o如 …|u协议≈xz  ~ vl 基于 ∞°• 佯谬的 ∞°• 对方案 o由 ∞®¨ µ·于 t||t年提出 o称为 ∞°• 协议或 ∞|t协 议≈x{  ~ wl 基于正交态的密钥分配方案≈ut ox| oys  o其基础为正交态的不可克隆定理≈ut  ∀ 显然 o这里所说的量子密码k量子密钥分配l实际上是量子辅助的经典密码 ∀最近 o我 们建立了真正意义上的量子密码体系≈yt  ∀ 量子密钥分配k± Ž⁄l的第一个演示性实验由 …¨ ±±¨ ··等人完成≈yu  ∀目前的实验方 向有二 }光纤中的 ± Ž⁄和自由空间的 ± Ž⁄∀光纤中的 ± Ž⁄实验已经逐渐走向成 熟≈yv ∗ yy  o目前传输距离已经达到 w{ 公里≈yy  ∀自由空间中的 ± Ž⁄也不断取得突 破≈yz ∗ y|  o现在达到的传输距离为 t qx公里≈y|  o而且是在白天进行的实验 ∀前面的实验 都是基于 ……{w或 …|u协议 o最近 ∞|t协议的 ± Ž⁄也已取得重大进展≈zs ∗ zu  ∀ 关于量子保密通信 o还有许多问题需要解决 ∀其中最典型和最重要的是量子比特承 诺问题 ∀量子比特承诺是最基础的量子保密通信协议 o如果比特承诺是可行的 o则可利用 它来实现各种各样的保密通信协议 o如远程硬币投掷 !保密量子计算等等 ∀ 问题本身很简单 o比如 Α向 Β宣称自己有特异功能 o如果 Β要投掷一枚硬币 oΑ能 预测出硬币是/正面0还是/反面0朝上 ∀两个人需要用比特承诺的办法来检验 Α是否说 谎 ∀一个很实际的办法是 }Α把他的预测写在一张纸上 o如果/正面0朝上 o则写 s o/反面0 朝上 o则写 t ∀然后把纸放到一个密码箱里 ∀ Α把密码箱给 Β o但钥匙必须自己保留k否 则 Β可以根据纸上的结果来投掷硬币l ∀等 Β掷完硬币后 oΑ再打开密码箱检验他是否 预测成功 ∀然而这个办法却是不安全的 o因为 Β可以用透视等等办法看到纸上的内容 ∀ 用量子力学的办法能否实现比特承诺呢 ‚ 开始时 o许多量子比特承诺的方案被提出 ∀但是后来 ¤¼¨ µ¶≈zv  o²和 ≤«¤∏≈zw 独立 证明所有以前的比特承诺方案都是有漏洞的 o即存在 ∞°• 攻击 ∀ Α可以利用量子纠缠的 办法任意地改变 s和 tk此结论被称为 ¤¼¨ µ¶Ο²Ο≤«¤∏定理l ∀此后 o量子信息界对量子 比特承诺比较悲观 ∀但是 ¤¼ µ¨¶Ο²Ο≤«¤∏定理并没有表明任意的量子比特方案都是不 安全的 o现在关于量子比特承诺是否安全的争论仍在继续 ∀ |tw w期 李传锋等 }量子信息研究进展 v 量子计算 量子比特可以制备在两个逻辑态 s和 t的相干叠加态 o换句话讲 o它可以同时存储 s 和 t ∀考虑一个 Ν个物理比特的存储器 o若它是经典存储器 o则它只能存储 u Ν个可能的 数当中的任一个 o若它是量子存储器 o则它可以同时存储 u Ν个数 o而且随着 Ν的增加 o其 存储量子信息的能力将指数上升 o例如 o一个 uxs量子比特的存储器k由 uxs个原子构成l 可能存储的数目比现有已知的宇宙中的全部原子数目还要多 ∀ 由于数学操作可以同时对存储器中全部的数进行 o因此 o量子计算机在实施一次的计 算中可以同时对 u Ν个输入数进行数学运算 ∀其效果相当于经典计算机要重复实施 u Ν 次操作 o或者采用 u Ν个不同的处理器实行并行操作 ∀可见 o量子计算机可以节省大量的 运算资源k如时间 !记忆单元等l ∀ 量子加速表现最明显的是大数因子分解问题 o其量子算法k≥«²µ算法l≈zx ozy 是经典算 法的指数加速 ∀另外存在指数加速的还有 ⁄ύ算法≈zz 和多体量子体系模拟≈z{ 等 ∀相对 而言 o有大量的问题存在方根加速 o即解决此类问题的量子算法所需时间正比于经典算法 所需时间的平方根 o其代表是搜索问题≈z| o{s  ∀而对于其它问题则没有量子加速 o这包括 迭代问题≈{t 和宇称问题≈{u 等 ∀ v qt 量子算法 我们主要介绍具有广泛影响的 ≥«²µ算法和 Šµ²√ µ¨算法 ∀ v qt qt 大数因子分解算法k≥«²µ算法l 为开拓出量子计算机巨大的并行处理能力 o必须寻找适用于这种量子计算的有效算 法 ∀≥«²µ于 t||w年发现的 ≥«²µ算法≈zx 可以有效地用来进行大数因子分解 ∀大数因子 分解是现在广泛用于电子银行 !网络等领域的公开密钥体系 • ≥„安全性的依据 ∀采用现 有计算机对数 Νk二进制长度为 ²¯ª Νl做因子分解 o其运算步骤k时间l随输入长度k¯ ²ª Νl指数增长 ∀ ≥«²µ算法的主要思想为 o首先利用数论中的一些定理 o将大数因子分解转化为求一 个函数的周期问题 o而后者可以用量子快速傅立叶变换在多项式步骤内完成 ∀设 Ν为要 分解的自然数 o首先随机地选择一个与 Ν互质的自然数 χ o构造如下函数 φ( ξ) = χξ(°²§ Ν) (ty) 其中 °²§ Ν表示 φ( ξ)与 χξ 对 Ν的余数相等 o如 t € wk°²§vl ∀ ≥«²µ证明 o只要求得 φ ( ξ)的周期 ,就能按一定程序得到 Ν的一个因子 ∀求 φ( ξ)的周期 o用的是量子 ƒƒ × 算 法 ∀输入态 | 7 ι > = 6 ξ = tt . . .t ξ = ss . . .s φ( ξ) | ξ > (tz) 的量子 ƒƒ× 由下式给出 suw 物 理 学 进 展 us卷 | 7 φ > = 6 ξ = tt . . .t ξ = ss . . .s [ u− κ/ u 6 εuΠιξξχ] φ( ξχ) | ξ > (t{) 其中 κ为 ξ 在二进制表示下数据长度 ∀可以看出 o量子 ƒƒ× 实际上就是将态前面的叠加 系数变为原叠加系数的离散傅里叶变换 o可以证明 o上述变换可以大约在 κu步骤内完成 ∀ 对变换后的波函数进行位置的测量 o就可以得出原叠加系数的周期 o这非常类似于利用晶 格的 ÷ 光衍射来确定晶格周期 o晶格周期就相当于这里 φ( ξ)的周期 ∀得到 φ( ξ)的周期 后 o按照一定的概率算法 o可以推导出 Ν的一个因子 o但因为是概率算法 o所以不一定每 次都成功 ∀≥«²µ证明 o成功的概率仅随着输入数 Ν的二进制长度多项式递减 ∀因此只 要将上述过程重复多项式次 o就可以以非常接近 t的概率找到 Ν的一个因子 o而多项式 算法的多项次重复 o仍然是个多项式算法 ∀这就证明 o利用量子计算机 o可以在多项式步 骤内进行大数因子分解 ∀ 实验上 o目前一个推广了的 ≥«²µ算法已经在核磁共振中得到实现≈{v  ∀ v qt qu 量子搜索算法kŠµ²√¨算法l t||z年 Šµ²√ µ¨发现了另一种很有用的量子算法 o即所谓的量子搜索算法≈zy  o它适用 于解决如下问题 }从 Ν个未分类的客体中寻找出某个特定的客体 ∀经典算法只能是一个 接一个搜寻 o直到找到所要的客体为止 o这种算法平均地讲要寻找 Ν/ u次 o找到几率为 tru o而采用 Šµ²√ µ¨的量子算法则只需要 Ν次 ∀例如 o要从有着 tsy 号码的电话本中找 出某人的电话号码 o该电话本是以号码排序的 ∀经典方法是一个个找 o平均要找 x ≅ tsx 次 o才能以 tru几率找到所要电话号码 ∀ Šµ²√ µ¨的量子算法每查询一次可以同时检查所 有 tsy个号码 ∀由于 tsy量子比特处于纠缠态 o量子干涉的效应会使前次的结果影响到 下一次的量子操作 o这种干涉生成的操作运算重复 tsssk即 Νl次后 o获得正确答案的 几率为 tru ∀但若再多重复操作几次 o那么找到所需电话号码的几率接近于 t ∀ Šµ²√ µ¨算法的用途很广 o可以寻找最大值 !最小值 !平均值等 o也可以用于下棋 ∀最 有趣的是可有效地攻击密码体系 o如 ⁄∞≥ k·«¨ §¤·¤ ±¨¦µ¼³·¬²