Fault tolerant quantum computation is a technique to perform reliable quantum computation using noisy components. In this context, quantum error correcting codes are used to keep the amount of errors under a sustainable threshold. One of the main problems of this field is to determine the minimum cost, in terms of memory and time, which is needed in order to transform an ideal quantum computation into a fault-tolerant one. In this PhD thesis, we show that the family of quantum expander codes and the small-set-flip decoder can be used in the construction of ref. [arXiv:1310.2984] to produce a fault-tolerant quantum circuit with constant space overhead. The error correcting code family and the decoder that we study has been introduced in ref. [arXiv:1504.00822] where an adversarial error model was examined. Based on the results of this article, we analyze quantum expander codes subjected to a stochastic error model which is relevant for fault-tolerant quantum computation [arXiv:1711.08351], [arXiv:1808.03821]. In addition, we show that the decoding algorithm can be parallelized to run in constant time. This is very relevant to prevent errors from accumulating while the decoding algorithm is running. Beyond the theoretical results described above, we perform a numerical analysis of quantum expander codes to measure their performance in practice [arXiv:1810.03681]. The error model used during these simulations generates X and Z type errors on the qubits with an independent and identically distributed probability distribution. Our results are promising because they reveal that these constant rate codes have a decent threshold and good finite length performance.
Fault tolerant quantum computation is a technique to perform reliable quantum computation using noisy components. In this context, quantum error correcting codes are used to keep the amount of errors under a sustainable threshold. One of the main problems of this field is to determine the minimum cost, in terms of memory and time, which is needed in order to transform an ideal quantum computation into a fault-tolerant one. In this PhD thesis, we show that the family of quantum expander codes and the small-set-flip decoder can be used in the construction of ref. [arXiv:1310.2984] to produce a fault-tolerant quantum circuit with constant space overhead. The error correcting code family and the decoder that we study has been introduced in ref. [arXiv:1504.00822] where an adversarial error model was examined. Based on the results of this article, we analyze quantum expander codes subjected to a stochastic error model which is relevant for fault-tolerant quantum computation [arXiv:1711.08351], [arXiv:1808.03821]. In addition, we show that the decoding algorithm can be parallelized to run in constant time. This is very relevant to prevent errors from accumulating while the decoding algorithm is running. Beyond the theoretical results described above, we perform a numerical analysis of quantum expander codes to measure their performance in practice [arXiv:1810.03681]. The error model used during these simulations generates X and Z type errors on the qubits with an independent and identically distributed probability distribution. Our results are promising because they reveal that these constant rate codes have a decent threshold and good finite length performance.
The threshold theorem is a seminal result in the field of quantum computing asserting that arbitrarily long quantum computations can be performed on a faulty quantum computer provided that the noise level is below some constant threshold. This remarkable result comes at the price of increasing the number of qubits (quantum bits) by a large factor that scales polylogarithmically with the size of the quantum computation we wish to realize. Minimizing the space overhead for fault-tolerant quantum computation is a pressing challenge that is crucial to benefit from the computational potential of quantum devices. In this paper, we study the asymptotic scaling of the space overhead needed for fault-tolerant quantum computation. We show that the polylogarithmic factor in the standard threshold theorem is in fact not needed and that there is a fault-tolerant construction that uses a number of qubits that is only a constant factor more than the number of qubits of the ideal computation. This result was conjectured by Gottesman who suggested to replace the concatenated codes from the standard threshold theorem by quantum error-correcting codes with a constant encoding rate. The main challenge was then to find an appropriate family of quantum codes together with an efficient classical decoding algorithm working even with a noisy syndrome. The efficiency constraint is crucial here: bear in mind that qubits are inherently noisy and that faults keep accumulating during the decoding process. The role of the decoder is therefore to keep the number of errors under control during the whole computation. On a technical level, our main contribution is the analysis of the SMALL-SET-FLIP decoding algorithm applied to the family of quantum expander codes . We show that it can be parallelized to run in constant time while correcting sufficiently many errors on both the qubits and the syndrome to keep the error under control. These tools can be seen as a quantum generalization of the BIT-FLIP algorithm applied to the (classical) expander codes of Sipser and Spielman.
Quantum computing has the potential to transform information technology by offering algorithms for certain tasks, such as quantum simulation, that are vastly more efficient than what is possible with any classical device. But experimentally implementing practical quantum information processing is a very difficult task. Here we study two important, and closely related, aspects of this challenge: architectures for quantum computing, and quantum error correction Exquisite quantum control has now been achieved in small ion traps, in nitrogen-vacancy centres and in superconducting qubit clusters, but the challenge remains of how to scale these systems to build practical quantum devices. In Part I of this thesis we analyse one approach to building a scalable quantum computer by networking together many simple processor cells, thus avoiding the need to create a single complex structure. The difficulty is that realistic quantum links are very error prone. Here we describe a method by which even these error-prone cells can perform quantum error correction. Groups of cells generate and purify shared resource states, which then enable stabilization of topologically encoded data. Given a realistically noisy network (10% error rate) we find that our protocol can succeed provided that all intra-cell error rates are below 0.8%. Furthermore, we show that with some adjustments, the protocols we employ can be made robust also against high levels of loss in the network interconnects. We go on to analyse the potential running speed of such a device. Using levels of fidelity that are either already achievable in experimental systems, or will be in the near-future, we find that employing a surface code approach in a highly noisy and lossy network architecture can result in kilohertz computer clock speeds. In Part II we consider the question of quantum error correction beyond the surface code. We consider several families of topological codes, and determine the minimum requirements to demonstrate proof-of-principle error suppression in each type of code. A particularly promising code is the gauge color code, which admits a universal transversal gate set. Furthermore, a recent result of Bombin shows the gauge color code supports an error-correction protocol that achieves tolerance to noisy measurements without the need for repeated measurements, so called single-shot error correction. Here, we demonstrate the promise of single-shot error correction by designing a decoder and investigating its performance. We simulate fault-tolerant error correction with the gauge color code, and estimate a sustainable error rate, i.e. the threshold for the long time limit, of ~0.31% for a phenomenological noise model using a simple decoding algorithm.
This thesis is concerned with fault-tolerant quantum information processing using quantum error-correcting codes. It contains two major pieces of work. The first is a study of coherent noise in the context of stabilizer error-correcting codes. The second is a proposed scheme for a universal set of fault-tolerant logical gates in a particular code family built out of the 3D toric code. Chapter 1 provides an introduction to quantum computation and fault tolerance. Many basic concepts in error-correcting codes are defined. Special attention is paid to the set of code properties that are most likely to determine how easily a given fault-tolerant scheme might be implemented on a physical device. These include the fault-tolerant noise threshold and the overhead. In Chapters 2 and 3 we study the effectiveness of quantum error correction against coherent noise. Coherent errors (for example, unitary noise) can interfere constructively, so that in some cases the average infidelity of a quantum circuit subjected to coherent errors may increase quadratically with the circuit size; in contrast, when errors are incoherent (for example, depolarizing noise), the average infidelity increases at worst linearly with circuit size. We consider the performance of quantum stabilizer codes against a noise model in which a unitary rotation is applied to each qubit, where the axes and angles of rotation are nearly the same for all qubits. In Chapter 2 we introduce coherent noise and incoherent noise and a number of methods that are useful for the study of coherent noise. We study the repetition code as a basic example, and we also study a correlated noise model. In Chapter 3 we show that for the toric code subject to such independent coherent noise, and for minimal-weight decoding, the logical channel after error correction becomes increasingly incoherent as the length of the code increases, provided the noise strength decays inversely with the code distance. A similar conclusion holds for weakly correlated coherent noise. Our methods can also be used for analyzing the performance of other codes and fault-tolerant protocols against coherent noise. However, our result does not show that the coherence of the logical channel is suppressed in the more physically relevant case where the noise strength is held constant as the code block grows, and we recount the difficulties that prevented us from extending the result to that case. Nevertheless our work supports the idea that fault-tolerant quantum computing schemes will work effectively against coherent noise, providing encouraging news for quantum hardware builders who worry about the damaging effects of control errors and coherent interactions with the environment. Chapter 4 is connected to another aspect of fault tolerance, fault-tolerant logical gates. The toric code is a promising candidate for fault-tolerant quantum computation because of its high threshold and low-weight stabilizers. A universal gate set in the toric code generally requires magic state distillation, which can incur a significant qubit overhead. In this work we construct an error-correcting code in three dimensions based on the toric code that features a fault-tolerant T gate with no magic state distillation required. We further describe a subsystem version of our code which supports a universal set of fault-tolerant gates. This code can be converted into the stabilizer version using gauge-fixing. We also argue that our code can be converted to a (2+1)-D protocol, where a 2D lattice undergoes a measurement-based protocol over time. In this way, a fault-tolerant logical T gate can be realized in a 2D toric code structure.
We construct the first known fault-tolerant scheme for injecting states into quantum error-correcting codes with constant space and time overhead. That is, we construct a family of constant-rate quantum error-correcting codes for which a set of bare physical qubits can be injected, i.e. fault-tolerantly encoded, into a code block. Similarly, a code state can be ejected, i.e. fault-tolerantly decoded, back into bare physical qubits. We show that these injection and ejection procedures succeed under circuit-level locally stochastic noise, while incurring just a small constant probability of corrupting each qubit, which is unavoidable for bare physical qubits. We also show how to perform fault-tolerant error correction and code-state preparation under locally stochastic noise. All of our gadgets can be implemented with constant quantum circuit depth (i.e. are single-shot), and with a number of physical qubits growing linearly with the number of logical qubits, assuming the ability to run polynomial-sized noiseless classical circuits on the side.
We construct our quantum codes by taking a high-dimensional hypergraph product of classical LDPC codes, which in turn are a simplified version of Spielman's linear-time encodable codes (STOC'95). As our resulting product codes are only resilient to physical errors occurring with non-uniform probabilities across qubits, we then show how to concatenate with inner codes of various sizes to obtain fault-tolerance against uniform noise.
Quantum computers have the potential to solve several interesting problems in polynomial \ntime for which no polynomial time classical algorithms have been found. However, \none of the major challenges in building quantum devices is that quantum systems are very \nsensitive to noise arising from undesired interactions with the environment. Noise can lead \nto errors which can corrupt the results of the computation. Quantum error correction is \none way to mitigate the effects of noise arising in quantum devices. \nWith a plethora of quantum error correcting codes that can be used in various settings, \none of the main challenges of quantum error correction is understanding how well various \ncodes perform under more realistic noise models that can be observed in experiments. \nThis thesis proposes a new decoding algorithm which can optimize threshold values of \nerror correcting codes under different noise models. The algorithm can be applied to \nany Markovian noise model. Further, it is shown that for certain noise models, logical \nClifford corrections can further improve a code's threshold value if the code obeys certain \nsymmetries. \n \nSince gates and measurements cannot in general be performed with perfect precision, \nthe operations required to perform quantum error correction can introduce more errors \ninto the system thus negating the benefits of error correction. Fault-tolerant quantum \ncomputing is a way to perform quantum error correction with imperfect operations while \nretaining the ability to suppress errors as long as the noise is below a code's threshold. \nOne of the main challenges in performing fault-tolerant error correction is the high resource \nrequirements that are needed to obtain very low logical noise rates. With the use of \nflag qubits, this thesis develops new fault-tolerant error correction protocols that are applicable \nto arbitrary distance codes. Various code families are shown to satisfy the requirements \nof flag fault-tolerant error correction. We also provide circuits using a constant number of \nqubits for these codes. It is shown that the proposed flag fault-tolerant method uses fewer \nqubits than previous fault-tolerant error correction protocols. \n \nIt is often the case that the noise afflicting a quantum device cannot be fully characterized. \nFurther, even with some knowledge of the noise, it can be very challenging to use \nanalytic decoding methods to improve the performance of a fault-tolerant scheme. This \nthesis presents decoding schemes using several state of the art machine learning techniques \nwith a focus on fault-tolerant quantum error correction in regimes that are relevant to near \nterm experiments. It is shown that even in low noise rate regimes and with no knowledge \nof the noise, noise can be further suppressed for small distance codes. Limitations of machine \nlearning decoders as well as the classical resources required to perform active error \ncorrection are discussed. \n \nIn many cases, gate times can be much shorter than typical measurement times of \nquantum states. Further, classical decoding of the syndrome information used in quantum \nerror correction to compute recovery operators can also be much slower than gate times. \nFor these reasons, schemes where error correction can be implemented in a frame (known \nas the Pauli frame) have been developed to avoid active error correction. In this thesis, we \ngeneralize previous Pauli frame schemes and show how Clifford frame error correction can \nbe implemented with minimal overhead. Clifford frame error correction is necessary if the \nlogical component of recovery operators were chosen from the Clifford group, but could \nalso be used in randomized benchmarking schemes.
We show that quantum expander codes, a constant-rate family of quantum LDPC codes, with the quasi-linear time decoding algorithm of Leverrier, Tillich and Z\'emor can correct a constant fraction of random errors with very high probability. This is the first construction of a constant-rate quantum LDPC code with an efficient decoding algorithm that can correct a linear number of random errors with a negligible failure probability. Finding codes with these properties is also motivated by Gottesman's construction of fault tolerant schemes with constant space overhead.In order to obtain this result, we study a notion of α-percolation: for a random subset W of vertices of a given graph, we consider the size of the largest connected α-subset of W, where X is an α-subset of W if |X∩W|≥α|X|.