arXiv:1004.1127 · IEEE Transactions on Information Theory

Concatenated Quantum Codes Can Attain the Quantum Gilbert–Varshamov Bound

Yingkai Ouyang

Published Mar 28, 2014• 20 citations

Abstract

A family of quantum codes of increasing block length with positive rate is asymptotically good if the ratio of its distance to its block length approaches a positive constant. The asymptotic quantum Gilbert-Varshamov (GV) bound states that there exist q -ary quantum codes of sufficiently long block length N having fixed rate R with distance at least NH-1((1-R)/2), where Hq2is the q2-ary entropy function. For q<;7 , only random quantum codes are known to asymptotically attain the quantum GV bound. However, random codes have little structure. In this paper, we generalize the classical result of Thommesen to the quantum case, thereby demonstrating the existence of concatenated quantum codes that can asymptotically attain the quantum GV bound. The outer codes are quantum generalized Reed-Solomon codes, and the inner codes are random independently chosen stabilizer codes, where the rates of the inner and outer codes lie in a specified feasible region.

DOI: 10.1109/tit.2014.2313577

Related papers

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

Tushant Mittal, Shashank Srivastava, Madhur Tulsiani +1 more

cs.ITCross-listedarXiv:2610.02648Oct 5, 20260 citations

Quantum Generalized Reed-Solomon codes concatenated with random rate one inner stabilizer codes asymptotically attain the Quantum Gilbert-Varshamov bound

Yingkai Ouyang

Apr 7, 20100 citations

A Family of Asymptotically Good Quantum Codes Based on Code Concatenation

Zhuo Li, Lijuan Xing, Xinmei Wang

We explicitly construct an infinite family of asymptotically good concatenated quantum stabilizer codes where the outer codes use quantum Reed-Solomon codes and the inner codes use a set of special quantum codes. In the field of quantum error-correcting codes, this is the first time that a family of asymptotically good quantum codes is derived from bad codes. Its occurrence supplies a gap in quantum coding theory.

arXiv:0901.0042IEEE Transactions on Information TheoryJul 18, 200921 citations

The Gilbert-Varshamov Bound for Stabilizer Codes Over $\mathbb{Z}_m$

Nianqi Tang, Zhuo Li, Lijuan Xing +1 more

IEEE AccessJan 1, 20182 citations

Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically

Jihao Fan, Jun Li, Ya Wang +3 more

arXiv:2107.05174IEEE Transactions on Information TheoryAug 24, 20225 citations

Entanglement-Assisted Concatenated Quantum Codes: Parameters and Asymptotic Performance

Jihao Fan, Wei Cheng, Gaojun Luo +2 more

arXiv:2501.04921Jan 9, 20250 citations

arXiv:1004.1127 · IEEE Transactions on Information Theory

Concatenated Quantum Codes Can Attain the Quantum Gilbert–Varshamov Bound

Yingkai Ouyang

Published Mar 28, 2014• 20 citations

arXiv HTML PDF

Abstract

DOI: 10.1109/tit.2014.2313577

Related papers

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

Tushant Mittal, Shashank Srivastava, Madhur Tulsiani +1 more

We show that for any $R,ε>0$ and any prime $p\geq 2$ , there exists an infinite family of $p$ -ary quantum low-density parity-check (QLDPC) codes, rate $R$ , checks of weight $O_ε(1)$ , and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$ . Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$ -ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.We show that for any $R,ε>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_ε(1)$, and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$. Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.

cs.ITCross-listedarXiv:2610.02648Oct 5, 20260 citations

Quantum Generalized Reed-Solomon codes concatenated with random rate one inner stabilizer codes asymptotically attain the Quantum Gilbert-Varshamov bound

Yingkai Ouyang

