Quantum error-correcting codes are used to protect quantum information from decoherence. A raw state is mapped, by an encoding circuit, to a codeword so that the most likely quantum errors from a noisy quantum channel can be removed after a decoding process.A good encoding circuit should have some desired features, such as low depth, few gates, and so on. In this paper, we show how to practically implement an encoding circuit of gate complexity O(n(n - k + c)/ log n) for an [[n, k; c]] quantum stabilizer code with the help of c pairs of maximally-entangled states. For the special case of an [[n, k]] stabilizer code with c = 0, the encoding complexity is O(n(n-k)/ log n), which is previously known to be O(n2/ log n). For c > 0, this suggests that the benefits from shared entanglement come at an additional cost of encoding complexity.Finally we discuss decoding of entanglement-assisted quantum stabilizer codes and extend previously known computational hardness results on decoding quantum stabilizer codes.
Quantum error-correcting codes are used to protect quantum information from decoherence. A raw state is mapped, by an encoding circuit, to a codeword so that the most likely quantum errors from a noisy quantum channel can be removed after a decoding process.A good encoding circuit should have some desired features, such as low depth, few gates, and so on. In this paper, we show how to practically implement an encoding circuit of gate complexity O(n(n - k + c)/ log n) for an [[n, k; c]] quantum stabilizer code with the help of c pairs of maximally-entangled states. For the special case of an [[n, k]] stabilizer code with c = 0, the encoding complexity is O(n(n-k)/ log n), which is previously known to be O(n2/ log n). For c > 0, this suggests that the benefits from shared entanglement come at an additional cost of encoding complexity.Finally we discuss decoding of entanglement-assisted quantum stabilizer codes and extend previously known computational hardness results on decoding quantum stabilizer codes.
We introduce a construction for entanglement-assisted quantum error-correcting codes (EAQECCs) that saturates the classical Singleton bound with less shared entanglement than any known method for code rates below $ \frac{k}{n} = \frac{1}{3} $. For higher rates, our EAQECC also meets the Singleton bound, although with increased entanglement requirements. Additionally, we demonstrate that any classical [n,k,d]q code can be transformed into an EAQECC with parameters [[n,k,d;2k]]q using 2k pre-shared maximally entangled pairs. The complexity of our encoding protocol for k-qudits with q levels is O(klogq−1q(k)), excluding the complexity of encoding and decoding the classical MDS code. While this complexity remains linear in k for systems of reasonable size, it increases significantly for larger-levelled systems, highlighting the need for further research into complexity reduction.
We show how entanglement-assisted codes can be constructed from arbitrary quantum codes by associating them with quantum codes for erasure channels. If a subset of physical qubits is correctable for an erasure error, then it naturally forms the receiver's share of a bipartite state that can be used for entanglement-assisted communications, both in the noiseless and noisy ebit error models. In the case of degenerate codes, we show that the receiver's share of the bipartite state can sometimes be compressed, at the cost of potentially reduced error-correction ability in the noisy ebit error model. We also give examples of permutation-invariant and XP-stabilizer entanglement-assisted codes, the first outside of the stabilizer and codeword-stabilized frameworks.
Quantum computing is an emerging technology that has the potential to achieve exponential speedups over their classical counterparts. To achieve quantum advantage, quantum principles are being applied to fields such as communications, information processing, and artificial intelligence. However, quantum computers face a fundamental issue since quantum bits are extremely noisy and prone to decoherence. Keeping qubits error free is one of the most important steps towards reliable quantum computing. Different stabilizer codes for quantum error correction have been proposed in past decades and several methods have been proposed to import classical error correcting codes to the quantum domain. Design of encoding and decoding circuits for the stabilizer codes have also been proposed. Optimization of these circuits in terms of the number of gates is critical for reliability of these circuits. In this paper, we propose a procedure for optimization of encoder circuits for stabilizer codes. Using the proposed method, we optimize the encoder circuit in terms of the number of 2-qubit gates used. The proposed optimized eight-qubit encoder uses 18 CNOT gates and 4 Hadamard gates, as compared to 14 single qubit gates, 33 2-qubit gates, and 6 CCNOT gates in a prior work. The encoder and decoder circuits are verified using IBM Qiskit. We also present encoder circuits for the Steane code and a 13-qubit code, that are optimized with respect to the number of gates used, leading to a reduction in number of CNOT gates by 1 and 8, respectively.
Quantum computers have the potential to provide exponential speedups over their classical counterparts. Quantum principles are being applied to fields such as communications, information processing, and artificial intelligence to achieve quantum advantage. However, quantum bits are extremely noisy and prone to decoherence. Thus, keeping the qubits error free is extremely important toward reliable quantum computing. Quantum error correcting codes have been studied for several decades and methods have been proposed to import classical error correcting codes to the quantum domain. Along with the exploration into novel and more efficient quantum error correction codes, it is also essential to design circuits for practical realization of these codes. This article serves as a tutorial on designing and simulating quantum encoder and decoder circuits for stabilizer codes. We first describe Shor’s 9-qubit code which was the first quantum error correcting code. We discuss the stabilizer formalism along with the design of encoding and decoding circuits for stabilizer codes such as the five-qubit code and Steane code. We also design nearest neighbor compliant circuits for the above codes. The circuits were simulated and verified using IBM Qiskit.
Recent years have seen rapid development in the subject of quantum coding theory, with breakthroughs on many exciting classes of codes, including quantum LDPC codes, quantum locally testable codes, and quantum codes with interesting transversal gates. However, a natural class of quantum codes, which has been well-studied classically, has not yet been treated: those which can be quickly encoded and decoded. This problem concerns the channel capacity setting, where a noise channel sits between perfect encoding and unencoding/decoding operations; this is the setting that is relevant for communication between fault-tolerant quantum computers. In this work, we construct asymptotically good quantum codes that can be encoded and unencoded by quantum circuits of logarithmic depth and consisting of a linear total number of gates. The classical decoding algorithms also run in logarithmic depth and use O(nlogn) gates, or alternatively a linear number of gates but with higher depth. We further construct explicit and asymptotically good quantum codes whose encoding, unencoding and decoding all use a linear number of gates, and additionally whose encoding and unencoding may be run in logarithmic depth.
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.