Quantum Information Processing manuscript No.
(will be inserted by the editor)

Two Gilbert-Varshamov Type Existential Bounds for
Asymmetric Quantum Error-Correcting Codes

arXiv:1705.04087v2 [quant-ph] 19 Oct 2017

Ryutaroh Matsumoto

19 October 2017

Abstract In this note we report two versions of Gilbert-Varshamov type existential bounds
for asymmetric quantum error-correcting codes.
Keywords asymmetric error · quantum error correction
PACS 03.67.Pp
Mathematics Subject Classification (2010) 94B65

1 Introduction
Quantum error-correcting codes (QECC) are important for construction of quantum computers, as the fault-tolerant quantum computation is based on QECC [13]. There are two
kinds of errors in quantum information, one is called a bit error and the other is called a
phase error. Steane [16] first studied the asymmetry between probabilities of the bit and
the phase errors, and he also considered QECC for asymmetric quantum errors, which are
called asymmetric quantum error-correcting codes (AQECC). Research on AQECC has become very active recently, see [7, 9, 16] and the references therein.
On the other hand, in the study of error-correcting codes, it is important to know the
optimal performance of codes. For classical error-correcting codes, the Gilbert-Varshamov
(GV) bound [11] is a sufficient condition for existence of codes whose parameters satisfies
the GV bound. By the GV bound, one can know that the optimal performance of classical
codes is at least as good as the GV bound.
For QECC, Ekert and Macchiavello obtained a GV type existential bound for general
QECCs. An important subclass of general QECCs is the stabilizer codes [2, 3, 8], as they
enable efficient encoding and decoding. Calderbank et al. [2] obtained a GV type existential
bound for the stabilizer QECCs. After that, Feng and Ma [6] and Jin and Xing [10] obtained
improved versions of GV type bounds for the stabilizer QECCs.
This note will be published in Quantum Information Processing with DOI:10.1007/s11128-017-1748-y
Ryutaroh Matsumoto
Department of Communication and Computer Engineering, Nagoya University, 464-8603 Japan.
http://www.rmatsumoto.org/research.html

2

Ryutaroh Matsumoto

The Calderbank-Shor-Steane (CSS) QECCs [4, 15] are an important subclass of the stabilizer QECCs, as the CSS codes enable more efficient implementation of the fault-tolerant
quantum computation than the stabilizer codes.
Those existential bounds [2, 4, 5, 6, 10] did not consider the asymmetric quantum errors,
while the asymmetry in quantum errors is important in practice [14]. As far as the author
know, nobody has reported existential bounds for the stabilizer or the CSS QECC for asymmetric quantum errors. In this note we report such ones. Our proof arguments are similar to
ones in [2, 4].
2 A GV type existential bound for the CSS codes
An [[n, k, d x , dz ]]q QECC encodes k q-ary qudits into n q-ary qudits and detects up to d x bit
errors and up to dz phase errors. It is known [1, 3] that a nested classical code C 2 ⊂ C 1 ⊂ Fnq
with dimensions k2 and k1 can construct an [[n, dim C 1 − dim C 2 ]]q CSS code, where Fq is
a finite field with q elements. A quantum error can be expressed as a pair (e x , ez ), where
e x ∈ Fnq corresponds to the bit error component of a quantum error and e x ∈ Fnq does to the
phase error component.
Let GLn (Fq ) be the group of n × n invertible matrices over Fq . Let Bn = {(C 1 , C 2 ) |
C 2 ⊂ C 1 ⊂ Fnq , dim C 1 = k1 , dim C 2 = k2 }. For a nonzero vector e ∈ Fnq , let Bn,x (e) (resp.
Bn,z (e)) be the set of nested code pairs that cannot detect e as a bit error (resp. a phase error),
that is, Bn,x (e) = {(C 1 , C 2 ) ∈ Bn | e ∈ C 1 \ C 2 } (resp. Bn,z (e) = {(C 1 , C 2 ) ∈ Bn | e ∈ C 2⊥ \ C 1⊥ }),
where C 1⊥ is the dual code of C 1 with respect to the standard inner product.
Lemma 1 For nonzero e, we have
qk1 − qk2
♯Bn ,
qn − 1
qn−k2 − qn−k1
♯Bn .
♯Bn,z (e) =
qn − 1