AbstractA good quantum code corrects for a linear number of errors. It has been shownthat random codes attains the QGVB with a relative distance H −1q 2 ((1−R)/2) wherethe code is q-ary and R is the rate of the code (number of encoded systems / blocklength). However,randomcodeshavelittlestructure. Inthispaper,westudyafamilyofconcatenatedq-arystabilizercodes. Eachoftheinnercodesisarandomrate1q-arystabilizer code of block length n. The outer code is a quantum MDS code with blocklengthq n andalphabetsizeq n ,anarbitraryrateR≤1,anddistanceN(1−R)/2+1thatmeets the Quantum Singleton bound. Fixing the outer code rate and letting n grow,the concatenated stabilizer code has a distance that almost surely attains the QGVB.This partially generalizes Thommesen’s result, where heshowed thatthedistanceof aconcatenated code with a Reed-Solomon outer code and random inner linear codes ofarbitraryrateattainstheGilbert-Varshamovboundalmostsurely. 1 Introduction A family of q-ary quantum codes of increasing block length is deﬁned to be good if the ratioof its distance to its block length approaches a non-zero constant. Designing good quantumcodes is highly nontrivial, just as it is in the classical case. The quantum Gilbert-Varshamovbound (QGVB) is a lower bound on an achievable relative distance of a quantum code ofa ﬁxed rate. Explicit constructions of good quantum codes for q ≤ 7 have been studied[1, 2, 3], but they all fail to satisfy the QGVB. The QGVB bound is attainable for the familyof all random quantum codes [4], the family of random stabilizer codes [5], and the familyof random nondegenerate stabilizer codes [6], and the family of random degenerate stabilizercodes [6]. We show that concatenated quantum codes, with a quantum outer code havinga known structure and being eﬃciently decodable, and randomly chosen independent innerquantum codes also attains the QGVB. Thus our family of random quantum codes has morestructure than previously studied examples.In this paper, we generalize a special case of Thommesen’s result [7] to the quantumcase. He showed that a code from the family of binary concatenated codes made with a1AbstractA good quantum code corrects for a linear number of errors. It has been shownthat random codes attains the QGVB with a relative distance H −1q 2 ((1−R)/2) wherethe code is q-ary and R is the rate of the code (number of encoded systems / blocklength). However,randomcodeshavelittlestructure. Inthispaper,westudyafamilyofconcatenatedq-arystabilizercodes. Eachoftheinnercodesisarandomrate1q-arystabilizer code of block length n. The outer code is a quantum MDS code with blocklengthq n andalphabetsizeq n ,anarbitraryrateR≤1,anddistanceN(1−R)/2+1thatmeets the Quantum Singleton bound. Fixing the outer code rate and letting n grow,the concatenated stabilizer code has a distance that almost surely attains the QGVB.This partially generalizes Thommesen’s result, where heshowed thatthedistanceof aconcatenated code with a Reed-Solomon outer code and random inner linear codes ofarbitraryrateattainstheGilbert-Varshamovboundalmostsurely. 1 Introduction A family of q-ary quantum codes of increasing block length is deﬁned to be good if the ratioof its distance to its block length approaches a non-zero constant. Designing good quantumcodes is highly nontrivial, just as it is in the classical case. The quantum Gilbert-Varshamovbound (QGVB) is a lower bound on an achievable relative distance of a quantum code ofa ﬁxed rate. Explicit constructions of good quantum codes for q ≤ 7 have been studied[1, 2, 3], but they all fail to satisfy the QGVB. The QGVB bound is attainable for the familyof all random quantum codes [4], the family of random stabilizer codes [5], and the familyof random nondegenerate stabilizer codes [6], and the family of random degenerate stabilizercodes [6]. We show that concatenated quantum codes, with a quantum outer code havinga known structure and being eﬃciently decodable, and randomly chosen independent innerquantum codes also attains the QGVB. Thus our family of random quantum codes has morestructure than previously studied examples.In this paper, we generalize a special case of Thommesen’s result [7] to the quantumcase. He showed that a code from the family of binary concatenated codes made with a1

Apr 7, 20100 citations

A Family of Asymptotically Good Quantum Codes Based on Code Concatenation

Zhuo Li, Lijuan Xing, Xinmei Wang

arXiv:0901.0042IEEE Transactions on Information TheoryJul 18, 200921 citations

The Gilbert-Varshamov Bound for Stabilizer Codes Over $\mathbb{Z}_m$ The Gilbert-Varshamov Bound for Stabilizer Codes Over $\mathbb{Z}_m$

Nianqi Tang, Zhuo Li, Lijuan Xing +1 more

Quantum codes over finite rings have received a great deal of attention in recent years. Compared with quantum codes over finite fields, a notable advantage of quantum codes over finite rings is that they can adapt to quantum physical systems of arbitrary order. Moreover, operations are much easier to execute in finite rings than they are in fields. The modulo m residue class ring ℤmis the most common finite ring. This paper investigates stabilizer codes over ℤmand presents the Gilbert-Varshamov (GV) bound. The GV bound shows that surprisingly good quantum codes exist over ℤm, which makes quantum coding feasible for arbitrary quantum physical system. We also provide an enhanced version of the GV bound for non-degenerate stabilizer codes over ℤm. The enhanced GV bound has an asymptotical form and ensures the existence of asymptotically good stabilizer codes over ℤm. Finally, these two bounds are well suited for computer searching.Quantum codes over finite rings have received a great deal of attention in recent years. Compared with quantum codes over finite fields, a notable advantage of quantum codes over finite rings is that they can adapt to quantum physical systems of arbitrary order. Moreover, operations are much easier to execute in finite rings than they are in fields. The modulo m residue class ring ℤmis the most common finite ring. This paper investigates stabilizer codes over ℤmand presents the Gilbert-Varshamov (GV) bound. The GV bound shows that surprisingly good quantum codes exist over ℤm, which makes quantum coding feasible for arbitrary quantum physical system. We also provide an enhanced version of the GV bound for non-degenerate stabilizer codes over ℤm. The enhanced GV bound has an asymptotical form and ensures the existence of asymptotically good stabilizer codes over ℤm. Finally, these two bounds are well suited for computer searching.

