2122

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 48, NO. 7, JULY 2002

B. Proof of Lemma 5.3[8] D. L. McLeish, “Dependent central limit theorems and invariance principles,” Ann. Probab., vol. 2, no. 4, pp. 620–628, 1974.
[9] K. S. Miller, Complex Stochastic Processes: An Introduction to Theory
and Application, 1st ed. Reading, MA: Addison-Wesley, 1974.
[10] D. Mitra and J. A. Morrison, “A distributed power control algorithm forbursty transmissions on cellular, spread spectrum wireless networks,” inProc. 5th WINLAB Workshop on Third Generation Wireless Information
Networks, J. M. Holtzman, Ed. Boston, MA: Kluwer Academic, 1996,pp. 201–212.
[11] F. D. Nesser and J. L. Massey, “Proper complex random processes withapplications to information theory,” IEEE Trans. Inform. Theory, vol.
39, pp. 1293–1302, July 1993.
[12] H. V. Poor and S. Verdú, “Probability of error in MMSE multiuser detection,” IEEE Trans. Inform. Theory, vol. 43, pp. 858–871, May 1997.
[13] J. W. Silverstein and Z. D. Bai, “On the empirical distribution of eigenvalues of a class of large dimensional random matrices,” J. Multivariate
Anal., vol. 54, no. 2, pp. 175–192, 1995.
[14] T. J. Sweeting, “On conditional weak convergence,” J. Theor. Probab.,vol. 2, no. 4, pp. 461–474, 1989.
[15] D. N. C. Tse and S. V. Hanly, “Linear multiuser receivers: Effective interference, effective bandwidth and user capacity,” IEEE Trans. Inform.
Theory, vol. 45, pp. 641–657, Mar. 1999.
[16] S. Verdú, Multiuser Detection. Cambridge, U.K.: Cambridge Univ.
Press, 1998.
[17] S. Verdú and S. Shamai (Shitz), “Spectral efficiency of CDMA withrandom spreading,” IEEE Trans. Inform. Theory, vol. 45, pp. 622–640,Mar. 1999.
[18] J. Zhang, “Design and performance analysis of power-controlled CDMA
wireless networks with linear receivers and antenna arrays,” Ph.D. dissertation, Purdue Univ., West Lafayette, IN, May 2000.
[19] J. Zhang and E. K. P. Chong, “CDMA systems in fading channels: Admissibility, network capacity, and power control,” IEEE Trans. Inform.
Theory, vol. 46, pp. 962–981, May 2000.
[20] J. Zhang, E. K. P. Chong, and D. N. C. Tse, “Output MAI distributions oflinear MMSE multiuser receivers in DS-CDMA systems,” IEEE Trans.
Inform. Theory, pp. 1128–1144, Mar. 2001.

It is clear that for any given S , MI is positive definite, and hence
MI01 is also positive definite. It then follows that for every S0<pP

101 <1 + P1 sH
1 MI s1

p

P1 :

(21)

Combining (11) and (12) with (21), we have thatP
W1(N ) (X ; Z ) 0!

1P
W2(N ) (X ; Z ) 0!

12
2

a2g
a2g

101

dG3 ()(22)dG3 ():(23)( +  )2( +  )20Then, for every subsequence fN 0 g of fN g, combining (21) with (10)yields that

P 0:
U (N ) (X ; Z ) 0!
Appealing to Lemma 5.2, we conclude that there exists a subsequence
fJ 0 g of fN 0 g such that

P 0
P !: U (J ) (X (! ); Z ) 0!

= 1:

Based on (22) and (23), for the subsequence fJ 0 g, we resort to Lemma
5.2 again and conclude that there exists a further subsequence fN 00 gof fJ 0 g such that

PP! : W1(N ) (X (! ); Z ) 0!

1PP! : W2(N ) (X (! ); Z ) 0!

122a2g
a2g

10

10

dG3 ()=1

dG3 ()= 1:( +  )2( +  )2Furthermore, it is clear thatP 0P ! : U (N ) (X (! ); Z ) 0!

Improvement of Ashikhmin–Litsyn–Tsfasman Bound for
Quantum Codes=1

thereby concluding the proof.

Ryutaroh Matsumoto, Member, IEEE

ACKNOWLEDGMENT
The authors would like to thank David N. C. Tse for helpful discussions. The authors would also like to thank the anonymous reviewers
for their helpful comments that improved the presentation of the correspondence.

Abstract—We improve performance of the asymptotically good quantum
codes constructed by Ashikhmin, Litsyn, and Tsfasman, by using morerational points on algebraic curves.
Index Terms—Algebraic-geometry code, Ashikhmin–Litsyn–Tsfasmanbound, quantum code.

