If you were not worried about having exponentially large memory for a classical computer I suppose to be fair we should allow this for a quantum computer too. In that case, you could have the quantum computer seek 2^(n*C) words, at least two of which agree about the first n bits of their hash. This has probability of occurrence that is of order 2^(-max(1-2*C, 0)*n) if random words are tried. Now there are versions of Grover search algorithm, which run in expected #steps proportional to about squareroot(1/p) where p=probability of occurrence. If time for a step is here 2^(n*C), then total time is of order 2^( (C + max(1-2*C,0)) * n ) which is optimized by choosing C=1/3, which causes the quantum runtime to be of order 2^( n*2/3 ). So... no. The quantum computer here is faster than the classical algorithm, so Adam Goucher's proposal only partially worked. While I'm at it, I think bitcoin is incredibly stupid and cannot believe anybody wants to use it. It is an embarrassment to humankind. Far far better proposals for digital money based on public key cryptography have been made, and made well before the idiots who came up with bitcoin too, and they do NOT require any idiots to keep on grinding for ages and to prove they did (which, if bitcoin really caught on, would be a huge consumer of power forever). Instead, when using money you just do one polynomial time computation then stop, confident you will never be breakable unless PKC is broken. These still will be busted by quantum computers though (which bust the PKC schemes that were used).