14
$\begingroup$

How well has the following problem been investigated in TCS? (I apologize if the problem statement sounds vague!)

Given a Model of Computation MC (Turing Machine, Cellular Automata, Kolmogorov-Uspenskii Machine ... etc.) and a Model of Noise that could affect the computation of MC, is there a way of recovering from the errors caused by this noise in an effective way? For instance, say some type of noise affects a Turing Machine M, could one devise a Turing Machine M' that simulates M without a major cost and is reliable (which means that M' is tolerant to this noise)?

It seems that some models of computations are better than others in doing this: Cellular Automata for instance. Any results if the noise is replaced by an adversary model?

Sorry for the tag! I don't have enough reputation to put a suitable tag (reliable-computing, fault-tolerant-computing ... etc.)

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ I think that you are essentially asking what is done in the field of fault-tolerant computing. $\endgroup$
    – Tsuyoshi Ito
    Jan 26, 2011 at 20:48

6 Answers 6

Reset to default
14
$\begingroup$

While there are some techniques that can be applied to fault-tolerance for all models, how resistant a computational model is to fault tolerance depends on the model. For instance, Peter Gacs has done quite a bit of research with fault tolerance on cellular automata, and he shows that (with a lot of work) you can build fault-tolerant cellular automata.

Von Neumann proved that by using redundancy, you could build a reliable computer out of unreliable components using only logarithmic overhead.

