4
$\begingroup$

Obviously they do not correspond to classical clock speeds, but they still have a number of operations they can do per second.

And it does really matter a lot. Suppose you are attacking an SHA256 hash. Because of rainbow tables, you only have about 128 bits of security. Grover's algorithm halves the size of the search space of basically anything, so until proven otherwise that's now it's 64 bits of security.

If you expect and equivalent of 50 "attacks" per second per multi-million dollar machine, this is a basically unbreakable level of security, on the other hand, if you expect 5 million attack equivalents per second on a tens to hundreds of thousands of dollars machine, it becomes doable in under a year to a few decades depending on attack budget, which can't be considered secure at all.

So what are we closer to right now, and how much of a shift seems likely?

I know (close enough) why and how quantum speedup works algorithmically, I just can't dig up anything decent on hardware specs.

$\endgroup$

1 Answer 1

6
$\begingroup$

A few things:

  1. The 128 bits of security of SHA-256 is the hardness of a collision search, and pre-image resistance is still (classically) 256 bits. Grover's algorithm only helps with pre-image resistance. For collision search, there are a few ways to search for pairs of $(x,y)$ with the same hash using Grover's algorithm, but they end up with a complexity which is the square root of $2^{256}$, i.e., $2^{128}$, but we can achieve that classically with various methods (probably Pollard's rho would be the most effective). There is a slightly better query complexity if we use a lot of QRAM, but there's a lot of reasons to believe that's less practical. Basically, there isn't really a quantum advantage for collision search.
  2. Actually attacking a massive problem with complexity at least $2^{64}$ simply isn't done sequentially. That is, $2^{64}$ operations is considered classically feasible, but even with a 5 GHz processor, that would take 117 years. It's feasible because we can build so many processors, and run them in parallel. For example, it would only take 1400 5 GHz processor to complete $2^{64}$ operations in one month.

However, that requires the underlying algorithm to be perfectly parallelizable, meaning that the total number of operations doesn't change if we use multiple processors to solve the problem faster. While most classical algorithms (like Pollard's rho) are perfectly parallelizable, Grover's algorithm is definitely not. If you want to solve the problem twice as fast, you need 4 times as many processors, and thus 2 times as many total operations.

  1. To answer your actual question: Table 1 from https://arxiv.org/pdf/1905.13641.pdf gives some gate times; they're around 10s-100s of nanoseconds per gate on superconducting qubits (which I believe are one of the fastest types). This isn't the full answer, though, because these are physical qubits with error rates that are too high. We expect to need logical qubits (i.e., an abstract qubit formed of many physical qubits with error correction), and each logical operation will take 100s or 1000s of cycles. The number of cycles increases with the level of error correction we need, which in turn is based on the overall complexity of the algorithm. For something exponential like Grover, it will likely be at least 1000. Thus, we can wildly estimate about 1-100 microseconds per logical gate.

Actual published estimates for, e.g., Shor's algorithm, guess about 0.2-1 microseconds per "surface code cycle", meaning about 0.2-1 milliseconds per logical gate.

Then if you're using Grover's algorithm to attack something like SHA-256 or AES, you need many gates (again, 100s to 1000s) to compute the function itself. AES in particular needs approximately 2000 sequential gates. Multiply all these extra factors and you're looking at about 2 seconds per AES evaluation.

This means a single quantum "processor" running Grover's algorithm could do something like $2^{28}$ sequential computations of AES in 10 years, and thus search a space of $2^{56}$ keys. This means you would need $2^{128}/2^{56}= 2^{73}$ quantum processors to break AES in 10 years.

For pre-image search on SHA-256, it would be much much worse, because the search space is $2^{256}$, so you'd need about $2^{200}$ processors (assuming computing SHA takes as long as computing AES).

I was a bit lazy in looking up exact gate times, but that's because, thanks to all the overheads, even fast gate times are worse than "50 attacks per second".

$\endgroup$
5
  • 1
    $\begingroup$ Agree with everything except the 1us cycle implying 1ms logical gates in the surface code. Code deformation doesn't take 1000 rounds to do; more like 25-100. And once you really start optimizing the packing of the computations into spacetime, instead of just finishing one gate then starting the next, the actual limiting factor ends up being the number of magic state factories or the reaction time. $\endgroup$ Mar 29, 2022 at 15:41
  • $\begingroup$ Oh I forgot that the qubit overhead is $d^2$ for a distance-$d$ code but the cycle overhead is just $d$. Is that what you're referring to is there something deeper? As in, won't most gates (I'm thinking CNOT for example) require around $d$ cycles, if we assume the same rate for different types of errors? $\endgroup$
    – Sam Jaques
    Mar 29, 2022 at 16:25
  • $\begingroup$ Yes, that's where I got the 25-100 from. Also, sometimes it takes two or three code deformation steps. But once you start optimizing you realize Cliffords are so flexible they're pretty irrelevant to the duration (you can sequence them over space instead of over time, and you can always defer them past non-Cliffords by tweaking the observables the non-Cliffords apply to). $\endgroup$ Mar 29, 2022 at 16:29
  • 1
    $\begingroup$ Grover is not really parallelizable in this way. For $k$ machine one can get $\sqrt{k}$ speed-up 1. $\endgroup$
    – kelalaka
    Jun 17, 2022 at 16:58
  • 1
    $\begingroup$ That's what I'm describing, but I'm just taking the reverse view: if you want a speed-up of $k$, you need $k^2$ machines. With $2^{73}$ machines the speed-up factor is $2^{36}$. Take that off of $2^{64}$ and you get $2^{28}$, as I said (modulo rounding errors). $\endgroup$
    – Sam Jaques
    Jun 18, 2022 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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