Can Grover's algorithm be parallelized?

Question

Grover's algorithm can search an unordered list of length $N$ in time $\sqrt{N}$ on a quantum computer. Applied to cryptography, this means that it can recover n-bit keys and find preimages for n-bit hashes with a cost of $2^{n/2}$.

But the basic version of Grover's algorithm is sequential. Each iteration uses the output of the previous iteration as input. I don't see an obvious way to parallelize the algorithm. Reducing the number of iterations significantly reduces the success probability more than linearly.

If the algorithm is inherently sequential, building a bigger computer won't speed up the attack, limiting its impact. $2^{80}$ sequential cipher invocations looks pretty hard to achieve to me. On the other hand, $2^{80}$ parallel cipher invocations is already on the edge of feasibility today using classical computers.

Assume an attacker using a quantum computer is limited to $T$ timesteps with $T<\sqrt{N}$, so they can't run Grover's algorithm with the optimum number of sequential steps. What's the cost for finding a preimage/recovering a key? What is the average cost per-break if they have multiple targets?

Answer 1

This is an older question, but it's come up a couple times for me recently and I want add some clarification.

If you want to speed up Grover's algorithm, you can split the search space up into $k$ chunks and run independent searches on $k$ machines. Since your search space is $\frac {N} k$, each search will complete in $O(\sqrt{ \frac {N} k})$. You only get a square-root speedup because you're losing quantum parallelization when you split up the search space. A more detailed explanation of this can be found here.

The issue of parallelization is separate from that of multiple targets. Contrary to mephisto's answer, Grover's algorithm works just fine on a search space containing $k$ correct indices/inputs, provided you modify the number of iterations to $\frac {\pi} 4 \sqrt{\frac {N} k}$. When $k$ is unknown (as is often the case), you may need to employ some cleverness to keep it $O(\sqrt{\frac {N} k})$ (see section 4 of this paper). Importantly, $N$ does not need to be "kept small" to accommodate this. The main constraint on $N$ is the underlying hardware capability.

Answer 2

We recently discussed this question with some colleagues, and this is what we came up with (no guarantees):

Grover's algorithm only outputs a correct answer if it is fed with an input set such that the target function evaluates as 1 for a single input and as 0 otherwise. The algorithm then iterates a subroutine $\sqrt{N}$ times (where $N$ is the size of the input set) to push the amplitude of the input that evaluates as 1 up. That way, the correct input is measured with a high enough probability (sorry for being vague at this point).

To use Grover's algorithm to attack a hash function's preimage resistance, you select a random subset of inputs and hope that there is one input that is actually a preimage of the target value (I guess a small number of preimages should also be OK, as all their amplitudes should be pushed up and eventually one of these is measured). Now, the runtime of Grover's algorithm depends on the size of the input set $N$. So, we want to keep this $N$ small. On the other hand, we have to select $N$ such that with significant probability there is a preimage in this set. In general, it is assumed that we need to take $N$ in the order of the output size of the hash function to get this probability high enough.

If we want to parallelize this, it should work as follows. Assume we get a quantum computer with twice the number of qubits needed to run Grover with an input set of size $N$. In that case, we can run it on two input sets of size $N$ while still taking only time $\sqrt{N}$. However, the benefits are also only linear, the probability of finding a preimage (or rather the probability of finding an input set containing a preimage) is only doubled.

Of course, we could also run it with an input set of size $N^2$, increasing our success probability exponentially, but this also increases the runtime exponentially.