Scott Aaronson in PBS [h/t: Jennifer Ouellette] (image Credit: Marcin Wichary/Flickr, under a Creative Commons license):
[S]ome physicists are already beginning to theorize about what might lie beyond quantum computers. You might think that this is a little premature, but I disagree. Think of it this way: From the 1950s through the 1970s, the intellectual ingredients for quantum computing were already in place, yet no one broached the idea. It was as if people were afraid to take the known laws of quantum physics and see what they implied about computation. So, now that we know about quantum computing, it’s natural not to want to repeat that mistake! And in any case, I’ll let you in on a secret: Many of us care about quantum computing less for its (real but modest) applications than because it defies our preconceptions about the ultimate limits of computation. And from that standpoint, it’s hard to avoid asking whether quantum computers are “the end of the line.”
Now, I’m emphatically not asking a philosophical question about whether a computer could be conscious, or “truly know why” it gave the answer it gave, or anything like that. I’m restricting my attention to math problems with definite right answers: e.g., what are the prime factors of a given number? And the question I care about is this: Is there any such problem that couldn’t be solved efficiently by a quantum computer, butcould be solved efficiently by some other computer allowed by the laws of physics?
Here I’d better explain that, when computer scientists say “efficiently,” they mean something very specific: that is, that the amount of time and memory required for the computation grows like the size of the task raised to some fixed power, rather than exponentially. For example, if you want to use a classical computer to find out whether an n-digit number is prime or composite—though not what its prime factors are!—the difficulty of the task grows only like n cubed; this is a problem classical computers can handle efficiently. If that’s too technical, feel free to substitute the everyday meaning of the word “efficiently”! Basically, we want to know which problems computers can solve not only in principle, but in practice, in an amount of time that won’t quickly blow up in our faces and become longer than the age of the universe. We don’t care about the exact speed, e.g., whether a computer can do a trillion steps or “merely” a billion steps per second. What we care about is the scaling behavior: How does the number of steps grow as the number to be factored, the molecule to be simulated, or whatever gets bigger and bigger?
More here.