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