Re:IBM Wants Everyone to Try a Quantum Computer
by Natanael_L on Wednesday May 04, 2016 @12:04PM
(#11629290)
Computing 2xSHA256 on a some hundred bytes block header with one section open for randomness will not be that easy on a quantum computer (the more complex the problem, the easier for noise to drown out the answer), not to mention you'll still need fast ASIC hardware to evaluate all QC outputs looking for valid blocks.
And you must reset part of the problem (the previous block hash, at minimum) when new blocks are released, adding some latency (you need to recompute the qubit configuration before resuming).
But perhaps a SIDH based proof-of-work algorithm could be implemented to further resist QC speedups. Don't know exactly how that would work. Does Grover's still apply?
So while classical miners are brute forcing through a 2^70 search space, the quantum miner can find a solution in roughly sqrt(2^70) = 2^35 steps.
Other proof-of-work systems can be more quantum resistant, e.g. looking for a fixed-length cycle in a huge random graph, for which no efficient quantum algorithm is known.