Quote from: tromp on December 21, 2015, 05:38:46 PM

Quote from: Come-from-Beyond on December 21, 2015, 05:18:50 PM

Quote from: tromp on December 21, 2015, 04:31:26 PM

PoWs requiring billions of bits are pretty safe from QC quadratic speedup,
which is still struggling to work for mere dozens of qubits.

We have stopped on time-memory trade-off...

Not all TMTOs are linear...

You don't even need a PoW with superlinear TMTO.
A simple and practical PoW like Cuckoo Cycle suffices.

They key insight is that the longer a single proof attempt takes,
relative to the block interval, the smaller the advantage of the QC.

Let's say the block interval only allows for a 100 proof attempts (nonces) by a single miner.
(e.g. 10 second block interval, and 0.1 second proof attempt).

A QC can use quadratic speedup to search those 100 nonces in 1/10 the time,
but this will small 10x advantage will be completely wiped out by

1) the TMTO slowdown and penalty (already a factor 10^3 for a million qubit QC running cuckoo on 2^27 nodes)

2) cycle time of QC being way longer than that of classical computers

3) constant factor overhead in running Grover algorithm.