（基础数学专业论文）关于量子fourier变换的研究及其应用.pdf

关于量子f o u r i e r 变换的研究及其应用 李莉 摘要量子f o u r i e r 变换( q u a n t u mf o u r i e rt r a n s f o r m ) 是量子计算中的一种重 要算法量子计算机可以使用基于s h o r 的量子f o u r i e r 变换和基于g r o v e r 的量子搜索 算法来解决那些在经典计算机上需要过多资源才能求解的问题本文从矩阵论与算 子论的观点，研究了量子f o u r i e r 变换的一系列重要性质，并给出了相关的应用全文 共分两章： 第一章首先简单介绍了量子计算与量子信息的一些基本概念，如量子，量子比 特然后阐述了量子计算与量子信息应遵循的量子力学中的一些原则，如量子比特所 遵循的一些线性代数运算原则以及量子力学假设，还解释了量子态不可克隆这个很 重要的定理最后讨论了几种量子比特门在几量子比特上的作用情况 第二章首先讨论了量子f o u r i e r 变换在基态上的作用，对量子f o u r i e r 变换在计算 基下的矩阵进行了因子分解，使我们能更好的理解量子f o u r i e r 变换的有效线路图，并 给出了具体的例子，根据三量子比特的量子f o u r i e r 变换的有效线路图计算出三量子 比特的量子f o u r i e r 变换的矩阵最后用类似的方法得出相位估计第一阶段运算的一 个因子分解 关键词量子比特；量子f o u r i e r 变换；因子分解；矩阵；基态；量子比特门；相位 估计：有效线路 r e s e a r c ho nq u a n t u mf o u r i e rt r a n s f o r m a t i o n a n di t sa p p l i c a t i o n s l il i a b s t r a c t ：q u a n t u mf o u r i e rt r a n s f o r m ( q f t ) i sa ni m p o r t a n ta l g o r i t h mi n q u a n t u mc o m p u t a t i o n q u a n t u mc o m p u t e rc a ns o l v et h ep r o b l e mu s i n gq f ta n d q u a n t u ms e a r c h i n ga l g o r i t h m ，w h i c hp r o b l e mn e e dt o om u c hr e s o u r c ei nc l a s s i c a l c o m p u t e r i nt h i sp a p e r ，w et r a n s l a t et h ep o t e n tc i r c u i t r yo fq f ta n dt h ef i r s t m o m e n to fp h a s ee s t i m a t i o na g a i n t h i sp a p e ri so r g a n i z e da sf o l l o w s i nc h a p t e r1 ，f i r s tw ei n t r o d u c es o m ed e f t n i t i o n si nq u a n t u mc o m p u t a t i o na n d q u a n t u mi n f o r m a t i o n ，e g q u a n t u m ，q u a n t u mb i t t h e nw ee x p o u n ds o m ep r i n c l p i e i nq u a n t u mm e c h a n i c s a n dw ee x p l a i nt h eq u a n t u ms t a t ec a nn o tb ec l o n e d a t l a s t ，w ed i 8 c i l 8 8af e wo fq u a n t u mb i tg a t e s i nc h a p t e r2 ，f i r s tw ei n t r o d u c et h ed e f i n i t i o no fq f t t ou n d e r s t a n dt h ep o t e n t c i r c u i t r yo fq f tm o r e ，w es t u d yt h ef a c t o r i z a t i o no fq f ta n dw eg i v ea ne x a m p l e b ys i m i l a rw a y , w eg e tt h ef a c t o r i z a t i o no ft h ef i r s tm o m e n to fp h a s ee s t i m a t i o n k e y w o r d s ：q u a n t u mb i t ；q u a n t u mf o u r i e rt r a n s f o r m ；f a c t o r i z a t i o n ；m a t r i x ； b a s i cs t a t e ；q u a n t u mb i tg a t e ；p h a s ee s t i m a t i o n ；p o t e n tc i r c u i t r y i i 记号 互卜_ 至卜_ 互卜- 互卜 互卜- 互卜 名称 h 门 x 门 爪| 黾 受控非门 工 矧； - 困 垂 测量 量子比特 主要符号表 说明 击( ：二) ( ：。1 ) ( ；：) ( ( ( 1 0 o 一1j 1 0 o j 1o 、1 0e i 删) 1o o 0 o10o o 0 o1 0 o10 1o oo 0 0l0 ol0 0 o o o1 投影到i o ) 和1 1 ) 上 传送单一量子比特信号的电信 n 量子比特传送他单一量子比特信号的电信 】陪u 阳 砷 撇 学位论文独创性声明 本人声明所呈交的学位论文是我在导师的指导下进行的研究工作及取得的研 究成果。尽我所知，除文中已经注明引用的内容外，论文中不包含其他个人已经 发表或撰写过的研究成果，也不包含为获得陕西师范大学或其它教育机构的学位 或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中 作了明确说明并表示谢意。 学位论文使用授权声明 本人同意研究生在校攻读学位期间论文工作的知识产权单位属陕西师范大 学。本人保证毕业离校后，发表本论文或使用本论文成果时署名单位仍为陕西师 范大学。学校有权保留学位论文并向国家主管部门或其它指定机构送交论文的电 子版和纸质版；有权将学位论文用于非赢利目的的少量复制并允许论文进入学校 图书馆、院系资料室被查阅；有权将学位论文的内容编入有关数据库进行检索； 有权将学位论文的标题和摘要汇编出版。 作者签名： 盔茎1日期：竺丑兰盥 前言 2 0 世纪初叶，科学经历了一场出人意料的革命，物理学遇到了一系列危机问题在 于当时的物理学理论( 现在称为经典物理学) 作出了一些荒唐预言，诸如存在包含无 穷能量“紫外灾”或电子必然旋转着进到原子核内部，起初这些问题是通过在经典物 理学中附加特别的假设来解决，但随着人们对原予和辐射更好的了解，这些尝试性的 解释越来越让人困惑，经过四分之一世纪的混乱，导致量子力学这一现代理论的创 立 。 自从m p l a n c k 于1 9 0 0 年首先提出量子概念以来，经过众多物理学家的不断创新 努力，到2 0 世纪2 0 年代就已经建成了一套完整的量子力学理论，量子力学一出现就成 为科学不可缺少的一部分，并已有无数成功的例子，包括原子结构，恒星核聚变，自然 界基本粒子等的几乎所有方面 1 5 】 量子计算与量子信息的研究可以追溯到几十年前，但真正引起广泛关注是在2 0 世 纪9 0 年代中期，这期间发现t s h o r 量子因子分解算法和g r o v e r 量子搜索算法，这两类 算法展示了量子计算从根本上超越经典计算机计算能力和在信息处理方面的巨大 潜力与此同时，量子计算机和量子信息处理装置在物理实现方面的研究，成为继并行 计算机，生物计算机等之后的非串行计算体系的又一热点 量子计算机可能是计算机历史上的下一个革命最早的量子计算机已经使用激 光，离子，核磁共振等技术构造出来了，g r o v e r 量子搜索算法平方的快于经典计算机 的任何可能的搜索算法，而s h o r 量子因式分解算法乘方的快于任一已知的经典的相 应部分这些实验和理论结果表明了量子计算机是可行的，而且将不容置疑的快于传 统计算机量子计算机的软件和硬件是建立在量子力学的基础上的，正是由于这个原 因，诸如态的叠加，纠缠态等全新现象开始起作用，我们将会看到，这些现象对量子计 算机是非常重要的 量子计算机引入入胜的前景在于它可以使用新算法，解决那些在经典计算机上 需要过多的资源才能求解的问题我们已经知道有两大类量子算法可以实践这个诺 言第一类算法基于s h o r 的量子f o u r i e r 变换，包括解区 = f ：( f a c t o r i n g ) i h l 题和离散对数 ( d i s c r e t e l o g a r i t h m ) 问题的令人瞩目的算法，这些算法提供了对最好的经典算法的惊 人的指数加速，在第二章我们将详细描述量子f o u r i e r 变换第二类算法基于g r o v e r 的 量子搜索( q u a n t u ms e a r c h i n g ) 篚j 算法这些算法提供的略为逊色，但仍相当可观的对 最好的经典算法二次( q u a d r a t i c ) 加速量子搜索算法的重要性在于经典算法中基于 搜索技术应用非常广泛，这些应用中，许多都可以直接搬用比经典算法更快的量子算 1 法 量子计算与量子信息的研究对象是用量子力学系统能够完成的信息处理任务人 们想到用量子力学系统进行信息处理其实花了很长时间，为量子计算与量子信息提 供基本概念的领域有量子力学计算机科学，信息论和密码系统 量子力学是一个数学框架或一套构造物理学理论的规则量子力学的规则很简 单，但即使是专家有时也会感到违反直观量子力学最著名的批判者e i n s t e i n ，直到去 世都不能接受他帮助发明的这个理论几代物理学家一直在为使量子力学作出的预 言更令人满意而奋斗景子计算与量子信息的一个目标就是增进我们对量子力学直 观上的把握 2 第一章预备知识 1 1 引言 利用微观粒子的状态表示的信息就称为量子信息信息一旦量子化，描述“原子 水平上的物质结构及其属性”的量子力学特性便成为描述信息行为的物理基础，在此 基础上研究信息的存储，传输和处理的一般规律的学科称为“量子信息学”量子信息 学是量子力学与经典信息学结合的新兴学科，微观系统的量子特性为信息学带来许 多令人耳目一新的现象，在信息的表示，加工，处理和传输上生长出一些新的概念，原 理和方法量子信息与量子通信将在未来的信息与通信的研究领域具有独特的不可 替代功能，将发挥重要的作用而量子计算最引入入胜的发现在于量子计算机可以 有效地完成某些在经典计算机上做不到的任务为了更好的理解量子计算与量子信 息的研究情况，也作为本文的出发点，本章主要介绍了量子计算与量子信息中的一些 基本概念及理论，同时给出了几种量子比特逻辑门作用在n 量子比特上的情况及其证 明 1 2 量子与量子比特 量子状态的变换可以用量子计算的语言来描述，类似于经典计算机是由包含连 线和逻辑门的线路建造的量子计算机是由包含连线和基本量子门排列起来形成的 处理量子信息的量子线路建造的 量子最早出现在光量子理论中，是微观系统中能量的一个力学单位，现代物理将 微观世界中所有的微观粒子( 如光子、电子、原子等) 统称为量子普朗克于1 9 0 0 年在 有关黑体辐射问题研究中提出。物质辐射( 或吸收) 的麓量只能是某一最小能量单位 的整数倍数”的假说，称为量子假说假说的含义是：对于定频率p 的电磁辐射，物体 只能以此最小单位吸收或发射它( 由此可见微观世界物质的能量是不连续的1 换言 之，吸收或发射电磁辐射只能以“量子”方式进行，每个“量子”的能量为 e = h u ( 其中h 为一个普适常量) 这种吸收或发射电磁辐射能量的不连续性的概念，在经典力 学中是无法理解的【6 】 微观世界中量子具有宏观世界无法解释的微观客体的许多特性，这些特性集中 表现在量子的状态属性上如量子态的叠加性，量子态的纠缠，量子状态的不可克隆，量 3 子的“波粒二象性”以及量子客体的测量将导致量子状态“波包塌缩”等现象这些 奇异的现象来自于微观世界中微观客体问存在的相互干涉，即所谓的量子相干特性 利用微观粒子的量子态叠加及相干特性能够实现未来计算机超高速并行计算：利 用微观粒子的量子态纠缠，量子态不可克隆的力学特性能够实现超高速的信息传送，实 现不可破译不可窃听的保密通信 相对于经典信息的基本存储单元比特( b i t ) ，量子信息的基本存储单元称为量子 比特( q u b i t ) 量子比特被描述为具有特定属性的数学对象单量子比特f 或记为量子 比特) 的两个可能状态是l o ) 和1 1 ) ，记号“i ) ”称为d i r a c 记号，它在量子力学中表示状 态量子比特和比特的不同之处在于量子比特的状态可以落在1 0 ) 和1 1 ) 之外，可以是 状态的线性组合，不能确定地说状态是i o ) 或1 1 ) ，常称为叠加态( s u p e r p o s i t i o n ) 例如 妒) = n l o ) + p 1 1 ) 其中。和口是复数，尽管许多时候把它们当作实数也不会有太大问题换句话说量子比 特的状态是二维复向量空间中的向量特殊的i o ) 和1 1 ) 状态称为计算基态 ( c o m p u t a t i o n a lb a s i ss t a t e ) ，是构成这个向量空间的一组正交基【7 】 多量子比特与量子比特相对应如n 量子比特的基态为 l o o o ) ，1 0 0 1 ) ，1 1 1 1 ) 、- - v 一、- - 一、_ - v 一 它们构成2 “维复向量空间的一组正交基，同时n 量子比特也可能是叠加态，即 i 妒) = a o l 0 0 0 ) + a l l 0 0 1 ) + + 0 2 ，l 一1 1 1 1 1 ) 、- - v 。_ 一、- - v 。_ 一、_ - v 。一 母1 、重亍亡| 二待i j 郁口j 以与一，| 、矩1 5 牛硼珂比，帚见明早重于比待i j 伺p a u l i n e 8 j x = 0 ：) ，y = 0 0 ) ，z = ( ：三) 雨q h a d a m a r d f - 8 9 日= 去( ：h x 称为量子非门，其作用是把i o ) 变成1 1 ) ，把1 1 ) 变成i o ) ，即 x l o ) = 1 1 ) x 1 1 ) = 1 0 ) 4 y f - jl 拘作用是把l o ) 变成i 1 1 ) ，把1 1 ) 变成一q o ) ，即 y o ) = 1 1 ) ，y 1 1 ) = - i i 0 ) z 门的作用是保持i o ) 不变，而把1 1 ) 变成一1 1 ) ，即 z l o ) = i o ) ，z 1 1 ) = - 1 1 ) h a d 锄a r d 门把l o ) 变到l o ) 和1 1 ) 的中间状态譬妒，而把1 1 ) 变到l o ) 和1 1 ) 的中间状态 咎磐，即 日l o ) = 去( i o ) + 1 1 ) ) ，日1 1 ) = 去( i o ) 一1 1 ) ) 、，z 5v 二 多量子比特门的原型是受控非门( c o n t r o l l e d - n o tg a t e 或c n o tg a t e ) ，该门有两 个输入量子比特，分别是控制量子比特和目标量子比特，该门的作用为若控制量子比 特置为0 ，则目标量子比特将保持不变，若控制量子比特置为1 ，则目标量子比特将翻 转即 u c m o o ) = i o o ) ，u c m 0 1 ) = 1 0 1 ) ，v c n l l o ) = 1 1 1 ) ，u c m l l ) = 1 1 0 ) 该门的作用也可总结为 l a ，b ) 一i a ，口o a ) ， 其中。是模2 加法 1 3 线性代数中的量子符号及其运算的简介 量子力学对己知世界的描述是最精确和完整的，也是理解量子计算与量子信息 的基础量子力学理论是线性的，线性代数研究向量空间及其上的线性算子下面是 一些常用记号及其含义 6 1 1 1 0 ： ( 1 ) 矿，复数z 的共轭如果z = o + 酾，则矿= n b i ( 2 ) a ，矩阵a 的复共轭 ( 3 ) a t 7 矩阵a 的转置 ( 4 ) a t ，矩阵a 的h e l t n i t i a n 共轭或复共轭转置，a t = ( a t ) 即 ( ：小( ：象) 5 cs，i砂，右矢量堪-i妒，=(三=c钆q，岛，t ( 6 ) 渺i ，l 妒) 的对偶矢量即( 妒i = ( 噬，c 6 ，嚷) ( 8 ) i i , l i 脚) 肭钏训= 厕2 惦肼 = i 篇a x l b ：a 1 2 bi：alnb， 1 4 量子力学假设 量子力学是用物理理论发展的一个数学框架量子力学本身不能告诉我们物理 系统服从什么定理，但它却提供了研究这些定律的数学和概念的框架下面将介绍量 子力学的基本假设，这些假设把物理世界和量子力学的数学描述联系了起来 量子力学的假设是经过长期的尝试与失败后而推导出来的，经过了发明者的大 量猜测和摸索假设的动机不明显，这不足为奇，因为量子力学的基本假设即使对专家 而言也是令人吃惊的 量子力学的第一条假设建立起量子力学适用的场合，即线性代数中熟知的h i l b e r t 空间 假设1 【7 】任一孤立物理系统都有一个称为系统状态空间的复内积向量空间( 即 h i l b e r t 空间) 与之相联系，系统完全由状态向量所描述，这个向量是系统状态空间的一 个单位向量 最简单最基本的量子系统是量子比特一个量子比特有一个二维的状态空间，设 1 0 ) 和1 1 ) 构成这个状态空间的一个标准正交基，则状态空间中的任意状态向量可写作 l 妒) = a l o ) + 6 1 1 ) 其中瘌b 是复数，于是i 妒) 为单位向量的必要条件，即似l 妒) = l ，就等价于l o l 2 + l b l 2 = 1 ，条件妒i 妒) = 1 5 称为状态向量的归一化条件 量子力学的第二条假设描述了量子力学系统的状态1 1 j ，) 如何随时问变化 假设2 1 7 1 一个封闭量子系统的演化可以由一个酉变换来刻画，即系统在时刻t l 的 状态i 妒) 和系统在时刻2 的状态) ，可以通过一个仅依赖于时间t l 和f 。的酉算子u 相 联系： i 妒) = ，l 妒) 正如量子力学不告诉我们状态空间或一个特定量子系统的量子状态，它也不告 诉我们什么样的酉算子u 描述了现实世界的量子动态，量子力学仅仅向我们保证，任 意封闭量子系统的演化都可以用这种方式描述一个显然的问题是：自然选择什么样 酉算子? 实际上单量子比特的情形下，所有的酉算子都可以在实际系统中实现 假设2 描述了封闭量子系统的量子状态在两个不同时刻的关系，作为这条假设的 一个更精细的版本，可以给出描述量子系统在连续时间上的演化从这个更精细的假 设可以重新得到假设2 ，其中的h 算子不同于前面引出的h a d a m a r d 算子 假设2 ，【7 1 封闭量子系统的演化由s c h r 甜i n g e r 方程描述 i 危掣：h i e ) a s 7 这个方程中壳称为p l a n c k 常数，其值必须由实验确定它的精确值对我们并不重要，实 践中，常把因子h 的值放入到日中，而置 = 1 , h 是一个称为封闭系统h a m i l t o n 量的固 定h e r m i t e 算子 我们已经假设封闭量子系统按酉算子演化，尽管系统演化可以不与世界其他部 分相互作用，但是一定有某些时刻实验者和实验设备换句话说外部物理世界一要 观察系统，以了解系统内部的情况，这个观测作用使系统不再封闭，也就是不再服从酉 演化。为解释这样做的影响，我们引入假设3 ，以便为描述量子系统的测量提供一条途 径 假设3 f 7 】量子测量由一组测量算子描述，这些算子作用在被测系统状态空间 上，指标m 表示实验中可能的测量结果若在测量前，量子系统的最新状态是l 妒) ，则结 果m 发生的可能性由 p ( m ) = ( 妒i a 臻 i 奶 给出，且测量后系统的状态为 l 妒) ( 妒i j l 孺 l 妒) 测量算子满足完备性方程 豫= 1 完备性方程表达了概率为1 的事实： 1 = p ( m ) = ( 妒i 砩i 妒) tn,”l 该方程对所有i 妒) 成立，等价于完备性方程 测量的一个简单但重要的例子是，单量子比特在计算基下的测量，这是在单量子 比特上的测量，有由两个测量算子 矗= i o ) ( q l 和m l = 1 1 ) ( 1 l 定义的两个结果注意到 每个测量算子都是h 咖i t e 的，并且嚼= i o ， 砰= 帆，于是满足完备性关系，= 删 矗+ 删m 1 = m i + m 假设被测状态是n l o ) - 4 - b 1 1 ) ，则获得测量结果。的概率是 p ( o ) = ( 妒l 磁m o l e ) = ( 妒l m o l l j f ) = i n l 2 类似的，获得测量结果1 的概率是p ( 1 ) = 忙1 2 ，两种情况下，被测量后的状态分别为 箐a = 帮a1 0 i川 8 m l 砂)b 可广一雨1 1 ， 像o l 口i 这样的模为l 的倍数，实际上可以忽略，因此测后有效状态是l o ) 和1 1 ) 设想我们感兴趣的是两个( 以上) 不同物理系统组成的复合量子系统，如何描述 该复合系统的状态? 下面的假设描述了如何从分系统的状态空间构造出来复合系统 的状态空间 ， 假设4 【7 】复合物理系统的状态空间是分物理系统状态空间的张量积，若将分系 统编号为1 到礼，系统泊自状态被置为陬) ，则整个系统的总状态为i 妒1 ) 圆ol 以) 是 1 5 量子态不可克隆定理 可克隆定理的道理很简单，因为量子力学的理论是线性的钮亩- 量子态 剩晕 这便是量子态不可克隆定理( n o n c l o n a b i l i t yo fas i n g l eq u a n t u mt h e - o r e m ) ，定理的证明可以简述如下【6 】： 设a 和b 是两个量子系统，它们分别处于i 以) 和i o 口) 状态后者是系统b 在拷贝前 所处的空白状态假设有某种操作能够把系统a 的任意量子态拷贝到系统b 上，即 i 加) o i 吩) + i 九) o l 如) 那么同样的操作当然也能够将另一量子态从系统a 拷贝到系统b 上： 饥) o1 0 b ) + l 纵) 固) 取它们的叠加态 l 虬) = i 以) 4 - l 饥) 按量子态的线性叠加原理，我们有 皿a ) 0 1 0 b ) = l 妒 ) 0 1 0 8 ) + l “) 固1 0 b ) i a ) o l 妒雷) 4 - i 妒a ) p i 妒口) i 皿a ) o i 皿b ) 因为i 母a ) o i 皿口) = l 机) o i 口) + l 妒a ) o f b ) + i “) p i 妒占) + l ) p i 妒口) 结论的矛盾表明，量子态的线性叠加原理排斥了克隆任意量子态的可能性，量子 不可克隆定理是信息理论的重要基础，它为量子密码的安全性提供了理论保障 9 证明首先，我们有 h i o ) h 1 1 ) ) = ) = 去( i o ) + i i ， v 。 去( i o 卜1 1 ) ) v z 情况 0 ，1 ) ( 1 6 1 ) 则日i z ) 2 麦( i o ) 4 - ( 一1 ) 。 而在( 1 6 1 ) 式中，令n = 1 , 有h z 1 ) = 击( - 1 ) ”“i z l ) = 去( i o ) 4 - ( 一1 ) “1 1 ) ) ：1 e o ，1 】 所以当n = l 时，( 1 6 1 ) 式是成立的 假设当n = 枷寸，( 1 6 1 ) 式是成立的，即 日鼬1 2 7 1 - z k ) = 去( 一1 ) “4 扣”扣4 i 魂缸) 令n = 七+ 1 测 月。( 七+ 1 ) i z l z 量z 七+ 1 ) h 龇i x l z t ) oh l z k + 1 ) z l - i - + z l t z l t1 2 1 z k ) ”1 1 1 ) ) 2 1 + + ”。托i z l z k l ) 1 - i ) 。1 旬+ + 2 。+ 。+ 1 。+ 1 l z l z k z k + 1 ) 因此，( 1 6 1 ) 式对所有的扎n 是成立的 1 0 i i i ；i 篡 瓠 袖 佣 懒一 嘴胁黔训一磊 量 撇枥描一嗉 6 盯 r “ 叫 砌 题 徘 p ，一，一、l、l 。o ，以 ，一，一 一l 以上以 命题1 2 i t h a d 锄a r d 门日的竹次张量积有如下性j 1 1 - 日畦去赢邶叶晰一圳y l y n i ( 1 6 2 ) 证明首先，我们有 c 。i 。，= ( ，。) ( ：) = ，i - ，= ( - ，。) ( ：) = 0 ， t i 。，= ( 。，1 ) ( ：) = 。，c 1 i 1 ，= ( o ，) ( ：) = 1 ， 日| o ) = 去( 1 0 ) + 1 1 ) ) v 二 = 去( ( oio ) 1 0 ) + ( 1io ) 1 0 ) + ( 0 o ) 1 1 ) 一( 110 ) 1 1 ) ) v 二 = 杀( i o ) ( o l l o ) + i o ) ( 1 l l o ) + 1 1 ) ( o l l o ) 一1 1 ) ( 1 l l o ) ) v 二 = 二呙( i o ) 1 2 赤乙，赢( _ ”4 ”“叫挑k 1 ) 纰h ) ( 鲰 阶w ) 】 【 ( - - 1 ) k + i v k + i 挑+ 1i + 1 ) 1 ) 】 x k + l ，“+ l o ，1 1 , 2 去l 赢卜”彻十“协时嘶m + l ( 纨，i 魂) ( 抛iz 2 ( 挑+ 1 iz 1 ) i z l 。z t + 1 ) 】 2 去乙磊m 卜d 4 时。+ “时阱l 玑j 弧+ 1 i 忽魂+ 1 ) l z l z 女+ 1 ) j 2 南l ，赢卜”8 时押m m + l 则有日。( 1 ) = 了1 1 ；万 ( - 1 ) 。1 m + 。“m + 1 l z l x k + 1 ) ( 管1 弧+ 1 z l * o ，1 ) 因此，( 1 6 2 ) 式对所有的n n 是成立的 类似的，我们可以得到一些关于x ，k z ，的等式 命题1 3p a u l i 矩阵x ，z 的n 次张量积有如下性质： x 跏i z l z 2 z 。) = 1 1 一x a ) 1 一现) 1 1 一z 。) y 舒i z l x 2 。) = ( 一1 ) 2 1 + + 。“i ”1 1 一x 1 ) l z 2 ) 1 1 一z 。) ， z 4 研i z l z 2 z n ) = ( - 1 ) 。1 + + 。”l z l 。眨z 。) ， 其中如 o ，l ，i = 1 ，他 证明 = 1 1 ) = 1 0 ) 贝0 我竹】有x l x ) = 1 1 一。) 而在( 1 6 3 ) ，令n = 1 ，有x x 1 ) = 1 1 一z 1 ) 所以，当n = 1 时，( 1 6 3 ) 式是成立的 假设当n = 堋寸，( 1 6 3 ) 式是成立的，则有 x 。i z l z 2 z k ) = 1 1 一x 1 ) 1 一x 2 ) 1 1 一z 女) 令n = k + 1 ，有 x 。七+ 1 i z l z 2 霉膏+ 1 ) =x 龇i z l x 2 z k ) x l z + 1 ) j 1 一z 1 ) i l 一勉) 1 1 一孤) 1 1 一z k 4 - 1 ) 因此，对所有的竹n ，( 1 6 3 ) 式是成立的 y 0 ) y 1 ) ( ；- i ) ( 1 ) 00 = ( 垆 ( ：) ( ：) = ( 言) = 1 4 1 1 ) ， - - i 1 0 ) ( 1 6 3 ) ( 1 6 4 ) ( 1 6 5 ) 、l o 1 l o ，、，、 l | = lll， 1 o o 1 ，ii、，it、l 1 o l o o 1 o 1 ，i、，ii、 | | | 77 o 1 x x 则我们有y x ) = ( 一1 尸i l l z ) 而在( 1 6 4 ) ，令n = 1 ，有y l x l ) ；( - 1 ) 8 i l l 一钆) 所以，当n = 1 时，( 1 6 4 ) 式是成立的。 假设当礼= 时，( 1 6 4 ) 式是成立的，则 y 。i z l x 2 z k ) = ( 一1 ) 。1 + “+ + 。产1 1 一z 1 ) 1 1 一z ) 令n = k + 1 ，有 y 。+ 1 ) l z l z 2 x k x k + 1 )= y 田i x l x 2 x k ) oy x k + 1 ) = f ( 一1 ) 。- + “+ + 。t 护1 1 z 1 ) 1 1 一z ) 】 o ( 一1 ) “+ 1 t l l 一+ 1 ) 】 = ( 一1 ) 。1 + 。2 + + 。+ 1 i h + 1 1 1 一z 1 ) 1 1 一x k + 1 ) 因此，对所有的n n ，( 1 6 4 ) 式是成立的 z i o ) z 1 1 ) ( ： ( 。1 则我 f 】有z j z ) = ( - 1 ) 。i 。) 而在( 1 6 5 ) ，令几= 1 ，z x 1 ) = ( 一1 ) “i z l ) 所以当n = 1 时，( 1 6 5 ) 式是成立的 假设当n = 七时，( 1 6 5 ) 式是成立的，则 z 。丘i z l - 写七) = ( 一1 ) 。1 + 托+ “_ 诹l z l ：g k ) 令n = k + 1 ，有 z 。( 膏+ 1 ) i z l 玩z 抖l =z 。膏l 勋z ) oz l z 1 ) = 【( 一1 ) 2 1 + 。2 + + 2 l 。1 z k ) 】o ( ( 一1 ) z k + l i z + 1 ) 】 =( 一1 ) 。1 + 2 2 + + 2 。+ 1l z l x k - i - 1 ) 1 5 h 一 旧 i l =、 l 小叫o q ，-i、，li、 = = 、i、l， 1 0 o 1 ，i，fi一一 、， o o o o 因此，对所有的n n ，( 1 6 5 ) 式是成立的 命题1 4 受控非门u c 的n 次张量积有如下性质： u s ；, i x l 可1 ) i z 2 耽) i ) = 鸯圳( 1 一戤) l 玑) + 毛1 1 一鼽) ， ( 1 6 6 ) 其中矗，玑 o ，1 ) ，i = 1 ，m 证明 u c n l 0 0 ) = u c n l 0 1 、= u c n 1 0 、= u c n 1 l 、= oo 1o o0 01 0o 10 0o o1 0o 10 o o 01 00 lo 00 o1 = 1 0 0 ) = 1 0 5 1 1 1 0 ) + 0 1 1 ) 】 = 1 0 1 ) = 1 0 ) 1 1 1 ) + ol 0 5 ， = 1 1 1 ) = 1 1 5 1 0 l o ) - 4 - 1 1 1 ) 1 = i i 0 ) = 1 1 ) 0 1 1 ) + 1 1 0 5 1 贝我 有u c n i x y ) = i z ) 【( 1 一z ) l ) - i - x l l 一鲈) 】 而在( 1 6 6 ) 式中，令n = 1 ，则u c n x l y l ) = l 1 ) 【( 1 一z 1 ) i ”1 ) - 4 - z 1 1 1 一可1 ) 】 所以当n = 1 n ，( 1 6 6 ) 式是成立的 假设当扎= 七时，( 1 6 6 ) 式是成立的即 嗽胁5 i z e 弧) = 垒圳( 1 一z d l u , ) + x , 1 1 一肌) 】 、llj、li、l、ii 1 o o o o 1 o o o o o 1 o 0 l o ，j-_il_-lli，i-_l_li、，-_illlli_lil、，jii_11_-i_-i、 = = = = 、l，、iiii、lli、lfi、 1 o o 0 0 l o 0 o o l o o o o 1 ，-。一，-li、，l-i，-一 、i、l、li、lll 0 0 1 o o o l o 0 o 1 o o o l o 1 o o o l 0 o o 1 o o o l o o o ，fjl_ll_lll_-一，j-_l_i_。l一，j-。l_i_-_-一，j-_-il-_li-t1一 令n = k + 1 ，有 c ，蓦+ i x l 讥) i z s 腱) l z 七+ 1 3 瞻+ 1 ) 嗡i x l y l ) l x k y k ) ou c l x , + l y k + 1 ) 鱼i 甄) 【( 1 一孔) i 职) + 黾1 1 一鼽) 】。i z t + 。) 【( 1 一z ，) l 弧+ ，) + z 七+ 。1 1 一可知+ 。) 】 k 鲁+ l 训( 1 一置) i y 0 + x d l 一玑) 】 因此，对所有的佗n ，( 1 6 6 ) 式是成立的 命题1 5 受控非门_ 的几次张量积有如下性质： v 器l z l 玑) i z n 蜘) = 为- - - - 1i 甄) i 鼽。孔) ， ( 1 6 7 ) 其中黾，玑 o ，1 ) ，i = 1 ，2 ，n ，o 是模2 的加法 证明 v c m o o ) = u c m 0 1 ) = u c n i o ) = u c n 1 1 ) = 1 0 0 ) = i o ) 1 0 0 0 ) ， j 0 1 ) = i o ) 1 1 0o ) ， 1 1 1 ) = 1 1 ) 1 0 01 ) ， 1 1 0 ) = 1 1 ) 1 1 0 1 ) = = i i = 、ii_、lil一、lii、iii7 l 0 o o o l o 0 o o o 1 0 o 1 0 ，j-_lii_ili、，fiii-_一，f-_iill1-i、，j-1-_1 | | 1 1 = = l0，l，、l、l，7 l o o o o 1 o o o o 1 o o o o l 1 ，j_l_il、，l-lli_i_i，-li-_i。il、，l_ii。一 、l、ll、lii、li o o 1 o o o 1 o o o 1 0 o o 1 o o o o 1 o o o 1 o o 0 1 o o 0 1 o l o 0 o 1 o o o l 0 o o l o 0 l o o o l 0 o o l o o o l o o o ，j-l_l_-i、，f-_l_i-lii、，j-_il_li，jl_-_-i_i-i 贝q 我1 】有u c n i z u ) = l z ) is ，oz ) 而在( 1 6 7 ) 式中，令礼= 1 ，有i z l y l ) = i z l ) i f lox 1 ) 所以当疗= 1 时，( 1 6 7 ) 式是成立的 假设当几= 七时，( 1 6 7 ) 式是成立的，即 令付= k + 1 嘴l z l 可1 ) i z k 鲰) = 点i 磊) i 轨。黾) l = i u c s ( k + 1 i z l y l ) i z 膏g 纯) i l + 1 3 船+ 1 ) = u 。k 。z l 玑) i x k y k ) ou c l = k + l y k + 1 ) = ： 点i z f ) j 扰oz ) oi z k + 1 ) 1 3 膳+ 1oz 七+ 1 ) ：簧l 鼽。戤) 因此对所有的n n ，( 1 6 7 ) 式是成立的 1 8 第二章量子f o u r i e r 变换 2 1 引言 量子计算中有两类引人注目的新算法一类算法是基于s h o r 的量子f o u r i e r 变换， 它是量子因子分解和许多其他有趣量子算法的关键部分并且提供了对最好的经典 算法的惊人的指数加速，另一类算法是基于g r o v e r 的量子搜索算法( q u a n t u ms e a r c h - i n ga l g o r i t h m ) ，这些算法提供的略为逊色，但仍相当可观的对最好的经典算法二次加 速( q u a d r a t i cs p e e d i n g ) ，量子搜索算法的重要性在于，经典算法中基于搜索技术的应 用非常广泛本章阐述的量子f o u r i e r 变换是进行量子力学幅度的f o u r i e r 变换的有效 量子算法，它并没有加速计算经典数据的f o u r i e r 变换的经典任务，但它的一个重要任 务是相位估计，即近似酉算子在某些场合的特征值还可用来求解若干其他有趣的问 题，如求阶问题( o r d e r - f i n d i n gp r o b l e m ) 和因子问题( f a c t o r i n gp r o b l e m ) 2 2 量子f o u r i e r 变换 近年来，量子力学已经给物理界提供了许多有效描述，许多新的发现都被应用 于量子信息和量子计算科学1 1 2 1 而经典世界的许多可行性算法在量子世界里已经 不可用【1 3 】，比方说，一个未知的量子态是不可克隆的【1 4 】【15 】 数学或计算机科学中解决问题的最重要的方法之一，是把问题变换为其他解为 已知的问题有些这类变换出现得非常频繁，并且用于非常多的不同场合，以致形成 了对这些变换自身的研究领域量子计算的一项伟大发现就是，某些这样的变换在 量子计算机上的计算，可以比在经典计算机上快得多，这个发现使我们能针对量子 计算机建立快速算法 、 离散f o u r i e r 变换就是这类变换之一按通常的数学记号，离散f o u r i e r 变换是作 用在复维欧氏空间c 上的一个酉变换，当输入为复向量( z o ，x n 一1 ) 时，其输出 为复向量( 铷，蛐一1 ) ，其中 y k - - 嘉薹巧酬警- o ，1 ，_ 1 ) ( 2 2 1 ) 在量子计算中，称空间c 2 ”中的元素( 2 f l 维复列向量) 为竹量子比特因而，作用在 空间c 2 ”上的离散f o u r i e r 变换称为量子f o u r i e r 变换 7 】下列的2 f 1 个札量子比特( 称为 基态) 构成t h i l b e r t 空间c 2 ”的正规正交基 0 ) 1 ) 2 n 一 ( 1 ，o ，0 ，o ，o ) r ， ( o ，l ，o ，o ，o ) t ， ( 2 删 1 ) = ( 0 ，0 ，0 ，0 ，1 ) 丁 也称为n 量子比特的量子计算机的计算基( 简称为量子计算基) 易知0 ，1 ，2 ，2 ”一 1 z 2 。，其中z 2 。为整数的模2 - i j n 群，d e u t s c h 证明了群z 2 n 上的f o u r i e r 变换可以在 量子计算机上有效实现 1 6 1 根据公式( 2 2 1 ) ，量子f o u r i