<p>The question asked is "Is there a way of recovering from the errors caused by [quantum] noise in an effective way?" and <a href="https://cstheory.stackexchange.com/questions/4565/what-is-known-about-the-effectiveness-of-reliable-computing/4583#4583">Peter Shor's answer</a> admirably covers one effective way to answer this question, namely, by designing fault-tolerant quantum computers.</p>

<p>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."   </p>

<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.</p>

<p>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 <a href="http://arxiv.org/abs/0810.4340v1" rel="nofollow noreferrer"><i>Upper bounds on fault tolerance thresholds of noisy Clifford-based quantum computers</i></a> (arXiv:0810.4340v1).</p>

<p>Classical dynamicists use a very different language in which noise mechanisms go by the technical name of <i>thermostats</i>; Frenkel and Smit's <a href="http://books.google.com/books?id=5qTzldS9ROIC&amp;pg=PA1" rel="nofollow noreferrer"><i>Understanding Molecular Simulation: from Algorithms to Applications</i></a> (1996) provides a basic mathematical introduction.</p>

<p>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.</p>

<p>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).  </p>

<p>The exceptions to this heuristic, both classical and quantum, represent important open problems.  Their number strikingly diminishes year-by-year; the biennial <a href="http://www.predictioncenter.org/casp8/index.cgi?page=description_exper" rel="nofollow noreferrer"><i>Critical Assessment of Structure Prediction</i> (CASP)</a> provides one objective measure of this improvement.  </p>

<p>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 <i>not</i> quantum computers.  Either way, it's good news.</p>

CC BY-SA 2.5
2011-02-11T18:11:07.020Z
2011-02-11T18:32:59.233Z
2017-04-13T12:32:28.077Z
John Sidles
<p>It looks like Gacs is on his way of constructing a fault-tolerant Turing machine.
Take a look at this: <a href="http://arxiv.org/abs/1203.1335" rel="nofollow">http://arxiv.org/abs/1203.1335</a></p>

CC BY-SA 3.0
2012-04-04T16:10:34.287Z
2012-04-04T16:10:34.287Z
user8719
<p>I think work related to <a href="http://en.wikipedia.org/wiki/Self-stabilization" rel="nofollow">self-stabilisation</a> is close to the spirit of your question.</p>

<p>A self-stabilising system recovers from any corruption of the RAM.</p>

CC BY-SA 2.5
2011-01-26T20:06:18.930Z
2011-01-26T20:06:18.930Z
Jukka Suomela
<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-01-27T03:10:31.313Z
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?
Artem Kaznatcheev
CC BY-SA 2.5
2011-01-27T04:49:49.730Z
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?).
Peter Shor 
CC BY-SA 2.5
2011-02-11T13:56:25.240Z
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.
Peter Shor 
CC BY-SA 2.5
2011-02-11T20:05:40.593Z
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.
John Sidles
CC BY-SA 2.5
2011-01-26T18:07:03.027Z
2011-01-26T18:07:03.027Z
Ross Snider
<p>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: <a href="http://dx.doi.org/10.1007/978-3-642-13073-1_3" rel="nofollow">Resilient Algorithms and Data Structures</a>  (I just found this article and did not read it myself yet, but I am confident that it is a good pointer).</p>

CC BY-SA 2.5
2011-02-11T09:48:00.553Z
2011-02-11T09:48:00.553Z
Riko Jacob
<p>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.</p>

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

<p>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).</p>

