（计算机软件与理论专业论文）量子稳定子码若干理论研究.pdf

s t u d yo fs e v e r a lp r o b l e ms 烈 t h e o r yo f q u a n t u m st a bi l i z e rco d es ad i s s e r t a t i o ns u b m i t t e dt o s o u t h e a s tu n i v e r s i t y f o rt h ea c a d e m i cd e g r e eo fm a s t e ro fe n g i n e e r i n g b y x i n gm e i j u s u p e r v i s e db y p r o f e s s o rh a n w uc h e n s c h o o lo fc o m p u t e rs c i e n c ea n de n g i n e e r i n g so u t h e a s tu n i v e r s i t y 2 0 1 0 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除 了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获 得东南人学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示了谢意。 研究生签名：墅丞鱼日期：三：坦主：2 东南大学学位论文使用授权声明 东南人学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档， 可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密 期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括以电子信息形式刊登) 论文的全部内容或中、 英文摘要等部分内容。论文的公布( 包括以电子信息形式刊登) 授权东南大学研究生院办理。 勰醢新签名艋珙：址争 摘要 摘要 量子计算机理论上具有强大的计算能力，所以引起了人们极大的兴趣。要使量子计算机成 为现实，一个核心问题就是克服消相干带来的量子噪声，量子纠错码是解决这一问题的有效的 方法之一，而量子稳定子码是量子纠错码的一个类别。这是本论文研究工作的目的。 本文在总结量子纠错码基本理论的基础上，首先详细的给出了c s s 型量子码的构造性证 明，再次，研究给出了有限域上的另一类类似b c h 码的经典码，并证明与该经典码相对应的 【 ，k ，d m 量子码和扩展量子码【+ l ，k 一1 ，d + l n ( q 2 ) 都存在。二元域上构造扩展量 子码的过程主要采用了偶校验，运算在内积上进行；非二元域上构造扩展量子码的过程主要采 用了使得行向量各个元素相加为0 的方法，并借助了有限域上本原元的性质，运算在h e r m i t i a n 内积上进行。研究结论扩展了利用经典码构建量子码的范围，证明了扩展量子码的最小距离为 d + l ，并给出了有关经典非二元码校验位的构造及其相关纯量子码存在的构造性证明方法。 最后，提出了从一类 【，k ，d 儿纯量子码至u n - 1 ，k + 1 ，d m 纯量子码的基于矩阵初等变 换的新构造方法。该方法正确可行的构造性证明简单，易懂，理论结果显示出该方法对一类量 子码的构造非常实用。 【关键词】：稳定子码；内积；h e r m i t i a n 内积；初等行变换；校验矩阵 东南人学硕上学位论文 a b s t r a c t p e o p l ei n t e r e s t e dq u a n t u mc o m p u t e rf o rt h a tq u a n t u mc o m p u t e rh a sp o w e r f u lc o m p u t a t i o nt h e o r e t i c a l l y i tw a s n e c e s s a r yt of i n dae f f e c t i v em e t h o dt oo v e r c o m eq u a n t u md e c o h e r e n c et om a k eq u a n t u mc o m p u t e rp r a c i i c a l ， q u a n t u me r r o r - c o r r e c t i n gc o d e sw e r eo n eo fg o o dm e t h o d st og e to v e rd e c o h e r e n c e a l s o ，q u a n t u ms t a b i l i z e rc o d e s w e r eas o r to fq u a n t u me r r o r - c o r r e c t i n gc o d e s t h i sw a st h ep u r p o s eo fm yw o r k a l lt h eb a s i ct h e o r i e so fq u a n t u me r r o r - c o r r e c t i n gc o d e sw e r es u m m a r i z e d c o n s t r u c t i v ep r o o fo fc s s q u a n t u mc o d e sw e r eg i v e ni nd e t a i lf i r s t l y s e c o n d l y , ac l a s so fc l a s s i c a lc o d e ss i m i l a rt ob c hc o d eo v e rf i n i t e f i e l d sw e r eg i v e n ，a n dt h ee x i s t e n c eo fb o t hc o r r e s p o n d i n gq u a n t u mc o d e s 【i n ，k ，d 】口a n de x t e n d e dq u a n t u m c o d e s 【 + 1 ，k l ，d + l 】q ( 9 2 ) o f t h o s ec l a s s i c a lc o d e sw e r ep r o v e d o nt h eb i n a r yf i e l d ，t h ec o n s t r u c t i o n p r o c e s so fe x t e n d e dq u a n t u mc o d e sm a i n l yu s e dp a r i t y , a n dt h eo p e r a t i o nw a sc a r r i e do u t o ni n n e rp r o d u c t o nt h e n o n b i n a r yf i e l d ，t h ec o n s t r u c t i o np r o c e s so f e x t e n d e dq u a n t u mc o d e sm a i n l ya d o p t e dt h a tt h es u mo fe v e r yd e m e n t o ft h ev e c t o ri s0 。t h ec h a r a c t e ro fp r i m i t i v ee l e m e n tw a su s e di nt h ec o n s t r u c t i o na n dt h eo p e r a t i o nw a sc a r r i e do u t o nh e r m i t i a ni n n e rp r o d u c t r e s e a r c hr e s u l t se x p e n d e dt h er a n g eo ft h ec o n s t r u c t i o no fq u a n t u mc o d e su s i n g c l a s s i c a lc o d e sa n dp r o v e dt h a tt h em i n i m u md i s t a n c eo fe x t e n d e dq u a n t u mc o d e sw 鹤e q u a lt od + 1 硼1 e c o n s t r u c t i o no fc h e c kb i t so fc l a s s i c a ln o n b i n a r yc o d e sa n dt h ec o n s t r u c t i v ep r o o fo fe x i s t e n c eo fr e l a t e dp u r e q u a n t u mc o d e sw e r eg i v e ni nt h er e s e a r c hr e s u l t s i nt h ee n d , an e wc o n s t r u c t i o nm e t h o db a s e do ne l e m e n t a r yt r a n s f o r m a t i o nw a sp u t t e df o r w a r d ，w h i c h c o n s t r u c t e dac l a s so f p u r eq u a n t u mc o d e 【一1 ，k + i ，d 儿f r o mac l a s so f p u r eq u a n t u mc o d e n ，k ，d i 口t h i s m e t h o di ss i m p l e ，s t r a i g h t f o r w a r da n d e a s yt oi m p l e m e n tb yc o m p u t e ra n da l lk i n d so f h a r d w a r e k e yw o r d s ： s t a b i l i z e rc o d e s ；i n n e rp r o d u c t ；h e r m i t i a ni n n e rp r o d u c t ；e l e m e n t a r yr o wt r a n s f o r m a t i o n ； p a r i t y - c h e c km a t r i x 目录 目录 摘昙蕈i a b s t r a c t i i 第一章绪论l 1 1 弓i 言1 1 2 国内外研究现状2 1 3 论文安排及研究成果4 第二章量子纠错码基本理论5 2 1 经典纠错码5 2 2 量子比特7 2 3 量子码的错误模型8 2 4 稳定子码1 1 第三章c s s 型量子码1 3 3 1 基础知识1 3 3 2 构造方法1 4 3 3 ，j 、结1 6 第四章有限域上的一类量子码。1 7 4 1 基础知识1 7 4 2 二元域。1 9 4 3 非二二元域2 0 4 4 ，j 、结2 3 第五章基于初等变换的量子码的新构造一2 4 5 1 基本定义和定理2 4 5 2 构造方法2 6 5 2 1 【n ，k + 1 线性码的构造2 6 5 2 2 计算最小距离矿一2 8 5 2 3 【一l ，k + l ，d 】。纯量子码。2 9 5 3 编码效率分析2 9 5 4 ，、结3 0 第六章结束语3 1 至殳谢3 2 参考文献3 3 在校期间发表文章3 5 第一章绪论 1 1 引言 第一章绪论 二十世纪初，科学经历了一场革命，物理学遇到了一系列危机，一些预言如紫外灾，电子 必然进入原子核n 1 等无法用经典物理学理论解释这些预言到底对还是不对。但正是这场危机导 致了量子力学的诞生。量子力学揭示了世界的本源是量子的，物质的微观世界遵循的是量子规 律，无法用经典物理来解释；经典物理对物质世界的描述仅在宏观条件下是正确的。 现代计算机科学的发展与兴起是在二十世纪。伟大的数学家a l a nt u r i n g 在1 9 3 6 年发表的 篇令人瞩目的论文宣告了现代计算机科学的形成。t u r i n g 描述了一种称之为可编程计算机 的抽象概念，并证明存在一个通用t u r i n g 机可以模拟任何其他的t u r i n g 机。t u r i n g 的论文发 表后不久，第一台计算机就诞生了。 1 9 4 8 年c l a u d es h a n n o n 发表了通信的数学理论的文章乜1 ，给信息以定量的科学描述，标志 着信息论作为一门科学建立了。 伴随着信息存储、处理和传输技术的日益成熟，计算机科学和信息理论有了飞速的发展。 自19 4 7 年开发出晶体管以后，计算机硬件发展速度迅速。可是，随着计算机硬件的集成化技 术发展，电子器件越来越小，量子效应将会越来越明显，以致影响其原有功能；另一方面，早 在二十世纪六七十年代，人们就发现，能耗会导致计算机芯片的发热，影响芯片的集成度，从 而限制了计算机的运行速度。计算机的发展出现了瓶颈。这个问题的一个可能的解决方式是计 算机转向另外的计算机模型。量子计算机理论提供了解决方法，它基于量子力学的基本理论进 行信息处理。量子计算刮在密码学方面的潜在应用极大的推动了量子信息理论的发展。 1 9 9 4 年，p e t e rs h o r 等人n 们在量子叠加性和相干性这一量子最本质特征基础上提出了量子 并行计算的量子计算机理论，给出了大数因数分解的量子多项式时间算法，并且说明具有经典 计算机不可比拟的信息处理功能。这一理论的提出，引起了各国政府和学术界的轰动。1 9 7 7 年r i v e s t 、s h a m i r 和a d e l m a n 三人发明的r s a 公钥体系n ，就是利用两个大素数的乘积难以 分解来加密的。一旦基于s h o r 提出的大数分解量子算法的量子计算机投入使用，那么传统的 r s a 公钥体系将崩溃。 目前密码学加密原理利用的都是n p 问题，即窃听者在没有解密密钥的情况下，在有限的 时间内无法完成破译密钥所需的大量计算，从而保证信息的安全。但是，随着经典密码学的广 泛应用及社会科技的飞速发展，有些加密方法不再安全。比如，我国学者王小云教授就提出了 一种有效的攻击方案，破解了在信息安全领域广泛应用的m d 5 算法。更让人担忧的是，也许一 些重要加密算法实际上已经被某些国家破译，但是它选择了不公开。 面对经典加密信息的不安全性越来越高，人们开始寻找一种在物理基本原理上能够证明绝 对安全的通信手段。量子通信n 2 2 j 下好符合这一需要，量子通信的安全性依赖于量子力学中的 量子态叠加原理和量子不可克隆定理，在量子通信系统中，量子密钥系统采用量子态作为信息 载体。窃听一般有两种方式：一，对携带经典信息的量子态进行测量，从观测的结果获取所需 的信息，但是量子力学的基本原理告诉我们测量会引起量子态的变化，从而使收发双方用户发 现。二，直接在信息传输过程中复制，但是量子不可克隆定理禁止量子态的复制。因此采用量 子态作为信息载体能够准确的检测出是否存在窃听，从而保证信息通信的安全。 量子计算机是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物 理装置。虽然量子计算机还没有产生，但从“量子计算机”这个词的产生背景来看，它具有经 典计算机没有的两大优点：一，实现量子并行计算，计算速度非常快；二，能够模拟量子通信 东南大学硕士学位论文 系统。这两大优点本质上都利用了量子相干性。然而，在实际环境中，量子计算机的量子比特 不是孤立的，时刻与外部环境发生相互作用，破坏量子比特相干性，导致量子消相干。因此， 量子计算机实现的前提的核心问题是克服量子消相干带来的量子噪声。经过人们的研究发现， 量子纠错编码晗2 。3 引是克服量子消相干最有效的方法之一。量子纠错编码能使量子计算机在有噪 声的环境中进行有效的计算，使量子信息在有噪声的信道中实现可靠的通信。 量子纠错码理论已成为量子信息领域的研究热点，也是各国研究的热点，因为在当今信息 高度发达的社会，信息安全至关重要。 1 2 国内外研究现状 量子纠错码不是经典纠错码的简单推广，在量子情况下，编码存在着一些基本困难，表现 在如下三个方面口5 1 ： ( 1 ) 不可克隆性：经典纠错码一般通过复制引进冗余位来纠正出错的信息位，但在量子 力学中，量子态不可克隆定理禁止态的复制，所以在量子环境下，无法通过复制引进冗余位。 ( 2 ) 不可测性：量子纠错码在纠错时，需要进行测量以确定错误图样；在量子力学中， 观测一般会破坏所观测的量子状态，造成量子状态的塌缩，从而使恢复变的不可能。 ( 3 ) 差错是连续：经典码的错误是离散的，只有0 和1 之间的跃迁；但在量子情况下， 错误是连续的，对于一种确定输入态，其输出可以是二维复空间的任意态。 因为这些原因，量子纠错比经典纠错困难的多。事实上，直到1 9 9 5 年底至1 9 9 6 年，s h o r 和s t e a n e 才独立的提出了最初的两个量子纠错编码方案。量子纠错码通过一些巧妙的措施， 克服了上面的三个困难，具体如下： ( 1 ) 为了不违背量子态不可克隆定理，在量子编码时，单量子比特的态并不是复制为多 比特的直积态，而是编码为一个复杂的纠缠态。通过编码为纠缠态，既引进了信息冗余，又没 有违背量子力学的原理。 ( 2 ) 量子纠错在确定错误图样时，只进行部分测量。通过编码，可以使得不同的量子错 误对应于不同的正交空间，通过部分的量子测量( 只对一些附加量子比特，而不是对全部量子 比特进行测量) 使量子态投影到某一正交空间。在此j 下交空问，信息位之间的量子相干性仍被 保持，同时测量的结果又给出了量子错误图样。 ( 3 ) 量子错的种类虽然为连续统，但人们发现，它可以表示为三种基本量子错误的线性 组合。只要纠正了这三种基本量子错误，所有的量子错误都将得到纠正。 量子态的不可克隆性、不可测性和连续性等量子特性决定了量子纠错码与经典纠错码有着 本质上的不同。尽管不同而且相对困难，但是人们仍然兴致勃勃的开展对它的研究工作，并且， 研究成果不断涌现。 1 9 9 5 年量子纠错研究取得了重大突破。p e t e rs h o r m l 和s t e a n e b 7 1 在物理机制上，把复杂的 纠缠态量子错误归结和化简为只需考虑每个量子位上独立发生的错误，并且错误的类型只有三 种：比特反转错误，比特相位反转错误和相位翻转错误，抽象成三个p a u l i 矩阵 x ：f ? ! l ，】，：fu 叫1 ，z ：f 1u1 ，这三种错误的任意组合可以解决连续的量子码错误。基 klo lf0 jl o l ，j 于这种物理简化模型，s h o r 构造了世界上第一个量子纠错码 9 ，1 ，3 】。 1 9 9 6 年，c a l d e r b a n k ，s t e a n e 和s h o r 采用经典线性分组纠错码的思想，利用两个特殊的 经典二元纠错码设计了量子纠错码的第一个系统的构造方法叫s s 量子编码定理。 至此运用量子纠错码来更正错误的概念广泛的被学术界所接受，世界各地的研究人员相继提出 2 第一章绪论 各种类型的量子纠错码，也分为几种描述形式，如基于群论的稳定子码描述，基于图论的的量 子码描述。 1 9 9 7 年，c a l d e r b a n k ，r a i n ，s h o t 和s l o a n e 提出了一个构造量子纠错码的群理论框架， 这个框架可以简化对已知量子纠错码的描述，并且使构造新的纠错码变的方便。这个框架的基 础是群论，它基于一个特殊的有限a b e l 群歹。歹是向量空问碍”( 最= o ，1 ) ) 的七维辛自正交 子空间，那么i 有2 t 个不同的特征标，从而它的表示的作用空间( 2 一维复向量空间) 可以被 分解为2 个向量子空间的直和。其中的每个子向量空间都对应一个量子纠错码。这些理论最 终于1 9 9 8 年发表口引，极大的推动了量子纠错码理论的研究。 1 9 9 7 年g o t t e s m a n 提出了构造量子纠错码的稳定子体系，并引入稳定子体系的证明方法， 定义了稳定子量子纠错码，给出了量子纠错码和经典辛码之间的联系h 引。 1 9 9 9 年，s t e a n e 进一步改进完善了c s s 构造方法，使c s s 码的最小距离的参数更大，纠 错能力更强，并利用本原和非本原b c h 码构造了很多参数较好的码字h 1 j 。 1 9 9 5 年至1 9 9 9 年间，研究人员主要研究的是二元域上的量子码，当然以后也有研究。1 9 9 9 年及以后，研究人员开始研究p 元域上的量子码。 1 9 9 9 年，r a i n s 讨论了p 元域上的量子m d s 码，截短码，线性码等量子码n 刳。 2 0 0 1 年，a l e x e ia s h i k h m i n 等人利用非二元的错误基讨论了特征为g 的：域上的经典码 和g 元量子码的关系n 引。 2 0 0 2 年，马智和冯克勤教授利用有限酉几何的计数结果给出量子纠错码【 ，l ，k ，d 】口的一个 界，它可以看成是经典码g - v 界的量子模拟，并且用非构造性证明方法证明当n k + 2 d 一2 时， 则对充分大的素数幂q ，纯的稳定子量子码 ，z ，k ，d 口均存在；还证明了对每个奇素数p ，量 子码 6 ，2 ，3 1 1 ，和 7 ，3 ，3 】，均存在h 们。 2 0 0 6 年，s a l a ha a l y 等利用分圆陪集证明了最小设计距离和b c h 码是否包含它的欧氏 或h e r m i t i a n 对偶码的关系，而且分析了b c h 的维数和最小距离，并且由此推导出两类不同参 数的量子码引。 2 0 0 6 年，a v a n t ik e r t k a r 等描述了有限域上稳定子码的基本理论，文中阐述了迹辛型、迹 交替性、h e r m i t i a n 内积的概念；推导出稳定子码的最小距离的上下界；证明了非二元域上的 c s s 码构造定理；并列举了若干量子码的构造方法，包括量子海明码，量子b c h 码，二次剩 余码，量子特征码等；系统地构建了有限域上非二元稳定子码的理论框架m 3 。 上面提到的基本上都是基于稳定子码描述方式的文章，还有量子码的其他的描述方式，只 是现在研究的相对较少。 2 0 0 1 年，s c h l i n g e m a n n 和w e r n e r 两人提出了通过构造具有某些特性的图来构造量子码的 方法，实质上利用有限域上的矩阵组合性质构造稳定子量子码，证明了每个图都等价于一个稳 定子量子码的稳定子生成元h 。 2 0 0 5 年，刘太琳等人利用s c h l i n g e m a n n 和w e r n e r 两人提出的构造量子码纠错码的图论方 3 东南大学硕士学位论文 法，给出了一个构造非二元量子循环码的方法；对于任意的奇素数p ，构造出量子码【 8 ，2 ，4 m 和 ，l ，l 一2 ，2 】，4 8 | 。 图论方法构造量子纠错码需要两个基本要素：无向图f = 缈，e ) ( 矿为定点集，e 为边集) 和有限阿贝尔群g 。无向图1 1 的顶点集v 可以区分为两类不相交的顶点集x 和y 的并集，即 矿= xu y ，勘厂、y = 矽。x 和】，分别表示输入顶点集和输出顶点集，其中输入顶点集代表想要 编码的逻辑系统，顶点集的大小和待编码的信息位数相等；输出顶点集代表编码后的物理系统， 顶点集的大小和编码后的比特数相等。图f 的邻接矩阵满足l = l ，l = o ，若l g i = p ，则 k g f ( p ) ；有限阿贝尔群g 的阶为单个量子信息位的维数。 1 3 论文安排及研究成果 本文主要研究了量子稳定子码若干理论。 第二章介绍了量子纠错码的基本概念和一般理论，为后续章节的介绍提供理论基础。 第三章介绍的c s s 型量子码是稳定子码的一种，c s s 型量子码的构造代表了稳定子码目 前的主要构造方法。 第四章和第五章是我们的工作，也是本文的核心。 第四章研究给出了有限域上的另一类类似b c h 码的经典码，并证明与该经典码相对应的 【，k ，刎 口量子码和扩展量子码【 + l ，k l ，d + l 珥( q 2 ) 都存在，并且扩展量子码 【+ 1 ，k 一1 ，d + l n 比量子码 【，k ，d 】。更适宜于信息的传递。 第五章提出了从一类 ，k ，d 儿纯量子码构造 一1 ，k + i ，d 儿纯量子码的基于初等变 换的新构造方法。该方法用初等变换将 ，k ，d 珥纯量子码相对应的经典码的生成矩阵和校验 矩阵化成阶梯形，据此构造新的生成矩阵和校验矩阵，形成新的经典码，从新的经典码可以构 造出【 一l ，k + i ，d 地纯量子码；而且最后分析了两者的编码效率。 第六章是全文的总结。 4 第二二章量予纠错码基本理论 第二章量子纠错码基本理论 本章介绍有关量子编码的基本概念和一般理论，作为后续章节的基础。 2 1 经典纠错码 噪声是通信系统无差错实现的一大障碍，为了克服这一问题，出现了编码理论。编码理论 是提高信息传输可靠性的一种重要手段，分为信源编码和信道编码。对于信源编码来说，由于 信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，因此，信源编码的主要任务是 减少冗余度，提高编码效率。具体说，就是针对信源输出符号序列的统计特性，寻找一定的把 信源输出符号序列变换为最短字序列的方法h 引。信道编码是以信息在信道上的正确传输为码表 的编码，信道编码的实质是在信息码中增加一定数量的多余码元，使它们满足一定的约束关系， 这样，由信息码元和监督码元共同组成一个由信道传输的码字。一旦传输过程发生错误，则信 息码元和监督码元间的约束关系被破坏，在接收端按照既定的规则校验这种约束关系，从而达 到发现和纠正错误的目的。我们所说的纠错码就是上述的信道编码。 下面我们举例说明一种最简单的纠错码一重复码。考虑一个有噪声的信道，通过该信道发 送1b i t 的信息。由于信道受到噪声的影响，信息在传输过程中容易出错，为了尽量减少出错 率，可以采用重复码。方法是在传送1b i t 信息之前将信息o 或l 重复三次再发送出去。即分 别将0 ，l 编码为0 0 0 ，1 1 1 发送出去。由于受信道噪声的影响，0 0 0 或1 1 1 也许在信道中已经 发生改变，为了在大多数情况下保证接收到的信息是j 下确的，采用多数决定法译码。例如，收 到的信息是1 1 0 ，在1 1 0 中l 出现2 次，0 出现1 次，根据多数决定法，可以判定要传送的信 息是l 。根据多数决定法，如果接受方收到的信息是0 0 0 ，0 0 1 ，0 1 0 或1 0 0 ，将被译码为0 ； 如果接收端收到的信息是1 1 1 ，1 1 0 ，1 0 1 或0 1 1 将被译码为l 。 采用重复码的编码方式，译码失误的概率是一定要考虑的。假定传输的3b i t 里有2b i t 以 上在信道中发生错误，那么大多数决定法译码必定失败。假设lb i t 信息在信道传输过程出现 1 错误的概率为p ( 0 4 ) 中的信息，因此无法判断接收信息的对错。为了使接收端可以判 断接收的信息的对错，可以将g ”个信息用长为，l 仰 m ) 的向量表示，这些向量形成c 的子集 s 东南大学硕：卜学位论文 合s ，并且蚓= q m 。s 中的向量代表信息，而其余的q ”一g “个向量没有意义。发送端将s 中 一个信息通过信道发送到接收端，如果接收端收到的信息不在s 中，则接收到信息肯定是错误 的，如果在s 中，接收到的消息的对错的概率依赖于s 选择的是否恰当。 将上述的s 加上代数结构变为露的向量子空间c ，设k ( 1 k 以) 是向量子空间的维数， 则c 存在一组基“l ， 2 ，“t ，其中u f = ( 口订，口j f ，1 ) ( 1 i 尼，口 ) ，因此c 中每个码字c 可以 表示为“l ，“2 ，“t 的线性组合，即c = b l u l + b 2 u 2 + b k u ( b i ) 。设 g = “l u 2 ： “七 f a i l a 1 2 l = l i i l a k 2 任意码字c 都可以表示为c = b l u 。+ b 2 u ：+ 以“。= ( 岛如以) g ，称g 为码字c 的生成矩阵。 从另一方面， 的向量子空间c 可以看成是变量为x i 工：，x n 的方程 b l l 而+ 6 1 2 石2 + 6 i 。h = 0 b 2 l 工l + b 2 2 而+ 6 2 。= 0 ； 吃吨l x l + 以吨2 而+ 饥吨 z h = 0 的解空间。其中系数矩阵 h = ： 6 l 。 6 2 。 吃叱l乞吨2吒吨。 是上的，l k 行，l 列的矩阵，并且秩为刀一k 。 岛l 五十岛2 x 2 + 饥。h = 0 b 2 i x l + b e 2 工2 + 如 z n = 0 ： 吃一t 1 x l + b n t ，2 x 2 + b n t ，”石 = 0 可以写为 kx 2 吒) r = 0 ， 所以v c c ，h c r = 0 。所以可以称日为校验矩阵。若接收端收到的信息为y ，所以可以用m y r 是否为0 判断y 是否在c 中。若毋r 0 ，则y 不在c 中，信息在信道中发生错误。译码误码 6 ， 1j 三 一 h 口 口 第二章量了纠错码皋本理论 率的好坏在于g 的选择是否恰当。 定义2 1 ：设“= 0 。“：u n ) ，y = p 。v ：y 。) 巧，向量“的汉明权重w ( 甜) 定义为 非零分量“，( 1 i 刀) 的个数，即以“) = i l i ，z ，材f 0 ) 。向量“和1 ，的汉明距离d ( u ，1 ，) 定义为 “和，相异位的个数，即d ( u ，) = i l i 甩，“f u ) = w ( u 一，) 。 定义2 2 ：对于码长为，z 的q 元码c ，c 的最小距离d = d ( s ) = m i n d ( u ，v ) l u ，1 ，s ，“订。 定理2 1 若d 为码c 的最小距离，则码c 可检测出最多d l 位错误，纠正最多【- 孚j 位错误。 若c 是参数为 ，z ，k ，d 】的码字，则表示c 是码长为以，信息位长为k ，最小距离为d 的码字。 2 2 量子比特 比特( b i t ) 是经典信息的基本概念，经典比特只有两个状态0 或1 。而量子比特( q u b i t ) 是量子信息的基本概念，与经典信息不同的是量子比特除了有l o ) 和1 1 ) 两个基态之外，量子比 特可以是l o ) 和1 1 ) 状态的线性组合，称为叠加态。例如l 少) = a o ) + b 1 1 ) 也是量子比特的一个态， 其中口，6 是复数，并且h 2 + 1 6 1 2 = 1 ，也是说量子比特的态是二维复向量空间中的向量。 考虑二元域上一个码长为n 的量子比特系统，这个系统是由n 个复二维向量空间c 2 通过张 量积运算所得到的2 4 维复向量空间c r = c 2o c 2p c 2 ，这个系统的基态形如i 而恐矗) ， 并且h 工：) = i x ，) i x ：) o i x 。) ，例如l 1 0 1 ) = 1 1 ) o l o ) p 1 1 ) 。一个具有刀位量子位的态是 2 ”维复向量空间的一个矢量，并且这个空间的基为f ) i = 0 , 1 ，2 8 一1 ) ，那么这个，l 位量子态 可以表示为l 西= 口，l i ) ，其中xa 小= 1 。 对于经典比特，可以很容易的判断某一个比特是0 还是1 ，但对于量子比特却并非易事， 而且量子比特的状态是以概率的方式变成比特信息。例如l y ) = 口l o ) + 纠1 ) ，我们不知道口，b 的 值，也不知道l y ) 的所传输的信息是0 还是1 。首先算概率，i 沙) = a l o ) + b 1 1 ) ，测量后取到0 的概率是i ( o j i f ，) 1 2 ，取到1 的概率是i ( 1 1 5 f ，) 1 2 ， 东南大学硕一 ：学位论文 ( o 陟) = 口( o i o ) + 6 ( 0 1 1 ) = 口 ( 1 陟) = a ( i o ) + b ( 11 ) = 6 即i y ) 以概率| 口1 2 取值o ，以概率1 6 1 2 取值1 。 2 ”一l 那么对形如i 缈) = 口，l i ) 的量子比特的信息是什么呢? 例如 i = o i 驴) = a i l 0 0 ) + a ：0 1 ) + a ，1 0 ) + a 。1 11 ) ，它的信息是0 0 ，1 0 ，0 1 还是1 17 与单个的量子比特情况 相同，通过测定量子比特可获得概率，取经典比特的概率为 测定结果出现概率 0 0 l ( o o l q , ) j 2 = l 口。( o o l o o ) + 口：( o o l 0 1 ) + 口，( 0 0 1 1 0 ) + 口。( 0 0 1 1 1 ) 1 = 1 口。1 2 0 1 l ( 0 1 | 硝= i 口。( 0 1 1 0 0 ) + a 2 ( 0 1 1 0 1 ) + 吩( 0 1 1 1 0 ) + 口4 ( 0 1 1 1 1 ) 1 = 1 口：1 2 1 0 1 0 0 1 缈 1 2 = l 口。( 1 0 l o o ) + 口：( 1 0 1 0 1 ) + 口，o o l l o ) + 口。( 1 0 1 11 ) 1 - 1 口，1 2 1 1 i ( 11 1 o ) 1 2 = i 口。( 11 1 0 0 ) + 口：( 110 1 ) + a , ( 11 1 1 0 ) + 口。( 11 1 11 ) 1 = 口。1 2 即i 驴) = 口，i o o ) + 口：1 0 1 ) + 口，1 1 0 ) + 口。1 1 1 ) p a 概率i a , | 2 】玟0 0 ，以概率k ：1 2 取0 1 ，以概率i 口，1 2 取1 0 ， 以概率| 口4 1 2 取1 1 。i 伊) = 口】| f ) 取f 的概率为i 口f 1 2 ，值得说明的是，在测量i 缈) = 2 - i 口小) 时，不 管各个i 的概率是多少，只能得到某个特定的i 。而且，在多量子比特的情况下，我们可以只 测定其中某一比特的概率。如对i 妒) = a 1 1 0 0 ) + a ：1 0 1 ) + 口，i l o ) + a 。1 1 1 ) ，若测定第一量子比特为0 的概率，只需要将第一位量子比特是0 的概率加起来即可，第一量子比特取值比特0 的概率是 i ( 0 0 1 o ) 1 2 + j ( 0 1 i 缈) 1 2 ，第一量子比特取值比特1 的概率是l ( 1 0 1 9 ) 1 2 + 1 0 1 1 o ) 1 2 。在做这样的测量后， 剩余的第二位量子比特发生变化。在测量第一位比特是0 后，第二位剩余量子比特的状态是 a l i o ) + a ：1 1 ) 在测量第一位比特是1 后，第二位剩余量子比特的状态是 a 3 i o ) + 口。1 1 ) 着测定第二量子比特代表的信息，按照单量子比特的方法测定其概率即可。 2 3 量子码的错误模型 若接 在经典数字通信信道中，若信息x = ( x lz ：x 。) 在信道传输中发生错误 占= ( 占。占：s 。) ，则接收端接收到得信息为y = x + s 。在量子通信中，如果信息非零向量 8 第二章量了纠错码罐本理论 i y 7 友生错误，会句：甚样明毂字公瓦? 对于二元域，量子通信中基本的错误只有比特反转错误，相位翻转错误，比特相位反转错 误三种。比特反转错误用矩阵x 表示，x = ：习；相位翻转错误用矩阵z 表示，z = 三二 ， 比特相位反转错误用】，表示，y = i x z = i ? ：l ( f 2 = 一1 ) 。如果不发生错误，则用，表示， ，= 口0 。任何错误都是这四种错误的组合，所以可将错误算子占写成 s = w l w 2 圆o ( w f x ，y ，z ，) ，1 i n ) 。 设信息向量l v ) = l v 。v ：v 。) ，如果信息向量i v ) 在信道传输中发生错误s ，则接收端收到的 量子信息为s i v ) ，占i v ) = w l i v 。) ow 2 i y ：) 固ow 。l v 。) 。 举例：s = xo z ，l y ) = a l o o + b 11 ) ，则 f i v ) = ( x o z ) ( 以i o o ) + 6 1 1 1 ) ) = 厦x i o ) 圆z l o ) + 色r 1 1 ) p z l l ) = 口1 1 ) 圆l o ) + 6 i o ) 圆( 一1 1 ) ) = 口i l o ) 一6 1 0 1 ) 所有错误算子组成的集合e = i a w l 圆w 2 固i o 五3 ， j ，x ，y ，z o i ，1 ) ) 是 一个乘法群，其中p = i a w , ow 2 圆ok 和e = f 彳w ：oto p 吨乘法的定义规定为 e e = 彳( w 1w ：) 圆( 以) 。 为了使用及计算的方便，将错误算子p = f zw l 圆w 2o 0 ( w f ，彳，y ，z ) ) 表示成 e = i a x ( a ) z ( b ) ，a = ( 口la 2 a n ) 霹，b = ( 包也包) e ，其中 ( 口，包) = ( 0 ，o ) ( 1 ，0 ) ( o ，1 ) ( 1 ，1 ) 对于一个错误算子e = f 五w 1 圆w 2 固0w n = i a x ( a ) z ( b ) ， 定义e 的量子权 ( e ) = o l w , ，1 f 玎) 。 定理2 2 ：x ( 口) 和z ( 6 ) 分别作用于l v ) = l v 。y ：屹) ，贝t lx ( a ) l v ) = l 口+ v ) ，z l v ) = ( 一1 ) 扣1 v ) ；如 9 、l ， n 一 z ，i 口) ，i 石) 。 设厶表示2 2 的单位矩阵，吒= ? 三 ，吒= 墨 x ( o ) = 1 20 1 2 , x ( 1 ) = 1 2 o x x ( a ) = 仃，01 2 ，x ( a ) = o r ，o 盯， z ( o