Analog computers and the Church-Turing thesis

Question

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.

Answer 1

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.

Answer 2

that passage (written over a decade ago) is indeed key and invoking quite a bit of background knowledge and very well anticipating some future research directions. it is alluding to the field of hypercomputation which is sometimes at the fringes of TCS, because it studies models of computation that are supposedly "more powerful" than Turing machines. the interesting point about Turing machines here is that they have zero noise, so in a sense computer science is founded on this idealization which in some ways is physically unrealistic. and electronic systems mimic this noiselessness as a design principle, it is ever present in low level chip dynamics but very effectively abstracted away in the higher level designs that restrict all electrical signals to ideal 0/1 bits. re this:

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.

it would appear that some of their assertions are looking rather prematurely optimistic in retrospect. it is true that large amounts of theory have been devised in QM error correcting codes. however, very little of it has been experimentally tested and verified. there are some scientists/ experts who suspect/ hypothesize that there may be physical laws that require noise to scale in a "bad" way for larger n-bit quantum systems. so its an area of active research and some controversy. in fact this is a key area of contention for two leading QM computing designs/ approaches, one by DWave systems and the other by the Martinis UCSB/Google group.

To be clear, I am asking if analog computers cannot beat Turing machines in efficiency due to noise.

that is the big question isnt it? to try to answer that, consider that there are classical analog systems and the more recently considered quantum systems. for classical systems, the general consensus is as outlined by Nielsen/ Chuang, that there are theoretical models that "seem" more powerful but when noise is correctly taken into account, this theoretical "advantage" "melts away". in other words to propose the existence of analog computing systems "fundamentally theoretically faster" than electronic systems already built seems to nearly violate the laws of physics/ thermodynamics.

however the question for QM computing is much more an open question and is (as they anticipate somewhat) hinging on the nature of QM noise and whether it can actually be experimentally/ controlled as has been hypothesized and is under active investigation.

there is some deeper analysis of these issues in Aaronsons paper NP-complete Problems and Physical Reality. the skeptical overview can be found in Dyakonov Prospects for quantum computing: extremely doubtful.