What's the effective speed of quantum computers circa 2022?

Question

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.

Answer 1

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.

3. 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".