^^I also wonder what might happen when quantum computing becomes real and practical. Since, in theory at least, quantum computing can make short work of decrypting well-encrypted stuff, perhaps it could also make short work of mining (calculating hashes).^^

This isn't my area, but from what I have read, quantum computing is a danger to public key signature algorithms that are based on discrete logs or integer factorization. Bitcoin mining involves discrete log problem but can - and would - be changed with a soft fork, which would go through with very little opposition. A fork involving this change is planned already, but if Quantium computing was expected to suddenly become available, a Bitcoin would be forked more quickly to keep it protected.

There are already have quantum computing resistant encryption public key crypto, for example NTRU Quantum-Resistant High Performance Cryptography. This system is based on integer lattices rather than discrete logs or factoring, and no one seems to know how to use quantum computing to simplify this problem at the moment. Many more such algorithms are on the way because of contests at the Computer Security Resource Center.