Isn't this the type of problem a "quantum" computer with enough qbits could solve extremely quickly?
No, they can solve integer factoring. This result shows that polynomial factoring is fundamentally different from integer factoring. The latter is believed to not be NP Hard.