Why is classical computing possible at all? A silly question, but one which never ceases to amaze me. Part II of my attempt to explain one of my main research interests in quantum computing: “self-correcting quantum computers.” Prior parts: Part I
\n
\nLast time I discussed how quantum computing was a lot like classical probabilistic computing. Given this, one can think about a question which seems silly at first: how is it possible to compute when you have a classical probabilistic computer?<\/p>\n
Classical computers are both digital and deterministic. But if you go and take a microscope to your classical computer what you will see isn’t anything like these two categories. For example, if you go and look at the electrons in your silicon based transistor, not all of the electrons are doing the same things. Even in todays ultra pure system, real systems have defects (are dirty) and the electrons in the system are behaving in all sorts of strange ways. Of course the aggregate effect of all of these electrons bouncing around and doing all sorts of crazy things is, when digitized, deterministic. Thus the transistors in your computer are digital and deterministic in spite of the fact that the systems out of which they are constructed are both analog and probabilistic (or worse analog and quantum!) How is this possible? How is it possible to take probabilistic (read noisy) classical analog systems and turn them into deterministic digital computers? The answer to these questions isn’t as obvious at first thought as you might think. The first part of the answer is how to go from analog to digital. This is done, in most physical systems, by applying a discretization to some analog set of configurations. Of course, any such discretization must map some values which are nearby in an analog space to differing digital values. So there are always precision questions in defining digital configurations. But, and here is an important point, it is often possible to take an analog system and keep it out of the regimes of difficulty.<\/p>\n
| \n<\/td>\n<\/tr>\n | ||
| Claude Shannon<\/td>\n<\/tr>\n<\/table>\n Okay so going from analog to digital seems fairly straightforward. But what about going from probabilistic to deterministic. This problem, of how to take systems which change in time according to probabilistic laws, and turn them into systems which compute deterministically has quite a few answers. If we approach this problem from a simple theoretical perspective, then the answer really comes from the theory of classical error correction, and its further extension to the theory of fault-tolerant classical computation. The former of these is founded in the groundbreaking work of Claude Shannon. What Shannon and others showed was that if a classical system is sent through a probabilistic channel which destroys deterministic information, then repeated use of this channel, along with the ideas of classical error correction, can be used to make this probabilistic channel behave nearly deterministically (where nearly means as close to nearly as you want with a good scaling in the resources used.)
|