patternMinor
Analog computers and the Church-Turing thesis
Viewed 0 times
thethesiscomputerschurchandturinganalog
Problem
I'd like to quote from Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, page 5 (emphasis mine):
One class of challenges to the strong Church–Turing thesis comes from the field of
analog computation. In the years since Turing, many different teams of researchers have
noticed that certain types of analog computers can efficiently solve problems believed to
have no efficient solution on a Turing machine. At first glance these analog computers
appear to violate the strong form of the Church–Turing thesis. Unfortunately for analog
computation, it turns out that when realistic assumptions about the presence of noise in
analog computers are made, their power disappears in all known instances; they cannot
efficiently solve problems which are not efficiently solvable on a Turing machine. This
lesson – that the effects of realistic noise must be taken into account in evaluating the
efficiency of a computational model – was one of the great early challenges of quantum
computation and quantum information, a challenge successfully met by the development
of a theory of quantum error-correcting codes and fault-tolerant quantum computation.
Thus, unlike analog computation, quantum computation can in principle tolerate a finite
amount of noise and still retain its computational advantages.
Is this a statement that noise scales faster than some power of the problem size, or can someone point me in the right direction so that I can find out more about whether these scaling limits are fundamental or merely an "engineering issue"?
To be clear, I am asking if analog computers cannot beat Turing machines in efficiency due to noise.
One class of challenges to the strong Church–Turing thesis comes from the field of
analog computation. In the years since Turing, many different teams of researchers have
noticed that certain types of analog computers can efficiently solve problems believed to
have no efficient solution on a Turing machine. At first glance these analog computers
appear to violate the strong form of the Church–Turing thesis. Unfortunately for analog
computation, it turns out that when realistic assumptions about the presence of noise in
analog computers are made, their power disappears in all known instances; they cannot
efficiently solve problems which are not efficiently solvable on a Turing machine. This
lesson – that the effects of realistic noise must be taken into account in evaluating the
efficiency of a computational model – was one of the great early challenges of quantum
computation and quantum information, a challenge successfully met by the development
of a theory of quantum error-correcting codes and fault-tolerant quantum computation.
Thus, unlike analog computation, quantum computation can in principle tolerate a finite
amount of noise and still retain its computational advantages.
Is this a statement that noise scales faster than some power of the problem size, or can someone point me in the right direction so that I can find out more about whether these scaling limits are fundamental or merely an "engineering issue"?
To be clear, I am asking if analog computers cannot beat Turing machines in efficiency due to noise.
Solution
First of all, the authors seem to be confusing two different thesis: the Church–Turing thesis and the Cook–Karp thesis. The first concerns what is computable, and the second concerns what is computable efficiently.
According to the Cook–Karp thesis, all reasonable "strong" computational models are polynomially equivalent, in the sense that they all polynomially simulate each other. Equivalently, every reasonable computational model can be polynomially simulated by a Turing machine. Quantum computers are a counterexample to this thesis, since they appear to be exponentially more efficient than classical computers. However, they are not a counterexample to the Church–Turing thesis, that is, using quantum computers you can't compute anything that you can't already compute with a Turing machine. We can also formulate an updated Cook–Karp thesis, stating that all physically realizable computational models are polynomially simulated by quantum computers.
Several physical models of computations have been proposed as challenging these theses, but under scrutiny, they all seem to not violate the Church–Turing thesis, or not to be more powerful than quantum computation. Scott Aaronson proposes to consider this situation as a "law of nature". However, as far as I know there are no theoretical arguments supporting these theses other than the inductive argument that all models which have been proposed have been shown to conform to them.
According to the Cook–Karp thesis, all reasonable "strong" computational models are polynomially equivalent, in the sense that they all polynomially simulate each other. Equivalently, every reasonable computational model can be polynomially simulated by a Turing machine. Quantum computers are a counterexample to this thesis, since they appear to be exponentially more efficient than classical computers. However, they are not a counterexample to the Church–Turing thesis, that is, using quantum computers you can't compute anything that you can't already compute with a Turing machine. We can also formulate an updated Cook–Karp thesis, stating that all physically realizable computational models are polynomially simulated by quantum computers.
Several physical models of computations have been proposed as challenging these theses, but under scrutiny, they all seem to not violate the Church–Turing thesis, or not to be more powerful than quantum computation. Scott Aaronson proposes to consider this situation as a "law of nature". However, as far as I know there are no theoretical arguments supporting these theses other than the inductive argument that all models which have been proposed have been shown to conform to them.
Context
StackExchange Computer Science Q#35343, answer score: 7
Revisions (0)
No revisions yet.