REFERENCES

I. INTRODUCTION[1] P. Billingsley, Probability and Measure, 3rd ed. New York: Wiley,
1995.
[2] T. M. Cover and J. A. Thomas, Elements of Information Theory. New
York: Wiley, 1991.
[3] M. L. Honig, U. Madhow, and S. Verdú, “Blind adaptive multiuser detection,” IEEE Trans. Inform. Theory, vol. 41, pp. 944–960, July 1995.
[4] E. A. Lee and D. G. Messerschmitt, Digital Communication, 2nded. Boston, MA: Kluwer Academic, 1994.
[5] U. Madhow and M. L. Honig, “MMSE interference suppression for directed-sequence spread-spectrum CDMA,” IEEE Trans. Commun., vol.
42, pp. 3178–3188, Dec. 1994.
[6], “On the average near–far resistance for MMSE detection of directed-sequence CDMA signals with random spreading,” IEEE Trans.
Inform. Theory, vol. 45, pp. 2039–2045, Sept. 1999.
[7] T. L. Marzetta and B. M. Hochwald, “Capacity of a mobile multiple-antenna communication link in Rayleigh flat fading,” IEEE Trans. Inform.
Theory, vol. 45, pp. 139–157, Jan. 1999.

Recently, quantum computation and quantum communication haveattracted much attention, because the use of quantum-mechanicalphenomena can offer unusual efficiency in computation and com-Manuscript received October 14, 2001; revised January 15, 2002. The
material in this correspondence was submitted for consideration of presentation
at the 2002 IEEE International Symposium on Information Theory, Lausanne,Switzerland.
The author is with the Department of Communications and IntegratedSystems, Tokyo Institute of Technology, Tokyo 152-8552, Japan (e-mail:ryutaroh@rmatsumoto.org).
Communicated by P. W. Shor, Associate Editor for Quantum Information
Theory.
Publisher Item Identifier S 0018-9448(02)05176-3.

0018-9448/02$17.00 © 2002 IEEEIEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 48, NO. 7, JULY 2002

munication. We have to protect quantum states from environmental
noise in quantum computation and some methods in quantum communication, such as the quantum superdense coding [2], [3]. The
quantum error-correcting codes (or quantum codes) independently
proposed by Shor [12] and Steane [13] constitute one of the techniques for protecting quantum states.
Let us explain quantum codes. We begin with the notion of t-error
correction. Let H be a q -dimensional complex linear space, where q
is a prime power, and suppose that H represents a physical system ofinterest. A quantum code Q is a q k -dimensional subspace of H n .
When we want to protect a quantum state j'i 2 H k , we encode j'i
into a state in Q. So we encode a quantum state of k particles intothat of n particles. Such a code Q is said to be an [[n; k]] quantum
code. Suppose that we send j'i 2 Q and receive j i 2 H n . Aquantum code Q is said to be t-error-correcting if we can decode j'ifrom j i provided that at least the states of n 0 t particles in j i areleft unchanged from j'i.
Since a change of a quantum state is continuous, the notion of t-error
correction seems irrational at first glance [8]. This notion can be justified as follows. In general, the decoding process of a quantum code
does not decode perfectly the transmitted quantum state from a received
one. However, the decoded state and a transmitted state become closer
as t increases provided that the quantum channel used is memorylessas a q -ary channel [11, Sec. 7.4], [9]. A quantitative relation between
the closeness of states, the noisiness of a channel, and t can be foundin [9].
In [9], it is shown that one can make the decoded state arbitrarilyclose to the transmitted state by increasing the code length provided
that the ratio t=n is fixed and is sufficiently large compared with thenoisiness of the channel. This is a major motivation for studying longcodes as in the classical coding theory [10, Sec. 4.3].
A sequence of ti -error-correcting [[ni ; ki ]] quantum codes is said tobe asymptotically good if
lim ni =!1i1

lim inf ki =ni > 0!1
i!1

i

lim inf ti =ni > 0:

Ashikhmin, Litsyn, and Tsfasman [1] constructed the first asymptotically good sequence of quantum codes. After that, Chen, Ling, andXing [5] also constructed an asymptotically good sequence of binary
quantum codes from algebraic curves based on the idea in [16] better
than those in [1] in certain range of parameters. Note that Chen [4] also
proposed the same construction of quantum codes as that in [1].
The construction of Ashikhmin et al. used a sequence of algebraic
curves having many rational points over a finite field. In their construction, they do not use at least g rational points on the curve (see [1,remark below Theorem 4]), where g is the genus of the curve. We caneasily see that the use of more rational points improves the performanceof the constructed sequence of quantum codes.
Garcia and Stichtenoth [7] showed the first sequence of algebraic
curves with many rational points defined by explicit equations. By
using their explicit sequence of curves we shall construct an asymptotically good sequence of quantum codes using asymptotically all therational points on algebraic curves.
II. CONSTRUCTION
Ashikhmin et al. used the following fact in their construction ofquantum codes. The minimum distance of a quantum code is the maximum number of detectable quantum errors that can be written as atensor product of the Pauli spin operators.

