It's an interesting technical question: analogous to the quantum fourier transform, is there an algorithm only quantum machines can run that computes sha-256 ha

It's an interesting technical question: analogous to the quantum fourier transform, is there an algorithm only quantum machines can run that computes sha-256 hashes faster? I don't have the answer. (I know sha-256 is O(N) normally.) As for bitcoin, though, I don't think there's too much to worry about. If a quantum algorithm grants a complexity speed up (or some sort of deal-breaking cryptographic weakness is discovered in sha-256 for that matter), I imagine the network could agree to update to a new protocol using a different hash, if that was the proper solution. If a quantum computer just gave integer-factor speedups such as ASICs are currently doing to GPUs and FPGAs, then I suspect by the time a quantum computer is made that can efficiently mine bitcoins, enough can be made at once that, just as we're seeing with ASICs, quite a lot of miners will grab them (avoiding a 51% issue) and the difficulty will simply rise. Edit: https://bitcointalk.org/index.php?topic=78693.0 https://bitcointalk.org/index.php?topic=78693.0 tells me http://en.wikipedia.org/wiki/Grover%27s_algorithm http://en.wikipedia.org/wiki/Grover%27s_algorithm would work, making the algorithm O(sqrt(N)) and effectively making the problem of finding a sha-256 hash into finding a sha-128 hash.