2020.02.04 19:13:34 (1224757908682027008) from Daniel J. Bernstein, replying to "John Schanck (@susurrusus)" (1224749552474955777):
Let's work out the numbers for getting the obvious n=53 1000-gate attack done in 1 second. Parallelize across, say, 2^23 chips, each storing 2^30 floats and doing 2^40 simple ops/second. Spreading chips across 100m x 100m handles the heat. Speed of light is nowhere near an issue.
2020.02.05 23:42:44 (1225188033403801602) from Daniel J. Bernstein:
Side note further confirming my model: Google's Nature paper https://www.nature.com/articles/s41586-019-1666-5.pdf also says that it uses the obvious space-2^n algorithm for as many qubits as it can (namely 43) given the amount of RAM on the target computer. Realistic parallelism gets latency down to 2^(n/2).
2020.02.04 18:04:10 (1224740440160731136) from Daniel J. Bernstein, replying to "John Schanck (@susurrusus)" (1224735804393709574):
IBM's "2.5 days" is bottlenecked by _disk_, precisely because they don't have enough RAM (which would cost roughly $100 million). "Treewidth" on slide 17 sounds like an allusion to vastly slower algorithms: Google estimates 10000 years for these circuits. Why do you claim faster?
2020.02.04 18:09:17 (1224741730941112320) from Daniel J. Bernstein:
And, to be clear, the arxiv paper that you cite is one of the vastly slower algorithms for these circuits. Google skipped the obvious much faster algorithm because they didn't realize space 2^53 is feasible; this is questionable for legitimate users and wrong for attackers.
2020.02.04 18:24:42 (1224745610718384128) from "John Schanck (@susurrusus)":
Treewidth is an allusion to tensor network contraction algorithms. IBM's estimate of 2.5 days is limited by disk, but they estimate 0.45 days on tensor network contraction. Their estimate is based on Table 1 of the arxiv paper I cited.
2020.02.04 18:40:22 (1224749552474955777) from "John Schanck (@susurrusus)", replying to "John Schanck (@susurrusus)" (1224745610718384128):
Correction: 0.17 days. I pulled the percent compute time from the wrong table.