（计算机软件与理论专业论文）量子信息处理中的纠缠态及其应用.pdf

量子信息处理中的纠缠态及其应用：摘要摘要量子信息学是量子力学与信息科学的结合。它利用量子系统来实现信息的产生、存储、编码、传输、抽取、转换等任务。纠缠态是量子力学所特有的一种现象，在经典物理中没有对应。一般情况下，量子信息处理都要借助纠缠态来实现。本文讨论了量子信息处理中的纠缠态的性质及其应用。首先，我们分析了处于混合态的系统，说明它们实际上都是包含它在内的更大的扩展纠缠态系统的子系统。但是因为我们无法观测到扩展系统的其它部分丽表现为定域的( 能够观测到范围内的) 混合态。我们给出了由混合态构造它的扩展纠缠态系统的方法。一般情况下，一个混合态对应的扩展系统纠缠态可能有无穷多种，它们彼此相差一个幺正变换。可以证明，对于定域的操作和测量，所有的扩展系统纠缠态是等价的，因此，我们可以根据需要选择最方便的构造方法。进一步，我们提出“混合态不同于纯态的所有性质都是起源于扩展系统的纠缠”的假设。我们证明了对于定域的观察者，他所观察到的混合态的性质及其演化与整体的观察者看到的扩展系统的子系统的性质及其演化是完全等同的。对于所有的可观测量，例如平均值、测量值、s h a n n o n 熵、冯诺伊曼嫡等，定域的观察者所得到的观测值与整体的观察者对于子系统得到的观测值都是相等的。同时，混合态的幺正变换与扩展系统的幺正变换也是一致的。最后，混合态的算符和表示与扩展系统对应的算符和表示也是一致的。纠缠态的本质是各个部分测量结果之间的关联，而冯诺伊曼熵是混合态不同于纯态的最重要的性质。我们证明了混合态系统的冯诺伊曼熵与相应的扩展纠缠态系统的各部分之间的关联对于问题的描述是一致的。根据“混合态不同于纯态的所有性质都是起源于扩展系统的纠缠”的假设，我们提出了“子系统混合态的性质可以用来作为整体系统纠缠的度量”的思想。混合态与纯态的最重要的区别是冯诺伊曼熵不等于零，所以，冯诺伊曼熵可以用来作为纠缠的度量。据此，我们给出了三量子位系统中纠缠度的概念及其计算方法。第一，三量子位系统中每一个量子位之所以成为混合态，完全是因为其他量子位与它的纠缠，所以，可以定义某个量子位与其他所有量子位组成的集体的纠缠度为：三量子位系统关于该量子位的约化冯诺伊曼熵。第二，处于纠缠态的三量子位系统关于某两个量子位的约化子系统是一个处于混合态的双量子位系统。所以，三量子位系统中任意两个量子位之间的纠缠度可以定义为：三量子位系统关于这两个量子位的约化密度矩阵的e n t a n g e l m e n tf o r m a t i o n 上述定义可以推广到任意的n 量子位系统：任意一个量子位与其他量子位集体的纠缠度即等于a 量予位系统关于该量子位的约化冯诺伊曼熵；任意两个量子位之间的纠缠度即等于n 量子位系统关于这两个量子位的约化子系统的e n t a n n g l e m e n tf o r m a t i o n 纠缠的本质是非定域性，然而，非定域性的存在不一定需要纠缠态。某些正交直积态也可以具有非定域性。因此，研究纠缠与非定域性的联系与区别是一个非常重要的任量子信息处理中的纠缠态及其应用：摘要务，本文中我们将给出初步的探讨。结合量子信息学的实际需要，我们定义非定域性为“整体系统的信息大于组成它的子系统信息的总和”，或者，更严格地，“各个子系统的定域测量不足以唯一确定整体系统的状态”。纠缠可以看作是一类特殊的非定域性，它的特别之处在于：作为整体性质的纠缠必然会影响到定域的子系统的性质，反过来，定域的子系统的性质可以用来描述非定域的纠缠性。广义的量子信息处理涵盖了量子信息学的所有领域。本文中，我们研究了纠缠态在量子信息处理的几个领域中的应用，主要是量子信息存储与提取，量子信息隐藏和量子密码学。我们对量子信息存储和提取做了一般性的讨论，提出了利用非最大纠缠态的量子信息隐藏方案和利用正交直积态的量子信息隐藏方案。我们提出了几种利用纠缠态的量子密钥分配方案，包括：利用纠缠态的高效量子密钥分配协议；不对称量子密钥分配协议；利用贝尔测量的量子密钥分配协议。量子力学的基本原理保证了它们的安全性。它们共同的优越之处是所有的量子位( 除了用作纠错的部分) 都对密钥的生成有贡献，因而是高效的。不对称密钥分配协议还可以被用来发展可能的量子公开密钥系统。我们提出了两种利用纠缠态作为身份标志的量子身份鉴别协议，任何没有身份标志的人都不可能通过鉴别。与经典身份鉴别协议相比，它的最大的优势在于量子身份标志是无法复制的，所以攻击者即使能够窃取身份标志也难免最终被发现。我们的量子身份鉴别协议不需要辅助的经典信息和经典通信过程。如果没有传输错误和攻击者，身份标志是可以重复使用的。关键词：量子信息处理，纠缠态，混合态，冯诺伊曼熵，纠缠度，非定域性，量子信息存储与提取，量子信息隐藏，量子密码学，量子密钥分配，量子身份鉴别量子信息处理中的纠缠态及其应用：a b s t r a c te n t a n g l e m e n ti nq u a n t u mi n f o r m a t i o np r o c e s s i n gx i a o y ul i ( c o m p u t e rs o f t w a r e )d i r e c t e db yr u q i a nl uq u a n t u mi n f o r m a t i o ni sas u b j e c to ft h ei n f o r m a t i o np r o c e s s i n gt a s k sw h i c hc o u l db ea c c o m p l i s h e du s i n gq u a n t u ms y s t e m i ti n c l u d e sq u a n t u mc o m p u t i n g ，q u a n t u mc o r r t r n u c a t i o n ，e n t a n g l e m e n t ，q u a n t u mc r y p t o g r a p h y , q u a n t u mc o r r e c t i o na n ds oo n t h i sd i s s e r t a t i o na d d r e s s e se n t a n g l e m e n ta n di t sa p p l i c a t i o ni nq u a n t u mi n f o r m a t i o np r o c e s s i n gh e r ew ep r e s e n tah y p o t h e s i st h a ta n ym i x e ds t a t ec a nb el o o ko na sas u b s y s t e mo fe n t a n g l e de x t e n d e ds y s t e m s ow ei s s u eah y p o t h e s i st h a ta l lt h ep r o p e r t yo fam i x e ds t a t eo r i n g i nf r o mt h eo t h e rp a r to f t h ee x t e n d e ds y s t e m se n t a n g l e m e n tw i t hi t w ea n a l y s i z ep o s s i b l eo r i n g i n a t i o no fam i x e ds t a t ea n ds h o wt h a ta n ym i x e ds t a t es y s t e mc a nb er e g a r d e da sas u b s y s t e mo fab i g g e re x t e n d e ds y s t e m i ts e e m sl i k eam i x e ds t a t es y s t e mb e c a u s ew ec a l l to b s e r v et h eo t h e rp a r to ft h ee x t e n d e ds y s t e m w eg i v et h em e t h o dt oc o n s t r u c tt h ee x t e n d e de n t a n g l e ds y s t e mo fam i x e ds y s t e m g e n e r a l l yt h e r ea r ei n f i n i t ee n g t a n g l e de x t e n d e ds y s t e m sw h i c ha r ea s s o c i a t e dt h r o u g hau n i t a r yo p e r a t i o nc o r r e s p o n d i n gt oam i x e ds t a t es y s t e m w ep r o v et h a ta l lt h ee n t a n g l e de x t e n d e ds y s t e ma r ee q u i v a l e n c ei f o n l yl o c a lo p e r a t i o no rm e a s u r e m e n ti sp e r m m i t t e d s ow ec a nc h o o s et h em o s tc o n v e n i e n tm e t h o dt oc o n s t r u c tt h ee x t e n d e ds y s t e m t h e nw es h o wt h a tt oal o c a lo b s e r v e ra l lt h ep r o p e r t ya n de v o l u t i o no fam i x e ds t a t es y s t e mi se q u a la st h a to ft h ee x t e n d e ds y s t e m ss u b s y s t e mt oa l lo b s e r v a b l ep h y s i c a lv a r i a b l e ，s u c ha sa v e r a g ev a l u e ，m e a s u r e m e n to u t c o m e ，s h a n n o ne n t r o ya n dv o nn e u m a ne n t r o y , w h a tal o c a lo b s e r v e rg e ti st h es a m ea sw h a tac o l l e c t i v eo b s e r v e rg e tf r o mt h es u b s y s t e m a tt h es a m et i m et h eu n i t a r yo p e r a t i o no f t h em i x e ds t a t es y s t e mi sc o n s i s t e n tw i t hc o r r e s p o n d i n gu n i t a r yo p e r a t i o no ft h ee x t e d n e ds y s t e m f i n a l l yt h eo p e r a t i o n s u n lr e p r e s e n to f t h em i x e ds t a t es y s t e mc a nb o i ld o w nt ou n i t a r yo p e r a t i o no f t h ee x t e n d e ds y s t e m t h ee s s e n c eo fe n t a n g l e m e n ti st h ec o r r e a l a t i o n sb e t w e e nt h es u b s y s t e mo ft h ee n t a n g l e ds t a t es y s t e mw h i l ev o nn e u m a ne n t r o yi st h em o s te s p e c i a lc h a r a c t e ri nw h i c ham i x e ds t a t ei sd i f f e e r e n tf r o map u r es t a t e s ot h e r em u s tb ec o r r e l a t i o n sb e t w e e nt h e m w ep r o v et h a tt h ev o nn e u m a ne n t r o ye n t r o yo fam i x e ds t a t ea n dc o r r e l a t i o n so fc o r r e s p o n d i n ge x t e n d e ds y s t e mi se q u i v a l e n c et od e s c r i b eap h y s i c a lp h e n o m e n o n o nt h eb a s i so fo u rh y p o t h e s i st h a ta l lt h ep r o p e r t yo fam i x e ds t a t eo r i n g i nf r o mt h eo t h e rp a r to ft h ee x t e n d e ds y s t e m se n t a n g l e m e n t ，w ec o n c l u d et h a tt h ep r o p e r t yo fm i x e ds u b s y s t e mc a nb el o o ko na sae n t a n g l e m e n tm e a s u r e a sk n o w nt h em o s ti m p o r t a n tp r o p e r t yo fam i x e ds t a t er e l a t i v et oap u r es t a t ei st h a ti t sv o nn e u m a ne n t r o yi sn o n z e r o i nae n t a n g l e ds t a t es y s t e m ，i t ss u b s y s t e mi si nm i x e ds t a t e s ow ec a nt a k ev o nn e u r n a ne n t r o ya sm e a s u r eo fe n t a n g l e m e n t w ed e f i n em e a s u r eo fe n t a n g l e m e n ti nt h r e e q u b i ts y s t e ma sf o l l o w s i i i量子信息处理中的纠缠态及其应用：a b s n a c t( 2 )t h er e a s o nt h a to n eo ft h et h r e e q u b i t si si nm i x e ds t a t ei sb e c a u s et h eo t h e rq u b i t si se n t a n g l e dw i t hi t s ow ec a l ld e f n et h em e a s u r eo fe n t a n g l e m e n tb e t w e e no n eq u b i ta n dt h eo t h e rt w oi sr e d u c e dv o nn e u m a ne n t r o yo ft h eq u b i t at w o - - q u b i ts u b s y s t e mo ft h ee n t a n g l e dt h r e e - q u b i ts y s t e mi sa l s oae n t a n g l e ds y s t e mw h i c hi si nm i x e ds t a t e t oal o c a lo b s e r v e rh ec a nu t i l i z ek n o w no u t c o m e so fm i x e de n t a n g l e db i p a r t i t es y s t e me n t a n g l e m e n tf o r m a t i o nt oc a l c u l a t eo u te n t a n g l e m e n tm e a s u r eb e t w e e nt h et w oq u b i m a c c o r d i n gt oo u rh y p o t h e s i s ，am i x e de n g t a n g l e dt w o q u b i ts y s t e mi si n d i s t i n g u i s h a b l ef r o mt h er e d u c e dt o w q u b i ts u b s y s t e mo fi t se x t e n d e ds y s t e m s ow ec a r ld e f m et h em e a s u r eo fe n t a n g l e m e n tb e t w e e nt w oq u b i t si nat h r e e - q u b i ts y s t e ma se n t a n g l e m e n tf o r m a t i o no f t h er e d u c e ds u b s y s t e mc o n s i s t i n go f t h et w oq u b i t s w ec a ng e n e r a l i z e dt h ei d e aa b o v et om u l t i q u b i ts y s t e m t h em e a s u r eo fe n t a n g l e m e n tb e t w e e no n eq u b i ta n dt h eo t h e rq u b i t si sr e d u c e dv o nn e u m a ne n t r o ya b o u tt h i sq u b i t ；t h em e a s u r eo f e n t a n g l e m e n tb e t w e e na n yt w oq u b i t si nt h em u l t i - q u b i ts y s t e m e n t a n g l e m e n ti si ne s s e n c en o l o c a l i t y b u tn o l o c a l i t yd o e s n tn e e dt ob ee n g t a n g m e n t s o m eu n e n t a n g l e dp r o d u c ts t a t ec a na l s os h o wn o l o c a l i t y s oi t si m p o r t a n tt os t u d yt h er e l a t i o n sa n dd i f f e r e n c eb e t w e e ne n t a n g l e m e n ta n dn o l o c a l i t y i nt h i sd i s s e r t a t i o nw ed e f m en o l o c a l i t ya s “i n f o r m a t i o no ft h ew h o l es y s t e mi s n te q u a lt ot h es u mo fi n f o r m a t i o no fa l li t ss u b s t e m ”，o r ，m o r es t r i n g e n t l y , “l o c a lm e a s u r e m e n tc a n td e c i d et h es t a t eo ft h ew h o l es y s t e me x a c t l y ”g e n e r a l i z e dq u a n t u mi n f o r m a t i o np r o c e s s i n gi n c l u d e sa l ls u b j e c t si nq u a n t u mi n f o r m a t i o ni nt h i sd i s s e r t a t i o nw em a i n l ys t u d ys e r v e r a lf i l e d s ，s u c ha sq u n t u mi n f o r m a t i o ns s t o r a g ea n de x t r a c t i o n ，q u a n t u mi n f o r m a t i o nh i d i n ga n dq u a n t u mc r y p t o g r a p h y w ed i s c u s sq u a n t u mi n f o r m a t i o ns t o r a g ea n de x t r a c t i o ni ng e n e r a l a n dw ei s s u et w oq u n t u mi n f o r m a t i o nh i d i n gp r o t o c o l s ：q u a n t u mi n f o r m a t i o nh i d i n gp r o t o lu s i n gn o n m a x i m a le n t a n g l e ds t a t e sa n dq u a n t u mi n f o r m a t i o nh i d i n gu s i n gp r o d u c ts t a t e s w ep r o v i d es e r v e r a lq u n t u mk e yd i s t r i b u t i o ns h c e m e sw h i c ha l la p p l ye n t a n g l e ds t a t e s ，t h e ya r e ：e f f i c i e n tq u a n t u mk e y d i s t r i b u t i o np r o t o c o lu s i n ge n t a n g l e ds t a t e s ；a s y m m e t r i c a lq u a n t u mk e yd i s t r i b u t i o np r o t o c o l ；q u a n t u mk e yd i s t r i b u t i o nw i t hb e l ls t a t em e a s u r e m e n t t h em e r i to fa l lt h ep r o t o c o l si st h a ta l lt h eq u b i t se x c e p ts o m ef o re r r o r - c h e c k i r i ga r ec o n t r i b u t i n gt ot h ek e y s ot h e ya r ee f f i c i e n t m o r e o v e rt h ea s y m m e t r i c a lq u a n t u mk e yd i s t r i b u t i o np r o t o c o lc a nb eu s e dt ob u i l dap u b l i ck e ys y s t e m w ep r o v i d et w oq u a n t u ma u t h e n t i c a t i o ns c h e m eu s i n ge n g t a n g l e ds t a t e sa si d e n t i f i c a t i o nt o k e n n oo n ew i t h o u tt h ei d e n t i f i c a t i o nt o k e n sc a np a s st h ea u t h e n t i c a t i o np r o c e s s t h eo fq u a n t u ma u t h e n t i c a t i o np r o t o c o li st h a tt h ei d e n t i f e a t i o nt o k e n sc a n tb ec o p i e d s oa ne a v e s d r o p p e rw i l lb ef o u n ds u r e l yi fs h es t e a lt h ei d e n t i f i c a t i o nt o k e n s o u rp r o t o c o ld o n tn e e da u x i l i a r yc l a s s i c a li n f o r m a t i o na n dc o m m u c a t i o n so fc l a s s i c a li n f o r m a t i o n i ft h e r ea r cn oe r r o r si nt r a n s m i t t i o na n dn oe a v e s d r o p p e r se x s i t i n g ，t h ei d e n t i f i c a t i o nt o k e n sc a nb e量予信息处理中的纠缠态及其应用；a b s t t a c tr e u s e d k e y w o r d s ：q u a n t u mi n f o r m a t i o n ，m i x e ds t a t e ，v o nn e u m a ne n t r o y , e n t a n g l e m e n t ，e x t e n d e ds y s t e m ，e n g t a n g l e m e n tm e a s u r e ，n o l o c a l i t y , q u n t u mc r y p t o g r a p h y , q u n t u mi n f o r m a t i o ns t o r a g ea n de x t r a c t i o n ，q u a n t u mi n f o r m a t i o nh i d i n g ，q u a n t u mk e yd i s t r i b u t i o n ，q u a n t u ma u t h e n t i c a t i o nv声明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。作者签名：鸯、轧寄日期：2 铲关于论文使用授权的说明中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、缩印或其它复制手段保存该论文。作者签名：毒晚字导师签名：e 积池穆日期：2 铲第一章绪论第一章绪论二十世纪技术科学最突出的成就是电子计算机及信息科学的产生、发展和应用。今天，信息科学对人类社会的发展和进步起着不可替代的作用。它深刻地影响了整个社会的面貌和发展方式，对人类的未来发展方向有着深远的意义。我们熟悉的“数字化”社会、“信息时代”等名词形象地体现了信息科学无与伦比的重要性。量子力学是二十世纪物理学最重要的成就之一，它使人类对于自然界的认识发生了里程碑式的突破。量子力学是微观粒子运动规律的概括和总结，与经典物理相比，它解释和预言了大量奇妙的物理现象。例如波粒二象性、隧道效应、纠缠态等等。这些现象不但是经典物理所不能解释的，而且是远远超出人们的常识之外。利用这些现象，科学家们实现了很多令人赞叹的技术奇迹，包括核能、激光技术、半导体材料等等。量子信息学是量子力学与信息科学的结合。它的核心思想是利用量子系统来实现信息的产生、存储、传输、转换等任务。由于量子系统不同于经典系统的独特性质，例如量子并行性、纠缠态等等。因此，相对于经典信息学，量子信息学也体现出一些非常惊人的特殊性质，从而可能赋予人们更强大、更安全、更灵活的计算能力和信息处理能力。近年来，量子信息学成为一门快速发展的边缘学科，成为计算机学家和物理学家共同关心的一个热点领域，在理论和实验上都取得了令人瞩目的突破。1 ，1 量子信息学的发展现状广义上说，量子信息学是量子力学与信息科学( 计算机科学) 的互相渗透与结合。它既包括量子力学在信息科学中的应用，也包括信息论的思想对于量子物理学的启发和渗透。后者是最近几年刚剐开始的研究课题，其核心思想是将“信息”的概念纳入物理学的范畴，研究它的本质和演化规律。某些研究者，如p r e s k i u ，甚至认为信息将成为物理学的基本概念之- - 1 1 。通常人们所说的“量子信息学”主要是指前者，它包括量子计算、量子密码学、量子通信、纠缠态等多个领域。本文中，我们按照美国物理学会( a m e r i c a np h y s i c ss o c i e t y ) 的网站提供的分类标准，把量子信息学的研究领域分为：量子计算，量子通信，纠缠态，量子密码学，量子纠错五个主要研究方向。下面我们分别介绍这些领域的发展现状。1 ，1 1 量子计算众所周知，电子计算机是一种利用电子元件进行计算的机器。它实现信息存储以及计算的基本单元是集成电路芯片上的逻辑电路原件。这些原件本质上都是宏观的物体，e t f 的性质和工作原理服从经典物理的规律。经典的计算理论实际上是建立在这些中国科学院博士学位论文：量子信息处理中的纠缠态及其应用规律基础上的逻辑抽象。然而，我们知道，经典物理适用的范围是宏观低速的世界，它并不是我们对于自然界最好最准确的描述。量子力学是更深入更能反映自然界本质和演化规律的科学理论。因此，理论上讲，将计算理论建立在量子力学的基础上是更合理的，甚至可能是更富有成果的。二十世纪七十年代以来，随着计算机科学的发展，两个不同方向上的研究使人们逐渐认识到一个崭新的可能性：量子计算机。首先，摩尔定律告诉我们，电子计算机的发展过程是一个不断小型化，不断在一块电路板上集成更多逻辑电路的过程。随着单位面积上集成的逻辑电路数目的上升，计算机的结构越来越复杂，功能不断增强，同时单个逻辑电路的尺度也越来越小。目前的芯片技术已经达到了0 ，1 微米( 1 0 - 7 米) 的量级。可以预见到，这个过程不可能无限持续下去，因为，单个原子的尺度大概是1 0 。o 米的量级。如果单个逻辑电路小到这个程度，那么它就会仅仅由少数几个原子构成，在这个尺度上，经典物理已经不再适用，相应的经典计算理论也就失去了基础。实际上，在远远大于这个量级的尺度上，即l o _ 9 1 0 8 米的量级上，量子效应对于逻辑电路单元的影响已经不能忽略。显然，按照目前芯片产业的发展速度，在不远的将来，我们就将面临这个问题。当组成逻辑电路的单元表现出量子效应时，经典的计算理论的基础就发生了动摇，相应的，今天的计算机的工作原理和技术实现都不可避免地面临变革。从这个角度说，量子计算机的出现是计算机科学发展的必然结果。另方面，早在芯片技术的发展迫使人们不得不考虑量子效应之前，为了克服经典计算机的一些本质缺陷，探索更强有力的计算技术，一些科学家就已经开始考虑量子计算的可能性。传统的经典计算过程是不可逆的过程，因而必然产生能耗，导致芯片发热，如果不采取有效的散热措施，就可能会引发错误和故障。二十世纪六、七十年代，随着大规模集成电路的发展，人们发现单位面积上能耗不断上升，发热量也随之上升，而散热却随着计算枫的小型化而越来越困难。这就严重地限制了芯片集成度的增加，从而限制了计算机的运行速度。因此，能不能设计一种不产生能耗的机器，从而一劳永逸地解决发热的问题昵? l a n d a u e r 最早研究了这个问题f 2 】，指出计算过程的不可逆性( 也就是能耗) 并非本质固有，而是来自予信息的擦除。如果对基本的逻辑电路加以改进。避开信息擦除过程，那么，计算过程就变成了可逆的，从而消除了能耗的问题。l a n d a u e r证明理论上这是可以做到的。b e n n e t t 更严格地分析了可逆计算过程 3 】，他证明了所有经典的不可逆的计算机都可以改造为可逆计算机而保持计算能力不变。沿着这条思路，b e n i o f f 最早探讨了服从量子力学的可逆计算机【4 】。但是，他并没有利用量子力学不同于经典物理的本质特征，例如叠加原理、相干性、纠缠态等，而是简单地考虑了利用微观粒子( 服从量子力学) 来构造纯粹的经典逻辑电路，其中信息的存储和逻辑门的操作仍然是完全经典方式的。因此，他的“可逆量子计算机”只不过是经典计算机的使用量子系统的实现。第一个认识到量子特性可能赋予计算过程意想不到的形式和威力的人是f e y m a n n ，他指出了利用量子力学特性来实现计算的可能性【5 】。随后，d e u s t c h 提出了第一个真正的量子算法【6 】，对于这一类特定的问题，存在多项式时间复杂度的量子算法，第一章绪论而经典算法是指数时间复杂度的。这是一个非常惊人的结果，它预示着量子计算机可能具有比经典计算机更强大的功能。量子计算的威力来自于所谓的“量子并行性”。根据量子力学，量子系统不仅可以处在确定的本征态，而且可以处于任意的无穷多种叠加态。与经典计算机中“位”的概念对应，通常把量子计算机中信息的最小单元叫作“量子位”，而“计算”操作是通过对量子位施加特定的幺正变换来实现的。每一个位都是一个量子系统，所以，它可以处于多个态的线性叠加态，因此，对叠加态的量子位进行幺正变换就可以一次性地同时计算出所有分量的值。然后，通过恰当操作和测量，我们就可以使不需要的值发生相消干涉，留下想要的结果。这个过程通常称为“量子并行计算”，它是量子计算的本质特征，也是量子计算机优于经典计算机的原因所在。1 9 9 4 年，a t & t 的s h o r 提出了一种可以在多项式时间完成的量子大数分解算法【7 ， 8 】，轰动了全世界。众所周知，大数分解问题是一个困难的问题，至今为止，还没有找到能够在经典计算机上完成的多项式时间算法。而且，大部分数学家认为，它实际上可能根本就没有多项式时间算法。这一事实对于密码学有着至关重要的意义。当前应用最广泛的公开密钥系统就是建立在r s a 加密算法的基础上的，而r s a 算法正是利用了大数分解的指数时间复杂度。s h o r 的发现表明。在量子计算机上可以轻而易举地破解r s a算法，从而使已有的公开密钥系统失去作用。这样一来，量子计算机就不仅仅是理论家思辨的对象，而且具有重要的应用价值，甚至可能从根本上改变密码学和计算理论的面貌。s h o r 的工作激起了人们的极大兴趣，使量子计算成为一个蓬勃发展的热点研究领域，同时也促使实验家们开始严肃地着手在实验室里探索制造量子计算机的方法。另一个重要的量子算法是g r o v e r 在1 9 9 6 年提出的量子数据库搜索算法 9 】。在n个元素构成的集合中寻找某个元素，最好的经典算法也要n 2 次的搜索才能达到1 2 的成功率，而g r o v e r 算法只需要4 n 次搜索就可以以同样的概率找到目标元素。当n 很大的时候，相对于经典算法，g r o v e r 算法是高效的。现在，越来越多的人们致力于研究新的量子算法，寻找将经典的n p 问题在多项式时间内解决的量子高效算法。同时，s h o r 算法的出现说明了传统的经典计算复杂性类的分类方法已经不适合未来的量子计算机。一些学者开始研究量子计算复杂性的理论问题 1 0 1 4 。除了解决具体问题的算法之外，另一个引人注意的方向是量子计算基础理论的研究。所有的经典计算机本质上都是一个通用图灵机，相应的量子计算机也可以归结为量子图灵机。量子图灵机的形式与经典的概率图灵机很相似，只不过它的运算结果不是按照概率相加，而是按照概率幅叠加。已经证明，量子图灵机至少与经典图灵机一样强大 1 5 】。1 9 9 3 年，姚期智证明了量子图灵机可以等价为一个量子逻辑电路 1 6 】，所以现实中的量子计算机可以通过量子逻辑电路的组合来实现。随后，很多人研究了如何使用量子逻辑电路来构造实用的量子计算机【1 7 【1 8 1 9 】，包括单量子位门，双量子位门以及任意的多量子位逻辑电路。最后，b a r e n c o 等证明了所有的量子逻辑电路都可以分解成双量子位的异或门与单量子位门的组合 2 0 1 ，从而为建造实用的量子计算机提供了坚实中国科学院博士学位论文：量子信息处理中的纠缠态及其应用的理论基础。经典计算理论中，自动机是计算机的一种简化模型，它虽然不如图灵机的功能强大，但是却能够模拟计算机的大部分计算过程。相对于图灵机，自动机更简单，更易于实现。因此，二十世纪六十年代以来，关于各种类型的自动机的研究发展迅速，成果累累，在计算机科学的很多领域都起着重要的作用。显然，量子自动机对于量子计算理论的研究也同样有着重要的意义。近年来，关于量子自动机的研究也引起了人们的兴趣【2 1 3 5 】，成为量子计算的一个非常活跃的研究领域。在量子计算机由理论设想走向实际建造之前，还有一个核心的问题需要解决，这就是纠错。量子计算机的优越性来自量子系统的特殊性质，如叠加态、纠缠态、幺正变换等，而所有这些都必须依赖于量子相干性。一旦失去了相干性，量子系统就退化成为经典系统，量子计算的优越性就完全消失了。然而，在实际系统里，维持量子相干性是很困难的，因为量子系统必然会与外界不断发生相互作用，其平均的结果即导致相干性丧失( 消相干) 。理论分析和实验都表明，一般情况下，消相干是不可避免的，而且会在极短的时间内即完成。除非能在消相干的特征时间之内完成计算，否则量子计算机就毫无意义。另一方面，在量子计算机的工作过程中也难免出现偶然错误，如逻辑门的误操作以及外界的噪声等，如果不能及时发现并纠正，错误将逐级传递并且放大，从而导致计算过程失去意义。解决这个问题的方法就是量子纠错，它最早是由s h o r 提出的，目前已经发展出量子纠错码、量子避错码、量子防错码等多种方案，我们将在1 1 5 节里做详细的介绍。最后，s h o r 证明了：在量子计算机中，只要门操作和电路传输的错误率低于一定的闽值，就可以正确地完成任意精度的计算。因此，量子计算机最后的一个理论上障碍也被克服，不再存在任何原则的困难，剩下的就是如何把它制造出来了。在理论研究的同时，很多科学家也积极着手在实验室里建造真正的量子计算机。首先要找到合适的量子系统来构成量子位，然后利用它实现各种量子逻辑电路。已经提出的方案有离子阱系统1 3 6 3 7 ，腔量子电动力学系统【3 8 】【3 9 】，核磁共振系统 4 0 】以及量子点系统 4 1 1 e 4 2 等。1 9 9 7 年，i s s a cc h u a n g 首先利用核磁共振实现了两个量子位的逻辑门。到目前为止，在实验室里已经成功实现了五个、七个量子位的量子逻辑电路：量子计算机的实验研究已经成为当代物理学和计算机科学的热点课题，不断取得激动人心的进展。当然，目前的技术距离真正实用的“量子电脑”还相差很远，仍然有很多基本原理和技术难点需要突破。最大的问题是如何操作与控制大量的量子位。最简单的d e u s t c h 算法只需两个量子位就可以实现，而演示s h o r 算法至少需要1 6 个量子位，目前的技术还达不到这个要求。如果要利用s h o r 算法来完成实用的因数分解任务( 破译r s a 加密算法) ，最少也需要数百个量子位。以现在的技术水平来看，短期内尚没有实现的希望。但是世界各地的许多实验室正在夜以继日地工作，随着时间的推移，实验家们可能利用上述的某种方案攻克难关，也可能会发明新的材料，新的实验手段乃至全新的设计方案，实现造出量子计算机的梦想。最后，可以毫不夸张地说，量子计算机一定会成为现实，并且将会给计算机科学与4第一章绪论技术带来深刻的变革，大大提高人类认识世界和改造世界的能力。1 1 2 纠缠态纠缠态是量子物理不同于经典物理的最奇特、最不可思议的现象，也是量予信息学区别于经典信息学的最独特之处。纠缠态在量子信息学的各个领域都有着广泛而重要的应用。本论文的主要内容就是探讨纠缠态的性质及其在量子信息处理中的应用。纠缠态最早是被爱因斯坦( e i n s t a i n ) 、波多尔斯基( p o d o l s k y ) 和罗森( r o s e n ) 的4 3 注意到的。根据量子力学，复合系统可以处在一种特殊的状态：系统的各个组成部分是不可分割的，对其中一部分的操作必然会影响到另一部分，即使各个部分之间是类空分隔的。这就是著名的e p r 佯谬。后来，人们就把子系统之间的这种神奇的联系称为”e p r 关联”，将处于最大纠缠态的双粒子复合系统称为“e p r 对”。随后，薛定谔将这种特殊状态叫作纠缠态 4 4 1 ，并且指出它是量子力学与经典力学最重要的区别之一。1 9 6 4 年，贝尔( b e l l ) 详细分析了量子力学所预言的纠缠态系统内部的关联，并且将其与经典的定域隐变量理论的结果进行比较，得出了著名的“贝尔不等式” 4 5 1 ，对量子系统的非定域性给出定量的描述。同时，是否满足贝尔不等式也成为量子力学与定域隐变量理论之间决定性的差别。1 9 8 2 年a s p e c t 等人的实验【4 6 精确地观察到了贝尔不等