2123

Proposition 1: Suppose that we have a chain of classical linear?
codes C ?  C  C 0 in F n
2 , where C denotes the dual codes of
C with respect to the standard inner product. Suppose also that C isan [n; k; d] code and C 0 is [n; k0 ; d0 ] one with k0  k + 2. From thischain we can construct a [[2nm; 2m(k + k0 0 n); minfd; 32 d0 g]]
binary quantum code. Proposition 1 is based on the construction ofquantum codes proposed in [6], [14].
Hereafter, we shall use the formalism of algebraic function fields instead of algebraic curves. Notations used are exactly the same as thosein Stichtenoth’s textbook [15]. We construct an asymptotically goodsequence of binary quantum codes from the Garcia–Stichtenoth function field [7]. Let Fi = F q (x1 , z2 , . . ., zi ) withqzi + zi0 x 0+11 = 0;
qixi = zi =xi01 :Proposition 2: For an integer m
2 there exists a sequence of[[2mni ; 2mki ; di ]] binary quantum codes such thatlim ni =!1i1 Rm ()!1
lim inf di =2mni  i!1
lim inf ki =niifor0< 21m120 2 10 1m(1)whereRm ( ) = 10 103 m 0 2 20 1 :m

(2)

Remark 3: For those who read [1], we highlight the difference between the construction in [1] and ours. The problem of constructing afamily of classical self-orthogonal algebraic geometry codes suitablefor Proposition 1 is to find a set of rational places fP1 , . . ., Pn g anda divisor G with supp G \ fP1 , . . ., Pn g = ; such that there exists adifferential  whose divisor is2G0 (P1 + 1 1 1 + P ):n

For the general algebraic function field used in [1], it seems difficult touse asymptotically all the rational places as fP1 , . . ., Pn g and find Gand  . From the Garcia–Stichtenoth function fields, we shall explicitly
construct G and  in the following proof while using asymptoticallyall the rational places, namely,

02 dx1
q 01
x01
q

=x1

1

G = (( ) + P1 +1 1 1 + P )=2nwhere P1 + 1 1 1 + Pn is the zero divisor of xq1 01 0 1.
Proof of Proposition 2: We shall consider the Garcia–Stichtenoth
function field Fi over F 2 with i  2. Let q = 2m .
Let ni = (q 2 0 1)q i01 and y = xq1 01 0 1. The zero divisor of yconsists of ni places of degree one [7, Sec. 3]. Therefore, we can write
the zero divisor of y as P1 + 1 1 1 + Pn such that Pj 6= Pl for all j; l.
F q with supp D \ fP1 , . . ., Pn g = ;, weFor a divisor D of Fi =F
shall consider a classical linear code C (D) defined byf

j 2 L(D)g:

C (D) = (f (P1 ); . . . ; f (Pn ) f

2124IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 48, NO. 7, JULY 2002

Let  = dy=y = xq1 02 dx1 =y , G00 = () + P1 + 1 1 1 + Pn , andP1 be the unique pole of x1 in Fi . We have

0G0 = (q2 0 2)(x1 ) 0 (q2 0 1)vP(x1 )P1 + (dx1 ):The different exponent of Fi =F1 is even at every place of Fi (see [7,text below Lemma 2.9]). Hence, the discrete valuation of (dx1 ) is evenat every place of Fi by [15, Remark IV.3.7]. Observe that vP (x1 ) =0qi01 [7]. Therefore, the valuation of0 the divisor G00 is an even integer
at every place of Fi . Define G0 = G0 =2. We haveni + deg(dx1 )deg G0 =2

ni + 2gi=

02

2= ni =2 + gi

01

Fq .
where gi is the genus of Fi =F
Let j be a nonnegative integer. Let
H = (P1 +Fig. 1.

1 1 1 + Pn ) 0 (G0 + jP1) + () = G0 0 jP1 :By [15, Proposition VII.1.2], we have C (G0 + jP1 )? = C (H ). Since
G0 + jP1

H?  C (G0 + jP1 ):C (G0 + jP1 )Observe that C (G0 + jP1 ) is an [ni , j + ni =2,  ni =2 0 gi + 1 0 j ]classical linear code if j  ni =2 0 gi .
There is the inclusion of classical codes
C0 0 ni 0 gi + 1 P1
21G0 +

 C G0 +1

 C G0 +1220 0ni?

1G0 +20 gi + 1 P10 23 0 ni 0 gi + 1 P10 0 ni 0 gi + 1 P1 + 2

 dim C G0 +120 23 0 ni 0 gi + 1 P1 :Hence, by applying Proposition 1 to the inclusion above, for
09=ni    1=2 0 gi =ni we can construct [[2mni ; 2mki ; di ]]binary quantum codes withki

 1 0 35 0 ni 0 2gi ;di 0 ni :Since limi!1 ni =gi = 2m 0 1 [7], by setting  =  0 =2m we haveki Rm ();i!1 nifor the range of  specified in (1).
lim inf

lim inf

i!1di2mni

mation rate of our sequence is always larger than that of [1] at every
relative minimum distance.
ACKNOWLEDGMENT
The author wishes to thank the anonymous referees for providing
detailed comments on the initial manuscript, which identified several
errors.
REFERENCES

for 0   0  1=2 0 gi =ni , and the condition 9=ni   0  1=2 0 gi =ni
impliesdim C

Asymptotically good sequences of quantum codes.

By choosing an appropriate value m for every  , we can construct asequence of [[2mni , 2mki , di ]] binary quantum codes withkidi R(); liminf
i!1 nii!1 2mni
where R( ) = Rm ( ) formm01312   min 845 ; 5(2m0311021)(2m 0 1) :5(2m 0 1)(2m+1 0 1)
lim inf

The sequences in [1], [5] and the sequences in this correspondence
are compared in Fig. 1. Since (2) is larger than [1, eq. (21)], the infor-[1] A. Ashikhmin, S. Litsyn, and M. A. Tsfasman, “Asymptotically goodquantum codes,” Phys. Rev. A, vol. 63, no. 3, p. 032311, Mar. 2001.
[2] C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, “Entanglement-assisted capacity of a quantum channel and the reverse Shannon
theorem,” arXiv:quant-ph/0106052, June 2001.
[3] C. H. Bennett and S. J. Wiesner, “Communication via one- and two-particle operations on Einstein–Podolsky–Rosen states,” Phys. Rev. Lett.,
vol. 69, no. 20, pp. 2881–2884, Nov. 1992.
[4] H. Chen, “Some good quantum error-correcting codes from algebraicgeometric codes,” IEEE Trans. Inform. Theory, vol. 47, pp. 2059–2061,July 2001.
[5] H. Chen, S. Ling, and C. Xing, “Asymptotically good quantum codes exceeding the Ashikhmin–Litsyn–Tsfasman bound,” IEEE Trans. Inform.
Theory, vol. 47, pp. 2055–2058, July 2001.
[6] G. Cohen, S. Encheva, and S. Litsyn, “On binary constructions ofquantum codes,” IEEE Trans. Inform. Theory, vol. 45, pp. 2495–2498,
Nov. 1999.
[7] A. Garcia and H. Stichtenoth, “A tower of Artin–Schreier extensionsof function fields, attaining the Drinfeld–Vladut bound,” Invent. Math.,
vol. 121, no. 1, pp. 211–222, July 1995.
[8] S. Kak, “The initialization problem in quantum computing,” Found.
Phys., vol. 29, no. 2, pp. 267–279, Feb. 1999. arXiv:quant-ph/9811005.
[9] R. Matsumoto, “Fidelity of a -error correcting quantum code with morethan errors,” Phys. Rev. A, vol. 64, no. 2, p. 022314, Aug. 2001.
[10] W. W. Peterson and E. J. Weldon, Jr., Error-Correcting Codes, 2nded. Cambridge, MA: MIT Press, 1972.
[11] J. Preskill. (1998) Lecture Notes for Physics 229: Quantum Informationand Computation. [Online]. Available: http://www.theory.caltech.edu/people/preskill/ph229[12] P. W. Shor, “Scheme for reducing decoherence in quantum computer
memory,” Phys. Rev. A, vol. 52, no. 4, pp. 2493–2496, Oct. 1995.
[13] A. M. Steane, “Error correcting codes in quantum theory,” Phys. Rev.
Lett., vol. 77, no. 5, pp. 793–797, July 1996.
[14] A. M. Steane, “Enlargement of Calderbank–Shor–Steane quantum
codes,” IEEE Trans. Inform. Theory, vol. 45, pp. 2492–2495, Nov.
1999.
[15] H. Stichtenoth, Algebraic Function Fields and Codes. Berlin, Germany: Springer-Verlag, 1993.
[16] C. Xing, H. Niederreiter, and K. Y. Lam, “A generalization of algebraicgeometry codes,” IEEE Trans. Inform. Theory, vol. 45, pp. 2498–2501,
Nov. 1999.