Barcode scans, clear phone calls, reliable data storage, satellite communication, and large-scale quantum computation are all made possible by error correction. We present a handbook version of The Error Correction Zoo, a curated reference of methods for protecting classical or quantum information from errors during storage and transmission. The handbook includes descriptions of these error-correcting codes and a classification according to the symbols they use. It also catalogues relations among codes and related objects such as sphere packings, lattices, designs, groups, and classical and quantum phases of matter. The collection is intended both as a rigorous reference and as a practical aid for tracing the web of code relationships and uncovering new connections.
Comments
440 classical codes, 619 quantum codes, 15 c-q codes. Online zoo at https://errorcorrectionzoo.org/. Notify zookeeper of errors or issue a pull request at https://github.com/errorcorrectionzoo/eczoo_data
Barcode scans, clear phone calls, reliable data storage, satellite communication, and large-scale quantum computation are all made possible by error correction. We present a handbook version of The Error Correction Zoo, a curated reference of methods for protecting classical or quantum information from errors during storage and transmission. The handbook includes descriptions of these error-correcting codes and a classification according to the symbols they use. It also catalogues relations among codes and related objects such as sphere packings, lattices, designs, groups, and classical and quantum phases of matter. The collection is intended both as a rigorous reference and as a practical aid for tracing the web of code relationships and uncovering new connections.
In the preceding chapter we mentioned the inevitable errors that occur when one tries to send quantum signals over, say, an optical fiber, even when there is no eavesdropper. But errors in transmission are not a problem just for quantum cryptography. For this entire chapter we forget about sending quantum information and instead focus on simply transmitting ordinary data faithfully over some kind of channel. Moreover, we assume that the data either is not sensitive or has already been encrypted. Unfortunately, many methods for transmitting data are susceptible to outside influences that can cause errors. How do we protect information from these errors? Error-correcting codes provide a mathematical method of not only detecting these errors, but also correcting them. Nowadays error-correcting codes are ubiquitous; they are used, for example, in cell-phone transmissions and satellite links, in the representation of music on a compact disk, and even in the bar codes in grocery stores. The story of modern error-correcting codes began with Claude Shannon's famous paper “A Mathematical Theory of Communication,” which was published in 1948. Shannon worked for Bell Labs where he specialized in finding solutions to problems that arose in telephone communication. Quite naturally, he started considering ways to correct errors that occurred when information was transmitted over phone lines. Richard Hamming, who also worked at Bell Labs on this problem, published a groundbreaking paper in 1950 on the subject.
Noise is one of the central obstacles to building useful quantum computers, and quantum error correction (QEC) provides the framework for protecting quantum information against it. Unlike classical error correction, QEC must preserve fragile quantum states without copying them, measuring them directly, or destroying the information they encode. Driven by rapid progress in both theory and experiment, this challenge has grown into one of the most active areas of quantum information science. This tutorial gives a guided introduction to modern QEC, developing the core concepts of codes, syndromes, stabilizers, decoding, and fault tolerance before connecting them to major code families and current research directions. We cover both established constructions and newer developments, including topological and subsystem codes, bosonic and qudit codes, dynamical codes, and quantum low-density parity-check (qLDPC) codes. The emphasis is on building operational understanding: explaining not only what the main objects are, but how they are used in code design, error diagnosis, decoding, and fault-tolerant computation. The tutorial is intended for newcomers seeking a first path through QEC, as well as researchers looking for a coherent reference for the concepts, code families, and tools that arise in current work.
Quantum computing exists at the intersection of mathematics, physics, chemistry, and engineering; the main goal of quantum computing is the creation of devices and algorithms which use the properties of quantum mechanics to store, manipulate and measure information. There exist many families of algorithms, which, using non-classical logical operations, can outperform traditional, classical algorithms in terms of memory and processing requirements. In addition, quantum computing devices are fundamentally smaller than classical processors and memory elements; since the physical models governing their performance are applicable on all scales, as opposed to classical logic elements, whose underlying principles rely on the macroscopic nature of the device in question. \n \nQuantum algorithms, for the most part, are predicated on a theory of resources. It is often assumed that quantum computers can be placed in a precise fiducial state prior to computation, and that logical operations are perfect, inducing no error on the system which they affect. These assumptions greatly simplify algorithmic design, but are fundamentally unrealistic. In order to justify their use, it is necessary to develop a framework for using a large number of imperfect devices to simulate the action of a perfect device, with some acceptable probability of failure. This is the study of fault-tolerant quantum computing. In order to pursue this study effectively, it is necessary to understand the fundamental nature of generic quantum states and operations, as well as the means by which one can correct quantum errors. Additionally, it is important to attempt to minimize the use of computational resources in achieving error reduction and fault-tolerant computing. \n \nThis thesis is concerned with three projects related to the use of error-prone quantum systems to transmit and manipulate information. The first of these is concerned with the use of imperfectly-prepared states in error-correction routines. Using optimal quantum error correction, we are able to deduce a method of partially protecting encoded quantum information against preparation errors prior to encoding, using no additional qubits. The second of these projects details the search for entangled states which can be used to transmit classical information over quantum channels at a rate superior to classical states. The third of these projects concerns the transcoding of data from one quantum code into another using few ancillary resources. The descriptions of these projects are preceded by a brief introduction to representations of quantum states and channels, for completeness. \n \nThree techniques of general interest are presented in appendices. The first is an introduction to, and a minor advance in the development of optimal error correction codes. The second is a more efficient means of calculating the action of a quantum channel on a given state, given that the channel acts non-trivially only on a subsystem, rather than the entire system. Finally, we include documentation on a software package developed to aid the search for quantum transcoding operations.
Bits as well as qubits are affected by noise in transmission, the process of computation or even storage. We will refer to the error-prone area as a channel. The error is introduced by unwanted but unavoidable interaction with the rest of the world and needs to be corrected before the data can be reliable. Classically this is important in communication systems and there is a whole thriving field of study of classical error correction. In quantum systems, states are intrinsically so fragile that unless they are impossibly isolated from the rest of the world, errors or noise would make computation or communication using them infeasible. Fortunately, it was discovered early in the history of this subject that it is possible to encode qubits in special ways so as to make the information resilient to errors. The qubits are decoded at the end of the computation/communication (schematic of Figure 10.1).
Error-correcting codes are the means by which people compensate for interference in communication, and are essential for the accurate transmission and storage of digital data. All communication mechanisms and storage devices are subject to interference, typically called "noise," which corrupts communicated messages and stored data. Thus, for a communication system to faithfully transmit data, it must build redundancy into its transmissions in such a way that even if a transmission is partially corrupted, the intended message may be reconstructed. Error-correcting codes provide the mapping from messages to redundant transmissions. While a tremendous theoretical advance, more work is required before these codes can be used in practical communication systems. The decoding algorithms run in polynomial time, but need to be faster before they can be applied in practice.
The discovery in 1993 of the turbo codes Berrou C., A. and P. Glavieux Thitimajshima at the International Conférence of Communication Florida has revolutionized communication. This innovation made it possible to rediscovery the error correcting codes invented by Robert Gallager in 1963 and rediscovered by Mackay in 1995, currently called Low Density Parity Check (LDPC). This code is one of the error correction codes introduced by the transmission channel that have the fastest and most effective level of protection and correction of the information transmitted during the communication. This code has been almost generalized in communication standards such as satellites. The objective of our article is to minimize the number of iterations and in some cases completely remove the iteration produced by the LDPC code bit flipping algorithm. The result of this algorithm, if we take for example the LDPC code (n, k), the number of possible syndromes which we can find is 2k-1 and for each syndrome different from zero, we can do almost four iterations to correct the errors, which gives 4x(2k-1) iterations in totality. On the other hand, the proposed algorithm removes the iteration for k syndromes and reduces iterations for the rest of the cases from four to two iterations. This study of the new design gave more performance results and the results of the simulation below according to a hardware description language used in digital electronics using quartus software tools show the importance of this algorithm.