（计算机软件与理论专业论文）基于图论的量子纠错码理论研究.pdf

r es e a r c ho n q u a n t u m e i 汛o r c o i u 冱c t 烈gc o d e sb a s e d o n g r a p h at h e s i ss 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 f e n g i n e e r i n g b y z h a n gj i n h u a s u p e r v i s e db y p r o f c h e nh a n 。w 1 1 s c h o o lo fc o m p u t e rs c i e n c ea ne 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 67 iii6帅7 1洲y 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得东南人学或其它教育机构的学位或证二伟而使川过的材料。与我一同i j 作的同：占对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：j 篁蜱日期： 弘f 羔彬 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图抒馆有权保留本人所送交学位论文的复印件和电子文 档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除 在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括以电子信息形式刊登) 论文的全部 内容或中、英文摘要等部分内容。论文的公布( 包括以电子信息形式刊登) 授权东南人学研究生院办理。 觥躲和钎一名海喵一& w 东南人学硕： = 学位论文 摘要 1 9 9 4 年，p e t e rs h o r 给出了关于大数质因子分解的多项式时间内可解的量子算法。之 后人们又发现了各种各样的快速量子算法，但是由于量子的退相干性，如果不加入量子纠 错技术，实现任何量子算法将十分困难。直到1 9 9 5 1 9 9 6 年，s h o r 和s t e a n e 分别独立提出 了两个著名的量子纠错码方案，之后量子纠错码的研究进展很快。2 0 0 1 年，s c h l i n g e m a n n 和w e m e r 两人提出了通过构造具有某些特性的图来构造量子纠错码( 图态码) 的方法。之 后基于图的量子纠错码编码方案也在快速发展。 基于稳定子理论来构造稳定子码的理论现在比较成熟，而基于图理论的方法来构造量 子纠错码的方法现在还没有系统化的方法，但是图态码和稳定子码之间有等价关系，可以 借助稳定子理论来研究图态码。 本文首先介绍了量子纠错码的基础理论；其次综述了s c h l i n g e m a n n 和w e m e r 提出的图论 量子纠错码的编码方法，并基于此图论编码理论，我们能够得到满足量子s i n g l e t o n 界的参 数为f _ i n f ，k + d z i | f p 是素数) 的量子码，并给出了图态码的个应用的例子；然后综述 i - - 。一p 、 二维图态量子纠错码，对相关定理给予证明，给出了二维图态量子纠错码实例：最后在二 维图态量子码的基础上，我们定义了奇素数维的图态及错误算子，讨论了图态纠错码存在 的条件，并且给出了构造高维( 奇素数) 图态量子纠错码的一般算法思想。 关键词 ：图态码；图态稳定子；量子纠错；量子纠缠；量子图态 东南火学硕十学位论文 a b s t r a c t i l ll9 9 4 aq u a n t u ma l g o r i t h mw h i c hc a ns o l v et h ep r o b l e mo fl a r g en u m b e r sp r i m e f a c t o r i z a t i o ni np o l y n o m i a lt i m ew a sp r e s e n t e db yp e t e rs h o r t h e nav a r i e t yo fr a p i dq u a n t u m a l g o r i t h mw e r ef o u n d b u td u et ot h eq u a n t u md e c o h e r e n c e i fn o t ，b e i n gi n t r o d u c e da n yq u a n t u m c o r r e c t i o nt e c h n o l o g y , q u a n t u ma l g o r i t h mi sv e r yd i m c u l tt ob ea c h i e v e d u n t i l19 9 5 s h o ra n d s t e a n ei n d e p e n d e n t l yp u tf o r w a r dt w of a m o u sq u a n t u m ( e r r o r - c o r r e c t i n gc o d e ，e c c ) e c cs c h e m e s ， t h er e s e a r c hp r o g r e s so fq u a n t u me c c ( e c c ) w a sf a s t i n2 0 0 1 ，s c h l i n g e m a n na n dw e r n e rp u t f o r w a r daq u a n t u ms t a t ec o d e ( e c c ) m e t h o dw i t hs o m ec h a r a c t e r i s t i c so ft h eg r a p h s t h e n q u a n t u me c c ( e c c ) s c h e m eb a s e do ng r a p hi si nr a p i dd e v e l o p m e n t t h et h e o r yo fs t a b i l i z e rc o d e sb a s e do nt h et h e o r yo fs t a b l ed i s c si sq u i c km a t u r en o w , a n d m e t h o d sb a s e do ng r a p ht h e o r yt oc o n s t r u c tq u a n t u me c ca r en o ts y s t e m a t i c ，b u tt h eg r a p hc o d e s a n ds t a b i l i z e rc o d e sa r ee q u i v a l e n c e ，w ec a nu s et h es t a b l ed i s c st h e o r yt os t u d yg r a p hc o d e s ，n l i sp a p e ri n t r o d u c e dt h eb a s i ct h e o r yo fq u a n t u me c c s e c o n d l yw e m e r sq u a n t u me c c c o d i n gm e t h o db a s e do nt h eg r a p ht h e o r yw a sr e v i e w e d b a s e do nt h i sg r a p ht h e o r y , w ec a nh a v e 一f ，k + i ，d 一划。( pi sp r i m e ) q u a n t u me c cw h i c hs a t i s f i e ss i n g l e t o np a r a m e t e r s ，a n dg i v e a na p p l i c a t i o ng r a p hc o d ee x a m p l e f i n a l l yb a s e do nt h et w o d i m e n s i o n a lg r a p hs t a t eq u a n t u m c o d e ，w ed e f i n eh i g l ld i m e n s i o n a lg r a p hs t a t ea n dp a u l io p e r a t o r , d i s c u s st h ec o n d i t i o n so f e x i s t e n c eo d dp r i m e sg r a p hc o d e s ，a n dp r e s e n tt h eg e n e r a lc o n d i t i o n so ft h ea l g o r i t h m k e yw o r d s ：g r a p hc o d e s ，g r a p hs t a b l ed i s c ，q u a n t u mc o r r e c t i o n ，q u a n t u me n t a n g l e m e n t ， q u a n t u mg r a p hs t a t e i l 东南人学硕1 ：学位论文 目录 摘要i a b s t r a c t i i 第一章绪论1 l 、研究背景及意义一l 2 、研究现状。l 3 、论文组织一3 第二章量子纠错编码理论基础4 2 1 经典纠错码4 2 1 1 经典码的相关概念。4 2 1 2 经典线性码4 2 2 量子纠错码5 2 2 1 量子纠错码5 2 2 2 量子错误一6 2 2 3 量子稳定子码7 第三章图论量子纠错码9 3 1 图论量子纠错码的基础9 3 2 图论量子码的构造方法l o 3 2 1 通过搜索获得量子纠错码1 0 3 2 2 分析特殊图构造量子码一l l 3 3 图论量子纠错码的应用1 2 第四章二维图态量子纠错码1 4 4 1 二维图态1 4 4 2 图态纠错码一1 5 4 2 1 图态稳定子1 5 4 2 2 图态量子纠错码1 6 4 3 构造图态纠错码算法1 8 4 4 二维图态码的构造实例1 9 4 5 本章小结2 0 第五章高维图态量子纠错码2 l 5 1 高维p a u li 算子和图态2 1 5 1 1 高维p a uii 算子2l 5 1 2 高维图态2 2 5 2 高维图态纠错码。2 3 5 3 ，j 、结。2 4 第六章结束语2 5 致谢2 6 参考文献2 7 第一章绪论 1 、研究背景及意义 第一章绪论 2 0 世纪6 0 年代至7 0 年代，人们就发现，能耗会导致计算机芯片的发热，影响芯片的 集成度，从而限制了计算机的运行速度，能耗问题成为经典计算机发展的瓶颈。为了克服 经典计算机中的能耗问题，人们对可逆计算机进行了研究，而对可逆计算机的研究导致量 子计算机概念的产生。 1 9 9 4 年，p w s h o t t l 等人在量子叠加性和相干性这一量子本质特征的基础上提出了量 子并行计算的量子计算机理论，给出了大数质因子分解的量子多项式时间算法，并且说明 量子计算机可以实现经典计算机不可比拟的信息处理功能。这一理论的提出使得有关量子 计算和量子计算机、量子纠错码、量子通信、量子密码、量子信息的理论和实验迅猛发展， 从而使得信息科学跨入了量子信息的新阶段。 量子计算和量子信息是基于量子级别的，在实际环境中的量子比特不是孤立的，它时 刻与外部环境发生相互作用，破坏量子比特原有的相干性，导致量子消相干。因此，要使 量子计算和量子通信成为现实，一个核心问题就是克服量子消相干。经过人们的研究发现， 量子纠错编码是克服量子消相干最有效的方法之一，因此，量子纠错码理论的研究便显得 十分重要。 类似于经典纠错编码原理，量子纠错码也是通过引入冗余信息，防止和纠j 下量子错误的。 但是，量子环境下有三个非常重要的性质，这使得量子纠错码不能是经典纠错码的简单推 广： ( 1 ) 不可克隆性：经典纠错码一般通过复制引进冗余位来纠正出错的信息位，而量子纠 错码具有不可克隆性，无法通过复制引进冗余位。 ( 2 ) 不可测性：在量子力学中，观测一般会破坏所观测的量子状态，造成量子状念的塌 缩，从而使恢复变的不可能。而在经典纠错中，我们观测来自信道的输出，并决定采取什 么样的解码步骤。 ( 3 ) 差错是连续：连续的不同差错可能出现在单量子比特上，为确定哪个差错出现以便 纠正它，需要无穷好的精度，因此要求无穷多的资源。而经典码的错误是离散的，只有0 和1 之间的跃迁。 由此可见，虽然量子纠错码与经典纠错码有紧密的联系，但也有显著的不同，因此，对 量子纠错码的研究是一项全新的工作。 2 、研究现状 1 9 9 5 1 9 9 6 年，量子纠错研究取得了重大突破。p e t e rs h o d 2 】和s t e a n e 【3 】分别独立提出了 两种量子纠错码的编码方案，具体为：( 1 ) 量子编码时，将单量子比特编码为较复杂的纠 缠态，即不是多个比特的直积态。这样，既引进了冗余信息，又不违背量子不可克隆定理。 ( 2 ) 量子纠错时，进行部分测量。通过编码，可使不同的量子错误对应于不同的正交空间。 而在该空问，信息位之间的量子相干性依然保持，同时又能测出错误模式。( 3 ) 物理机制 上，把纠缠态上的量子错误归结和化简为只需考虑每个量子位上独立发生的错误，并且错 误的类型只有三种：叽= ( ：三) ，巳= ( ；i ) ，c r z = ( 三二) ，分别表示比特反转错误，比 銮查盔堂塑：! 堂垡丝苎 特相位反转错误，相位反转错误，这三种错误的任意组合可以解决连续的量子码错误。 1 9 9 5 年，基于这种物理简化模型，p e t e rs h o r 构造了第一个量子纠错码 【9 ，l ，3 】码瞄j 。1 9 9 6 年，s t e a n e 给出了量子纠错方案的一般表述，具体构造出【7 ，1 ，3 】 码d j 。还是在1 9 9 6 年， l a f l a m m e 4 】等人和b e n n e t t 5 】等人给出了 【5 ，l ，3 1 码，这是最优码。 1 9 9 6 年，c a l d e r b a n k ，s h o 一6 】和s t e a n e 7 】【8 】采用经典线性分组纠错码的思想，利用两个 特殊的经典二元纠错码设计了量子纠错码的第一个系统的构造方法一s s 编码，从而建 立了以经典线性纠错编码为基础的量子纠错编码的理论和方法。 1 9 9 7 年，c a l d e r b a n k ，r a i n ，s h o r 和s l o a n e 提出了一个构造量子纠错码的群理论框架1 9 1 ， 这个框架可以简化对已知量子纠错码的描述，并且使构造新的纠错码变的方便，这些理论 成果最终在1 9 9 8 年发表【1 0 】。文献【1 0 】系统地建立了量子纠错码的数学模型，并利用有限交 换群的特征标理论及有限域上的辛几何理论，给出了一种从f 2 或f 4 上的经典纠错码来构造 量子纠错码的有效的数学方法，从而构造出了一些好的量子纠错码。这极大的推动了量子 纠错码理论的研究。 1 9 9 7 年g o t t e s m a n t 】发明了二元稳定子码，给出了构造量子纠错码的系统理论方法。量 子稳定子码是经典线性码的类比，它几乎概括了原先所有的量子纠错码，其中就包括c s s 码。 1 9 9 9 年，s t e a n e 1 2 】进一步改进完善了c s s 构造方法，使构造的c s s 码的最小距离更大， 纠错能力更强；并利用本原和非本原b c h 码构造了很多参数较好的量子纠错码。 在量子纠错码构造理论期间，一些研究人员也研究了量子码的界限问题，包括量子 h a m m i n g 界，量子s i n g l e t o n 界，量子g v 界等【l 惜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 码，截短码，线性码等量子码1 9 1 。 2 0 0 1 年，a l e x e i a s h i k h m i n 等人利用非二元的错误基，讨论了特征为g 的屹z 域上的经典 码和q 元量子码的关系【2 0 1 。 2 0 0 2 年，马智和冯克勤教授利用有限酉几何证明了q 元域上的量子g v 界，并且证明 了每个奇素数p ，量子码i 6 ，2 ，3 1 和r 7 ，3 ，3 1 均存在【2 1 】【2 2 1 。 l j - - i p i - - 。 一p 2 0 0 6 年，s a l a l la a l y 等人【2 3 】利用分圆陪集证明了最小设计距离和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 等人【2 4 】描述了有限域上稳定子码的基本理论，文中阐述了迹辛 型、迹交替性、h e r m i t i a n 内积的概念；推导出稳定子码的最小距离的上下界；证明了非二 元域上的c s s 码构造定理；并列举了若干量子码的构造方法，包括量子汉明码，量子b c h 码，二次剩余码，量子特征码等；系统地构建了有限域上非二元稳定子码的理论框架。 上面提到的基本上都是基于稳定子码描述方式的文章，还有量子码的其他的描述方式， 只是现在研究的相对较少。例如图论量子纠错码的研究，在本文中将会得到探索和研究。 2 0 0 1 年，s e h l i n g e m a n n 和w e r n e r 两人【2 5 】提出了通过构造具有某些特性的图来构造量子 码的方法，实质上利用有限域上的矩阵组合性质构造稳定子量子码，证明了每个图都等价 于一个稳定子码的稳定子生成元，这使得我们可以从一个新的角度去研究量子纠错码，扩 展了量子纠错码的研究范围。 2 0 0 5 年，刘太琳等人【2 6 1 利用s c h l i n g e m a n n 和w e r n e r 两人提出的构造量子码纠错码的图 2 第一章绪论 论方法，给出了一个构造非二元量子循环码的方法；对于任意的奇素数p ，构造出量子码 f 8 ，2 ，4 】i 刮 ，z ，z 一2 ，2 1i 。 h 一 一一， 一 一一p 2 0 0 7 年，郁司夏【2 7 】等人提出了二维图态量子纠错码，通过给定图来定义相应的图态及 图念稳定子来构造量子纠错码。 2 0 0 8 年，a n d r e wc r o s s e 2 8 1 等人提出码字稳定的量子码，基于图态和稳定子来构造量子码， 可以获得好的加性码和非加性码。 实际上从2 0 0 4 年以后，量子纠错码研究进展略显迟缓，论文也不如以前那么多。2 0 0 4 年，m a c k a y 等人【2 9 】研究了基于c s s 结构的量子稀疏图码。 2 0 0 7 年，f o m e y 等人【3 0 】对量子卷积码进行了系统的研究。 至此，量子纠错码作为一个量子信息科学的专门分支，其理论框架已经形成，并在不断 地得以发展和完善。 3 、论文组织 本文主要研究基于图论构造量子纠错码的方法。下面简述一下本文的安排和主要研究 结果。 第二章阐述了量子纠错码的基本理论，重点介绍了经典纠错码基本理论和量子纠错码 的基本概念，并介绍一类重要的量子纠错码，即量子稳定子码。 第三章，介绍w e m e r 提出的构造量子纠错码的图论方法，并在此基础上给出了相关推 论和在素数域上给定图寻找量子纠错码的方法。 第四章，介绍二维图态及图态稳定子的定义，给出量子纠错码的编码方法并用实例加 以说明，对文中的相关定理给出证明。 第五章，在第四章二维图态量子码的基础上，给出了高维图态量子纠错码的图态定义 及构造纠错码的基本方案。 最后，对全文进行了总结和展望。 东南大学硕l 学位论文 第二章量子纠错编码理论基础 本章主要介绍经典纠错码和量子纠错码的基础知识，以方便对后续章节的介绍和理解。 2 1 经典纠错码 经典纠错码和量子纠错码的物理机制是完全不同的，但是通过经典纠错码我们可以构 造出量子纠错码，所以，在讨论量子码之前，本节先介绍经典纠错码的一些基本知识。详 细内容可参见文献 3 1 】 3 2 】。 2 1 1 经典码的相关概念 定义2 1 上的刀维希尔伯特空间的任意一个非空子集c 称为一个q 元分组码 ( b l o c kc o d e ) 。c 中每一个向量( 或字) 称为一个码字。如果l c l = k ，则称c 是一个留元( 刀，k ) 码，其中n 表示码长，k 表示码字个数。 定义2 2 - + q 元( ，l ，k ) 码的码率定义为 尺( c ) = 竿 ( 2 1 ) 一个9 元( 刀，k ) 码有k 个码字，可以用于传送k 个不同信息中的任意一个。不难看出， 要传送k 个信息中的任意一个，码长只需要l o g 。k 就足够，因此，在一个g 元( 以，k ) 码中， 每个码字的信息位数为l o g 。k ，其余的刀一l o g ，k 为是冗余位，用于在信道接收端纠正信息 在信道传输过程中发生的错误，- + q 元( 刀，k ) 码使用刀个字符来传送1 0 9 。k 个信息字符， 其码率为尺( c ) = 1 0 9 i q k 。显然一个好的码应该具有较大的码率。 2 1 2 经典线性码 线性码是一类非常重要的分组码，是讨论各种码的基础。线性码具有非常简单的编码 和解码方案。本节介绍线性码的基本概念。 定义2 3 如果cg 碍是f 的一个子空间，则称c 为一个g 元线性码。如果c 是碍的一个七 维子空间，则称c 为一个g 元【，l ，七】线性码。进步，如果c 的最小距离是d ，则称c 为一 个g 元【刀，k ，d 】线性码。 4 第二章量子纠错编码理论基础 显然，c 露是一个线性码当且仅当 ( 1 ) 对任意的五y c ，都有x + y c ； ( 2 ) 对任意x c 和任意口巧，都有- a x ec 定义2 4 设c 是一个g 元【，z ，尼】线性码，将c 的一组基作为行向量构成一个尼，z 阶矩阵g ， 则称g 为线性码c 的生成矩阵。 定义2 5 设c 是一个g 元【甩，七】线性码，g y c 上竺 x 胃l 对任意的a e c ，x 口= o ) ，称为c 的 对偶码，即c 的对偶码c 上定义为f 中与c 所有码字均正交的向量的集合。 定义2 6 设c 是一个g 元【刀，七】线性码。对偶码c 上的生成矩阵h 称为线性码c 的校验矩阵。 显然，由于一个留元 ，z ，后】线性码c 的对偶码c 上的基不唯一，所以c 的校验矩阵也不唯 一，但校验矩阵的秩是唯一的，等于万一七。校验矩阵是一个( 珂一七) ，l 阶矩阵。 定理2 1 设c 是一个g 元【”，后 线性码，其校验矩阵为h 。则d ( c ) = d 的充分必要条件是日 的任意d 一1 列线性无关，并且存在d 列线性相关。 2 2 量子纠错码 本节主要介绍量子纠错码的基本概念。 2 2 1 量子纠错码 一个量子位( q u b i t ) 是2 维复向量空间c 2 中的非零向量，量子物理中把c 2 的一组基表示 为1 0 ) 和1 1 ) ，所以一个量子位表示为： 1 1 ，) = 口l o ) + 1 1 ) ( 口，f l e c ，( 口，) ( o ，o ) ) 一个长为咒的量子状态是n 个c 2 的张量积( c 2 ) 锄中的非零向量。( c 2 ) 锄是2 ”维复向量 空间，有一组基 l a l ) p l 口：) o o l a 。) ，其中a i o ，1 ) = e ，i f 一 这个基可以简记为：l a l 口：a n ) = l a ) ，其中口= ( q 口：a n ) e 。所以每个量子状态i y ) 是它 们的复线性组合： l d =c ( q 巴) l q 呸吒) = c ( a ) l a ) 东南人学硕十学位论文 其中c ( a l a 2 a n ) = c 0 ) c ( 不全为零) 。 定义2 7 【3 3 】复向量空间v = ( c 2 ) 锄= c 2 ”中每个复向量子空间q 都叫做一个量子码。n 叫做 q 的码长，q 的维数记为k = d i m q ，而令k = l 0 9 2 足。由l k 2 ”可知0 k 心。 除了码长n 和信息位数k 之外，量子码也有一个反应纠错能力的参数。这就需要解释量 子错误的概念。 2 2 。2 量子错误 在经典的通信领域中，信息和错误都是碍空间中的向量，错误对信息的作用是相加。 而在量子通信中错误是复向量空间上的酉线性算子，错误算子对量子信息的作用是信息上 的酉线性变换，而且通过错误算子可以建立起经典纠错码和量子纠错码之间联系。 s h o r 和s t e a n e 在物理机制上，把复杂的纠缠态量子错误归结和简化为只需考虑每个量 子位上独立发生的错误，并且错误类型恰好由四种p a u l i 矩阵表示：j ( 无错误) ，q = x ( 比 特翻转) ，q = y ( 比特和相位同时翻转) ，吒= z ( 相位翻转) 。而多量子比特上的量子错 误是上述四个算子的张量积，也即其在复向量空间v = ( c 2 ) 锄上的错误作用形式为 e = i a c o j 圆c o z o q 其中，0 五3 ，哆 厶，x ，y ，z ) ，并re 在基向量上的作用是按分量作用。 ( 2 2 ) 对任意两个错误算子e = i 2 q 哆p q 和p = i a c o 。7o 哆 c o n ，它们之间的乘 法运算定义如下： e e = z 五“( q q 7 ) p ( 哆哆) o p ( q q ) ( 2 3 ) 从而所有这些错误算子在乘法作用下构成一个群，也即，z 重p a u l i 群g ”，这里记为e ，因为 e e = e ，e ，所以e 是4 肿1 阶非交换群。群e 的中心为： e ( e ) = f 五厶p 0 厶1 0 旯3 ) 从而商群e = e e ( e ) ，并且它是4 ”阶交换群。 由映射( 式2 4 ) 可知，错误算子e = f a q0 嘎0 圆( - o n ，( 0 旯s3 ，哆 厶，x ，y ，z ) ) 可以表示成【1 0 】 e = i a x ( a ) z ( b ) 其中，a = ( a l , 口2 ，a 。) f ? ，b = ( 6 i ，b 2 ，吃) ， 6 第一二章量t - e q 错编码理论堆础 ( a i ，6 f ) = ( o ，0 ) w = 厶 鼎w ( 1 f ，z ) ( 2 4 ) ( o ，1 ) w = y 。 ( 1 ，1 ) w = z 若_ 表示第j 位为1 ，其余各位都为0 的向量；那么x ( v ，) 就表示对量子态的第j 位进 行q 运算，而其n 1 位不变。z ( _ ) 表示对量子态的第j 位进行吒运算，而其他n - 1 位不 变。当口，= 1 ，乃= 1 时，x ( 以) z ( 6 ) 对应于第j 位同时发生比特翻转和相位翻转。所以有 映射 x ( 口) ：i v ) 专i v + 口) ，z ( 6 ) ：i v ) 哼( 一1 ) l y ) 对于g ”中任意2 ，z 维向量石，其都可以写为( 口f 6 ) 的形式，其中口，b 是，z 维二元向量。 缈：e ，n ，e = f 丑x ( 口) z ( 6 ) 卜缈( p ) = ( 口ib ) 给出群西和加法群霹”的同构： 万：豆= e 冒- ( e ) 兰霹”，歹( 虿) = 妒( p ) = ( 口1 6 ) 从而秀等同于g ”，虿= ( 口ib ) 。 定义2 8 对于一个错误算子p = f a qo 哆p o 吃，当q = ，时，第f 个量子位没有错误作用。 而当哆= x ，y ，z 时，第i 个量子位有错误作用。用w 口( p ) 表示e 中有错误作用的量子位的个 数，称它为e 的量子权重，即： w o ( e ) = i f 1 1 f ，l ，w ，) l 而量子码q 的最小距离d = d ( q ) 是满足下述性质的最大正整数：对于i ，) 和卜) q ，如果 ( v l v - - o ，则对每个p e 。( d - 1 ) ，均有( v l e l v - o 。 最j 、足巨离为蹦量子纠错码可以幺q 正l 孚卜量子位的错误。对于码长为刀，维数为 k ( 或者k ) 和最小距离为d 的量子码q 可记为 ，z ，k ，e l i ，或者( ( ，z ，k ，d ) ) 。 2 2 3 量子稳定子码 量子稳定子码是基于稳定子群建立的一类量子码，其理论体系比较成熟，具有许多比 较好的性质。 定义 2 9 【3 4 】二 元域上， 量 子错误集合 7 东南大学硕士学位论文 e = i a w , w 2p 圆i o 力3 ，w i ，x ，y ，z ) ( 1 i 疗) ) 是一个群，并且把这个群叫作 以量子位p a u l i 算子群。若m j ，m e 。，满足【m f ，m 】= m f m ，一m ，m f = o ，则称m f ，m ， 对易。若满足 m f ，m ) = m ，m + m ，m ，= 0 ，则称m ，m 反对易。令s 为e 。的一个a b e l 子群，对于s 中所有元素的本征值为1 的共同本征空间记为q ，即当且仅当对所有m s ，有 m v ) = i v ) 成立时，才有l y ) q 。如果量子纠错码的码空间是q ，则称该量子纠错码为稳定 子量子纠错码，s 为该量子纠错码的稳定子。稳定子可以用它的生成元来表示，用刀个量子 位编码k 个逻辑量子位信息的量子纠错码其稳定子的生成元有，z k 个。 集合邑中所有与稳定子5 - 对易的算子的集合称为s 的中心子z ( s ：e ) ，显然 s z ( s ：e ) 。如果z ( s ：e 。) s 中算子元素的最小权重是d ，则由s 生成的稳定子量子码 的参数【 ，z ，k ，d 】。 非二元域上，错误群e 。= 和。x ( 口) z ( 6 ) l 口，b 碍，c ) 是由好的错误基 占。= x ( 口) z ( 6 ) l 口，b 碍) 生成的。对于乜的子群s ，稳定子码q 定义为 c 4 “( c 矿= c 9o c 9 圆 c 4 ) 的一个非零子空间，满足q = np c 矿e v = v j ，子群s 称 e e s 为9 的稳定子。 第三章图论量了纠错码 第三章图论量子纠错码 3 1 图论量子纠错码的基础 图论方法构造量子纠错码需要两个基本要素：无向图r = 缈，e ) ( y 为定点集，e 为边 集) 和有限阿贝尔群g 。无向图r 的顶点集矿可以区分为两类不相交的顶点集x 和y 的并 集，即v = xuy ，且工n 】，= 矽。x 和y 分别表示输入顶点集和输出顶点集，其中输入顶点 集代表想要编码的逻辑系统，顶点集的大小和待编码的信息位数相等；输出顶点集代表编 码后的物理系统，顶点集的大小和编码后的比特数相等。图1 1 的邻接矩阵满足r f = l - i ， l = o ，若i g i = p ，则l c ：有限阿贝尔群g 的阶为单个量子信息位的维数。 定义3 1 设( ，p ) ，( l ，p 。) 两个度量空间。如存在映射甲：n 专l ，满足：( 1 ) 甲满射。( 2 ) p ( x ，j ，) = 最一g ) ，甲( y ) ) g ，y ) 则称( ，p ) ，j v ! ，鼻) 是等距同构的，映射甲是等距同构映 射。 定义3 2 网定义映射少：g 专c ( c 为复数) ，缈在勒贝格意义上可积，且y 沙的积分有限。 若积分y = o ，则称少为零函数，若二函数之差缈一y 是零函数，则认为卿相等。希尔 伯特空间上的一个元素定义为与给定函数相等的一类函数矽。全体元素的集合成为希尔 伯特空间。形式化表示为h = r ( g ) ，其上的标积定义为：( 妒，y ) = 胁q 炫( g g ) 。 定义3 3 量子编码的输入系统可描述为：h 黜= r ( g z ) ， f g g c ( 厂日。x ) ，输出系统描述为：h 。y = r ( g r ) 定义3 4 定义等距同构映射咋：r ( g x ) 一r ( g 7 ) ， ( _ i f ，) g 7 ) = 船x 巧k 扎7p g x ) ，则等距映射咋就对应一个量子纠错码。 引理3 1 【2 5 】：一个量子码c 如果能纠正e ( e 为错误算子集合) 中的所有错误当且仅当 v i e , ) ，i c 2 ) c ， k + 2 ( d - 1 ) ，对于y 的任意含有d - 1 个顶点 的集合e ，量子纠错码咋存在的充分必要条件是：r t ( x o s ) 口舢= 0 ( ，= y e ) j 口x = o 和 f ，a = 0 3 2 图论量子码的构造方法 本节主要介绍图论量子码的构造方法。 3 2 1 通过搜索获得量子纠错码 本节给出的图论量子纠错码的搜索算法是基于f 面的定理3 2 。 定理3 2 瞵1 ：给定一个阿贝尔群g ( | g l = p ) 和一个加权图r = ( 矿，e ) ( f ，) ， v = xu y ，且x r 、】，= 矽，i x l = 七，l y - - n ，行= 七+ 2 0 1 ) ，如果存在c 上的刀+ 七阶对称方 阵r = 心l 。g ，使得对】，的任意含有d 1 个顶点的集合e ，r 的子阵r ，( x v d 都是可逆矩阵， 那么存在达到量子s i n g l e t o n 界的量子码卧，k ，d 卫p 。 l n 第三章图论量了纠错码 证明：f tc x u e ) d x “= 0 ，由于l ( x v e ) 可逆，所以d 舢= 0 ，推出d x = 0 和f x e d = o ，所以 存在达到量子s i n g l e t o n 界的量子码卧，k ，卫p 。 在定理3 2 中，取p 为素数，则c 2 z p ，那么可以设计算法通过计算机搜索n 较小的量 子纠错码，定理3 2 中的对称方阵是偶数阶的，n + 七= 2 ( k + d 一1 ) 。令m = k + d 一1 。 这里关键是选取一个合适的m ，有一个可以寻找比较小的m 的算法思想，如下： 用变量符号代替所有的元素r f ，( z j ) ，并且计算所有的m 阶子行列式，值用符号表 示； 确定合适的值，每一个行列式的取值都不能使得其他的行列式值为o ； 直到得到一个整数矩阵，任意的m 阶子行列式值均不为o ； 选取任意的素数p ，p 不整除矩阵中的任何一个整数。 若找到满足上述条件的m ，则任取k k + 2 ( d - 1 ) ， i = 心) f ，。x u y ( 0 e ) ，使得对y 的任意的含有d 1 个顶点的集合e ，j = y e ，l ( x u e ) 的 秩均为j i + j 一1 ，则存在图论量子码盼，k ，d 卫p 。 证明：由r ，( x u e ) 口x w = o 且r ，x u ) 的秩均为七+ d l ，可得到口x w = 0 ，即口z = o nr 牲口e = o ， 由定理3 1 可知存在图论量子码盼，k ，d 卫。 推论1 设p 为一个素数，x 和y 是两个不相交的集合，i x l = k ，l y l = n 后+ 2 ( d 一1 ) ， r = 虬) f ，。x u r ( t o c ) ，使得对】，的任意的含有d 一1 个顶点的集合e ，i = y e ，r ，似。e ) 的 秩均为后+ d 一1 ，则吐一1 ，k + l ，d l 卫，图论量子码也存在。 证明：任取y e ，令e = e ，l e = d - 2 ，x = xu ，陋i - k + , ，i y i _ n - 1 ， ，= ( y d e = y e = j ，x u e = x u e ，所以r ， ，u f ) - - - r , ( x u d ，即r ， ，u f ) 的秩也为 东南大学硕 j 学位论文 k + d 一1 = j j + 1 + p 一2 ) ，由定理3 3 可知存在盼一1 ，k + l ，d l 卫p 的图论量子码。 推论2 设p 为一个素数，x 和y 是两个不相交的集合，l x i = 尼，l r l - - ，l 尼+ 2 ( d 一1 ) ， r = 心l 。x u y ( c ) ，使得对】，的任意的含有d 一1 个顶点的集合e ，i = y e ，f t ( x 。e ) 的 秩均为七+ d 一1 ，令o i d 一2 则陆一i ，k + i ，d f 卫。图论量子码也存在。 证明：证明过程类似推论1 。任取e 中的i 个顶点集f ，令e = e i ，i e i = d 一“+ 1 ) ， x = x u i 。，防l = 后+ f ，| y ，i = n - i ，= ( y f ) e = e = ，x u e = x we ，所以 l ”，。f ) = f ，( x 。e ) ，即r ，”，u f ) 的秩也为后+ d 一1 = 后+ f + p 一( f + 1 ) ) ，由定理3 3 可知存在 盼一i ，k + i ，d f 卫。的图论量子码。 3 3 图论量子纠错码的应用 纠正一个量子比特错误的最优纯量子纠错码是著名的匝5 ，1 ，3 卫码，其图论描述如图( 1 ) 所示，其中输入顶点集x = o ) ，输出顶点集y = 1 ，2 ，3 ，4 ，5 。 图( 1 ) 量予5 ，1 ，3 卫码的图论描述 基于稳定子理论的构造方法在证明码的纠错能力时较复杂：而基于图论的量子纠错码， 验证其纠错能力则非常简单，只需应用定理3 1 去判断对于顶点集y 任意的含有d 一1 个顶点 的错误子集e 是否满足特定的条件。下面将验证基于图论描述的量子5 ，l ，3 卫码的纠错性能， 即验证图( 1 ) 中任意含有2 个顶点的错误子集e 是否满足定理3 1 的条件。 o l f = 2 3 4 5 ol o l lo 0l o1 l0 1 0 23 0 o 11 ol lo io 01 1 2 45 1l oo 1o 0l 0l 10 一 笙兰至