[bb88]

If you can find a quantum computing solution it's at worst O(sqrt(n)).

There still seems to be a time factor, if not energy factor to computation.

Shor's algorithm for factoring prime numbers is at best O(log(n)^2 * log(log(n)))