For a large number of processors on the right tasks, just getting instruction level parallelism (e.g.) is not even tiny bit as good as using an optimized algorithm.
The differentiation aspect of hardware is that it involves both logical and physical domains, where as software is limited to logic. We may require new approaches to hardware and architectures as the "intrinsic" aspect of the problem is very much rooted in underlying hardware architecture.
(I also wouldn't be surprised at all if the initial successful applications of quantum computing are memory related.)