Why do people say that Grover's algorithm does not parallelize well?

Question

I've seen several sources, including NIST, claim that Grover's algorithm is unlikely to be useful for attacking a symmetric-key algorithm like AES-128 or a hashing algorithm because "Grover's algorithm does not parallelize well."

But I don't understand that claim. According to this answer and this paper, $k$ different quantum computers running Grover's algorithm in parallel can search an $N$-element database in $\theta(\sqrt{N/k})$ time steps. Whereas $k$ classical computers running in parallel require $\theta(N/k)$ time steps.

My guess is that when people say that "Grover's algorithm doesn't parallelize well," what they really is that "The relative speedup of running Grover's algorithm on $k$ parallel quantum computers compared to over one quantum computer, which is $\theta(\sqrt{k})$, is asymptotically smaller than the relative speedup of running classical brute-force search on $k$ classical computers compared to over one classical computer, which is $\theta(k)$."

But it seems to me that this quantity doesn't really capture what we intuitively mean by "parallelize well". I suppose that the speedup that is contributed by parallelization itself is smaller in the quantum case than in the classical case, but the quantum case already starts out so far ahead that you still end up with an asymptotically faster runtime on $k$ parallel quantum computers than on $k$ parallel classical computers. Given any $k < N$ number of computers to search a given database, you would always prefer for them to be quantum over classical computers for any $k$, because the number of time steps is asymptotically smaller in the quantum case. So (while I acknowledge that this is largely a matter of semantics) I would say that Grover's algorithm parallelizes better than classical brute-force search, not worse.

More practically speaking: if you are willing to wait some maximum time $T_\text{max}$ to find the answer, and each classical or quantum oracle query requires time $T_C \ll T_\text{max}$ or $T_Q \ll T_\text{max}$ respectively, then searching an $N$-element database fast enough would require $N \frac{T_C}{T_\text{max}}$ parallel classical computers but only $N \left( \frac{T_Q}{T_\text{max}} \right)^2$ parallel quantum computers - an improvement that's asymptotic in $T/T_\text{max}$.

(It's true that if you could somehow combine the quadratic sequential Grover speedup with the linear relative speedup of classical parallelization to get a runtime $\theta \left(\frac{\sqrt{N}}{k}\right)$ for unstructured search - which has proven to be impossible under the standard model of quantum computing - then you'd only need $\sqrt{N} \frac{T_Q}{T_\text{max}}$ parallel quantum computers. This would give you a resource cost reduction that's asymptotic in $N$ rather than in $T/T_\text{max}$, which is probably more useful.)

Getting back to the task of breaking AES-128: I agree that it's probably impractical to do so with quantum computers for the foreseeable future. But that's simply because quantum computers will be very resource intensive, and it will probably be unaffordable to build as many parallel quantum computers as we can build parallel classical computers. But I don't see what that has to do with Grover's algorithm itself; that's a totally separate assumption about the resource costs of building quantum computers.

So is there in fact any meaningful sense in which quantum computers won't be able to attack AES-128 "because Grover's algorithm does not parallelize well," as opposed to simply "because quantum computers will be much more expensive than classical computers"?

Answer 1

Problems that parallelize well have a total cost that stays roughly the same as you apply more machines. You want to be doing roughly the same number of operations, just spread out. Grover search isn't like that; if you spread it over $k$ computers then it needs $\sqrt{k}$ times more operations to solve the problem. That means $\sqrt{k}$ times more energy used which means $\sqrt{k}$ times more money spent. The more parallelization you use, the worse the advantage over classical gets.

Answer 2

A more relevant consideration is not the total number of computers involved, but rather the total number of computational steps over all machines (or a very similar quantity: area-time, the total number of bits/qubits times the runtime). For classical computing this is directly proportional to the total energy consumption, and in most cases directly proportional to the economic cost of the computation (whether you pay for total server time on multiple machines, or the opportunity cost of occupying a server cluster with this computation). The same arguments apply to quantum computing, more or less: there is an energy cost for error correction that is (very likely) to be proportional to (number of qubits)*(total runtime). Even with a huge breakthrough in error correction, there is still this opportunity cost.

So, let's consider the calculation you did above, where we need $N\frac{T_C}{T_{max}}$ classical computers and $N\frac{T_Q^2}{T_{max}^2}$ quantum computers. Multiplying by the total runtime (which is $T_{max}$ for both) and the size of each computer (let's call it $S_C$ and $S_Q$) gives the area-time costs:

