The universe is not a quantum computer

Scott Aaronson and his fellow MIT professor are again bragging about the possibility of quantum computers, while dancing around the question of their impossibility.

[Lloyd] Immediately after the Physics Nobel Laureate Richard Feynman presented his vision of the quantum computer in 1982, researchers began to investigate how one could use the superposition of quantum states to do things that are not a conventional computer. ...

[Scott] If we were to discover that there is a deep reason why quantum computers are impossible, then that would ironically be the most exciting result. Because we would then have to rewrite the physics books in order to take account of the new understanding.

[Shmi] Scott, how can a quantum computer used to simulate quantum systems be impossible? After all, it’s just another quantum system, only somewhat more controlled. What might be the distinction between the simulator and the system itself that makes a quantum simulation impossible?

[Scott] You should probably be asking the QC skeptics that question, rather than me. ;-) But I assume they would answer something like: “the quantum systems that can occur in Nature are all extremely special, in ways that probably allow us to simulate them efficiently using a classical computer. So yes, you can presumably build a computer that simulates those systems, but what you had built wouldn’t deserve the title ‘quantum computer.’ What we don’t think you can build is a machine that implements a completely arbitrary sequence of 1- and 2-qubit unitary transformations, in order (for example) to efficiently factor a 10,000-digit number using Shor’s algorithm. And of course, consistent with our prediction, such machines are nowhere found in Nature.”

I am one of those QC skeptics, so I answer here. I have posted 5 reasons I believe QC is impossible, as well as various agreements and disagreements with Scott.

R.P. Feynman proposed a universal quantum simulator in 1982. He pointed out that if you program an ordinary Turing machine (ie, classical computer) to simulate the rules of quantum mechanics, then it suffers an exponential slowdown. But if a quantum computer had the mysteries of quantum mechanics baked in, then it could efficiently simulate a quantum system.

I have no argument with any of that, or with the basics of quantum mechanics.

Shmi argues above that any system could be said to simulate itself, and therefore a quantum system is simulating itself as a quantum computer. So quantum computers must exist, and he does not see how anyone can deny them. Scott calls this quantum computing in their sleep. (“Ein Quantencomputer hingegen wuerde solche Aufgaben im Schlaf erledigen …”)

It is a good question, because I am not denying quantum systems. Let me explain.

Consider a very simple quantum system, such as an electron trapped in a small cavity. Assume that the cavity is just sufficient to confine the electron. According to classical mechanics, the electron bounces around the cavity and cannot get out.

Experimentally, the electron eventually leaks out, at a seemingly random time.

Quantum mechanics teaches that the electron is really a wave of some sort, and eventually tunnels thru the potential energy barrier. Using a wave function for the electron, quantum mechanics can predict probabilities for the location of the electron and the time of escape. Physicists are satisfied with these probabilities because they believe in an inherent randomness of nature, so the quantum mechanical formulas are considered to be a complete solution to the problem.

Some people believe that there is, yet to be discovered, some underlying reality that will explain deterministically how the electron gets out.

This is all reasonable and straightforward, but simulating it has high complexity. Here is why. The simulator can never be sure when the electron leaves the cavity. As soon as the electron leaves, it will likely trigger a chain reaction of other events. So the simulator has to keep track of all possible times for the electron to leave, and then all those chain reactions. An electron leaving at an early time might trigger a very different chain reaction from the electron leaving at a later time.

Each of those chain reactions is another quantum process, and therefore subject to its own exploding number of possibilities. Thus the simulator has to keep track of many possibilities, each of which leads to many other possibilities, and so. Soon, there are way too many possibilities to keep track of.

You can use an approximation that divides time into discrete steps. But the number of possibilities increases exponentially with the number of steps. This is impractical on a Turing computer. The only hope, it seems, it to use a fancy quantum computer that can keep track of multiple states simultaneously without an exponential complexity explosion.

This is a valid argument that quantum simulations have very high Turing complexity. But does it prove the existence of a quantum computer?

For that, we need to run the argument backwards. We know that there are quantum systems in nature, and simulating themselves must have high Turing complexity, so those systems could be viewed as computers that can outperform a Turing computer. That is the (flawed) argument.

Let's go back to the electron in a cavity. Is it doing a quantum computation? To view it that way, you have to imagine that it is magically and silently keeping track of an exponentially increasing set of possibilities, and encoding them all in its wave function. Once you convince yourself that this electron is doing a computation that no Turing machine can do, you are then supposed to believe that advanced technology will be able to extract that ability, and apply it to factoring 200-digit numbers.

