Comment by SAI_Peregrinus
Comment by SAI_Peregrinus a day ago
And it's 64-bit equivalent in a way that's inherently impossible to parallelize, so 2^64 sequential quantum operations. Those operations are much, much slower than classical ones.
Comment by SAI_Peregrinus a day ago
And it's 64-bit equivalent in a way that's inherently impossible to parallelize, so 2^64 sequential quantum operations. Those operations are much, much slower than classical ones.
Well, you get sqrt(n / N) as a result. It works like any other parallel computation.
E.g. if you have 256 quantum computers, then each one of them needs to search only 60 bits of the key space to crack a 128-bit key (each one of them will only need to search 2^120 keys).
It's not really going to make much difference with near-future quantum computers. Especially since Grover's algorithm _has_ to complete all the 2^60 steps to produce a reliable result, you can't just run a quantum computer for a while, stop it, and then restart it.
You can trivially parallelize Grover's search by assigning each quantum computer it's own search space.