The microblog: 2017.09.07 09:27:07

2017.09.07 09:27:07 (905693902241501184) from Daniel J. Bernstein, replying to "JP Aumasson (@veorq)" (905682451565031425):

Looking more closely I see that the paper's cost analyses are wrong even for the non-quantum part: the usual instant-access-to-RAM mistake.

2017.09.07 09:43:45 (905698084600107008) from Daniel J. Bernstein:

"First proof of an actual quantum time speedup": The paper doesn't analyze actual time. For oversimplified "time", 1998 BHT proved speedup.


2017.09.07 08:20:25 (905677114384424960) from Daniel J. Bernstein:

Collisions: says time N^0.4 using hardware N^0.2. But parallel rho is better: time N^0.35 using hardware N^0.15.

2017.09.07 08:41:37 (905682451565031425) from "JP Aumasson (@veorq)":

time-space product of 12/25 is interesting, but yeah ignores the cost of QC hardware vs classical, the latency of Q circuits etc.