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.
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.
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.
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.
We still do not have perfect decoders for topological codes that can satisfy all needs of different experimental setups. Recently, a few neural network based decoders have been studied, with the motivation that they can adapt to a wide range of noise models, and can easily run on dedicated chips without a full-fledged computer. The later feature might lead to fast speed and the ability to operate at low temperatures. However, a question which has not been addressed in previous works is whether neural network decoders can handle 2D topological codes with large distances. In this work, we provide a positive answer for the toric code \cite{Kitaev2003Faulttolerantanyon}. The structure of our neural network decoder is inspired by the renormalization group decoder \cite{duclos2010fast, duclos2013fault}. With a fairly strict policy on training time, when the bit-flip error rate is lower than 9% and syndrome extraction is perfect, the neural network decoder performs better when code distance increases. With a less strict policy, we find it is not hard for the neural decoder to achieve a performance close to the minimum-weight perfect matching algorithm. The numerical simulation is done up to code distance d=64 . Last but not least, we describe and analyze a few failed approaches. They guide us to the final design of our neural decoder, but also serve as a caution when we gauge the versatility of stock deep neural networks. The source code of our neural decoder can be found at \cite{sourcecodegithub}.