"In all known classical factoring algorithms, the amount of time needed to find the prime factors of a number grows as an exponential function of the size of the number, making the algorithms impractical for very large numbers."
General number field sieve is sub-exponential. Factoring is interesting because it is not NP-complete, but not known to be in P either. It is my understanding that NP-complete problems remain so in the quantum world.
Saying "NP-complete problems remain so in the quantum world" is a bit imprecise because NP-complete is simply defined as a set of problems which can be solved by classical nondeterministic computers. Of course it "remains so" in the quantum world; it's a mathematical definition, it remains so in any world.
What's very interesting is that Scott Aaronson proved that normal quantum computers could have solved NP problems (in fact, something stronger: BQP = PP) if quantum mechanics allowed nonunitary linear operations or was based on the norm
norm = lambda vec: sum(abs(component) ** p for component in vec)
for p > 2 (quantum mechanics is based on p = 2, classical probability is based on p = 1). So if it were any larger, the quantum computer could do brute force with ease.
Right now it's not known whether BQP contains NP-complete or not; it might very well contain both problems in NP and problems not in NP while deftly evading NP-complete.
It is known that PostBQP = PP and therefore contains NP-complete. PostBQP is the set of quantum algorithms which are allowed to destroy the universe when they fail, under the anthropic principle reasoning that "humans will only live on in universes where the computation succeeds."
General number field sieve is sub-exponential. Factoring is interesting because it is not NP-complete, but not known to be in P either. It is my understanding that NP-complete problems remain so in the quantum world.