CC BY-SA 3.0
2012-09-12T18:05:09.700Z
Daniel Lidar has addressed fault-tolerant AQC in arXiv:0707.0021
S Huntsman
CC BY-SA 3.0
2013-08-04T12:25:04.930Z
Lidar can make AQC fault-tolerant "against decoherence and certain control errors". That doesn't completely solve the problem; we'd like AQC that is fault-tolerant against decoherence and all small control errors.
Peter Shor 
CC BY-SA 2.5
2011-01-28T02:01:55.827Z
Thanks Peter! I think Gacs managed to built an extremely complicated case in 1-dimension that exhibits fault-tolerance (ref. http://www.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?
user2471
CC BY-SA 2.5
2011-01-28T03:38:03.433Z
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.
Peter Shor 
CC BY-SA 2.5
2011-01-28T03:57:20.807Z
Why wouldn't you call Gacs 1-dimensional example fault tolerant?
user2471
CC BY-SA 2.5
2011-01-28T12:12:34.660Z
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.
Peter Shor 
CC BY-SA 2.5
2011-01-28T16:37:01.363Z
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 http://www.cs.bu.edu/faculty/gacs/papers/long-ca-ms.pdf section 5.2 Information storage and computation in various dimensions
user2471
CC BY-SA 2.5
2011-01-28T16:48:46.100Z
@user2471: Actually, it looks like you're right. I'm remembering the situation from some years ago.
Peter Shor 
CC BY-SA 2.5
2011-01-27T05:07:59.840Z
2011-01-28T16:50:19.077Z
2011-01-28T16:50:19.077Z
Peter Shor 
<p>How well has the following problem been investigated in TCS? 
(I apologize if the problem statement sounds vague!) </p>

<p>Given a <b>Model of Computation</b> MC (Turing Machine, Cellular Automata, Kolmogorov-Uspenskii Machine ... etc.) and a <b> Model of Noise</b> that could affect the computation of MC, is there a way of <b>recovering</b> from the errors caused by this noise in an <b>effective</b> 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)?</p>

<p>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?</p>

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

CC BY-SA 2.5
2011-01-26T20:48:16.067Z
I think that you are essentially asking what is done in the field of fault-tolerant computing.
Tsuyoshi Ito
<machine-models>
What is known about the effectiveness of reliable computing?
user2471
# What is known about the effectiveness of reliable computing?

(Asked by: username_0 on 2011-01-26)

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.)

**Tags:** machine-models

> **Comments:**
> **username_1**: I think that you are essentially asking what is done in the field of fault-tolerant computing.  

---

## 6 answers

### Answer by username_7 on 2011-01-27. Score: 14 | Accepted answer

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).

> **Comments:**
> **username_0**: Thanks Peter! I think Gacs managed to built an extremely complicated case in 1-dimension that exhibits fault-tolerance (ref. http://www.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?  
> **username_7**: 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.  
> **username_0**: Why wouldn't you call Gacs 1-dimensional example fault tolerant?  
> **username_7**: 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.  
> **username_0**: 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 http://www.cs.bu.edu/faculty/gacs/papers/long-ca-ms.pdf section 5.2 Information storage and computation in various dimensions  
> **username_7**: @username_0: Actually, it looks like you're right. I'm remembering the situation from some years ago.  
> **username_9**: Daniel Lidar has addressed fault-tolerant AQC in arXiv:0707.0021  
> **username_7**: Lidar can make AQC fault-tolerant "against decoherence and certain control errors". That doesn't completely solve the problem; we'd like AQC that is fault-tolerant against decoherence and all small control errors.  

---

### Answer by username_2 on 2011-02-11. Score: 2

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](https://cstheory.stackexchange.com/questions/4565/what-is-known-about-the-effectiveness-of-reliable-computing/4583#4583) 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*](http://arxiv.org/abs/0810.4340v1) (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*](http://books.google.com/books?id=5qTzldS9ROIC&pg=PA1) (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)](http://www.predictioncenter.org/casp8/index.cgi?page=description_exper) 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.


---

### Answer by username_3 on 2012-04-04. Score: 2

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>


---

### Answer by username_4 on 2011-01-26. Score: 2

I think work related to [self-stabilisation](http://en.wikipedia.org/wiki/Self-stabilization) is close to the spirit of your question.

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


---

### Answer by username_5 on 2011-01-26. Score: 1

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.

> **Comments:**
> **username_6**: 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?  
> **username_7**: 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?).  
> **username_7**: 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.  
> **username_2**: 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.  

---

### Answer by username_8 on 2011-02-11. Score: 1

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](http://dx.doi.org/10.1007/978-3-642-13073-1_3) (I just found this article and did not read it myself yet, but I am confident that it is a good pointer).


---

