Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Chapman & Hall/CRC eBooks

Algorithmic aspects of quantum error-correcting codes

Markus Grassl

Published Feb 14, 2002• 3 citations
Publisher

Abstract

Abstract We show how quantum algorithms for encoding and decoding of quantum error-correcting codes (QECC) can be derived from the underlying mathematical structure. For this, we first characterize general quantum error-correcting codes, followed by the discussion of CSS codes and additive quantum error-correcting codes. For the last two families, examples are given that illustrate the constructions.

DOI
10.1201/9781420035377-10

Related papers

Duality of Quantum and Classical Error Correction Codes: Design Principles and Examples

Zunaira Babar, Daryus Chandra, Hung Viet Nguyen +4 more

Quantum error correction codes (QECCs) can be constructed from the known classical coding paradigm by exploiting the inherent isomorphism between the classical and quantum regimes, while also addressing the challenges imposed by the strange laws of quantum physics. In this spirit, this paper provides deep insights into the duality of quantum and classical coding theory, hence aiming for bridging the gap between them. Explicitly, we survey the rich history of both classical as well as quantum codes. We then provide a comprehensive slow-paced tutorial for constructing stabilizer-based QECCs from arbitrary binary as well as quaternary codes, as exemplified by the dual-containing and non-dual-containing Calderbank-Shor-Steane (CSS) codes, non-CSS codes and entanglement-assisted codes. Finally, we apply our discussions to two popular code families, namely to the family of Bose-Chaudhuri-Hocquenghem as well as of convolutional codes and provide detailed design examples for both their classical as well as their quantum versions.

IEEE Communications Surveys & Tutorials•Jan 1, 2019•65 citations

Algebraic quantum codes: linking quantum mechanics and discrete mathematics

Markus Grassl

We discuss the connection between quantum error-correcting codes (QECCS) and algebraic coding theory. We start with an introduction to the relevant concepts of quantum mechanics, including the general error model. A quantum error-correcting code is a subspace of a complex Hilbert space, and its error-correcting properties are characterized by the Knill-Laflamme conditions. Using the stabilizer formalism, we illustrate how QECCs for can be constructed using techniques from algebraic coding theory. We also sketch how the information obtained via a quantum measurement can be interpreted as syndrome of the related classical code. Additionally, we present secondary constructions for QECCs, leading to propagation rules for the parameters of QECCs. This includes the puncture code by Rains and construction X for quantum codes.

arXiv:2011.06996•International Journal of Computer Mathematics Computer Systems Theory•Nov 17, 2020•21 citations

NP-hardness of decoding quantum error-correction codes

Min-Hsiu Hsieh, François Le Gall

Although the theory of quantum error correction is intimately related to classical coding theory and, in particular, one can construct quantum error-correction codes (QECCs) from classical codes with the dual-containing property, this does not necessarily imply that the computational complexity of decoding QECCs is the same as their classical counterparts. Instead, decoding QECCs can be very much different from decoding classical codes due to the degeneracy property. Intuitively, one expects degeneracy would simplify the decoding since two different errors might not and need not be distinguished in order to correct them. However, we show that general quantum decoding problem is NP-hard regardless of the quantum codes being degenerate or nondegenerate. This finding implies that no considerably fast decoding algorithm exists for the general quantum decoding problems and suggests the existence of a quantum cryptosystem based on the hardness of decoding QECCs.

arXiv:1009.1319•Physical Review A•May 31, 2011•71 citations

Classical enhancement of quantum-error-correcting codes

Isaac Kremsky, Min-Hsiu Hsieh, Todd A. Brun

We present a general formalism for quantum-error-correcting codes that encode both classical and quantum information (the EACQ formalism). This formalism unifies the entanglement-assisted coding theory and the classical coding theory in the sense that, after the encoding, error-correcting, and decoding steps, the encoded quantum and classical information can be correctly recovered by the receiver. We formally define this kind of quantum codes using stabilizer language, and derive the appropriate error-correcting conditions. We give several examples to demonstrate the construction of such codes.

arXiv:0802.2414•Physical Review A•Jul 21, 2008•36 citations

Bounds on Quantum Error Correcting Codes

Frank Gaitan

The previous two chapters laid out the theoretical framework for quantum error correcting codes, and especially for quantum stabilizer codes. Following Cleve and Gottesman [1], the present chapter will explain how to construct quantum circuits that efficiently encode and decode a quantum stabilizer code. Before entering into that discussion, it proves advantageous to introduce a standard form for quantum stabilizer codes. This is done in Section 4.1. Assuming that a quantum stabilizer code in standard form has been given, Sections 4.2 and 4.3 explain how to, respectively, encode and decode its code­ words. A brief summary of quantum circuits is given in Appendix C.

CRC Press eBooks•Feb 7, 2008•0 citations

On the Structure of Additive Quantum Codes and the Existence of Nonadditive Codes

Vwani Roychowdhury, Farrokh Vatan

