Aaronson lecture on Computational Physics

MIT complexity theorist Scott Aaronson posts a video lecture (download here) on "Computational Phenomena in Physics":

Scott Aaronson discusses the quest to understand the limits of efficient computation in the physical universe, and how that quest has been giving us new insights into physics over the last two decades. He explores the following questions: Can scalable quantum computers be built? Can they teach us anything new about physics? Is there some new physical principle that explains why they cannot be built? What would quantum computers be good for? Can quantum computing help us resolve which interpretation of quantum mechanics is the right one? Which systems in nature can be universal computers, and which cannot? Aaronson will end by describing a striking recent application of computational complexity theory to the black hole information loss problem.

At 37:00 he says he takes the "conservative" view that quantum computers (QC) are possible, or else "we would have to rewrite all the physics books."

For me, I like to say the single most important application of a quantum computer, even more important than a quantum simulation, is disproving the people who said it was impossible. The rest is icing.

You think his personal biases are clouding his judgment?

I say QC are impossible, and that no textbooks will have to be rewritten. I defy him to show me one quantum textbook that would need more than one page of change.

I doubt that his audience was convinced that QC is possible. He compared it to other impossibilities like faster-than-light travel, and perpetual motion machines. He also proposed that P!=NP might be a principle of physics. That is, even a QC would not be able to solve the traveling salesman problem or other NP-hard problems.

It is just as plausible that it is a principle of physics that no super-Turing computation is possible, and QC is like that perpetual motion machine or faster-than-light travel.

At 45:10, he says D-Wave has spent $150M to build a QC, but it is really no faster than a Turing machine. He explains how D-Wave could be running into physical limits that could prevent it from ever achieving its computational goals.

So why is it so hard to believe that other QC attempts will also run into physical limits?

He quotes David Deutsch as saying that QC should be possible because the computation can take place in parallel worlds of the many-worlds interpretation. But he also explains the flaw that such reasoning would lead you to believe that QC could solve NP-hard problems, and thus is more powerful than it really is.

I should not be too hard on Aaronson because at least he appears to desperately afraid that QC will turn out to be impossible. Almost everyone else refuses to admit the possibility.

Aaronson's latest post is somewhat embarrassing. He says that he is most known for a theorem in quantum computer complexity theory. He says it was easy, and he proved it in about an hour, and published it ten years ago. It is widely cited, but recently people found serious errors in the proof. To fix it, he posted a query publicly on MathOverflow, and people found clever work-arounds for his problem. He also says that some serious errors were found in other papers he wrote ten years ago. Hmmmm. I don't want to pile on here, but he is obviously not always right about everything, and he may not be right about his predictions for QC.