IEEE AccessJan 1, 20182 citations

Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically

Jihao Fan, Jun Li, Ya Wang +3 more

In this paper, we utilize a concatenation scheme to construct new families of quantum error correction codes achieving the quantum Gilbert-Varshamov (GV) bound asymptotically. Weconcatenate alternant codes with any linear code achievingthe classical GV bound to construct Calderbank-Shor-Steane (CSS) codes. We show that the concatenated code can achieve the quantum GV bound asymptotically and can approach the Hashing bound for asymmetric Pauli channels. By combing Steane’s enlargement construction of CSS codes, we derive a family of enlarged stabilizer codes achieving the quantum GV bound for enlarged CSS codes asymptotically. Asapplications, we derive two families of fast encodable and decodable CSS codes with parameters $\mathscr {Q}_{1}=[[N,\Omega (\sqrt {N}),\Omega (\sqrt {N})]]$ , and $\mathscr {Q}_{2}=[[N,\Omega (N/\log N),\Omega (N/\log N)/\Omega (\log N)]]$ . We show that $\mathscr {Q}_{1}$ can be encoded very efficiently by circuits of size $O(N)$ and depth $O(\sqrt {N})$ . For an input error syndrome, $\mathscr {Q}_{1}$ can correct any adversarial error of weight up to half the minimum distance bound in $O(N)$ time. $\mathscr {Q}_{1}$ can also be decoded in parallel in $O(\sqrt {N})$ time by using $O(\sqrt {N})$ classical processors. For an input error syndrome, we proved that $\mathscr {Q}_{2}$ can correct a linear number of ${X}$ -errors with high probability and an almost linear number of ${Z}$ -errors in $O(N)$ time. Moreover, $\mathscr {Q}_{2}$ can be decoded in parallel in $O(\log (N))$ time by using $O(N)$ classical processors.In this paper, we utilize a concatenation scheme to construct new families of quantum error correction codes achieving the quantum Gilbert-Varshamov (GV) bound asymptotically. Weconcatenate alternant codes with any linear code achievingthe classical GV bound to construct Calderbank-Shor-Steane (CSS) codes. We show that the concatenated code can achieve the quantum GV bound asymptotically and can approach the Hashing bound for asymmetric Pauli channels. By combing Steane’s enlargement construction of CSS codes, we derive a family of enlarged stabilizer codes achieving the quantum GV bound for enlarged CSS codes asymptotically. Asapplications, we derive two families of fast encodable and decodable CSS codes with parameters$\mathscr {Q}_{1}=[[N,\Omega (\sqrt {N}),\Omega (\sqrt {N})]]$, and$\mathscr {Q}_{2}=[[N,\Omega (N/\log N),\Omega (N/\log N)/\Omega (\log N)]]$. We show that$\mathscr {Q}_{1}$can be encoded very efficiently by circuits of size$O(N)$and depth$O(\sqrt {N})$. For an input error syndrome,$\mathscr {Q}_{1}$can correct any adversarial error of weight up to half the minimum distance bound in$O(N)$time.$\mathscr {Q}_{1}$can also be decoded in parallel in$O(\sqrt {N})$time by using$O(\sqrt {N})$classical processors. For an input error syndrome, we proved that$\mathscr {Q}_{2}$can correct a linear number of${X}$-errors with high probability and an almost linear number of${Z}$-errors in$O(N)$time. Moreover,$\mathscr {Q}_{2}$can be decoded in parallel in$O(\log (N))$time by using$O(N)$classical processors.

arXiv:2107.05174IEEE Transactions on Information TheoryAug 24, 20225 citations

Entanglement-Assisted Concatenated Quantum Codes: Parameters and Asymptotic Performance

Jihao Fan, Wei Cheng, Gaojun Luo +2 more

