Is it possible to generate BitCoins on quantum computer?
So while classical miners are brute forcing through a 2^70 search space, the quantum miner can find a solution in roughly sqrt(2^70) = 2^35 steps.
Other proof-of-work systems can be more quantum resistant, e.g. looking for a fixed-length cycle in a huge random graph, for which no efficient quantum algorithm is known.
And you must reset part of the problem (the previous block hash, at minimum) when new blocks are released, adding some latency (you need to recompute the qubit configuration before resuming).
But perhaps a SIDH based proof-of-work algorithm could be implemented to further resist QC speedups. Don't know exactly how that would work. Does Grover's still apply?
There are about 2^256/2^160=2^96 possible full public keys mapping to the known key hash, so you could run Grover's algorithm to recover one in about sqrt(2^96)=2^48 steps, but given the slow cycle time of quantum computers, that's still going to be infeasible for a long time.
This is why address re-use is not recommended...