♯Bn,x (e) =

Proof As each pair C 2 ⊂ C 1 has ♯C 1 \ C 2 = qk1 − qk2 undetectable errors, we have
P
0,e∈Fnq ♯Bn,x(e)
= qk1 − qk2 .
♯Bn
For nonzero e1 , e2 ∈ Fnq , we claim ♯Bn,x (e1 ) = ♯Bn,x(e)2 . Assuming the claim, we have
X
♯Bn,x (e) = (qn − 1)♯Bn,x (e).
0,e∈Fnq

Combining these two equalities, we have
♯Bn,x (e) =

qk1 − qk2
♯Bn .
qn − 1

We finish the proof by proving the claim. Let e1 , e2 be nonzero vectors. We have
♯Bn,x (e1 ) = ♯{(C 1 , C 2 ) ∈ Bn | e1 ∈ C 1 \ C 2 }
= ♯{(τC 1 , τC 2 ) | τ ∈ GLn (Fq ), e1 ∈ C 1 \ C 2 }
= ♯{(τC 1 , τC 2 ) | τ ∈ GLn (Fq ), τ′ e1 ∈ C 1 \ C 2 }
= ♯{(C 1 , C 2 ) ∈ Bn | τ′ e1 ∈ C 1 \ C 2 }
= ♯Bn,x(τ′ e1 ),

Gilbert-Varshamov Bounds for Asymmetric Quantum Codes

where τ′ ∈ GLn (Fq ) such that τ′ e1 = e2 .
For phase errors, we can make a similar argument with C 2⊥ ⊃ C 1⊥ .

3

⊔
⊓

Theorem 2 Let n, k1 , k2 , d x and dz be positive integers such that
dz −1 !
d x −1 !
qn−k2 − qn−k1 X n
n
qk1 − qk2 X
i
(q − 1)i < 1,
(q
−
1)
+
i
qn − 1 i=1 i
qn − 1
i=1

(1)

then an [[n, k1 − k2 , d x , dz ]]q CSS QECC exists.
Proof Recall that each quantum error can be expressed by its bit error component e x ∈ Fnq
and its phase error component ez ∈ Fnq . The bit error component e x cannot be detected by
codes in Bn,x (e x ) and the phase error component ez cannot be detected by codes in Bn,z (ez ).
The detectabilities of the bit errors and the phase errors are independent of each other. Therefore, if Eq. (1) holds then there exists at least one (C 1 , C 2 ) ∈ Bn that can detect all the bit
errors with weight up to d x − 1 and all the phase errors with weight up to dz − 1, which
implies it is an [[n, k1 − k2 , d x , dz ]]q quantum code. ⊓
⊔
Classical coding theorists often have interest in asymptotic versions of GV type existential bounds [11]. They are stated in terms of information rate and relative distance of
classical error-correcting codes. In the classical error correction, information rate is the ratio
of the number of information symbols to the code length, and relative distance is the ratio
of the minimum distance to the code length.
We can also derive an asymptotic version of Theorem 2. For an [[n, k, d x , dz ]]q AQECC,
we may define the relative distance δ x for bit errors as d x /n, and the relative distance δz for
bit errors as dz /n. The information rate of an [[n, k]]q QECC is defined as k/n [13].
Recall [11] that for 0 ≤ δ ≤ 1 − 1/q we have
!
⌊nδ⌋
X
n
(q − 1)i ≤ qnhq (δ) ,
i
i=1

(2)

where hq (δ) = δ logq (q − 1) − δ logq δ − (1 − δ) logq (1 − δ).
Corollary 3 Let δ x and δz be real numbers such that 0 ≤ δ x ≤ 1 − 1/q and 0 ≤ δz ≤ 1 − 1/q.
If
hq (δ x ) < 1 − R1 ,

(3)

hq (δz ) < R2 , and

(4)