Entanglement-assisted concatenated quantum codes (EACQCs) are constructed by concatenating two entanglement-assisted quantum error-correcting codes (EAQECCs). By selecting the inner and outer component codes carefully, it is able to construct state-of-the-art EACQCs with parameters better than previous quantum codes. In this work, we use almost maximum-distance-separable (MDS) codes and $\hbar$ -MDS codes as the outer codes to construct EACQCs. Because the range of code length of almost MDS and $\hbar$ -MDS codes is much more free than that of the commonly used MDS codes. We derive several families of new EACQCs with parameters better than the previously best known EAQECCs and standard quantum error-correcting codes (QECCs) of the same length and net transmissions. Moreover, we demonstrate that EACQCs are with maximal entanglement if both the inner and outer component codes are with maximal entanglement. As a result, we construct three new maximal-entanglement EACQCs which have optimal parameters. In addition, we present several new maximal-entanglement EACQCs whose minimum distance is only one less than the minimum distance of the optimal codes. In particular, we propose two new families of asymptotically good maximal-entanglement EACQCs with explicit constructions by using entanglement-assisted quantum algebraic geometry codes as the outer codes. At last, we prove that EACQCs can attain the quantum Gilbert-Varshamov bound for EAQECCs asymptotically.Entanglement-assisted concatenated quantum codes (EACQCs) are constructed by concatenating two entanglement-assisted quantum error-correcting codes (EAQECCs). By selecting the inner and outer component codes carefully, it is able to construct state-of-the-art EACQCs with parameters better than previous quantum codes. In this work, we use almost maximum-distance-separable (MDS) codes and $\hbar$-MDS codes as the outer codes to construct EACQCs. Because the range of code length of almost MDS and $\hbar$-MDS codes is much more free than that of the commonly used MDS codes. We derive several families of new EACQCs with parameters better than the previously best known EAQECCs and standard quantum error-correcting codes (QECCs) of the same length and net transmissions. Moreover, we demonstrate that EACQCs are with maximal entanglement if both the inner and outer component codes are with maximal entanglement. As a result, we construct three new maximal-entanglement EACQCs which have optimal parameters. In addition, we present several new maximal-entanglement EACQCs whose minimum distance is only one less than the minimum distance of the optimal codes. In particular, we propose two new families of asymptotically good maximal-entanglement EACQCs with explicit constructions by using entanglement-assisted quantum algebraic geometry codes as the outer codes. At last, we prove that EACQCs can attain the quantum Gilbert-Varshamov bound for EAQECCs asymptotically.

arXiv:2501.04921Jan 9, 20250 citations

We show that for any

R,ε>0

and any prime

p\geq 2

, there exists an infinite family of

p

-ary quantum low-density parity-check (QLDPC) codes, rate

R

, checks of weight

O_ε(1)

, and normalized distance at least

δ_{\mathrm{GV}}(p,R)-ε

. Here,

δ_{\mathrm{GV}}(p,R)

denotes the quantum Gilbert-Varshamov (GV) bound for

p

-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.

The Gilbert-Varshamov Bound for Stabilizer Codes Over

\mathbb{Z}_m

\mathscr {Q}_{1}=[[N,\Omega (\sqrt {N}),\Omega (\sqrt {N})]]

, and

\mathscr {Q}_{2}=[[N,\Omega (N/\log N),\Omega (N/\log N)/\Omega (\log N)]]

. We show that

\mathscr {Q}_{1}

can be encoded very efficiently by circuits of size

O(N)

and depth

O(\sqrt {N})

. For an input error syndrome,

\mathscr {Q}_{1}

can correct any adversarial error of weight up to half the minimum distance bound in

O(N)

time.

\mathscr {Q}_{1}

can also be decoded in parallel in

O(\sqrt {N})

time by using

O(\sqrt {N})

classical processors. For an input error syndrome, we proved that

\mathscr {Q}_{2}

can correct a linear number of

{X}

-errors with high probability and an almost linear number of

{Z}

-errors in

O(N)

time. Moreover,

\mathscr {Q}_{2}

can be decoded in parallel in

O(\log (N))

time by using

O(N)

classical processors.

\hbar

-MDS codes as the outer codes to construct EACQCs. Because the range of code length of almost MDS and

\hbar

-MDS codes is much more free than that of the commonly used MDS codes. We derive several families of new EACQCs with parameters better than the previously best known EAQECCs and standard quantum error-correcting codes (QECCs) of the same length and net transmissions. Moreover, we demonstrate that EACQCs are with maximal entanglement if both the inner and outer component codes are with maximal entanglement. As a result, we construct three new maximal-entanglement EACQCs which have optimal parameters. In addition, we present several new maximal-entanglement EACQCs whose minimum distance is only one less than the minimum distance of the optimal codes. In particular, we propose two new families of asymptotically good maximal-entanglement EACQCs with explicit constructions by using entanglement-assisted quantum algebraic geometry codes as the outer codes. At last, we prove that EACQCs can attain the quantum Gilbert-Varshamov bound for EAQECCs asymptotically.