Why not think in positive ways and say that if Quantum computers come online then we can use them to Solve the complex algorithm easily and then use these computers in the MINING operations ?
This can ease all the operations and may reduce the energy consumption and thus may help to take the blockchain or crypto currencies to the next level and have them used everywhere.
I think you are confused. More hashing power would not increase the efficiency of the network. To make it simple, if your laptop was the only computer mining on the network, it would find all blocks and thus validate all transactions of the network. It wouldn't be decentralized at all but it would work. We would have a new block every 10 minutes anyway as the difficulty would be adjusted to a ridiculously low level.
Mining is a competition and the incentive is the block reward. So, if a miner comes with a new solution which is more efficient (like what happened with ASIC's), the other miners will need to adopt the same solution to stay in the race. But if GPU's, FPGA's and ASIC's were never used for mining we would still be using CPU's and the network would be perfectly fine (actually, even better because more decentralized...)