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

Abstract

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. We concatenate alternant codes with any linear code achieving the 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. As applications, we derive two families of fast encodable and decodable CSS codes with parameters ${\mathcal{Q}}_1=[[N,\Omega (\sqrt{N}),\Omega (\sqrt{N})]],$ and ${\mathcal{Q}}_2=[[N,\Omega (N/\log N),\Omega (N/\log N)/\Omega (\log N)]].$ We show that ${\mathcal{Q}}_1$ can be encoded very efficiently by circuits of size $O(N)$ and depth $O(\sqrt{N})$. For an input error syndrome, ${\mathcal{Q}}_1$ can correct any adversarial error of weight up to half the minimum distance bound in $O(N)$ time. ${\mathcal{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 ${\mathcal{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, ${\mathcal{Q}}_2$ can be decoded in parallel in $O(\log (N))$ time by using $O(N)$ classical processors.

arXiv comment11 pages,2 figures

References in corpus (29)

• Quantum Computing in the NISQ era and beyond
• Fault-tolerant quantum computation by anyons
• Simple Proof of Security of the BB84 Quantum Key Distribution Protocol
• Good Quantum Error-Correcting Codes Exist
• Topological quantum memory
• Quantum Error Correction and Orthogonal Geometry
• Simple Quantum Error Correcting Codes
• Quantum Low-Density Parity-Check Codes
• Quantum Channel Capacity of Very Noisy Channels
• Ultrafast and Fault-Tolerant Quantum Communication across Long Distances
• Fast Decoders for Topological Quantum Codes
• Asymmetric quantum error correcting codes
• Quantum LDPC Codes with Almost Linear Minimum Distance
• Efficient Computations of Encodings for Quantum Error Correction
• Asymptotically Good Quantum Codes
• Quantum Expander Codes
• Fiber Bundle Codes: Breaking the $N^{1/2}\mathrm{polylog}(N)$ Barrier for Quantum LDPC Codes
• NP-hardness of decoding quantum error-correction codes
• Efficient Quantum Polar Coding
• Concatenated Quantum Codes Constructible in Polynomial Time: Efficient Decoding and Error Correction
• Algebraic geometric construction of a quantum stabilizer code
• Thresholds for correcting errors, erasures, and faulty syndrome measurements in degenerate quantum codes
• Concatenated quantum codes can attain the quantum Gilbert-Varshamov bound
• Efficient Quantum Polar Codes Requiring No Preshared Entanglement
• Entanglement-assisted concatenated quantum codes
• Fault-tolerant Coding for Quantum Communication
• Two Gilbert-Varshamov Type Existential Bounds for Asymmetric Quantum Error-Correcting Codes
• Asymmetric Quantum Concatenated and Tensor Product Codes with Large Z-Distances
• On Quantum Weight Reduction