基于有限几何的量子ＣＳＳ码的构造

摘要：首先利用有限几何的特点构造经典低密度奇偶校验(LDPC)矩阵，然后通过对校验矩阵的行或列变换构造其对偶码，本文提出了一种以量子CSS码为理论基础的基于有限几何的量子LDPC码。并对其进行了充分的理论推导，从而使用有限几何构造量子LDPC码称为一种可行的途径。

关键词：有限几何；LDPC码；量子CSS码；对偶码

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)09-11745-02

Construction Quantum CSS Codes Based on Finite Geometries

YUE Ke-feng,XUN Chun-ling

(Nanjing University of Posts & Telecommunications,Nanjing 210003,China)

Abstract: Using the low density parity check matrices created by finite geometric approach with its dual codes, which are constructed by splitting the rows of the LDPC check matrices,a quantum LDPC codes construction method is proposed based on finite geometries in this paper. Finally, this method is proved by theory deduction adequately.

Key words: Finite Geometries; LDPC Codes; Quantum CSS Codes; Dual Codes

1 引言

与经典信道一样，由于环境的影响，量子通信中的信息传输和处理不可避免地会产生消相干(decoherence)，借鉴经典纠错方法，量子纠错编码（quantum error correcting codes）技术成为克服这一问题的有效手段之一[1]。自95年以来，量子纠错码已成为编码界研究的方向,构造量子纠错编码的方法之一是借鉴经典纠错编码方法，目前很多经典纠错编码方案已移植到量子领域中，因此作为经典最好码的LDPC码的量子版本，量子LDPC码已成为这一领域的研究热点[2]。

低密度奇偶校验(LDPC)码又称为Gallager码，它是1962年Gallager提出的经典好码[3]，随后的研究发现用迭代译码算法该码具有非常接近香农限的性能特性[4]。Gallager最初提出的随机构造的方法经过后来的研究表明需要较长的编译码时间[4-5]。对此，文献[5]中提出了基于有限几何的方法构造LDPC码，实现了编码时间与码长成线性关系，并且基于有限几何的LDPC码的Tanner图不含4环，可用多种译码方法进行译码。本文是利用有限几何的特点提出一种构造量子LDPC码的方法，并对其进行了系统的理论分析。

2 基于有限几何的量子LDPC码的构造

