|
|
|
|
|
|
by cyphar
2731 days ago
|
|
|
> One estimate indicated that Bitcoin and ECDSA would be broken with Shor's by - optimistically - 2027. I think 2027 is beyond optimistic. We still haven't solved quantum storage (in fact, there's a strong argument that it might not be physically possible since you'd likely need 4-dimensional media to store passively-error-correcting qubits) or any other number of fairly fundamental issues before we can actually run CrackPrivateKey(). > Will Grover's algorithm find a more efficient approach? Grover's algorithm is the optimum speedup for problems of its form ("brute force" searches), and it gives a square-root speedup. So doubling keys solves post-quantum for Grover's algorithm. Shor's algorithm gives an exponential speedup, and so is going to always be a better speedup. |
|
|
I should've been more specific: is it at all likely that Grover's will enable faster/feasible search of "quantum algorithm space" (?) or crypto_algo_classical_implementations-space? Or are we limited by number of qubits and QEC for the foreseeable future?
... Quantum Algorithm Zoo: http://math.nist.gov/quantum/zoo/