From
http://arxiv.org/abs/1108.2316 (Merkle Puzzles in a Quantum World):
We showed in an earlier paper that Merkle's schemes are completely insecure against a quantum adversary...
Bitcoin mining algo can be used as Merkle's Puzzle. Does it mean that a quantum computer can find a nonce much faster (
sqrt[X] vs
X for a classical computer)? I can't find that paper to check this by myself.
Yes, a QC can do a brute force search that normally takes O(N) in O(sqrt(N)). But QCs are going to be a long way from exploiting that advantage until they (1) exist, and (2) are good enough to actually execute "guesses" that fast.
Consider for example that you need approximately 10
8 operations to brute-force guess something (in this case find a nonce that gives a particular target when hashed). Perhaps your ASIC does 10
8 guesses/sec, so it takes 1 second. It may only take 10
4 operations for your QC... but if it can only do 100 ops per sec, you're still far better off with your ASIC.
Of course the math and the scales are far from that simple, but you get the point -- even getting a
real QC that has enough qubits and gates to do the calculation may be decades off... and it may be far longer before it can even exploit such an advantage.
(On the other hand, it has a far greater advantage than that against breaking crypto schemes, so even a minimal QC might take minutes/hours/days to break a key, but it's better than the 10
32 years it would take a classical computer)