0 ≤ R1 − R2 ,
then, for sufficiently large n, there exists an [[n, ⌊nR1 ⌋ − ⌈nR2 ⌉, ⌊nδ x ⌋, ⌊nδz ⌋]]q CSS QECC
exists.
In Corollary 3, R1 is the information rate of classical ECC C 1 , and R2 is the information rate
of classical ECC C 2 . The corresponding quantum CSS code has information rate R1 − R2 ,
relative distance δ x for bit errors, and relative distance δz for phase errors.

4

Ryutaroh Matsumoto

Proof Assume that Eq. (3) holds. Then for sufficiently large n we have
nhq (δ x ) < n − nR1
qn
⇒ qnhq (δx ) < (1/2) nR1
q
nR1
q
⇒ n qnhq (δx ) < 1/2
q
!
⌊nδ x ⌋−1
n
q⌊nR1 ⌋ − q⌈nR2 ⌉ X
(q − 1)i < 1/2.
⇒
i
qn − 1
i=1

(5)

Similarly, for sufficiently large n Eq. (4) implies
nhq (δz ) < nR2
⇒ qnhq (δz ) < (1/2)
n(1−R2 )

⇒
⇒

q

qn

qn
qn(1−R2 )

qnhq (δz ) < 1/2

!
⌊nδz ⌋−1
qn−⌈nR2 ⌉ − qn−⌊nR1 ⌋ X n
(q − 1)i < 1/2.
i
qn − 1
i=1

(6)

Equations (5) and (6) imply that the assumption of Theorem 2 becomes true for sufficiently
large n, which shows Corollary 3. ⊓
⊔

3 A GV type existential bound for the stabilizer codes
Let C ⊂ F2n
q be a Fq -linear space of dimension n − k self-orthogonal with respect to the
standard symplectic inner product in F2n
q . C can be viewed as an [[n, k]]q stabilizer QECC.
Let An be the set of all such C’s. A nonzero e ∈ F2n
q can be viewed as a quantum error
on n qudits. Let An (e) be the set of stabilizer codes that cannot detect e as an error, that is,
An (e) = {C ∈ An | e ∈ C ⊥s \ C}, where C ⊥s is the dual of C with respect to the symplectic
1−q−2k
1
inner product. Then ♯An (e) ≤ 1−q
−2n · qn−k ♯An [12, Lemma 9].
Recall that, for C to be [[n, k, d x , dz ]]q , C must be able to detect all d x or less bit errors
and all dz or less phase errors. The number of such errors is
dX
x −1
i=1

!
!
dX
z −1
n
n
(q − 1)i ×
(q − 1)i .
i
i
i=1

By the same argument as [12][Remark 10] (or as the last section), we have the following
theorem:
Theorem 4 Let n, k1 , k2 , d x and dz be positive integers such that
!
dX
d x −1 !
z −1
1 − q−2k
1 X
n
n
i
·
(q − 1)i < 1
(q
−
1)
×
i
1 − q−2n qn−k i=1 i
i=1
then there exists an [[n, k, d x , dz ]]q stabilizer QECC. ⊓
⊔

Gilbert-Varshamov Bounds for Asymmetric Quantum Codes

5

By almost the same argument as Corollary 3 we can derive the following asymptotic
version of Theorem 4.
Corollary 5 Let δ x and δz be real numbers such that 0 ≤ δ x ≤ 1 − 1/q and 0 ≤ δz ≤ 1 − 1/q.
If
hq (δ x ) + hq (δz ) < 1 − R ≤ 1,
(7)
then, for sufficiently large n, there exists an [[n, ⌊nR⌋, ⌊nδ x ⌋, ⌊nδz ⌋]]q stabilizer QECC. ⊓
⊔
The quantum statilizer code in Corollary 5 has information rate R, relative distance δ x for
bit errors, and relative distance δz for phase errors.
By the relation between the CSS and the stabilizer QECCs [3], we see that the assumption in Corollary 3 is less demanding than that in Corollary 5 for the same n, R = R1 − R2 ,
δ x and δz , which means that Corollary 5 is a stronger existential bound than Corollary 3.
Remark 6 Theorems 2 and 4, and Corollaries 3 and 5 do not admit direct comparisons
against previously known GV type bounds even when d x = dz . The reason is as follows:
For a binary QECC to be [[n, k, 2, 2]]2 , it must detect at least n2 different errors. On the
other hand, for a binary [[n, k]]2 QECC to detect all single symmetric errors, it only has to
detect 3n errors, which is generally much fewer than n2 . The above example shows that the
number of asymmetric quantum errors is much different from that of corresponding symmetric quantum errors, even if we assume the same number of bit errors and phase errors in
asymmetric quantum errors.
In addition, the famous [[5, 1, 3]]2 binary stabilizer code in [3, 8] can detect up to four
bit errors if there is no phase error, and can detect up to four phase errors if there is no bit
error. Thus it is simultaneously both [[5, 1, 1, 5]]2 AQECC and [[5, 1, 5, 1]]2 AQECC. This
phenomenon makes the direct comparison even more difficult.
Acknowledgements The author would like to thank an anonymous reviewer for careful reading and the helpful report that improved this note, and Prof. Fernando Hernando for drawing his attention to the asymmetric
quantum error correction.

References
1. Ashikhmin, A., Knill, E.: Nonbinary quantum stabilizer codes. IEEE Trans. Inform. Theory 47(7),
3065–3072 (2001)
2. Calderbank, A.R., Rains, E.M., Shor, P.W., Sloane, N.J.A.: Quantum error correction and orthogonal
geometry. Phys. Rev. Lett. 78(3), 405–408 (1997)
3. Calderbank, A.R., Rains, E.M., Shor, P.W., Sloane, N.J.A.: Quantum error correction via codes over
GF(4). IEEE Trans. Inform. Theory 44(4), 1369–1387 (1998)
4. Calderbank, A.R., Shor, P.W.: Good quantum error-correcting codes exist. Phys. Rev. A 54(2), 1098–
1105 (1996)
5. Ekert, A., Macchiavello, C.: Quantum error correction for communication. Phys. Rev. Lett. 77(12),
2585–2588 (1996)
6. Feng, K., Ma, Z.: A finite Gilbert-Varshamov bound for pure stabilizer quantum codes. IEEE Trans.
Inform. Theory 50(12), 3323–3325 (2004). DOI 10.1109/TIT.2004.838088
7. Galindo, C., Geil, O., Hernando, F., Ruano, D.: Improved constructions of nested code pairs. IEEE Trans.
Inform. Theory (2017). DOI 10.1109/TIT.2017.2755682
8. Gottesman, D.: Class of quantum error-correcting codes saturating the quantum Hamming bound. Phys.
Rev. A 54(3), 1862–1868 (1996)
9. Ioffe, L., Mézard, M.: Asymmetric quantum error-correcting codes. Phys. Rev. A 75, 032345 (2007).
DOI 10.1103/PhysRevA.75.032345

6

Ryutaroh Matsumoto

10. Jin, L., Xing, C.: Quantum Gilbert-Varshamov bound through symplectic self-orthogonal codes. In:
Proc. 2011 IEEE International Symposium on Information Theory, pp. 455–458. Sait Petersburg, Russia
(2011). DOI 10.1109/ISIT.2011.6034167
11. MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes. Elsevier, Amsterdam (1977)
12. Matsumoto, R., Uyematsu, T.: Lower bound for the quantum capacity of a discrete memoryless quantum
channel. Journal of Mathematical Physics 43(9), 4391–4403 (2002). DOI 10.1063/1.1497999
13. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University
Press, Cambridge, UK (2000)
14. Sarvepalli, P.K., Klappenecker, A., Rötteler, M.: Asymmetric quantum codes: constructions, bounds and
performance. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
465(2105), 1645–1672 (2009). DOI 10.1098/rspa.2008.0439
15. Steane, A.M.: Multiple particle interference and quantum error correction. Proc. Roy. Soc. London Ser.
A 452(1954), 2551–2577 (1996)
16. Steane, A.M.: Simple quantum error-correcting codes. Phys. Rev. A 54(6), 4741–4751 (1996). DOI
10.1103/PhysRevA.54.4741

