For a number of quantum channels of interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these asymmetric channels, the decoding error rate can be reduced by tailoring the code used to the channel. However, analyzing the performance of stabilizer codes on these channels is made difficult by the #P-completeness of optimal decoding. To address this, at least for short codes, we demonstrate that the decoding error rate can be approximated by considering only a fraction of the possible errors caused by the channel. Using this approximate error rate calculation, we extend a recent result to show that there are a number of $[[5\ensuremath{\le}n\ensuremath{\le}12,1\ensuremath{\le}k\ensuremath{\le}3]]$ cyclic stabilizer codes that perform well on two different asymmetric channels. We also demonstrate that an indication of a stabilizer code's error rate is given by considering the error rate of a classical binary code related to the stabilizer. This classical error rate is far less complex to calculate, and we use it as the basis for a hill-climbing algorithm, which we show to be effective at optimizing codes for asymmetric channels. Furthermore, we demonstrate that simple modifications can be made to our hill-climbing algorithm to search for codes with desired structure requirements.
For a number of quantum channels of interest, phase-flip errors occur far more frequently than bit-flip errors. When transmitting across these asymmetric channels, the decoding error rate can be reduced by tailoring the code used to the channel. However, analyzing the performance of stabilizer codes on these channels is made difficult by the #P-completeness of optimal decoding. To address this, at least for short codes, we demonstrate that the decoding error rate can be approximated by considering only a fraction of the possible errors caused by the channel. Using this approximate error rate calculation, we extend a recent result to show that there are a number of [[5\ensuremath≤n\ensuremath≤12,1\ensuremath≤k\ensuremath≤3]] cyclic stabilizer codes that perform well on two different asymmetric channels. We also demonstrate that an indication of a stabilizer code's error rate is given by considering the error rate of a classical binary code related to the stabilizer. This classical error rate is far less complex to calculate, and we use it as the basis for a hill-climbing algorithm, which we show to be effective at optimizing codes for asymmetric channels. Furthermore, we demonstrate that simple modifications can be made to our hill-climbing algorithm to search for codes with desired structure requirements.
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.
Recently, quantum error-correcting codes have been proposed that capitalize on the fact that many physical error models lead to a significant asymmetry between the probabilities for bit- and phase-flip errors. An example for a channel that exhibits such asymmetry is the combined amplitude damping and dephasing channel, where the probabilities of bit and phase flips can be related to relaxation and dephasing time, respectively. We study asymmetric quantum codes that are obtained from the Calderbank–Shor–Steane (CSS) construction. For such codes, we derive upper bounds on the code parameters using linear programming. A central result of this paper is the explicit construction of some new families of asymmetric quantum stabilizer codes from pairs of nested classical codes. For instance, we derive asymmetric codes using a combination of Bose–Chaudhuri–Hocquenghem (BCH) and finite geometry low-density parity-check (LDPC) codes. We show that the asymmetric quantum codes offer two advantages, namely to allow a higher rate without sacrificing performance when compared with symmetric codes and vice versa to allow a higher performance when compared with symmetric codes of comparable rates. Our approach is based on a CSS construction that combines BCH and finite geometry LDPC codes.
Mapping an error syndrome to the error operator is the core of quantum decoding network and is also the key step of recovery. The definitions of the bit-flip error syndrome matrix and the phase-flip error syndrome matrix were presented, and then the error syndromes of quantum errors were expressed in terms of the columns of the bit-flip error syndrome matrix and the phase-flip error syndrome matrix. It also showed that the error syndrome matrices of a stabilizer code are determined by its check matrix, which is similar to the classical case. So, the error-detection and recovery techniques of classical linear codes can be applied to quantum stabilizer codes after some modifications. Some necessary and/or sufficient conditions for the stabilizer code over GF(2) is degenerate or nondegenerate for Pauli channel based on the relationship between the error syndrome matrices and the check matrix was presented. A new way to find the minimum distance of the quantum stabilizer codes based on their check matrices was presented, and followed from which we proved that the performance of degenerate quantum code outperform (at least have the same performance) nondegenerate quantum code for Pauli channel.
Recently, quantum error-correcting codes were proposed that capitalize on the fact that many physical error models lead to a significant asymmetry between the probabilities for bit flip and phase flip errors. An example for a channel which exhibits such asymmetry is the combined amplitude damping and dephasing channel, where the probabilities of bit flips and phase flips can be related to relaxation and dephasing time, respectively. We give systematic constructions of asymmetric quantum stabilizer codes that exploit this asymmetry. Our approach is based on a CSS construction that combines BCH and finite geometry LDPC codes.
This thesis deals with the study of computational complexity of decoding stabilizer codes. The first three chapters contain all the necessary background to understand the main result of this thesis. First, we explain the necessary notions in computational complexity, introducing P, NP, #P classes of problems, along with some examples intended for physicists. Then, we explain the decoding problem in classical error correction, for linear codes on the binary symmetric channel and discuss the celebrated result of Mcleicee et al., in [1]. In the third chapter, we study the problem of quantum communication, over Pauli channels. Here, using the stabilizer formalism, we discuss the concept of degenerate errors. The decoding problem for stabilizer codes, which simply neglects the presence of degenerate errors, is called quantum maximum likelihood decoding (QMLD) and it was shown to be NP-complete, by Min Hseiu Heish et al., in [2]. We focus on the problem of optimal decoding, called degenerate quantum maximum likelihood decoding (DQMLD), which accounts for the presence of degenerate errors. We will highlight some instances of stabilizer codes, where the presence of degenerate errors causes drastic variations between the performances of DQMLD and QMLD. The main contribution of this thesis is to demonstrate that the optimal decoding problem for stabilizer codes is much harder than what the previous results had anticipated. In the last chapter, we present our own result (in Thm. 5.1.1), establishing that the optimal decoding problem for stabilizer codes, is #P-complete. To prove this, we demonstrate that the problem of evaluating the weight enumerator of a binary linear code, which is #P-complete, can be reduced (in polynomial time) to the DQMLD problem, see (Sec. 5.1). Our principal result is also presented as an article in [3], which is currently under review for publication in IEEE Transactions on Information Theory. In addition to the main result, we also show that under certain conditions, the outputs of DQMLD and QMLD always agree. We consider the conditions developed by us to be an improvement over the ones in [4, 5].
The performance of quantum error correction can be significantly improved if detailed information about the noise is available, allowing to optimize both codes and decoders. It has been proposed to estimate error rates from the syndrome measurements done anyway during quantum error correction. While these measurements preserve the encoded quantum state, it is currently not clear how much information about the noise can be extracted in this way. So far, apart from the limit of vanishing error rates, rigorous results have only been established for some specific codes. In this work, we rigorously resolve the question for arbitrary stabilizer codes. The main result is that a stabilizer code can be used to estimate Pauli channels with correlations across a number of qubits given by the pure distance. This result does not rely on the limit of vanishing error rates, and applies even if high weight errors occur frequently. Moreover, it also allows for measurement errors within the framework of quantum data-syndrome codes. Our proof combines Boolean Fourier analysis, combinatorics and elementary algebraic geometry. It is our hope that this work opens up interesting applications, such as the online adaptation of a decoder to time-varying noise.