Quantum computers don't just turn exponential time into linear time. There are certain problems where they're known to be able to do that, but there are a lot of problems where that's not known. Finding a suitable nonce is a lot like reverse phonebook search, and Grover's algorithm operates in order sqrt(N) guesses, instead of the classical N guesses. Assuming this is in fact the best way to use a quantum computer for mining, this has a curious effect. It means that if the difficulty quadrupled, it would take only twice as long to find a suitable nonce – which is effectively twice the hashpower, but still finding blocks slower. The effective hashpower of a quantum computer increases with increasing difficulty, but it still falls behind. The difficulty would still be able to increase to keep up with hashpower, so there's no existential threat to Bitcoin mining.