$$ \text{Classical}: NT_CS_C\text{, Quantum:} \frac{NT_Q^2S_Q}{T_{max}}$$

Where does this leave us? With a few points:

• When $T_{max}$ is fixed, the total cost of classical and quantum search both grow proportional to the size of the search space. That is: the asymptotic quantum advantage is gone in this context. A fixed $T_{max}$ is a realistic constraint: in cryptography it translates to "how soon do we need to obtain these secrets". Granted, we might be able to drop $T_C$ or $T_Q$ (e.g., if processor speeds improve), but if $T_Q$ is dropping faster than $T_C$, that's not really an algorithmic advantage.
• Generally, the way people think about and talk about classical algorithms assumes a great deal of parallelism. When people say DES is insecure because they keyspace is only $2^{56}$ bits, so you can run an attack in time (on the order of) $2^{56}$, they don't really mean time: even on a modern, fast, 3 GHz processor, that would still take 90 years. It's insecure because people can easily parallelize the attack and they only need $2^{56}$ operations (which is readily affordable). Saying that Grover "doesn't parallelize well" emphasizes that we need to break from that way of thinking. More concretely, the "square-root speedup" that people often talk about isn't real: sequential attacks will never happen, and the advantage diminishes with parallelism.

For a bit of perspective, a somewhat reasonable value of $T_{max}$ is $2^{40}$ operations, which NIST estimated as the number of sequential operations on a surface code with current quantum hardware in a year. Then Grover needs $2^{80}$ qubits to break AES-128. With $2^{80}$ processors, classical computers only need $2^{48}$ sequential evaluations to break AES-128. So if classical computers can compute 256 sequential evaluations of AES in less time than one surface code cycle, there is no quantum advantage. Even if not, the quantum advantage is very very small.

Answer 3

I've been directed to this question from this related question on crypto.stackexchange.com. Apologies if I'm a little unfamiliar with the praxis of this group.

With regard to the definition of "parallelises well", I concur with Craig Gidney's answer that in my circles at least this means that up to a certain bound for $k$, applying $k$ times as many computational resources roughly reduces run time by a factor of roughly $k$.

This does not mean that Grover's algorithm does not parallelise at all, but does mean that one needs to be careful about how one describes attacks. For example, bringing $2^{20}$ quantum computers to bear on a 128-bit search space results in attack of $2^{74}$ operations rather than the $2^{64}$ of a single quantum computer.

With regard to the security of AES, as with all statements of complexity theoretic security this is a statement about economics. The statement that AES-128 is secure against classical computation does not mean that even given unlimited resources there is no way to deploy time and classical compute resources to brute force exhaust a 128-bit key space, rather that such a computation is economically infeasible for a certain timeframe. Likewise, when I say that AES-128 is secure against quantum attack, I mean that it is economically infeasible to deploy the resources required within a given timeframe.

Economic costing by necessity involves a certain level of assumption about the rate of development of technology e.g. with classical computing that the cost of resources does not significantly outstrip Moore's law. My own belief is that 7 billion logical qubits (as compared to say the roughly 2330 needed to attack elliptic curves systems or the 6189 needs to attack RSA), running for 1 year (as opposed to 1 hour for elliptic curve and 8 hours for factoring estimates, both using clock rates several order of magnitude smaller) is an infeasible rate of economic development for cryptographically relevant timescales. I similarly believe that achieving another 45-or-so-bits of speed up¹ in classical compute power is going to be economically infeasible for similar timescales, though maybe less infeasible than the required growth for quantum attacks.

1. I'm not sure of the exact model for current classical resources should be, but the world Bitcoin network is currently operating at around $2^{68}$ hashes per second.