Towards reliable organisms: fault-tolerance in unconventional models of computation
Computation is often described in abstract and idealized terms. In this setting, the details of the computer can be neglected: different models of computation are interchangeable for a cost which is at most polynomial in the size of the task at hand. The situation is more complicated for computers c...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2024
|
| Online Access: | https://hdl.handle.net/1721.1/156347 https://orcid.org/0009-0006-8183-5203 |
| Summary: | Computation is often described in abstract and idealized terms. In this setting, the details of the computer can be neglected: different models of computation are interchangeable for a cost which is at most polynomial in the size of the task at hand. The situation is more complicated for computers composed of imperfect components which are liable to introduce errors into the computation. Early work by John von Neumann showed that computers composed of imperfect components could be used to simulate perfect computation with high probability through the introduction of redundancy at the hardware level, i.e. they could be made fault-tolerant if certain conditions were met. These conditions, however, depend crucially on the details of noisy computational primitives; while the principles of fault-tolerance remain---store and manipulate data redundantly and perform error correction throughout---the constructions must be designed bespoke to the primitives at hand. In this thesis, we present examples of fault-tolerance in less conventional models of computation and investigate cases in which hardware-level fault-tolerant design may be more efficient in spite of the requisite redundancy.
First, we develop new fault-tolerance results in unconventional models of classical and quantum computation.
In particular, we study a model of formula-based computation over larger alphabets subject to symmetric noise;
and show that performing computation with large alphabet majority gates results in strictly larger nominal thresholds than achievable using Boolean majority gates. We then move away from a formula-based architecture to study large-alphabet computation based on feed-forward artificial neural networks subject to analog noise. Using the biologically-inspired grid code, we show that fault-tolerant neural network-based computation can be achieved. Then, we envision quantum computation composed of subroutines---rather than gates---developing a method for the error correction of noisy quantum subroutines based on the quantum singular value transform.
Second, we seek a precise understanding when fault-tolerance is not only possible but preferable. In certain cases, the choice between non-fault-tolerant and fault-tolerant designs is clear: for classical computation, hardware-based fault-tolerance is rarely used due to existence of cheap and reliable transistors; in quantum computation, fault-tolerance appears to be the most economical route towards large-scale computation owing to the difficulty of reliably manipulating quantum information.
The trade-off may not be as clear in less conventional models of computation. We make a detailed accounting of the resources required to achieve fault-tolerance in a simple setting which allows us to precisely delineate a regime in which hardware-level fault-tolerance is preferred despite the requisite redundancy.
Lastly, we discuss some connections between the study of fault-tolerance and information theory. In particular, we argue that an algorithm we developed for noisy compression can be understood to be finding optimal encodings over noisy channel and is therefore helpful for designing good encodings of data for fault-tolerant computation. This is followed by a review of upper bounds on the fault-tolerant threshold based on information theoretic arguments. We suggest that new measures of information are needed if existing upper bounds are to be improved for circuits, and propose a high-level template for this work.
We end with a reflection on the term "organism'' and a discussion of the implications of this collection of results. |
|---|