（应用数学专业论文）某些sobolev类上的量子积分误差.pdf

摘要 摘要 本文介绍了量子计算的起源和发展，包括离散问题与连续问题的最新进展。 在此基础上我们研究了各向异性s o b o l e v 类上的量子积分误差，确定了量子算法 的最优收敛阶，并用一种新的约简方法得到了非整数阶导数的各向异性s o b o l e v 类上的量子积分误差的下界估计，将所得到的结果与s o b o l e v 类上的积分问题的 确定性算法与经典随机化算法的误差加以对比，显示量子算法有比较优势。 关键词非整数阶各项异性s o b o l e v 类量子积分最优误差 a b s t r a c t l i lt i l i sp a p e rw ei n t r o d u c e dt h e o r i g i na n dd e v e l o p m e n to fq u a n t u m c o m p u t a t i o n 1 n c l u d i n gt h ei a t e s tp 斌e s s e si nb o t hd i s c r e t ea n d c o n t i n u o u sc a s e s ，b a s e du p o nw h i c h w es t u d l e dt h ei n t e g m t i o ne r r o ro na n i s o t r o p i cs o b o l e v c l a s s e si nt h eq u a l l m ms e 仕i n g a n dc o n c l u d e dt h eo p t i m a lc o n v e r g e n c e r a t e s 。 u s m ga n e wr e d u c t i o na p p r o a c hw e o b t a i n e dt h el o w e rb o u n do f i n t e g r a t i o ne 啪r o na n l s o 昀p i cs o b o l e vc l a s s e sb a s e do n f r a c t i o n a ld e r i v a t i v e s t h er e s u i t ss h o wt h a t t h ee 姗b o u n d so fq u a n t u m a l g o r i t h m sy i e l das p e e du p0 v e rt l l o s eo fd e t e 嘶i l i s t i c a n dr a n d o m i z e da l g o r i t h m sf r o mc l a s s i c a ls o b 0 1 e v f r a m e s k e y 附凼妇锄龇胁d v e 刎s 。t r o p i c s o b 。l e v c l a s s e s q u a n t u n li n t 唧t i o n o p t i m a le r r o rb o u n d 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：u 2 0 2 1 1 3 。2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 2 0年月日 南开大学研究生学位论文作者信息 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月 日 第章引言 第一章引言 1 1 量子计算简介 量子计算( q u a n t u mc o m p u t a t i o n ) 是对于一个或多个量子位元( q u b i t ) 或量子 三元( q u t r i t ) 以上进行操作以达到具有量子特性的演算功能。量予计算的课题 除了具有特殊量子态的操作对象即资讯储存单元外，还包括逻辑门等运算方法的 内容。实际的物理实践系统则属于量子计算机的课题范畴 1 】。 量子计算机概括地讲，就是利用“隧道效应”等已知的量子力学效应来实现 的超级并行计算机。在传统计算机上需要花费数年进行的计算放在量子计算机t 可能只用数个毫秒就能完成。在向普通计算机输入数据时，在一个瞬间只能输入 1 6 位或3 2 位等2 进制的数据段。从位数来看，输入的只能是0 或者1 。区分并控 制0 与1 只能利用晶体管等组件。与此相反，量子计算机可以同时大批量地输入 0 与1 。相当于晶体管的就是量子位元。 舟1 i 量子引算机 量子位有个，利用它们之间名为“e n t a n g l e m e n t ”的相互作用状态，可同时 输入的数据就有2 n 个。假如量子位有4 0 个的话，就可以同时在1 组运算电路上 计算约1 万亿个输 参量。而普通计算机是不可能将1 万亿台联接起来进行并行 第一章引言 运算的。科学家们认为如果在技术上仍然遵循摩尔定律，那么硅片上的集成电路 最终将会缩小到不能再缩小的极限，即那些独立的组件只有几个原子这么大。这 导致了一个问题的出现，因为在原子级上支配着电路的行为和性质的物理规律是 量子力学，而不是经典物理定律。这就提出了个问题：能否设计以量子物理原 理为基础的计算机。 1 2 量子计算的主要研究成果 加利福尼亚理工学院的r i c h a r dp f e y n m a n 在1 9 8 2 年建立了一个抽象模型， 该模型显示了如何利用量子系统进行计算，他还解释了这类机器如何用做量子物 理学的模拟器进行运算。这意味着一位物理学家将能够在一台量子计算机内完成 对量子物理学实验的模拟。1 9 8 5 年，牛津大学的d a v i dd e u t s c h 发表了一篇非常 重要的论文。他在论文中证明，任何物理过程原则上都能很好地被量子计算机模 拟。因此，量子计算机具有超过那些传统计算机的潜力。1 9 9 4 年，供职于美国一 家电信运营商的p e t e rs h o r 博士在一篇论文中提出了一种利用量子计算机解决一 项重要数论问题的方法，即大数分解。他证明一套专为量子计算机设计的数学运 算可使这种机器以快的速度分解巨大的数字，速度比传统计算机快得多。随着这 个突破，对量子计算机的兴趣不再仅仅局限于学术界，而是引起了世界的广泛兴 趣。由于量子特性在信息领域中的独特功能，在增大信息容量、提高运算速度、确 保信息安全等方面将突破现有传统信息系统的极限，量子计算科学在过去几年的 发展可以用突飞猛进来形容 2 】。 量子计算在2 0 多年的研究发展过程中，取得了较大的进展。尤其是最近几年， 实验室一级的科研成果不断涌现。自1 9 9 5 年以来，已提出的量子计算机的方案主 要包括利用原子和光腔相互作用( c a v i t y q e d ) 、冷束缚离子系统( t r a p p e d i o n s ) 、 电子或核自旋共振( n m r ) 、量子点( q u a n t u m d o t s ) 、超导约瑟芬森结( j o s e p h s o n j u n c t i o n ) 及光子晶格( p h o t o n i c l a t t i c e ) 等量子系统。在美国，2 0 0 1 年m m 公司 阿曼顿实验室的科学家已建构了7 位的核磁共振量子计算机。i b m 的实验把原子 变为离子，并使用离子的两个内部自转状态作为一个量子位。然后使用微波脉冲 作为地址。但n m r 方法还不能生成1 5 个以上的量子位。m m 还在开发更有前 途的固态器件技术。n e c 于1 9 9 9 年通过使用j o s e p h s o n 连接制造了一个超导单电 子盒，从而证明了一个固态量子位。但由于需要量子位更长的一致时间，所以用 于实际的量子计算还有很长的路要走。2 0 0 3 年2 月，n e c 与日本的物理和化学 2 第一章引言 研究所合作，成功制造了第一个同态“集成”电路( 包含两个连接着电荷的量子 位) 。 1 3 量子计算的关键技术和挑战 目前，量子计算机的研发主要涉及如下三项关键技术：量子编码、量子算法 和量子硬件技术 3 】。 量子编码用于解决可靠性、纠错、避错、防错问题。量子信息论中，信息的载 体不再是经典比特，而是一个一般的二态量子体系，这个二态量子体系，可以是 一个二能级的原子或离子，也可以是一自旋为1 2 的粒子或具有两个偏振方向的 光子，所有这些体系，均称为量子比特。区别于经典比特，量子比特可以处于o 、 1 两个本征态的任意叠加态，而且在对量子比特的操作过程中，两态的叠加振幅 可以相互干涉，这就是所谓的量子相干性。已经发现，在量子信息论的各个领域， 包括量子计算机、量子密码术和量子通信等，量子相干性都起着本质性的作用。 可以说，量子信息论的所有优越性均来自量子相干性。但受环境的影响，量子状 态( s u p e r p o s i t i o n ：叠加态) 十分不稳定，不管是外部噪音还是观测都会形成对量 子状态的干涉，使存储在量子计算机内的信息崩溃，导致计算错误。比如，当观 测一个量子状态时，该状态会立即塌陷为某个确定传值( 0 或1 ) 。这种现象在量 子物理上叫做脱散( d e c o h e r e n c e ) ，是量子的固有性质。由此可见，量子计算非常 脆弱，非常容易出错，并且随着机器规模的增大，计算的可靠性急剧下降，使制造 规模大的量子计算机变十分困难，研究人员必须设计一种方法，将脱散和其它潜 在错误源控制在可接受的水平。这就是困扰整个量子信息论的消相干问题。因此， 要使量子计算成为现实，一个核心问题就是克服消相干。而量子编码是迄今发现 的克服消相干最有效的方法。主要的几种量子编码方案是：量子纠错码、量子避 错码和量子防错码。量子纠错码是经典纠错码的类比，是目前研究的最多的一类 编码，其适用范围广，但效率不高。量子避错码和量子防错码有别于量子纠错编 码，这些方案防错而不纠错，它们本质性地利用了量子比特消相干过程中的合作 效应。量子编码是信息论领域一个激动人心的进展。通过量子编码，人们看到了 克服消相干的希望，从而使得量子计算机和量子传输等可以从梦想变为现实。 量子算法是加速运算的关键( 主要不靠器件速度与集成度) 。到目前为止，人 们找到了两个比较成功的量子算法：s h o r 算法和g r o v e r 算法。未来还需要更多 能解决实际重大问题的量子算法，以证明在哪些问题上量子计算机的确比传统计 3 第。章引言 算机要优越。p e t e rw s h o r 在1 9 9 5 年写下了一个量子算法，使得完成一个礼位大 数的因子分解所用的计算步数只是他的多项式函数，而不是佗的指数函数。这个 被称为“s h o r 大数因子化”的量子算法，充分发挥了量子并行性的强大作用，原则 上可以在一年左右的时间内分解一个4 0 0 位大数。由于现有的加密系统大多是建 立在大数难于分解的基础之上，如果人们能够在实际中实现“s h o r 大数因子化 的量子算法，现有r s a 保密体制完成的任何加密就会被解密。因此，量子计算 会对由传统密码体系保护的信息安全构成致命打击，对现有保密通讯提出严峻挑 战。表现量子计算独特能力的另一项算法，是贝尔实验室的l k g r o v e r 设计的 量子搜索算法。计算机在搜索藏在有n 个对象的数据库中的一个特定的对象时， 经典的搜索过程要比较每一个对象，平均说来需要进行佗2 次尝试才有较大的可 能找到那个对象。经典搜索的一个日常生活的例子是在一个按人名索引的、共有 个人的电话簿里，找到确定号码的人，通常要找o ( n ) 次才能成功。g r o v e r 把 它换成量子力学问题就是：对于个态的均匀相干叠加，通过若干次基本的正交 变换可以把其中一个特定分量的几率放大为1 。g r o v e r 的量子搜索可以通过大约 、次尝试就找出所需的对象。 量子计算机研究中最突出的特点是物理学的原理和计算机科学的交融和相互 促进。计算机不再是一个抽象的数学模型，物理原理对计算机计算能力和效率的 限制愈来愈引起人们的重视。自从s h o r 提出大数的因子分解的量子算法后，基于 量子并行处理的一些超快速算法接连地被发现，现在已形成一门新的研究领域： 量子复杂性理论。另一方面，量子计算机中消相干的克服，在理论上和实验上都 是人们最关注的问题，量子纠错方案被寄予高度厚望。与量子计算理论上的突飞 猛进相比，量子计算机的实验方案还很初步。现在的实验只制备出单个的量子逻 辑门，远未达到实现计算所需要的逻辑门网络。实验物理学家正在寻找更有效的 制备途径，以克服消相干并实现逻辑门的级联。理论上虽然已提出各种量子纠错 码，但在实验上如何利用量子编码来有效地克服消相干，这还是一个富于挑战性 的问题。总体来讲，实现量子计算，已经不存在原则性的困难。按照现在的发展 速度，可以比较肯定地预计，在2 0 2 0 年前后，量子通信和量子计算机在技术上将 出现实用化前景。虽然道路曲折，但量子计算机一定会成为现实。 目前，人们在量子计算领域的研究主要集中于计算机科学中的离散问题。德 国f r i e d r i c h s c h i l l e r 一u n i v e r s i t 的e r i c hn o v a k 教授为量子计算中的数值分析领 域研究做出了杰出的贡献，他建立了h 5 1 d e r 类中积分问题复杂度的匹配上下界。 4 第一章引言 随后，一系列多变量函数积分等问题研究结果随之发表。其中，h u 和y e 建立了 关于各项异性h ( i l d e r n i k o l s k i i 类的他次估计最小积分误差的量子算法，并得出 了相应的s o b o l e v 类中的结论。 1 4 量子算法的数学描述 首先，我们给出量子计算模型的描述【4 ，5 】。 在非空集合q 中，定义丁( q ，r ) 为从q 到r 的函数集合。令f 厂( q ，r ) 。 定义s 为一个从f 到r 的连续映射。即，一个从输入值，到精确解s ( f ) 的解算 子映射。我们希望应用量子算法来估计s ( ，) 。 定义皿为二维复值希尔伯特空间c 2 ，为皿的m 倍张量积。对于n n ，定义 z o ，n ) ：= ( o ，一1 ， 其中n = 1 ，2 ，3 ，) 。令c k = ( i ) ：i z o ，2 m - 1 ) ) 为的标准正交基，其中 f i ) 为量子物理学中玩的d i r a c 定义，即一个n 1 矩阵 令甜( ) 表示上的一元算子集合。f 上的一个量子查询用如下的数组来表 示 q = ( m ，仇，m ”，z ，7 - ，p ) ， 对任意m ，m ，m ，n ，有m + 彬m 。z 是z o ，2 m ，) 的非空子集，且 7 ：z q p ：r _ z o ，2 m ) 为任意映射。定义m ( q ) ：= m 为q 中量子位元的数量。使得对于任意，f ，数 组q 定义一个查询算法q ，即 q ，协i z ) l ) ：= ：；：三兄尹，丁 ” 旧：主要， 第一章引言 其中i i ) l x ) l y ) c 名：= ，oc , n ，oc 一m ，一m ”，符号。表示模加法。 令数组a = ( q ，( ) 务o ) 代表f 上的无测度量子算法，其中q 是一个f 上 的量子查询，扎n o ，v j 4 ( h m ) ，并且仇= m ( q ) 。对任意f f ，我们有 a s “( ) ，且 a f = q s 巩一1 阢q ， 查询的数量定义为( a ) ：= 他。一个礼次查询的量子算法即是数组 a n = ( m ，b o ，q ，( 玩) l - o ，) ， 其中是的单位向量，称为基态；是一个函数，定义为 ：z o ，少) _ r 算法生成了如下状态： 状态b a 是可测的，给定取值于 o ，2 m 一1 ) 的随机变量白 ) ，b l 以概率h ，1 2 取值f 。算法的输出为 a 佗( ，u ) = ( 白( u ) ) 定义输入为f 的误差如为： e 口( s ，厶，) = i n f e o ：p i s ( f ) 一九( ，u ) i e 】1 4 ) ， 以及 e g ( s ，a ，f ) = s u p e q ( s ，a ，) f e f 我们定义他次最小查询误差为 e 墨( s ，f ) = i n f e q ( s a ，f ) ：n q ( a ) 礼，几n ) ， 即，所有少于n 次查询的量子算法的最小可能误差。 6 八v q 脚 = a = h 第一章引言 下面我们介绍积分问题。令d = 0 ，1 】d 为d 维单位正方体；定义c ( d ) 为d 上具有上确界范数的连续函数空间；定义f 为c ( d ) 的一个有界子集。考虑积分 问题s = i d 在f 上的解算子，将之定义为 i d = | ( t ) d t 我们介绍一些光滑函数类。对于1 p o 。，定义岛( d ) 为具有一般范数 的实值p 次幂l e b e s g u e 可积函数空间。令k = ( k 1 ，) n d 为一个多维 向量，其中| k i = k 1 + - i - k d 。引入微分算子泸= 0 1 k l 扩t z l 泸a 黝。对于 r n ，令孵( d ) 为具有嵌入条件r p d 的经典s o b o l e v 空间，它包含所有函 数f l p ( d ) 以及所有多维r n 量1 = ( 1 l ，l d ) 酽；对于i i i r ，其偏导分布 伊- 厂：= 0 1 1 i 厂- x l 驰x d 包含在k ( d ) 中。空间孵( d ) 是一个巴拿赫空间，其 范数为 i l f l l q ( o ) ：= l l 伊州以d ) - 令r n ，经典s o b o l e v 类定义为 呀( d ) = = ，吲巩i 烈删i l p ( i d ) 1 k ) 胚p 如、 i d ，故函数类孵( d ) 可嵌入进c ( d ) 6 1 。令7 n ，0 q 。i l 剪z 茎y ， 第一章引言 u ( ，吩，d ) p 是f 在方向j 的p 次连续模数，我们将其定义为 u ( ，乃，d ) p = s u pi i f ( + 乃勺) 一，( ) l k p ( d ) 0 口j d ，故函数类叼( d ) 可嵌入进 c ( d ) 。对任意r 畔，各向异性h 6 1 d e r n i k o l s k i i 类峨( d ) 定义为 聊卜 f el o o ( d ) ：畛s u p 。半产组吲小乩，d ) ， 其中 u a j ( f ，d ) 2 o s 叼u p 幻i l z ( ，) | l l m ( 。) 为方便起见，我们用f 凹来表示l 0 9 2 。令c ，c i ，i = 1 ，2 ，表示只由参数 r ，p 和d 决定的正常数。我们还经常使用同一个符号c 来替代不同的正常数。在 研究收敛率的时候使用符号和会带来很多方便：对两个非负数列a n 和k ， 符号k 表示有某个常数c 和佗o n ，使得对所有死n o 有a n c k ；符号 a 竹xb n 表示a 竹b n 以及a n 。 1 5 已知结论 下面我们列出一些关于函数类上的最优量子积分误差的已有结论。定义一个 巴拿赫空间x 的中心位于原点的单位球召( x ) ，其表达式为 ，x ：l i f l l x 1 。 由n o v a k 【1 2 】可知 定理1 1 令r m0 口1 ，有 e 嚣( 厶，磁( d ) ) , - 字 由h e i n r i c h 4 】可知 r 第一一章引言 其中 定理1 2 令r n ，1 p d ，有 n 一三一1 e ：( 厶，v 曙( d ) ) 他一三一1 口( 亿) ， 咖，= i ；嚣嬲，啪9 n 2 p p = 2 ( 1 1 ) 1 p 2 1 6 本文章节安排 本文研究各向异性s o b o l e v 类的量子积分误差。在第一章介绍了量子计算机 和量子计算的背景知识以及量子算法的一般模型。第二章给出本文得到的三个主 要定理，并采用已有方法证明了整数阶导数各向异性s o b o l e v 类的量子积分误差 上下界估计。在第三章我们采用一种新的约简方法重新证明了第二章中给出的三 个定理。最后，将量子算法下的积分误差与经典s o b o l e v 框架下的积分误差加以 对比，显示量子算法加速了积分问题的收敛阶。 9 第二章量子算法模型及结论证明 第二章量子算法模型及结论证明 在本章中，我们将分别讨论s o b o l e v 类上整数阶和非整数阶导数的量子积分 误差。 2 1 主要结论 对于整数阶导数我们得n t 如下结论： 定l 1 2 1 令，刚，1 p d ，我们有 ? z - 警一1 e 嚣( i d ，孵( d ) ) n 一掣一a ( 佗) 其中函数a ( n ) 如r j j j 中所示。 而对于非整数阶导数我们有 定理2 2 令r 畦，1 p d ，有 礼一警一1 e x ：( 厶，召( 孵( d ) ) ) nd i 矗，d iw 二( ) ) 定理2 3 令，r 苎，有 e 三( i d ，召( 吧( d ) ) ) x 仃一警 ( 2 1 ) ( 2 2 ) ( 2 3 ) 2 2 定理证明 定理 2 1 】， 2 2 】已由y e ，h u 在 1 3 】中得到，首先我们简要介绍他们的证明 方法。证明主要应用 4 】中为研究经典s o b o l e v 类而建立的离散化方法，然而，由 于本文研究对象所独有的各向异性和弱光滑性， 4 】中的很多条件将在如下分析 中被改变或替代。所以我们需要如下的关于插值和估计的结论。 引理2 4 f n o v a k1 1 4 1 ) 。令y 为c ( d ) 的n 维线性子空间；l ：v r 为一 个线性泛函。则存在a 1 ，a n d 以及c 1 ，c n r ，使得 三( ，) = q m t ) i = l 1 0 第二章量子算法模型及结论证明 对任意f v 成立，且有 n 三i | = m i = 1 引理2 5 ( d a h m e ne t 以，j 5 j l j 。令q 为一个边长向量为j = ( j 1 ，如) 的矩 形。对于任意r 刚，令只= 8 p a n i - 1 1 = lx ? ：k 刚，码 巧，歹= 1 ，田，且 令己p r ( q ) = ，如( q ) ：加。j f l p ( q ) ，j = 1 ，d ) 。 f f ) 对任意f 锑( q ) ，存在多项式g b 使得 其中c 独立于6 和，。 f 训对任意f c ( q ) ，存在多项式g 只，使得 ，一gil 。( q ) 仅西( ，6 ，q ) 。， 其中w , - ( f ，6 ，q ) 。：= 墨。( ，国，q ) 。 引理2 6 f h e i n r i c h 4 ) 。定义s ，t ：f _ r 为任意映射，他n o 。则下式成 立 e 嚣( zf ) c ( e 嚣( s ，f ) 4 - s u p ，fi t ( f ) - s ( f ) 1 ) 似j 如若s ( a ，) = a s ( f ) 对任意入r 及f f 成立，则有 e 墨( sa f ) = i 入i e ：( sf ) 引理2 7 ( h e i n r i c h 4 ) 。令f 厂( d ，r ) ，户厂( 西，r ) 为非空集合，定义 r ：f 一户为如下形式：对k ，m + n 存在映射 仍：d _ d ， 卢：r _ z o ，2 彬) ， p ：b z o ，2 m ) 尤_ r ， 使得对f f 以及s b ，有 ( r ( ，) ) ( s ) = o ( s ，pofo 伽( s ) ，p of o 班一1 ( s ) ) ( 2 4 ) 1 1 q “ l，j 勺 护 d p 一 醪 d 芦 c 一 q l 9 一 ，j 第二章量子算法模型及结论证明 给定一个定义如( 2 4 ) 的映射r ：f 一户，个由户到r 的算法a ，存在一 个从f 到r 的量子算法a ，使得 n q ( a ) = 2 仡n q ( a ) ， 且对任意f f 有 a ( f ) = 4 ( r ( ，) ) 因此，如果雪：户_ r 为任意映射且s = 雪or ，则有对任意的n n o 有 e ! k n ( s ，f ) e 墨( s ，f ) ( 2 5 ) 引理2 8 ( h e i n r i c h 4 d 。令d ，fg 尸( d ，r ) 为非空集合，k n o 且最：f r ( t = 0 ，k ) 为映射。定义s ：f _ r 为s ( 厂) = 岛( 厂) ( ，f ) 。令 记o ， l l , k n o 。 f f ) 假设o o ，o k 0 并令佗= 怎。佗l 。有 k知 e 嚣( se 吼) 铝。( 岛，f , o r ) r 别假设峋，魄n 满足e 一8 1 4 。令n = u r n f 。则有 知 e 罢( s ，f ) e ( 岛，f ) 1 = 0 下面我们引入有限数组均值计算问题。令蟛定义所有函数f ：z o ，) _ 冗 的空间，赋予其范数 忖忪= ( 嘉n 驴- 1 驯p ) m 若1 p 。，且 l 萏= 仇n z i 巾) i ：i ez o ，) ) ， 令召( 蟛) 为够的单位球。则解算子鼬：召( 矽) 一r 可定义为 & ，= 丙in 之- i 朋) 1 2 第二章量子算法模型及结论证明 定理2 9 ( h e i n r i c h j ，n o v a k1 1 6 1 ) 。令2 p 。存在常数c 1 使得对所 有的n ，n n 且2 佗e l n ，有 e ：( 踟，召( 三多) ) xt t - 12 p 2 且 定义实数r 为 故 m j ( r ) = g a r 2 f 】，j = 1 ， d 局= 1 0 9 m j ( r ) j = 1 d 局= j = l 9 ( r ) l o g o 。】 一g ( 舶扎“产】) = l o g ( f 。g ( r ) 者+ 专+ + 去】) 一g ( 暖和) 赤1 ) = l o g t o 1 3 第二章量子算法模型及结论证明 此时 略( r ) = 啦 f o 。】q f 吕( 】 x2 1 0 9 1 9 ) ( o 】 、， 9 1 0 9 1 0 g ( r ) ，、_ x2 p o g ( ，j = 1 ，d ( 2 6 ) 一 。 i - u ， 将立方体d 分割成2 p 0 。个适合的长方体五t 2 p o t - i d = u i = 0 正t 的边长向量为( - - 。1 丽，而1i ) 。定义噩i 中的最小坐标点为s “o 令局 ： c ( d ) 一c ( d ) 为可拓算子，定义为 ( e l ，) ( s ) = ( s u + m 一。os ) ， ( 2 7 ) 对f c ( d ) 和s d ，令a = ( r l 】+ 1 ，h 】+ 1 ) ，由引理2 1 可知存在c ( d ) 上的积分法则 一一1 g f = b j ( t j ) ， ( 2 8 ) j = o 其中r ，勺d 对任意，只成立，即，对任意，只，有 由引理2 5 ( i i ) 和( 2 9 ) 可知 g i = i d ( 2 9 ) i 厶，一g i l i n 一。fl 厶( 厂一9 ) 一j ( f 一9 ) i g e i n 一。fm a x ( 1 l 厶l l ，i i j i i ) l l f g i l l 。( d ) 一 9 p i “”、。7 o ( ，e ，d ) ， ( 2 1 0 ) 其中e = ( 1 ，1 ，1 ) 。对任意f n ，将了按比例分割为子长方形五i ，我们得到 了一个复合积分 1 4 2 ，j日 j 虬枷 一 2 = ， 以 第二章量子算法模型及结论证明 对fe 瞻( d ) 有 2 1 o l 一1 i 厶，一以，i = l 厶，一2 删，( 玩，) i i i = 0 2 m o l l = 2 咧l ( 厶( 玩川一j ( e l t 川 注意到 则有 故有 2 唰i 厶( 蜀t ，) 一j ( e t t 删 i = 0 2 p o t _ l c 2 一罚2 w a ( e t i f ，e ，d ) 。 ( 2 1 2 ) ( 既，1 ，d ) o 。= ( ，町1 ，死) ( ，町1 ，d ) i 町。l 勺 c 2 一p o g ( 。) f ( 2 1 3 ) ( 玩f ，e ，d ) c 2 一p o g ( 。” i d f 一五，c 2 - p o g ( 。” ( 2 1 4 ) 我们首先用积分以，来估计厶，给定一个预设的精确度，以及远大于n 的 结点。以将被分割成一系列单积分以。的和，结点数量为t , ，并定义任一积分 z ( f = k o ，k 一1 ) 。我们精确计算j k o ( f ) 并将z ，降低到边界范数为矽的一 致有界序列均值水平m 。详细过程如下： j f ：( 一如) ， 2 p 0 1 尤一l托一1 2 - p 0 b j f ( s l i + m 一。b ) 一b j f ( t j ) i = 0j = o j = o k 一1 = 嘭，( e ) ， ( 2 1 5 ) j = o 1 5 第二章量子算法模型及结论证明 其中 对f n o ，令 ，c x ( 2 p o + 1 ) 五，= ，( 岛。，) = 由( 2 7 ) 和( 2 1 1 ) ，我们得到 故 + m 一。e ) ， 2 v o f - i j j = 2 喝。五 i = 0 2 p o l 一1 也+ ，= 2 删 ( 既n i = 0 j l + l l j t f = 2 一p o 、 由( 2 1 3 ) 和( 2 1 4 ) ，我们有 2 一p o t 文1 2 p o l 一1 五， i = 0 厶( 岛t f ) 一 ( 局t ，) i c 2 一局 ：c 2 一局 2 p 0 - 1 如( 易t ，) ) ( 历l 。既f ，e ，i d ) = 0 ) - 12 p o - 1d ff t ：一：t i 0 = 0j = t c 2 一p o g ( r ) ( 1 + 1 ) j ( e l i f ，町1 ，五，硒) ( 2 1 6 ) ( 2 1 7 ) ( 2 1 8 ) ( 2 1 9 ) ( 2 2 0 ) ( 2 2 d 下面我们应用如【4 】所述的离散化方法。根据以上的估计，我们可以应用定 理2 9 来估计量子算法的均值。 对z 1 p ，由嵌入性质 1 0 】和引理2 7 ，有 f i l e ( o ) c l l f l l w ：, ( d ) 1 6 ( 2 2 2 ) 第二章量子算法模型及结论证明 固定一个m + n 使得 且 2 一m 2 c 其中常数c 同式( 2 2 2 ) 。所以对f 叼( d ) ，我们有 i f i l e ( d ) 2 m * 2 现在我们定义如下四个映射，令r l t ( i ) ：z o ，m ) _ d0 = 1 ，k 7 1 ) 如 定义p ：i r _ z o ，2 m * ) ： r i z j ( i ) = s 舷+ m 一。 雕卜 鲐”2 州2 。1 列 定义7 ：z o ，2 ) _ r ： ( 2 2 3 ) ( 2 2 4 ) ( 2 2 5 ) ( 2 2 6 ) z - - 2 m 。2 1 2 m * 2 1 名 2 m 。2 1 ，y ( 可) = 2 - ? 2 可一2 m 2 显然对于一2 m * 2 1 茎z 2 m * 2 一，有 1 ( p ( z ) ) z 1 ( p ( z ) ) + - m * 2 第四个映射p ：z o ，2 m ) k 7 _ r 定义为 其中，歹z o ，圪7 ) 是j f 的系数。 现在所需工具已全部给出，我们给定f 叼( d ) 的复合映射r l ，即 r f ( ，) ( i ) = p ( ( p 。，。他( z ) ) 刍1 ) 1 7 ( 2 2 8 ) ( 2 2 9 ) ( 2 3 0 ) ( 2 3 1 ) 协 7 ， 山伽 = ，一 珈 “ 第二章量子算法模型及结论证明 令x = s l t + ! i l 一4 。由( 2 3 0 ) 和( 2 3 1 ) 我们有 尤一1 五，一r f ( 以i ) l l a j i f ( x ) 一，y ( p ( 雕) ) ) i ( 2 3 2 ) j = o 由( 2 2 3 ) ，( 2 2 5 ) 和( 2 2 9 ) ，有 五，一f t ( ，) ( i ) l 由z 的表达式有 在【1 7 】中已证 c k 一1 2 9 ( p o ( 2 3 3 ) y , f 一f f ( 删c k 一1 2 一g ( ) 编 2 p 0 l 一1 2 一p 0 。i 五，i p c 2 一阳r 岛。 i = 0 根据( 2 3 3 ) ，( 2 3 5 ) 且f 七，有 r z ( ，) i i l f j ( 五，) 篓i 1 i l l p l + i ir f ( ，) 一t ，f 训f ，、i n ：i 。- 1 i l l p l 我们可以得到 c 2 - g ( r ) p 0 1 r z ( 吩( d ) ) c 2 一g 。) p 0 召( 矽) ( 2 3 4 ) ( 2 3 5 ) ( 2 3 6 ) ( 2 3 7 ) 选择满足以下条件的p 。 p m i n ( 9 ( r ) e o ，兰晶( 9 ( r ) 一( 三一1 ) ) ) ， ( 2 3 8 ) 且令 聊= 2 p o k o p ( 。 ， 功= 8 ( 2 t n ( t 一+ 1 ) + f n 8 ) ， 1 8 ( 2 3 9 ) ( 2 4 0 ) ，吩 伽 胆 m 一 2 一 第二章量子算法模型及结论证明 对l = k o ，k 一1 ，经过简单计算可得 令 知一1 f e - p d 8 1 4 ：一 f = k o 七一1 行= n + 2 仡7 u t n t z = k o 由m ，耽，k o 以及k 的定义可知 七一b 一1 h n + 2 t c ( 2 p 0 + 1 ) 2 眦 8 ( 2 l n ( + 1 ) + l n8 ) f 2 一 1 = 0 c 2 p o 血o c t t 由引理2 5 ( i ) 以及( 2 1 4 ) ，有 由于t c 2 p o k o n ， 有 故有 e ：( 厶，晖( d ) ) c 2 一g 局詹+ e 晏( 以，吩( d ) ) e i ( ，晖( d ) ，0 ) = 0 e i ( 以，晖( d ) ) e 嚣( 乩，晖( d ) ，0 ) + e q 锄( 以一，岬( d ) ) 七一1 e ( 彳，晖( d ) ) 1 = k o e ；七，m ( z ，晖( d ) ) c k - 1 2 一g 。岛七+ e ! 惫，m ( 鼠。n ，晖( d ) ) c k 一1 2 一g p 0 知+ c 2 一g d p 0 。e 茏( 。，召( 矽) ) 由以上四式，可知 南一1 e ：( 厶，晖( d ) ) c 2 一夕r p 0 七+ c z = k o 1 9 ( 2 4 1 ) ( 2 4 2 ) ( 2 4 3 ) 2 - g ( o p o t e q n 。( ，召( 矽) ) ( 2 4 4 ) 第二章量子算法模型及结论证明 由( 2 4 4 ) ，定理( 2 9 ) 和m 及k 的定义，我们证出2 p o o 时的上界 4 , ( z d ，晖( d ) ) 七一b 一1 c 2 一o ( r + 1 ) p o k o + c 2 一( g ( r ) + 1 ) p o k of2 一o ( r ) p o p v j _ - - ， l = o c 2 一( g ( r ) + 1 ) p o k o 饥一9 ( r 卜1 同样论证可知当1 p 2 时 e i ( 厶，叼( d ) ) c n 一9 ( r ) 一1 ( t o a , o i 而当p = 2 时 ( 2 4 5 ) ( 2 4 6 ) e ；( 厶，孵( d ) ) m 一9 ( ) 一1 ( 1 0 9 l o g n ) 姚l o g l o g l o g n ( 2 4 7 ) 由( 2 4 5 ) ，( 2 4 6 ) 及( 2 4 7 ) 可知 吲厶蚓驯何咖h 1 2 p o o ( 1 0 9 l o g n ) 3 2 l o g l o g l o g np = 2， ( 1 0 9n ) 2 p 一11 p 2 故由( 2 4 3 ) 我们完成了定理的上界证明。 现在我们证明下界。我们将h e i r t r i c h 在 4 】中使用的方法和处理各向异性类 的方法结合。只需证明类嵋( d ) ，2 p 0( 2 4 8 ) 定义l 矽| | 睇( d ) = c r 2 。令n n ，七= 豸1 ( 1 0 f f ( n c 1 ) + 1 ) 】，其中c l 如引理2 9 中 所示，且令n = 2 而七。可知 令 n ( 2 4 9 ) 他( t ) = 砂( m 。o ( t 一瓯) ) ， ( 2 5 0 ) 一0 他 而 p 9 2c + 七 而g o 厶c 第二章量子算法模型及结论证明 有 以及 厶哦= 2 一p o 七厶矽= a 1 2 一p o 南= 盯1 n ，( 2 5 1 ) 哦i | 叼( d ) c 2 9 一1 p o 南i | 睇( d ) = c 2 9 。一1 肋p 0 七c r 2 ( 2 5 2 ) 故考虑到如各分支的不相交性，我们有 萎b i ) i ，2 i = o 慨| p i 嘲2 p p o g ( r ) k ) 铷n - 1 峰 给定任意m + n 使得 m + 2 1 p o k p 取定p 和，y 如前文所定义。对f 8 ( 碜) 有 所以由( 2 2 9 ) ， ，( i ) l n 1 p ：2 p o k l p 2 m +