The flaw in the argument is the assumption that the natural process is the same as how we model it in the simulation. It is not. The electron is just a dumb particle-like wave-like object that bounces around a cavity until it eventually busts out. It is not doing computations on its wave function.

The typical wave function will represent an electron that is 3/4 in the cavity and 1/4 outside the cavity. Nothing like that is ever observed in nature. Every time we measure the electron, we always find it either entirely inside or entirely outside the cavity. The wave function is just our way of representing our uncertainty about whether the electron has escaped yet. In philosophical jargon, the wave function is epistemic, not ontic.

To answer Scott's question, I doubt that a classical computer can efficiently simulate a quantum system. Too many possibilities proliferate. The wave function may well be the best possible mathematical representation of an electron, but still not a true representation of the physical object. The probabilities help us make sense out of what the electron is doing, but I very much doubt that what the electron is really doing is a computation on probabilities.

I am reminded of artificial intelligence (AI) researchers who try to program a computer to tell the difference between the image of a dog and a cat. They would have surely concluded that it is impossible, were it not for the fact that a 3-year-old child does it easily. The correct conclusion is that the 3yo child is doing something different from what the AI researchers are doing. Likewise the electron is doing something different from what the quantum computing simulators are doing.

Scott wants a proof that quantum computing is impossible, or else he dismisses me as a crackpot who cannot back up what I say. I do not have a proof. I cannot rule out the possibility that an electron really is typically 3/4 in a cavity, even tho no one has ever seen it that way, and that this split in possible electron states can somehow be used to do a computation that is otherwise impossible. It just seems very far-fetched to me.

I do say that the arguments for quantum computing are fallacious. The above argument is essentially to say that simulating a quantum system is too complex so some computational ability can be extracted from that complexity. It is like saying that distinguishing a dog and cat is too complex for our Turing machines, so let's harness the brainpower of 3yo kids to factor 200-digit numbers.

The usual argument for quantum computing is a variation of the above argument. It says that QC is a logical consequence of quantum mechanical rules that have been verified for 90 years. It is true that superpositions have been used to predict probabilities of events for almost 90 years, but QC goes further than that, and uses superpositions to predict superpositions and extract computations.

To me, the observables and events are real, and the probabilities and superpositions are mathematical artifacts. No one ever observes a probability. That is just our way of organizing what we see. And we do not observe a superposition either.

Quantum mechanics was created with a positivist philosophy that views science as being all about explaining observations and measurement. Nowadays it is more common to attach interpretations to wave functions with descriptions like "ontic" and "realist". The positivist view questions whether these have any scientific meaning. There is no experiment that shows that the ontic or realist interpretations have any tangible merit. Just metaphysical fluff, the positivist would say.

That metaphysical fluff is crucial for the belief in QC.

I know that there are 100s of papers claiming to see Schroedinger cat states, where something is alleged to be analogous to a cat being half alive and half dead. And 100s more claiming to use QC or quantum mechanics to do a computation. I admit that every transistorized computer is using quantum mechanics to do a computation.

What we do not see is anyone using cat states to do a super-Turing computation. Scott admits this, as he bashes those who make exaggerated claims. If some does that, I will be proved wrong. Until that, QC is just a sci-fi fantasy like those Interstellar wormholes.

Update: Here is Scott's 2012 offer, with the argument that simulating reality is an argument for QC:

An even more dramatic way to put the point is this: if quantum computing is really impossible, then we ought to be able to turn that fact on its head. Suppose you believe that nothing done by “realistic” quantum systems (the ones found in Nature) can possibly be used to outperform today’s classical computers. Then by using today’s classical computers, why can’t we easily simulate the quantum systems found in Nature? What is the fast classical algorithm for simulating those quantum systems? How does it work? Like a wily defense attorney, the skeptics don't even try to address such questions; their only interest is in casting doubt on the prosecution's case.

The reason I made my $100 000 bet was to draw attention to the case that quantum computing skeptics have yet to offer. If quantum computing really does turn out to be impossible for some fundamental reason, then once I get over the shock to my personal finances, I'll be absolutely thrilled. Indeed, I'll want to participate myself in one of the greatest revolutions in physics of all time, a revolution that finally overturns almost a century of understanding of quantum mechanics. And whoever initiates that revolution will certainly deserve my money.

I say that QC is impossible for non-revolutionary reasons. The impossibility of QC will not overturn a century of understanding of quantum mechanics. It will only overturn 30 years of misunderstandings of quantum mechanics.

I do not know the fastest classical algorithm for simulating a quantum system. If the simulation has to keep track of many divergent probabilistic branches, then I expect it would be slow. The real reason we cannot efficiently simulate nature is because our mathematical models of electrons do not fully capture their physical reality.