We first present a useful characterization of additive (stabilizer) quantum error-correcting codes. Then we present several examples of We first present a useful characterization of additive (stabilizer) quantum error--correcting codes. Then we present several examples of nonadditive codes. We show that there exist infinitely many non-trivial nonadditive codes with different minimum distances, and high rates. In fact, we show that nonadditive codes that correct t errors can reach the asymptotic rate R=1-2H(2t/n), where H(x) is the binary entropy function. Finally, we introduce the notion of strongly nonadditive codes (i.e., quantum codes with the following property: the trivial code consisting of the entire Hilbert space is the only additive code that is equivalent to any code containing the given code), and provide a construction for an ((11,2,3)) strongly nonadditive code.

arXiv:quant-ph/9710031•Oct 9, 1997•4 citations
Abstract We show how quantum algorithms for encoding and decoding of quantum error-correcting codes (QECC) can be derived from the underlying mathematical structure. For this, we first characterize general quantum error-correcting codes, followed by the discussion of CSS codes and additive quantum error-correcting codes. For the last two families, examples are given that illustrate the constructions.
Quantum error correction codes (QECCs) can be constructed from the known classical coding paradigm by exploiting the inherent isomorphism between the classical and quantum regimes, while also addressing the challenges imposed by the strange laws of quantum physics. In this spirit, this paper provides deep insights into the duality of quantum and classical coding theory, hence aiming for bridging the gap between them. Explicitly, we survey the rich history of both classical as well as quantum codes. We then provide a comprehensive slow-paced tutorial for constructing stabilizer-based QECCs from arbitrary binary as well as quaternary codes, as exemplified by the dual-containing and non-dual-containing Calderbank-Shor-Steane (CSS) codes, non-CSS codes and entanglement-assisted codes. Finally, we apply our discussions to two popular code families, namely to the family of Bose-Chaudhuri-Hocquenghem as well as of convolutional codes and provide detailed design examples for both their classical as well as their quantum versions.
We discuss the connection between quantum error-correcting codes (QECCS) and algebraic coding theory. We start with an introduction to the relevant concepts of quantum mechanics, including the general error model. A quantum error-correcting code is a subspace of a complex Hilbert space, and its error-correcting properties are characterized by the Knill-Laflamme conditions. Using the stabilizer formalism, we illustrate how QECCs for can be constructed using techniques from algebraic coding theory. We also sketch how the information obtained via a quantum measurement can be interpreted as syndrome of the related classical code. Additionally, we present secondary constructions for QECCs, leading to propagation rules for the parameters of QECCs. This includes the puncture code by Rains and construction X for quantum codes.
Although the theory of quantum error correction is intimately related to classical coding theory and, in particular, one can construct quantum error-correction codes (QECCs) from classical codes with the dual-containing property, this does not necessarily imply that the computational complexity of decoding QECCs is the same as their classical counterparts. Instead, decoding QECCs can be very much different from decoding classical codes due to the degeneracy property. Intuitively, one expects degeneracy would simplify the decoding since two different errors might not and need not be distinguished in order to correct them. However, we show that general quantum decoding problem is NP-hard regardless of the quantum codes being degenerate or nondegenerate. This finding implies that no considerably fast decoding algorithm exists for the general quantum decoding problems and suggests the existence of a quantum cryptosystem based on the hardness of decoding QECCs.
We present a general formalism for quantum-error-correcting codes that encode both classical and quantum information (the EACQ formalism). This formalism unifies the entanglement-assisted coding theory and the classical coding theory in the sense that, after the encoding, error-correcting, and decoding steps, the encoded quantum and classical information can be correctly recovered by the receiver. We formally define this kind of quantum codes using stabilizer language, and derive the appropriate error-correcting conditions. We give several examples to demonstrate the construction of such codes.
The previous two chapters laid out the theoretical framework for quantum error correcting codes, and especially for quantum stabilizer codes. Following Cleve and Gottesman [1], the present chapter will explain how to construct quantum circuits that efficiently encode and decode a quantum stabilizer code. Before entering into that discussion, it proves advantageous to introduce a standard form for quantum stabilizer codes. This is done in Section 4.1. Assuming that a quantum stabilizer code in standard form has been given, Sections 4.2 and 4.3 explain how to, respectively, encode and decode its code­ words. A brief summary of quantum circuits is given in Appendix C.
We first present a useful characterization of additive (stabilizer) quantum error-correcting codes. Then we present several examples of We first present a useful characterization of additive (stabilizer) quantum error--correcting codes. Then we present several examples of nonadditive codes. We show that there exist infinitely many non-trivial nonadditive codes with different minimum distances, and high rates. In fact, we show that nonadditive codes that correct t errors can reach the asymptotic rate R=1-2H(2t/n), where H(x) is the binary entropy function. Finally, we introduce the notion of strongly nonadditive codes (i.e., quantum codes with the following property: the trivial code consisting of the entire Hilbert space is the only additive code that is equivalent to any code containing the given code), and provide a construction for an ((11,2,3)) strongly nonadditive code.