For quantum computation, quantum circuits can be made fault tolerant with polylogarithmic overhead ($\log^c n$ overhead, where finding the correct value of $c$ is still open). Another open question for quantum computation is whether adiabatic quantum computation can be made fault tolerant in a physically reasonable manner (physically reasonable means it is possible that the method leads to a scalable adiabatic quantum computer; for example, you're not allowed to take the temperature to 0 as the size of the computation gets larger).

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thanks Peter! I think Gacs managed to built an extremely complicated case in 1-dimension that exhibits fault-tolerance (ref. cs.bu.edu/faculty/gacs/papers/long-ca-ms.pdf). As for Von Neumann, is the logarithmic overhead in the number of components or the wires in each component? $\endgroup$
    – user2471
    Jan 28, 2011 at 2:01
  • $\begingroup$ For von Neumann, you should be able to arrange it either way. I believe he was actually talking about the number of components, though. For the 1-dimensional Gacs result, it exhibits some aspects of fault-tolerance, but I wouldn't call it real fault-tolerance. $\endgroup$
    – Peter Shor
    Jan 28, 2011 at 3:38
  • $\begingroup$ Why wouldn't you call Gacs 1-dimensional example fault tolerant? $\endgroup$
    – user2471
    Jan 28, 2011 at 3:57
  • $\begingroup$ I probably misspoke. Gacs' 1-dimensional example is able to remember one bit. This may be fault-tolerant memory, but it's not fault-tolerant computation. Also, if I remember correctly, this 1 bit doesn't really stay in the same place in Gacs' example, but is encoded by an ever-increasing number of cells. $\endgroup$
    – Peter Shor
    Jan 28, 2011 at 12:12
  • $\begingroup$ I may be wrong, but doesn't Gacs use some time of computation on the encoded data (without any need to decode/encode every time)? ref cs.bu.edu/faculty/gacs/papers/long-ca-ms.pdf section 5.2 Information storage and computation in various dimensions $\endgroup$
    – user2471
    Jan 28, 2011 at 16:37
2
$\begingroup$

I think work related to self-stabilisation is close to the spirit of your question.

A self-stabilising system recovers from any corruption of the RAM.

Improve this answer
$\endgroup$
2
$\begingroup$

The question asked is "Is there a way of recovering from the errors caused by [quantum] noise in an effective way?" and Peter Shor's answer admirably covers one effective way to answer this question, namely, by designing fault-tolerant quantum computers.

An alternative effective way is very commonly encountered in engineering practice. We reason "If the noise is sufficiently large that no quantum computation is feasible, then perhaps the system dynamics can be simulated with classical resources in P."

In other words, oftentimes we can "recover in an effective way" from noise by recognizing that the noise is providing an important service to us, by exponentially reducing the computational complexity of simulating both classical and quantum systems.

The literature on noise-centric approaches to dynamical simulation is large and growing; a recent reference whose theorems are both physically motivated and pleasingly rigorous, and which includes many references to the broader literature, is Plenio and Virmani's Upper bounds on fault tolerance thresholds of noisy Clifford-based quantum computers (arXiv:0810.4340v1).

Classical dynamicists use a very different language in which noise mechanisms go by the technical name of thermostats; Frenkel and Smit's Understanding Molecular Simulation: from Algorithms to Applications (1996) provides a basic mathematical introduction.

When we transcribe classical and quantum thermostats into the language of geometric dynamics, we find (unsurprisingly) that classical and quantum methods for exploiting noise to boost simulation efficiency are essentially identical; that their respective literatures so infrequently reference one another is largely an accident of history that has been sustained by notational obstructions.

Less rigorously but more generally, the above results illuminate the origins in quantum information theory of a heuristic rule that is widely embraced by chemists, physicists, and biologists, that any classical or quantum system that is in dynamical contact with a thermal bath is likely to prove simulable with computational resources in P for all practical purposes (FAPP).

The exceptions to this heuristic, both classical and quantum, represent important open problems. Their number strikingly diminishes year-by-year; the biennial Critical Assessment of Structure Prediction (CASP) provides one objective measure of this improvement.

The fundamental limits to this noise-driven, many-decade "More than Moore" progress in simulation capability are at present imperfectly known. Needless to say, in the long run our steadily improving understanding of these limits will bring us nearer to building quantum computers, while in the short run, this knowledge greatly assists us in efficiently simulating systems that are not quantum computers. Either way, it's good news.

Improve this answer
$\endgroup$
2
$\begingroup$

It looks like Gacs is on his way of constructing a fault-tolerant Turing machine. Take a look at this: http://arxiv.org/abs/1203.1335

Improve this answer
$\endgroup$
1
$\begingroup$

Quantum Computing models explicitly deal with noise and ways to make computations resilient to errors introduced through this vector. Quantum Computing, curiously, can be done forwards and backwards (by nature of QM Hadamard transforms and the time independence of the Hamiltonian) - "uncomputing" is one technique used to stem the tide of such errors.

On 'real' computers - Enterprise servers - there is a small but feasible chance that a bit of RAM will be read incorrectly. The theory of error detecting and correcting codes can be applied at a machine word level to detect and fix such 1-bit errors (without very much overhead). And in fact many Enterprise servers that have critical operations invite a small parity bit on each word of RAM.

While far from a proof it seems to me that standard error correcting coding schemes could be made to work with almost any theoretical automata (cellular automata are suspect) with only polynomial (in fact linear?) slowdown.

Improve this answer
$\endgroup$
4
  • $\begingroup$ there are definitely models of computation where arbitrary error correcting is not possible (i.e. where a fault-tolerance theorem can't be proven). Isn't that the reason that we rarely study analog computers anymore? $\endgroup$
    – Artem Kaznatcheev ♦
    Jan 27, 2011 at 3:10
  • 5
    $\begingroup$ Analog computers are perfectly capable of computing fault-tolerantly, but as far as I know only by simulating digital computers (or did you think your computer has actual bits in it, and not electrons and voltages?). $\endgroup$
    – Peter Shor
    Jan 27, 2011 at 4:49
  • $\begingroup$ Let me add a caveat to my previous comment. I am sure it is possible to make a restricted model of analog computation where fault tolerance is not possible, so Artem indeed has a good point about fault tolerance not applying to all models of computation. $\endgroup$
    – Peter Shor
    Feb 11, 2011 at 13:56
  • 1
    $\begingroup$ At both the classical and quantum level, no computer design is fault-tolerant against all classes of noise, imprecision, and instability. Moreover, the history of technology provides plenty of examples in which Nature's supply of noise mechanisms was underestimated; the Wikipedia-hosted 56-item "List of plasma instabilities" is a one-page summary of why fusion power roadmaps from the 1950s-1990s fell short. As classical and quantum computation architectures merge in coming decades, it will be mighty interesting to watch the list of known noise, imprecision, and instability mechanisms grow. $\endgroup$
    – John Sidles
    Feb 11, 2011 at 20:05
1
$\begingroup$

There is some work on so called "resilient" data structures and algorithm (search trees, counters, dictionary). The model is that of a RAM with the assumption that up to $k$ bits can be modified by an adversary at any time. Constantly many registers cannot be modified by the adversary. Depending on the parameter $k$, you can get algorithms that still work correctly, and whose running time dependency on $k$ is better than running $k$ independent copies of one algorithm. A recent invited talk of G. Italiano should give an overview: Resilient Algorithms and Data Structures (I just found this article and did not read it myself yet, but I am confident that it is a good pointer).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.