2
$\begingroup$

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"?

$\endgroup$

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ It seems to me that that would be very much problem-dependent. If you care much more about runtime than about energy, hardware costs, etc., then (as I explained above) Grover's algorithm parallelizes better than classical brute-force search. I agree that for most problems, that won't necessarily be the appropriate utility function, but there might be some problems for which saving time is more important than saving hardware resources, in which case the optimal approach would be Grover's algorithm parallelized over as many quantum computers as possible. $\endgroup$
    – tparker
    Nov 12, 2022 at 22:13
  • 2
    $\begingroup$ @tparker It does not parallelize better. With classical bruteforce, using $k$ machines reduces the time by $k$. With grover using $k$ machines only reduces it by $\sqrt{k}$. That's enormously less efficient; a huge cost to pay for a space time tradeoff. Also, as $k$ increases, it's not limiting to something quantum it's just becoming classical brute force. $\endgroup$ Nov 12, 2022 at 23:48
  • $\begingroup$ You're correct, if you measure the gains to parallelization by the proportional reduction in resources gained from parallelization. But this quantity seems to me to be of limited operational utility. The only reason that brute-force search parallelizes "better" is because it starts from such an inefficient baseline; Grover's algorithm parallelizes "worse" because it's already more efficient at every combination of $N$ and $k$, so there are fewer gains left to be had from parallelization. To me, the more relevant fact is not comparing relative gains but absolute performance, and at the ... $\endgroup$
    – tparker
    Nov 13, 2022 at 3:07
  • $\begingroup$ algorithmic level, Grover's algorithm is much more efficient that brute-force search for every choice of $N$ and $k$. In the real world, a massively parallel Grover's algorithm is probably impractical to build, but that just reflects the practical engineering challenges of building quantum computers; it isn't a result that can be derived from Grover's algorithm itself. In the abstract, there's no reason to assume that 1 is the optimal elasticity of substitution for the space-time tradeoff; it depends on the relative costs of runtime vs. hardware for a given application. $\endgroup$
    – tparker
    Nov 13, 2022 at 3:11
  • $\begingroup$ @tparker The comparison to brute-force is a red-herring, I think. An algorithm parallelizes well/poorly relative to itself, in some sense. If you have X times the machines, how many times faster do you solve the problem? Perfect parallelism means X times, it doesn't matter what kinds of machines you're using, or what alternatives exist to your algorithm. $\endgroup$
    – mbrig
    Nov 13, 2022 at 8:07
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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 up1 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.
$\endgroup$
2
  • $\begingroup$ I agree with everything in this answer. My only (very limited) claim is that it's somewhat misleading to say that the main reason why Grover's algorithm is unlikely to affect the security of AES is that it "doesn't parallelize well". (I know that you don't make this claim, but other people do.) In my opinion, the main reason why Grover's will probably not be effective is the cost and engineering difficulty of building quantum computers (as compared to classical ones), and any results that can be directly derived from Grover's algorithm itself are only partially relevant. $\endgroup$
    – tparker
    Nov 13, 2022 at 17:06
  • $\begingroup$ The fact is that if we could make quantum computers as fast and as cheap as classical computers, then we might still be debating the semantics of whether Grover's algorithm "parallelizes well", but we'd also probably be running Grover's algorithm in a massively parallel fashion, not in serial, on real-world problems. $\endgroup$
    – tparker
    Nov 13, 2022 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.