3 ms·
You can trivially parallelize Grover's search by assigning each quantum computer it's own search space.
by cyberax 1y ago
You can trivially parallelize Grover's search by assigning each quantum computer it's own search space.
- upofadown 1y agoYes, but then you give up the advantage that Grover's gives you in the first place. The advantage is sqrt(n). You are reducing n by parallelizing.
- cyberax 1y agoWell, 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.
- SAI_Peregrinus 1y agoThey still take the same amount of time to run it. You don't get a result by running for 1/n of the steps, so adding more QCs lets you attack more keys at once but doesn't let you attack any given key any faster.