With QC (quantum computation), it gets even better.
In talking about program performance, rather than specify the time it takes as a number of seconds, we specify it as a function of the input size. How exactly input size is measured depends on the problem, so let’s sweep that issue under the rug.
So when talking about a simple program to sort a list of n numbers, we’d say that its running time is n^2. A program to search that same list for a given number has running time n. With me so far?
The problems we look at solving with quantum computation have running times like 2^n, or n! (see the first paragraph of http://mathworld.wolfram.com/Factorial.html for a discussion of what that symbol means).
One such problem that I did a little work on might be interesting to the t-men. Suppose you have a set of exercises, each of which works a given group of muscles. What’s the least number of exercises that you can get away with to hit all the muscles that you’re interested in? It turns out that if you have e exercises, the running time of a program to solve this problem is about 2^e.
Furthermore, if you could find a program that solves this problem significantly faster, you would be instantly famous and you’d win a million dollars. You’d also be more clever than a large percentage of the mathematicians, computer scientists, and other geeks who’ve been working over the last couple years.
The other problems that are that hard relate to much more practical applications, like internet security or file compression.
Anyway, before I forget the point I was making, the exercise problem has a running time of 2^e on a conventional computer. On a quantum computer, it has a running time of e.
Let’s say that the running time corresponds directly to how many seconds it takes. With 30 exercises, you’d need about a billion seconds (roughly 31 years) to solve the problem on a conventional computer. On a quantum computer, you’d need 30 seconds. Throw in another exercise, and the time on the conventional computer goes to over 60 years. On a quantum computer, you need 31 seconds.
That’s why people want these so badly.
The interesting thing is that we’ve been studying QC for almost 20 years now, and in that time, we’ve developed exactly two programs that couldn’t be run on a conventional computer. So it may not be exactly the revolution that we’re looking at, but it’s still pretty cool.