People pick predictable passwords. Thanks to compromises of large sets of random passwords, we know far more about how to predict passwords than we ever did in the past. That means that, given a new password database, we can crack more passwords with a shorter search.
But it gets worse. A long time ago, people interacted with very few systems with very few passwords needed. Today people interact with many systems, and most still use very few passwords. (Yes, I know all of the ways to make more passwords feasible. The fact is that people don't do that.) Therefore if you target a low security system, you frequently get access to much more worthwhile accounts on another system entirely.
Because of both problems (particularly the second), passwords alone are not sufficient for anything that actually needs reasonable security.
Passwords are lousy. Really lousy. As you point out the problem isn't with the security of them (when properly applied) but because it's all just so klunky and annoying and different websites have different implementations.
I know at least two websites that ask for a username, a password, and they also give a capcha. I have some websites that won't let Chrome save my password.
Really, I want a hardware thing with a long secure passphrase, that has all my other usernames and passwords (12 character alpha numeric with upper and lower case) in it, that confirms my identity to all these different websites. (Can I do this with Yubikey? or anything else?)
I was under the impression that QNP (the class of problems solvable by a quantum non-deterministic Turing machine in P-time) is a (non strict) subset of NP. Things might have changed since I last checked though.
I did mean subset, apparently a quantum computer could not solve every NP-complete problem in polynomial time. factorisation seems to be one of the candidates to benefit from quantum computation (thanks to Shor's algorithm), but SAT (for instance) would not, at least based on current state-of-art
It's not just a computational expense of one password hashing that has to be considered, the possibility of having the hashes precomputed can't be ignored. In such a light, we definitely have to start using longer passwords or passphrases regardless of the expense of computing one hash. Otherwise the search space is simply too small.
Pre-computed? You mean rainbow tables right? They have gone the way of the dinosaur with salts. Bcrypt has a big fat salt making it mightily impractical to use rainbow tables as the space required is so large.
Another problem with rainbow tables is that their size depends on the password length, and with current technology they become impractical almost as soon as brute forcing, and much sooner than smart dictionary attacks (e.g. hybrids where you take a dictionary and for each entry try every possible way to add 3 random characters).