Long distance communication of digital data, whether through a physical medium or a broadcast signal, is often subjected to noise. To deliver data reliably through noisy communication channels, one must use codes that can detect and correct the particular noise of the channel. For transmission of classical data, error correcting schemes can be as simple as the sending of replicates. For quantum data, and in tandem the development of machines that can process quantum data, quantum error correcting codes must be developed. In addition to a larger set of possible errors, quantum error correcting schemes must contend with other peculiarities of quantum mechanics, such as the no-cloning theorem which can prevent the sending of replicate messages. Stabilizer codes are one family of quantum error correcting codes which can protect and correct errors expressed in terms of the Pauli group, exploiting its group structure and utilizing classical codes and the corresponding duals. We develop and examine a family of quantum stabilizer codes which arise from reflexive stabilizers. Moreover, we provide a mapping from our reflexive stabilizer codes to the well-known CSS codes developed by Calderbank, Shor, and Steane. For the case of a 4-state system we show that these codes can obtain the minimal embedding for code which can correct any flip or phase error. We also provide heuristic algorithms for creating reflexive stabilizer codes starting from the noise of a quantum channel. Furthermore, we show that the problem can be posed in terms of finding maximal Cayley subgraphs with restrictions imposed by the set of potential errors.
Long distance communication of digital data, whether through a physical medium or a broadcast signal, is often subjected to noise. To deliver data reliably through noisy communication channels, one must use codes that can detect and correct the particular noise of the channel. For transmission of classical data, error correcting schemes can be as simple as the sending of replicates. For quantum data, and in tandem the development of machines that can process quantum data, quantum error correcting codes must be developed. In addition to a larger set of possible errors, quantum error correcting schemes must contend with other peculiarities of quantum mechanics, such as the no-cloning theorem which can prevent the sending of replicate messages. Stabilizer codes are one family of quantum error correcting codes which can protect and correct errors expressed in terms of the Pauli group, exploiting its group structure and utilizing classical codes and the corresponding duals. We develop and examine a family of quantum stabilizer codes which arise from reflexive stabilizers. Moreover, we provide a mapping from our reflexive stabilizer codes to the well-known CSS codes developed by Calderbank, Shor, and Steane. For the case of a 4-state system we show that these codes can obtain the minimal embedding for code which can correct any flip or phase error. We also provide heuristic algorithms for creating reflexive stabilizer codes starting from the noise of a quantum channel. Furthermore, we show that the problem can be posed in terms of finding maximal Cayley subgraphs with restrictions imposed by the set of potential errors.
We investigate a class of quantum error-correcting codes to correct errors on both qubits and higher-state quantum systems represented as qudits. These codes arise from an original graph-theoretic representation of sets of quantum errors. In this framework, we represent the algebraic conditions for error correction in terms of edge avoidance between graphs providing a visual representation of the interplay between errors and error-correcting codes. Most importantly, this framework supports the development of quantum codes that correct against a predetermined set of errors, in contrast to current methods. A heuristic algorithm is presented, providing steps to develop codes that correct against an arbitrary noisy channel. We benchmark the correction capability of reflexive stabilizer codes for the case of single-qubit errors by comparison to existing stabilizer codes that are widely used. In addition, we present two instances of optimal encodings: an optimal encoding for fully correlated noise, which achieves a higher encoding rate than previously known, and a minimal encoding for single-qudit errors on a four-state system..
Noise is a major obstacle in the development of practical schemes for quantum computation and communication. Similar to the case of classical communication, this noise can be protected against by employing a code, which provides a means for encoding quantum states prior to transmission and allows for errors to be inferred, and hopefully corrected, by a decoder at the receiver. Unfortunately, designing good codes and decoders is typically a difficult problem. This thesis focuses on developing low-complexity heuristic approaches to three such problems: the design of modified belief propagation decoders for quantum low-density parity-check codes, the design of stabilizer codes for asymmetric channels, and the design of codeword stabilized codes. Quantum low-density parity-check codes are stabilizer codes with low-weight generators. Such codes permit low-complexity decoding via the use of belief propagation, which is an iterative message passing algorithm that takes place on a factor graph defined by the code. However, the performance of such a decoder is limited both by code structure and the degenerate nature of quantum errors. To overcome these limitations, at least in part, a number of modifications to belief propagation are developed. Central among these is the augmented decoder, which in the case of a decoding error, iteratively reattempts decoding using modified factor graph. This heuristic modification simply involves the duplication of a randomly selected subset of the graph’s check nodes, which are in one-to-one correspondence with the code’s stabilizer generators. Across a range of codes, it is shown that the decoders developed perform as well as or better than other modified decoders presented in literature. For a number of channels of physical interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these so-called asymmetric channels, the decoding error rate can be minimized by tailoring the code used to the channel. However, assessing the performance of codes on a given channel is made difficult by the #P-completeness of optimal decoding. To address this complexity, it is shown that the decoding error rate can be accurately approximated using only a small fraction of the possible errors caused by the channel. This approximation is then used to identify a number of cyclic stabilizer codes that perform well on two different asymmetric channels. To further build on this, a heuristic is demonstrated for assessing code performance based on the decoding error rate of an associated classical code. The complexity of calculating this classical error rate is relatively low, and it is shown that it can be used as the basis for a hill-climbing search algorithm. Such searches have yielded a large number of highly performant codes satisfying various structure constraints. The family of codeword stabilized codes encompasses both the stabilizer codes as well as many of the best known nonadditive codes. Constructing a standard form codeword stabilized code is a matter of selecting a simple undirected graph and a binary classical code. This makes designing optimal codes difficult as the number of possible graphs grows exponentially with code length, and the clique search required to construct the classical code is NP-hard. To address the exponential growth of the search space, a heuristic is developed for assessing graphs. This heuristic is then employed by a genetic algorithm that also makes use of a novel crossover operation based on spectral bisection, which is show to be superior to more standard crossover operations. With a graph selected, it is demonstrated that the complexity of the clique search required to construct the associated classical code can be mitigated through the use of a heuristic clique finding algorithm. A number of best known codes are presented that have been found using this approach.
This chapter deals with the subject of quantum error correction and the related codes (QECC), which can be applied to noisy quantum channels and quantum memories with the purpose of preserving or protecting the information integrity. I first describe the basics of quantum repetition codes , as applicable to bit-flip and phase-flip quantum channels. Then I consider the 9-qubit Shor code , which has the capability of diagnosing and correcting any combination of bit-flip and phase-flip errors, up to one error of each type. Furthermore, it is shown that the Shor code is, in fact, capable of fully restoring qubit integrity under a continuum of bit or phase errors, a property that has no counterpart in the classical world of error-correction codes. But the exploration of QECC does not stop here! We shall discover the elegant Calderbank–Shor–Steane (CSS) codes, which have the capability of correcting any number of errors t , both bit-flip and phase-flip. As an application of the CSS code, I then describe the 7-qubit Hadamard–Steane code , which can correct up to one error on single qubits. A corresponding quantum circuit, based on an original generator-matrix example, is presented. Quantum repetition code In Chapter 11, we saw that the simplest form of error-correction code (ECC) is the repetition code , based on the principle of majority logic . The background assumption is that in a given message sequence, or bit string, the probability of a bit error is sufficiently small for the majority of bits to be correctly transmitted through the channel.
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.
Quantum error correction codes are needed to protect quantum systems from interference. An important family of quantum error correction codes are stabilizer codes. Many stabilizer codes in the literature belong to a subclass of stabilizer codes, referred to as CSS codes since they are based on the so-called CSS formalism. CSS codes have received significant attention because the dual-containing condition for the CSS formalism is relatively straightforward to satisfy and also because it is easy to produce CSS codes from classical error correction codes. However, some stabilizer codes in the literature show superior error correction performance than existing CSS codes, and are based on binary low-density parity-check (LDPC) codes. Since it has been shown that CSS codes based on nonbinary LDPC codes have good performance over quantum qubit channels, in this paper we investigate stabilizer codes based on nonbinary LDPC codes. In particular, we propose constructions of stabilizer codes based on nonbinary quasi-cyclic low-density parity-check (QC-LDPC) codes for qubit channels. The simulation results show that our QC-LDPC stabilizer codes decoded by a nonbinary sum-product algorithm have better performance than their binary counterparts.
We study mathematical, physical and computational aspects of the stabilizer formalism arising in quantum information and quantum computation. The measurement process of Pauli observables with its algorithm is given. It is shown that to detect genuine entanglement we need a full set of stabilizer generators and the stabilizer witness is coarser than the GHZ (Greenberger–Horne–Zeilinger) witness. We discuss stabilizer codes and construct a stabilizer code from a given linear code. We also discuss quantum error correction, error recovery criteria and syndrome extraction. The symplectic structure of the stabilizer formalism is established and it is shown that any stabilizer code is unitarily equivalent to a trivial code. The structure of graph codes as stabilizer codes is identified by obtaining the respective stabilizer generators. The distance of embeddable stabilizer codes in lattices is obtained. We discuss the Knill–Gottesman theorem, tableau representation and frame representation. The runtime of simulating stabilizer gates is obtained by applying stabilizer matrices. Furthermore, an algorithm for updating global phases is given. Resolution of quantum channels into stabilizer channels is shown. We discuss capacity achieving codes to obtain the capacity of the quantum erasure channel. Finally, we discuss the shadow tomography problem and an algorithm for constructing classical shadow is given.