A method for concatenating quantum error-correcting codes is presented. The method is applicable to a wide class of quantum error-correcting codes known as Calderbank-Shor-Steane (CSS) codes. As a result, codes that achieve a high rate in the Shannon theoretic sense and that are decodable in polynomial time are presented. The rate is the highest among those known to be achievable by CSS codes. Moreover, the best known lower bound on the greatest minimum distance of codes constructible in polynomial time is improved for a wide range.A method for concatenating quantum error-correcting codes is presented. The method is applicable to a wide class of quantum error-correcting codes known as Calderbank-Shor-Steane (CSS) codes. As a result, codes that achieve a high rate in the Shannon theoretic sense and that are decodable in polynomial time are presented. The rate is the highest among those known to be achievable by CSS codes. Moreover, the best known lower bound on the greatest minimum distance of codes constructible in polynomial time is improved for a wide range.

Jan 1, 200840 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

Constructive Conjugate Codes for Quantum Error Correction and Cryptography

Mitsuru Hamada

A conjugate code pair is defined as a pair of linear codes either of which contains the dual of the other. A conjugate code pair represents the essential structure of the corresponding Calderbank-Shor-Steane (CSS) quantum error-correcting code. It is known that conjugate code pairs are applicable to quantum cryptography. In this work, a polynomial construction of conjugate code pairs is presented. The constructed pairs achieve the highest known achievable rate on additive channels, and are decodable with algorithms of polynomial complexity.A conjugate code pair is defined as a pair of linear codes either of which contains the dual of the other. A conjugate code pair represents the essential structure of the corresponding Calderbank-Shor-Steane (CSS) quantum error-correcting code. It is known that conjugate code pairs are applicable to quantum cryptography. In this work, a polynomial construction of conjugate code pairs is presented. The constructed pairs achieve the highest known achievable rate on additive channels, and are decodable with algorithms of polynomial complexity.

arXiv:cs/0703141Mar 28, 20074 citations

Conjugate Codes for Secure and Reliable Information Transmission

Mitsuru Hamada

IEEE Information Theory Workshop (ITW)Oct 1, 200614 citations

Some classes of concatenated quantum codes: constructions and lower bounds

Hachiro Fujita

In classical coding theory code concatenation is successfully used to construct good errorcorrecting codes and most of the asymptotically good codes known so far are based on concatenation. In this paper we present some classes of asymptotically good concatenated quantum codes, which are a quantum analogue of classical concatenated codes, and derive lower bounds on the minimum distance and the rate of the codes. Our bounds improve on the best lower bound of Ashikhmin–Litsyn–Tsfasman and Matsumoto for rates smaller than about one half. We also give a polynomial-time decoding algorithm for the codes that can decode up to one fourth of the lower bound on the minimum distance of the codes.In classical coding theory code concatenation is successfully used to construct good errorcorrecting codes and most of the asymptotically good codes known so far are based on concatenation. In this paper we present some classes of asymptotically good concatenated quantum codes, which are a quantum analogue of classical concatenated codes, and derive lower bounds on the minimum distance and the rate of the codes. Our bounds improve on the best lower bound of Ashikhmin–Litsyn–Tsfasman and Matsumoto for rates smaller than about one half. We also give a polynomial-time decoding algorithm for the codes that can decode up to one fourth of the lower bound on the minimum distance of the codes.

Quantum Information and ComputationApr 1, 20151 citation

Quantum error correcting codes based on privacy amplification

Zhicheng Luo

Calderbank-Shor-Steane (CSS) quantum error-correcting codes are based on pairs of classical codes which are mutually dual containing. Explicit constructions of such codes for large blocklengths and with good error correcting properties are not easy to find. In this paper we propose a construction of CSS codes which combines a classical code with a two-universal hash function. We show, using the results of Renner and Koenig, that the communication rates of such codes approach the hashing bound on tensor powers of Pauli channels in the limit of large block-length. While the bit-flip errors can be decoded as efficiently as the classical code used, the problem of efficiently decoding the phase-flip errors remains open.Calderbank-Shor-Steane (CSS) quantum error-correcting codes are based on pairs of classical codes which are mutually dual containing. Explicit constructions of such codes for large blocklengths and with good error correcting properties are not easy to find. In this paper we propose a construction of CSS codes which combines a classical code with a two-universal hash function. We show, using the results of Renner and Koenig, that the communication rates of such codes approach the hashing bound on tensor powers of Pauli channels in the limit of large block-length. While the bit-flip errors can be decoded as efficiently as the classical code used, the problem of efficiently decoding the phase-flip errors remains open.

arXiv:0808.1392Aug 10, 20083 citations

\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.