有限几何包含欧氏几何与投影几何，欧氏几何相对投影几何要简单。在组合数学中，已知在GF(2s)上有2ms个m重向量(p0,p1,…,pm-1)( pi∈GF(2s))组成一个m维欧氏几何，记为EG(m,2s)。每一点m重向量看作欧氏几何中的一个点，而全零向量(0,0,…,0)记为欧氏几何的原点，在GF(2s)上这2ms个m重向量组成欧氏几何中的所有点，而这些向量又构成了GF(2s)的m维向量空间。因此，EG(m,2s)是由2ms个m重GF(2s)构成的向量空间，于是EG(m,2s)中的点与GF(2ms)中的元素一一对应。在欧氏几何EG(m,2s)中每条线由2s个点组成，并且有 条这样的线，另外每条线有2(m-1)s-1条与之平行，欧氏几何中的每一个点都会有 (2ms-1)/(2s-1)条线经过。在特殊情况下F可表示EG(m,2s)中的一条不经过原点(a∞=0)的直线[5]，于是F可表示GF(2s)上的矢量：VF=(v0,v1,…,v2ms-2。如果分量vi的位置数ai在直线F上，则对应的vi为1，否则为0。把EG(m,2s)中所有不经过原点的向量VF对应校验矩阵的行向量，这样得到的校验矩阵具有循环的特性，并且所得的校验矩阵还具有LDPC码的性质：(1)行重与列重都是2s；(2)任两列或列同时为1的数目最多只有一个；(3)校验矩阵的密度很小。投影几何校验矩阵的构造与欧氏几何类似，只是PG(m,2s)的LDPC矩阵的行重与列重是2s+1。量子CSS码是从经典纠错码获得对应的量子码最有效的方法之一，该量子码的实现是以经典线性码为基础[2]。由于经典LDPC码是一种线性码，因此可以结合CSS码的构造来实现量子LDPC码的构造。设C1和C2为[n,k1]和[n,k2]的经典线性码，使有C2⊂C1，且C1和C2┴两者可纠正t个错误。于是可定义纠t个量子比特的一个[n,k1-k2]量子CSS(C1,C2)码。设x∈C1为C1中任意的一个码字，于是量子态∣x+C2>可定义为：

量子CSS(C1,C2)码就定义为由所有x∈C1的量子态∣x+C2>所张成的向量空间，C1中C2的陪集的数目为∣C1∣/∣C2∣，所以CSS(C1,C2)的维数为∣C1∣/∣C2∣=2k1-k2，因此CSS(C1,C2)是一个[n,k1-k2]量子码。

利用基于有限几何的LDPC码具有循环或准循环的特点，通过对循环多项式的处理可得到该码的对偶码，这是构造量子LDPC码的可行途径[6-7]。结合有限几何构造的LDPC矩阵和CSS码的定义，我们提出一种基于CSS码的量子LDPC码的构造方法。具体步骤如下：

(1)利用上面构造的LDPC码的校验矩阵H1，把H1矩阵中每行以q进行分离，即把每行的1均匀的分布到q行中，并且其1的位置不发生变化，这样分离后可得矩阵H"；

(2)矩阵H"的行向量之间通过线性变换简化后可得矩阵H2，并且H2中的行向量可用其中的某一行向量S循环生成，而S可用多项式h(x)表示；

(3)由 g(x)=(xn+1)/(h(x))得到g(x)，其中n是校验矩阵的列数。把g(x)作为生成矩阵可以得到一个码字空间C2；

(4)以H为校验矩阵可以得到其对偶码C1，而C2⊂C1，这样就可以生成CSS码。

3 构造方法的理论分析

由上面的构造过程可知，C1*H1T=0，C2*H2T=0。设矩阵H1与矩阵H2分别为：

\ykf04.tif>(3)

其中bi=(b11,b12,…,b1n)；

设C1中的任一码子C=(C1,C2,…,Cn))，则由C1*H1T=0得：

H2是经过H"线性变化得到的，而H"又是对H1进行分离而生成的，所以存在：

两边乘以码子c后的

由此推得

进而可得

所以码空间C1、C2都在校验矩阵H2的对偶空间中。又码空间C2的维数小于码空间C1的维数，故可得到构造CSS码的基本条件C2⊂C1。具备了这样的条件就可以构造基于CSS码的量子LDPC码。

4 结束语

本文是在利用有限几何构造的稀疏校验矩阵的基础上，通过变换校验矩阵并以量子CSS码为理论依据获得基于有限几何的量子低密度奇偶校验码。由于本文的构造方法利用有限几何的特性，其所得的码字具有循环或准循环的特点，从而可以通过对多项式的处理得到该码字的对偶码，并且对该方法进行了充分的理论推导，所以用该方法构造量子LDPC码是一种简便可行的途径。

参考文献：

[1] 蔡乐才.量子纠错码的研究,四川理工学院学报,Vol.17,No.3,4,December,2004.

[2] 郑大钟,赵千川,译.量子计算和量子信息(二).北京:清华大学出版社,pp.92-99,February,2005.

[3] R.Gallager, "Low-Density Parity-Check Codes", IEEE Transactions on Information Theory, pp.21-28,January,1962.

[4] Y.Kou, S.Lin, and M.Fossorier,"Low-Density Parity-Check Codes Based on Finite Geometries: A Rediscovery and New Results", IEEE Transactions on Information Theory, Vol.47,No.7 November,2001.

[5] Y.Kou, "Finite Geometry Low Density Parity Check Codes", Ph.D. dissertation, Dept. of Elec. And Computer Eng., Univ. of California,2001.

[6] D.J.C.Mackay, G.Mitchison, and P.L.McFadden, "Sparse-Graph Codes for Quantum Error-Correction", IEEE Transactions on Information Theory, vol.50, No.10, October,2004.

[7] M.S.Postol, "A Proposed Quantum Low Density Parity Check Code", arXiv/quant-ph/0108131,Aug,2001.

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”