Author: dabacon

After reading Robert Laughlin’s book and thinking about his remarks on quantum computing, I’ve decided I can pinpoint exactly the error which he is making in his disregard for the possibility of building a quantum computer. The mistake, I believe, is basically a category error.
So let’s talk about computers. Computers are inheritly physical devices, so all discussion of what is and what is not a computer boils down, at some level to physics (I’m not taking a reductionist viewpoint here: I include the study of emergent properties of physical systems in what I call physics.) Now there are two separations which I want to make when I talk about what types of computers we encounter out in the wilds of the labratory: the first is the a description of the state space and the other is a description of the dynamics.
The state space of a classical computer come in two forms: digital and analog. For digital computers the state space is a discrete, finite space. Such state spaces don’t exist in nature (as far as we know) but are great approximations for a great series of physical devices. Thus the hard drive on your computer can store the value of a bit in the orientation of a ton of magnetic spins, but if we try to store a bit into a single spin we have problems. Every discrete finite space I know of is discrete only after some coarse graining. But surely, you say, quantum mechanics gives discrete state spaces, right? The energy levels from atomic orbitals are discrete. But this is only true if we have an isolated atomic system which does not interact with the rest of the universe. Introduce coupling to an electromagnetic field (acting either as the environment or as a measuring device) and these discrete energy levels “smear out,” meaning in effect that we can only think about them as discrete after we have coarse grained over this smearing. Whether there are truely discrete state spaces in physics (say in the wavefunction of the universe), I think, is something for which we have little concrete evidence.
Back to computers. On the opposite end of the spectrum from a digital computer, it has been useful to introduce the notion of an analog computer. Here the state space of the computer is taken to be some continuous parameter. Thus, for example, the position of a the planet Mercury could be considered a state space variable for our “solar system” computer. If one takes seriously the idea of an analog computer one runs into all sorts of problems. This is because it is easy to couple analog state spaces such that the variables of these systems are manipulated in such a way as to perform elementary arithmetic on these variables. And if you take seriously the continuous nature of the state space this allows you to do amazing things like solve NP-complete (and harder!) problems efficiently on these computers. Of course there is a fatal reason why no one has built such a computer: if we introduce any noise into these variables or we introduce imprecission in our measurements, this power disappears. (There is still interest in analog computers not, then, for the computational power arising from the continuous nature of their state spaces, but because the transformations one can perform on them are sometimes difficult to perform on a digital computer. There doesn’t seem to be any superpolynomial speedup in any such devices, but one might get more efficient algorithms because the dynamics happens to do something which is not natural for your digital computer.)
OK, so state spaces are digital or analog. And analog state spaces do not lead to robust computing devices. Now we move on to the second category describing classical computers, the dynamics. The first type of dynamics I want to draw out is deterministic evolution. In this case the time evolution of the state space is perfectly fixed by the initial conditions of the state space. So we set up our planets in a particular configuration and Newton’s laws (or general relativity) takes over and pushes forward the analog computation. Similarly two transistors work to enact a NAND gate where the digital data is transformed in a fully deterministic manner. As with the idea of digital data, deterministic evolution is often a consequence of some emergent property of the system (i.e. every once in a while your computer does have a hardware error…but you’ll have to wait around quite a long time for this to happen with modern computers!)
In the distinction between digital and analog, we saw that physics essentially gave us analog state spaces which for certain physical system, when we apply the appropriate coarse graining, we end up with a digital device. What, then, is the dynamics from which deterministic evolution arises for computer? For classical computers, this dynamics is basically probabilistic evolution. Instead of being able to completely predict the outcome of the evolution of the state space, now we can only predict the probability of the evolution. Sometimes this evolution is so unpredictable (so noisy) that there is no way for such a device to function as anything resembling a deterministic computer. But sometimes this evolution is predictable enough to allow us to construct a robust effectively deterministic computer from the evolution (and in the case of our real world computers this is effectively done for us by the physics of the semiconductor transistors.) It even seems that using the inherit probabilistic nature of the evolution can increase the computational power of the device (although this is certainly one of the outstanding problems in computer science: whether randomness really gives one any computational advantage (the BPP=P question).) So sometimes we not only want the probabilistic nature of our computer to yield deterministic evolution, but often we want it to evolve probabilistically, but in a manner such that we control the probabilities with a high degree of precission.
Notice further that the type of dynamics for a classical computer effects how we describe the state space of the computer. If the evolution is deterministic, we can just keep track of the variables, but one we introduce probabilistic evolution, we need to talk about probability distribtuions (over a discrete state space in the digital case and over a continuos state space in the analog case.)
So what is the category error which makes Laughlin sceptical of quantum computing? It appears that he is failing to distinguish between dynamics that is not deterministic and analog state spaces. The argument is basically that the amplitudes which appear in quantum theory are an analog state space and thus the computational power of quantum computers is analogous to that of analog classical computers. But this is to confuse the dynamics of a quantum computer (unitary evolution of probability amplitudes) with the state space itself. Among the first discoveries about quantum computers (which I basically credit to Bernstein and Vazirani) was that the amplitudes of quantum states behave, for most purposes, like probabilities and not like an analog state space. Indeed the state space of a quantum system can be either discrete (think energy levels) or continuous (think position of a particle). But since the dynamics is that funny form of evolution called unitary evolution, the description of either of these systems is in terms of probability amplitudes. Confusing the probability amplitudes with the state space is directly analogous to confusing the probability distribution of a classical system with the state space of the system.
Now just as probabilistically evolving digital classical computer can be made to act deterministically, we can talk about getting a digital quantum computer (digital means the state space is finite and discrete) to act deterministically. Or better yet, just as sometimes we desired probabilistic evolution with a given accuracy, we can get a digital quantum computer to behave as a unitary evolving systems with a given accuracy. This, of course, is what the theory of fault-tolerant quantum computation is designed to do. Of course the world didn’t have to give us the ability to perform fault-tolerant quantum computation, but this doesn’t seem to be true.
State spaces are different from the dynamics and hence the way we describe the system. In fact, it’s one of the reasons I cringe when I hear the word “analog” in discussions of not just quantum computers, but also in the biological sciences. The probabilistic nature of biological information processing has got nothing to do with the analog or digital nature of the underlying information (so while concentrations are analog, they should for all intensive purposes be thought of as a finite size frequentist version of probabilities.)
OK, I’ve clearly written too much on this subject. I’ll leave you be now. But just to finishing things off here is an interesting argument to give to those who believe that quantum computers are analog devices. As I mentioned above it is known how to use analog computers to solve NP-complete problems efficiently. But it is widely suspected that quantum computers will not be able to solve NP-complete problems efficiently (which in turn is perhaps a reason to think long and hard about whether this really true: I waver on about on three year period as to whether I should spend more time attempting to solve NP-complete problems efficiently on a quantum computer.) The question to ask a sceptic, then, is why is it, if quantum computers are analog computers that they cannot solve NP-complete (or harder) problems? Surely this indicates that there is not direct analogy between analog and quantum computers or one of the thousands of people working in the field would surely have discovered such a connection! Well, the argument might not work, but I’d be curious to hear the variety of sceptics retorts.