Category: Computer Science

For a long long time, I was very sympathetic towards the point of view that the universe is one gigantic digital computer. This point of view has been championed by many people, including Ed Fredkin and Stephen Wolfram. Seth Lloyd has recently writen a book in which he updates this point of view, taking the point of view that that the universe is one gigantic quantum computer. One of the essential reasons for believing this sort of things is that computers (classical or quantum) can be used to simulate the physics of the universe. Of course there are all sorts of issues with this idea, for example, the simulations are invariably done up to a certain fixed accuracy. So while you can certainly do the simulaton on a quantum computer, as the physics becomes more and more accurate, you will need to believe that the computer doing the simulation is larger and larger. There is nothing intrinsicaly wrong with this notion, and indeed it may be that at its bare base there is a final discrete unit, but until such a unit shoes up in experiment, the hypothesis seems to me indistinguishable from not believe that the universe is a quantum computer. But this isn’t why I’ve become more skeptical of the universe as a computer point of view.
The reason I’ve become more skeptical is that I do not believe in computers. Er, well, at least I do not believe in digital perfectly working computers, nor do I believe in exact perfectly working quantum computers. When we dig down into the bowls of our computers we find that in their most basic form, these computers are made up of parts which are noisy or have uncertainties arising from quantum theory. Our digital computers (like the coming quantum computers) are emergent phenomena, and, further, it seems that in this emergence, nothing resembling absolutely perfect fault-tolerant computation is possible. Fault-tolerance can only be achieved over a certain time horizon (in both classical, where we currently have very very low error rates, and in quantum, where we are struggling to get the emergence to give us very low error rates.) Now of course, one can always work with the model of a perfect computer (neglecting a meta-level of thinking about what “working” means in terms of you, who are also a computer.) But if you do this, you must admit that you are talking about an entity that does not exists, as far as we known, in our universe. So somehow we are supposed to be comfortable in looking at the universe as a perfect computer, when such objects don’t exist in our universe? This makes me feel uncomfortable.
So I guess this makes me the anti-Wolfram, not subscribing to the view of our universe as a computer. Does this mean that I think that computation or information theory doesn’t have anything to say about physics? Actually, the answer is no. I’m just unconfortable with a naive translation of what it means for the universe to be a computer where everything is perfect and error free. Somehow I think the real answer must, somehow, be much deeper.

David Bohm was one of the more interesting researchers in the field of the foundations of quantum theory. While a graduate student at Berkeley under Oppenheimer (after a short stay a Caltech where he was unhappy), he wrote, with David Pines, some early very influential papers on plasma physics. His textbook on quantum theory is a model for almost all of our modern quantum textbooks. And then, of course, there is the Aharonov-Bohm effect which shows how the vector potential can affect results even when the particles involved transverse regions where the vector potential magnetic field vanishes. It was supposedly while writing this textbook on quantum theory that he began to question the foundations of quantum theory and which led him to develop a non-local hidden variable theory for nonrelativistic quantum mechanics-a task whose supposed impossibility in turn led John Bell to formulate his famous inequality. Bohm, however, had consorted with the Oppenheimer crowd at Berkeley and got pulled into the whole “are you a communist” political mess and thus could not obtain a job in the United States, instead obtaining a job first in Brazil (on the recommendation of no one less than Einstein) and then in the United Kingdom where he continued his work in foundations and consorted with an assortment of interesting characters, including the Dali Lama and Jiddu Krishnamurti.
As you can see, I’ve always been fascinated by Bohm’s life. But what do I think of his hidden variable theory? It must be said right off the bat that Bohm constructed his theory more as a proof of principle than as the final solution to the foundational problems as he saw them (In fact it is probably best to say that Bohm did not believe there was a “final” solution as far as I can tell.) Well at various times in my life I have felt that Bohm’s theory was an intriguing direction towards understanding quantum theory. But as I’ve learned more and more from quantum compting, I’ve begun to think less and less of this theory. Indeed, I would say that quantum computing has taught me that there is something radical missing from approaches along the lines of Bohm’s non-local hidden variable theory. Quantum computing ruined Bohmian mechanics for me.
“Bah!” you say. What can quantum computing, which is obsensibly founded along the mantra “do not question quantum theory…accept it and rejoice at the splended information processing you can now do!” have to do with questions from the foundations of quantum theory, who are questions more associated with philosophy than constructive technological advance (yes this was a low blow to philosophy…sorry couldn’t resist)?
Well I would say it has pretty much everything to do with interpretations of quantum theory! Take you favorite interpretation of quantum theory. Now ask the question, how does this interprettion help explain to me why quantm computing is more powerful than classical computing. Whenever I do this for any of the interpretations, I find that I walk away even more appreciative of the weaknesses of each of the interpretations of quantum theory. For example, back to Bohmian mechanics. Now how does the idea that there is a pilot wave, or such, guiding the trajectory of a particle give us insight into why quantum computers can efficiently factor integers? Sure it seems reasonable that non-local hidden variable theories can be more powerful than local hidden variable theories, but why does the particular implementation of a non-local theory, as advocated by the Bohmian interpretation crowd, give us any extra insight into the power of quantum computing? Indeed, this is the crux of my problem: the more I learn quantum computing, the more I see it conected to the theory of computation. And the more I see it connected to the theory of computation, the less satisfying I find explanations such as “well it’s just a non-local theory”. Explanations such as that are like saying BQP is in PSPACE, so the power of quantum computing is obviously that of PSPACE. This leads to further weaknesses, I think, like the extreme wastefulness of non-local hidden variable theories in terms of their representation of the flow of classical inormation. I mean one of the astounding result of quantum computing is not that you can factor integers, but that you can’t also do everything in, say, NP. Why this theory with Goldilocks like power, able to solve problems not so difficult so as to rearrange our theory of tractible computation, but at the same time able to solve problems widely thought to be intractable on a classical computer?
Of course, you will object that I am asking too much of an interpretation. The interpretation is only supposed to make you feel good at night, when you crawl into bed with your copy of Cohen-Tannoudji et al, not to actually be useful (sorry, another low blow.) But I believe that an interepretation of quantum theory, which is obsensibly about resolving our conflicting feelings about the classical world we think we know and the quantum world, will only satisfy me if it comes along with an equal solution to resolving the conflicting feelings about why quantum computers are of the intermediate power we widely suspect them to be. Maybe, indeed this also offers an explanation for why there is little agreement over interpretations: the problem is related to a problem in computational compelxity, BQP?=BPP, whose resolution would represent a major insight in long standing difficult problems in computational complexity.

The arxiv is changing the way it labels papers on 1/1/07, in part because the math arxiv almost reached one thousand papers per month. One thousand papers per month! Basically the new format is YYMM.NNNNvV where YY are the last two digits for the year (starting with 07), MM are the month, NNNN represents the number and vV is the version of the paper. The subject class will now be placed at the end of the paper: for example, “arXiv:0701.0001v1 [quant-ph].” Still no word on when the new naming scheme will be introduced.
Oh: and an interesting paper today, a “lost” paper of David Bohm’s quant-ph/0612002.