The only question is we don't know if there is a better classical factoring algorithm.
Wikipedia:
> On a quantum computer, to factor an integer N, Shor's algorithm runs in polynomial time. This is almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time
Compare this for example to sorting. We have proven that any sorting algorithm working with comparisons can at best be O(n*log(n)) fast, it's impossible for a faster classical algorithm to exist.
You can have a faster classical algorithm if it's distributed across n threads for a size n array. For each index i in an array arr, spawn a thread that counts the number of values in arr that are less than arr[i] (an O(n) linear scan), call this x, then do outputArray[x] = (arr[i], 1), where outputArray is initialised to all zeros. If outputArray[x] already exists, instead increment the second term (count) in the tuple. Once all threads are finished, then outputArray will contain the sorted values and the count of duplicate values (so this only works if !(x < y) && !(y < x) implies y == x). Each thread does O(n) work, so total work is O(n^2), but because the threads all run in parallel, the runtime is only O(n).
"Total Work" is the important part to minimize in practice. If "total work" scales at O(n^2), then in practice, the job scales at O(n^2). Its infeasible to build O(n^2) CPUs running O(n^2) threads as n-grows.
Of course in reality we care about execution time, and in order to go from "we need O(n * log(n)) comparisons" to "we need O(n * log(n)) time" you need additional assumptions, like "memory access takes O(1) time, and the speed of one comparison is independent of the total amount of data". But for any reasonable set of assumptions an algorithm that uses O(n * log(n)) comparisons takes at least O(n * log(n)) time (probably more since memory access isn't really O(1), it's just common to pretend that it is).
That's like saying multiplication can't have any lower bound because multiplying by zero is O(1).
The thing that gets smoothed over with QC is managing the error rates and the fact that it hasn't been shown to be physically possible to scale up computation without the error rates also scaling up exponentially and making the thing useless.