Compare the complexity classes BQP (quantum) and BPP (classical). You might be more acquainted with P vs. NP; note that BPP ⊆ BQP and we don't know how BPP relates to NP. BPP is a probabilistic version of P. According to the BQP model of quantum computation, quantum computers are merely faster at solving some kinds of problems. I mean two things by using the very computer-sciency term 'merely faster':
- 'faster': because many interesting problems in computation have exponential increase in time as the input size grows, they cannot in practice be solved, except by approximation; if we can find exponential speed-ups, like Shor's algorithm, we change what is physically possible to compute (in a finite universe)
- 'merely': there is nothing that BQP in theory can solve which BPP cannot solve
Why can BQP be faster? Well, it turns out that we can exploit physically computable 'functions', such as period-finding, which is what allows prime factoring to be in the BQP complexity class. For more, see quantum algorithm. It is not correct to view quantum computation as "trying every answer simultaneously"—this would allow solving NP problems in P time—for there is no known physical model of computation which would allow this. Now, computer scientists do talk about "what if we could solve NP problems in constant time?"; see oracle machines.
What would be a more powerful kind of computation than Turing machines? Take a look at undecidable problem. In case you're not quite familiar with decision problems, you can think of a computation which produces some complex output upon some input as, instead, a computation which takes two inputs—the input and 'attempt' at a solution—and simply gives you a 'yes' or a 'no' as output. For examples of problems that something 'stronger' than classical or [known] quantum computing might address, see list of undecidable problems.
A characteristic of undecidable problems is that the problem requires us to find whether there exists some arbitrarily long sequence which solves our problem. Remember those problems where you have to get from one word to another through a few steps, each involving a single letter change, and each intermediate 'word' being valid? Imagine if you can have as many steps as necessary: it won't always be the case that a Turing machine could tell you whether some set of steps exists in any known time/space bound. This is because the time/space bound is a function of the input, not the output. If the output can be arbitrarily large, 'all bets are off', as it were.
If we step past 'quantum' to "true description of the universe", we might find that our universe is more powerful than Turing machines. For example, we might be able to somehow perform infinite (or arbitrarily large) computations in bounded times—times that don't 'explode' in the way that makes certain problems undecidable under the Turing machine model. The classical → quauntum transition doesn't get us this, but if we perform induction on that step, we could expect future transitions that are equally as unexpected; one of them might shatter the Turing machine model of physical reality.
