“And yet, even though useful quantum computers might still be decades away, many of their payoffs are already arriving. For example, the mere possibility of quantum computers has all but overthrown a conception of the universe that scientists like Stephen Wolfram have championed. That conception holds that, as in the “Matrix” movies, the universe itself is basically a giant computer, twiddling an array of 1’s and 0’s in essentially the same way any desktop PC does.
Quantum computing has challenged that vision by showing that if “the universe is a computer,” then even at a hard-nosed theoretical level, it’s a vastly more powerful kind of computer than any yet constructed by humankind. Indeed, the only ways to evade that conclusion seem even crazier than quantum computing itself: One would have to overturn quantum mechanics, or else find a fast way to simulate quantum mechanics using today’s computers.” http://www.nytimes.com/2011/12/06/science/scott-aaronson-quantum-computing-promises-new-insights.html?_r=1&ref=science&pagewanted=all
“Carson Chow Says:
Comment #2 December 5th, 2011 at 10:35 pm
Nice article but I am confused about this paragraph:
“For example, the mere possibility of quantum computers has all but overthrown a conception of the universe that scientists like Stephen Wolfram have championed. That conception holds that, as in the “Matrix” movies, the universe itself is basically a giant computer, twiddling an array of 1’s and 0’s in essentially the same way any desktop PC does.”
A quantum universe or a classical universe are both computable aren’t they? It’s just that the quantum universe is exponentially “bigger”. In principle, you could have a classical computer just chug away painfully slowly and simulate the quantum universe, no? There is nothing in the “Matrix” universe that says the computation must be efficient is there? There are still just a countable number of possible quantum universes right?”
“Scott Says:
Comment #5 December 5th, 2011 at 10:59 pm
Carson #2: Yes, as the tagline of my blog says, quantum computers can be simulated classically but with exponential slowdown.
What we learn from quantum computing is that, if both quantum mechanics and the prevailing conjectures in complexity theory are valid, then the physical universe can’t be feasibly simulated by a computer that “twiddles an array of 1’s and 0’s in essentially the same way any desktop PC does.”
(That last clause was meant to indicate that I was talking about efficient simulation by conventional computers — i.e., the Extended Church-Turing Thesis, or what Wikipedia calls the Feasibility Thesis. I wish I knew how to put the point more clearly within the constraints of this article, since you’re right that it might be misinterpreted!)
For what it’s worth, Stephen Wolfram, Ed Fredkin, and other believers in “digital physics,” have been very explicit in saying that they think the universe is a classical cellular automaton—basically, a three-dimensional array of pixels—and that their view would preclude exponential speedups from quantum computation. (Wolfram believes that quantum mechanics is wrong, whereas Fredkin believes that quantum mechanics can be efficiently simulated classically.) So, these viewpoints would indeed be ruled out under the assumptions I mentioned above.
A last remark: the Matrix movies aren’t very clear about what type of computer is being used, other than that it’s powered by human bodies! But since they never mention anything about quantum computing, and since the simulation clearly isn’t astronomically slow, it seems reasonable to assume that Keanu Reeves was trapped in some sort of classical simulation. So maybe he could’ve caused the simulation to crash by building a quantum computer and trying to run Shor’s factoring algorithm! For the version where Keanu is trapped in a quantum computation, we might need to wait for the followup trilogy, “The Unitary Matrix” (har, har).”
“Jiav Says:
Comment #8 December 6th, 2011 at 12:59 am
Nice essay Scott, but how could we know our simulation is not astronomically slow?
I’m curious to see if Greg Egan will comment this one 
”
http://www.scottaaronson.com/blog/?p=871
Cf. http://theunitedpersons.org/blog/if-the-answer-is-42-what-is-the-question
mazsa is discussing. 
Cf. “[...] even one-dimensional cellular automata can be universal. Wolfram (2002, pp. 644-656) gave an example of a 19-color universal one-dimensional next-nearest neighbor cellular automaton in which a block of 20 cells is used to represent each single cell in the cellular automaton being emulated. The examples above show the first few steps of the 19-color universal automaton emulating rule 90 and rule 30, respectively (Wolfram 2002, pp. 646-647).” http://mathworld.wolfram.com/UniversalCellularAutomaton.html and http://www.wolframscience.com/nksonline/page-645