Kitaev's toric code is arguably the most studied quantum code and is expected to be implemented in future generations of quantum computers. The renormalisation decoders introduced by Duclos-Cianci and Poulin exhibit one of the best trade-offs between efficiency and speed, but one question that was left open is how they handle worst-case or adversarial errors, i.e. what is the order of magnitude of the smallest weight of an error pattern that will be wrongly decoded. We initiate such a study involving a simple hard-decision and deterministic version of a renormalisation decoder. We exhibit an uncorrectable error pattern whose weight scales like d1/2and prove that the decoder corrects all error patterns of weight less than $\frac{5}{6}{d^{{{\log }_2}(6/5)}}$, where d is the minimum distance of the toric code.
Kitaev's toric code is arguably the most studied quantum code and is expected to be implemented in future generations of quantum computers. The renormalisation decoders introduced by Duclos-Cianci and Poulin exhibit one of the best trade-offs between efficiency and speed, but one question that was left open is how they handle worst-case or adversarial errors, i.e. what is the order of magnitude of the smallest weight of an error pattern that will be wrongly decoded. We initiate such a study involving a simple hard-decision and deterministic version of a renormalisation decoder. We exhibit an uncorrectable error pattern whose weight scales like d1/2and prove that the decoder corrects all error patterns of weight less than 65dlog2(6/5), where d is the minimum distance of the toric code.
Kitaev's toric code is arguably the most studied quantum code and is expected to be implemented in future generations of quantum computers. The renormalisation decoders introduced by Duclos-Cianci and Poulin exhibit one of the best trade-offs between efficiency and speed, but one question that was left open is how they handle worst-case or adversarial errors, i.e. what is the order of magnitude of the smallest weight of an error pattern that will be wrongly decoded. We initiate such a study involving a simple hard-decision and deterministic version of a renormalisation decoder. We exhibit an uncorrectable error pattern whose weight scales like d1/2 and prove that the decoder corrects all error patterns of weight less than 65dlog2(6/5), where d is the minimum distance of the toric code.
Kitaev’s toric code is arguably the most studied quantum code and is expected to be implemented in future generations of quantum computers. The renormalisation decoders introduced by Duclos-Cianci and Poulin exhibit one of the best trade-offs between accuracy and efficiency, with a time complexity inO(nlog2n). One question that was left open is how they handle worst-case or adversarial errors, i.e. what is the order of magnitude of the smallest weight of an error pattern that will be wrongly decoded. We initiate such a study involving a simple hard-decision and deterministic version of a renormalisation decoder. We exhibit an uncorrectable error pattern whose weight scales liked1/2and prove that the decoder corrects all error patterns of weight less than 5/6dlog2(6/5), wheredis the minimum distance of the toric code.
Quantum Low-Density Parity-Check (LDPC) codes provide a promising solution to protect quantum information from errors and are therefore considered an important step in the realisation of a fullscale fault-tolerant quantum computer. In this thesis, we study quantum LDPC codes under three different approaches, providing insights into renormalisation decoding for Kitaev’s toric code, establishing bounds on the minimum distance of geometrically-local codes, and constructing small instances of quantum Tanner codes. Kitaev’s toric code is a prominent quantum LDPC code that is currently the most widely pursued for experimental implementation. We focus on the probabilistic renormalisation decoders introduced by Duclos- Cianci and Poulin, a family of decoders that exhibit one of the best trade-offs between accuracy and efficiency. We study how they handle adversarial errors by introducing a deterministic renormalisation decoder that does not use a priori probabilities of the error model. We find that this renormalisation decoder allows for fractal-like uncorrectable error patterns, and we obtain a lower bound on the weight of such errors. Due to physical constraints, a lot of attention has gone into quantum LDPC codes whose stabilisers act only on a limited number of nearby qubits. We extend the well-known Bravyi-Terhal bound to quantum codes defined by local constraints on a lattice quotient, providing a crucial insight into the limitations of geometrically-local stabiliser codes. As an application, we provide upper bounds on the minimum distance of Abelian Two-Block Group Algebra codes, a family of quantum LDPC codes for which the minimum distance is currently unknown. In recent years, asymptotically good quantum LDPC codes were constructed, but provable results on their minimum distances only apply to impractically long codes. Following the effort in the design of near-term implementable codes, we construct short instances of quantum Tanner codes using square complexes obtained from lifted products of regular graphs. Several explicit instances of these codes exhibit minimum distances surpassing the square root of the code length.
Quantum error correction is needed for future quantum computers. Classical error correcting codes are not suitable for this due to the nature of quantum mechanics. Therefore, new codes need to be developed. A promising candidate is the toric code, a surface code, because of its locality and its high error correcting capability and thresholds (the error probability below which increasing the size of the code decreases the failure rate). This thesis provides an introduction to quantum error correction and the stabilizer formalism, which is used to introduce the toric code. Several decoders are looked at, including the Minimum Weight Perfect Matching (MWPM) decoder and a recently developed decoder, the Union-Find (UF) decoder. The UF decoder is useful because of its almost-linear time complexity, while only reducing the threshold by a marginal amount compared to the MWPM decoder. In this thesis, the time complexity of the weighted growth version of the UF decoder is analysed. The toric code and the decoders have been implemented and simulated, and the thresholds have been determined. For the MWPM decoder, the threshold was determined to be 11.5±0.2%, which is not in agreement with the threshold in literature of 10.3%, and should not be possible according to the optimal threshold of about 11%. This probably is a result of the low grid sizes (up to a gridsize of 11) of the code used due to the time needed to simulate the MWPM decoder. For the UF decoder, the threshold found was 9.7 ± 0.9%, which is in agreement with the threshold of 9.9% found by N. Delfosse and N. Nickerson. The time complexity of the UF decoder has also been determined, and is indeed almost-linear as expected by the analysis.
flip is an extremely simple and maximally local classical decoder which has been used to great effect in certain classes of classical codes. When applied to quantum codes there exist constant-weight errors (such as half of a stabiliser) which are uncorrectable for this decoder, so previous studies have considered modified versions of flip , sometimes in conjunction with other decoders. We argue that this may not always be necessary, and present numerical evidence for the existence of a threshold for flip when applied to the looplike syndromes of a three-dimensional toric code on a cubic lattice. This result can be attributed to the fact that the lowest-weight uncorrectable errors for this decoder are closer (in terms of Hamming distance) to correctable errors than to other uncorrectable errors, and so they are likely to become correctable in future code cycles after transformation by additional noise. Introducing randomness into the decoder can allow it to correct these "uncorrectable" errors with finite probability, and for a decoding strategy that uses a combination of belief propagation and probabilistic flip we observe a threshold of ∼5.5% under phenomenological noise. This is comparable to the best known threshold for this code ( ∼7.1% ) which was achieved using belief propagation and ordered statistics decoding [Higgott and Breuckmann, 2022], a strategy with a runtime of O(n3) as opposed to the O(n) ( O(1) when parallelised) runtime of our local decoder. We expect that this strategy could be generalised to work well in other low-density parity check codes, and hope that these results will prompt investigation of other previously overlooked decoders.
Quantum computers have the possibility of a much reduced calculation load compared with classical computers in specific problems. Quantum error correction (QEC) is vital for handling qubits, which are vulnerable to external noise. In QEC, actual errors are predicted from the results of syndrome measurements by stabilizer generators, in place of making direct measurements of the data qubits. Here, we propose Quantum Golay code Error Correction (QGEC), a QEC method using Golay code, which is an efficient coding method in classical information theory. We investigated our method's ability in decoding calculations with the Transformer. We evaluated the accuracy of the decoder in a code space defined by the generative polynomials with three different weights sets and three noise models with different correlations of bit-flip error and phase-flip error. Furthermore, under a noise model following a discrete uniform distribution, we compared the decoding performance of Transformer decoders with identical architectures trained respectively on Golay and toric codes. The results showed that the noise model with the smaller correlation gave better accuracy, while the weights of the generative polynomials had little effect on the accuracy of the decoder. In addition, they showed that Golay code requiring 23 data qubits and having a code distance of 7 achieved higher decoding accuracy than toric code which requiring 50 data qubits and having a code distance of 5. This suggests that implementing quantum error correction using a Transformer may enable the Golay code to realize fault-tolerant quantum computation more efficiently.