Quantum computers can get some speedup for this kind of "collision problem": I believe their running time would be O(2^(n/3)) in this case. See http://arxiv.org/abs/quant-ph/9705002 http://arxiv.org/abs/quant-ph/0112086 Best, Cris On Jul 13, 2014, at 6:37 AM, "Adam P. Goucher" <apgoucher@gmx.com> wrote:
The usual proof-of-work system involved in things such as Bitcoin mining is the following:
"Find a string S such that hash(S) begins with n leading zeroes"
A classical probabilistic computer can do this with O(2^n) operations (which are very parallelisable), whereas a quantum computer can do this with O(2^(n/2)) operations using Grover's algorithm (which is not parallelisable). Nevertheless, this would give quantum computers significant advantage over their classical counterparts in Bitcoin mining.
Instead, I propose the following alternative proof-of-work system:
"Find two distinct strings, S and T, such that hash(S) and hash(T) agree in the first n bits"
Now, a classical probabilistic computer with memory O(2^(n/2)) can do this in time O(n 2^(n/2)) by doing the following:
1. Create O(2^(n/2)) distinct strings; 2. Hash them; 3. Quicksort the hashes, and compare adjacent entries to see whether any agree.
The probability of success as a function of n is bounded below due to the birthday paradox.
A quantum computer using Grover's algorithm would take O(2^(n/2)) time with the following method:
1. Create a string S; 2. Search for a distinct string T whose hash agrees with S in the first n bits.
And O(2^(n/2)) is only slightly faster than O(n 2^(n/2)), and the difference is probably engulfed into the constant factor involved in implementing a fault-tolerant quantum computer. Hence quantum computers have no real advantage over classical computers, except for requiring less memory.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun