Self-Correcting Quantum Computers, Part II

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

Last 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?

Why Is Classical Computation Possible?

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.

Claude Shannon

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

The basic idea of classical error correction is simple. If you are sending information down a line where these information can be distorted, then you can lessen the probability of this distortion by encoding your message redundantly. When such an encoding is performed on information, then after it is sent down the noisy line, a suitable decoding can be performed such that if the noise is not too strong, the probability of correctly transmitting the information is greater than if it was just used without the encoding. So, by using classical error correction, one can turn a channel where information evolves probabilistically into one which behave much less probabilistically. If enough encoding is used, this makes the transmission of information effectively deterministic.

John von Neumann

A refinement of the idea of classical error correction is the idea of fault-tolerant computation. This is the study of what happens when you are not just transmitting information down a noisy/probabilistic channel, but also allow all of the components of your computer to fail. Thus for instance, in fault-tolerant computation, things like your logic gates can act probabilistically. Further even things like preparing a classical system in a well defined state can be taken into account in fault-tolerant computation. Von Neumann was one of the first to consider how to build an entire computer out of components which were probabilistic. Von Neumann's theory showed, that in principle, if noise was not too strong, then it is possible to build a fault-tolerant classical computer out of faulty components.

Next Time..

In part III, I'll discuss how the story of why classical computation is possible is actually connected to reality. In other words, how does it relate to how your hard drive operates?