Speed versus number of qubits for RSA factorization

Question

I'm trying to gain a better understanding of the requirements for successful 2048-bit RSA key factorization in relation to time needed versus qubits available. For this I have some questions that hopefully make sense.

In How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits several numbers are mentioned:

1. The amount of qubits needed for factorization of a n-bit long key is: 3n + 0.002n lg n

For a 2048 bit long RSA key this would then be 3*2048 + 0.002*2048 + lg(2048)= 6151.4 (=6152 qubits)

Question 1: Is my interpretation correct, that a minimum of 6152 (logical) qubits is required to achieve the capacity of factoring 2048 bit long integers (irrespective of how long this might take)? (By the way: Why are Gidney & Ekerå using much more logical qubits in their paper, 226*63=14,238?)

2. They report that for factoring 2048 bit long integers using their method this would take 5.1 hours when 20 million (physical) qubits are available.

Question 2: Will having more or less qubits available speed up or slow down the runtime? Question 3: If so, is the relationship between the amount of qubits available and runtime linear: Is it true that if we only had 2 million qubits the same calculation would take 51 hours (or with 200 million qubits 0.51 hours)?

The reason I'm asking these questions is to better understand if we do have to have all 20 million qubits for factorizing 2048 bit long keys or if it attacks would start to become possible even if we had less (e.g. 6152 qubits) but then with just longer runtimes. (It is understood that a plethora of other variable such as error rate and further optimizations also play a role but let's assume that these variables are held constant for the sake of the argument)

I'm curious for your replies!

---

Update on September 13th

After considering Craig's answer I would like to expand and elaborate my question a bit: My ultimate goal is to better understand what the "quantum breaks crypto"-moment will look like - presumably it happens in phases or stages rather than a singular moment. For this I'd like to entertain some thoughts that are intentionally agnostic to the particular technical/physical challenges that need to be solved:

If we assume that future quantum computing evolution can be described as a continuous function (exponential, as with Moore's law), then this might enable us to already make some deductions about future growth, for example for high-quality qubit sizes:

Now we have about $10^2$ qubits, and then perhaps in 2030 about $10^3$, 2040 then $10^4$, 2050 then $10^5$, 2060 then $10^6$ and in 2070 about $10^7$, etc..

These numbers do not serve to predict what we'll have achieved at a particular point in the future but showcase instead, how the Qubit growth ought to look like if the "quantum breaks crypto" epoch is going to realize itself in a not-too-distant future. (This is ruling out any "black-swan quantum development events" in which the number of usable high-quality qubit suddenly jumps from $10^2$ to $10^6$) If growth is indeed continuous, then from today's perspective some conclusions could be drawn in regard to key sizes (here citing numbers from Gidney & Ekerå):

• factoring 4096 instead of 2048 bit keys requires 55 megaqubits instead of 20 --> Can be achieved perhaps 3-4 years later
• factoring 8192 bit keys requires 140 megaqubits --> Will become feasible approximately one decade after factoring 2048

If the (presumably) exponential development happens faster or slower, then of course these capability stages are also reached faster/slower.

Some other conclusions could be drawn for runtime, which relates to my initial question.

• In Gidney & Ekerå 20 megabits are required for factoring a 2048 bit key within hours
• In Status of Quantum Computer Development (p. 123) it is estimated that with 1 megaqubit is required for factoring a 2048 bit key in 100 days

It is understood that comparing these two studies is a bit like comparing apples with oranges but I would assume that the general gist holds true: If a time-space tradeoff enables us to use less qubits by one order of magnitude, then this likely translates into being able to successfully factorize RSA keys earlier by years.

While my argumentation now was specifically talking about only one of the factors (qubit count) required for successful/efficient factorization and ignoring others, I would hope that the idea generally also holds true for the improvement of these other factors.

Thanks for everyone's time reading this & I'm curious to hear all your thoughts on this reasoning.

Answer 1

[Are] a minimum of 6152 (logical) qubits is required to achieve the capacity of factoring 2048 bit long integers[..]?

No, we intentionally used more logical qubits than needed because that reduced the amount of time so much that it allowed us to use smaller code distances. Ultimately this cut the number of physical qubits per logical qubit by more than enough to pay back the increased number of logical qubits.

The best "only pay attention to number of logical qubits" compilation of factoring 2048 bit RSA integers that I know of uses 4097 logical qubits (the abstract says that Zalka has a smaller one but actually Zalka's had a showstopping bug). 2047 of those qubits don't even need to be initialized; they can be borrowed from another computation and will be returned unchanged. But this construction is terrible when it comes to time cost or to physical qubit count.

---

Why are Gidney & Ekerå using much more logical qubits in their paper, 226*63=14,238?

The extra logical qubits are workspace for the actual computation, for magic state distillation, and for routing. See Figures 4,5,6,7 from the paper which all show how space is allocated:

---

Will having more or less qubits available speed up or slow down the runtime?

You can save space at the cost of time by using fewer magic state factories. Table 2 shows various examples of this:

You can save time at the cost of space by using more magic state factories and more oblivious carry runways (reducing the depth of the adders so that the magic states can actually be consumed quickly enough). This will also require adjusting the window sizes used for windowed multiplication/exponentiation to avoid table lookups dominating the time cost.

Note that these tradeoffs are not inversely proportional. Doubling space usage won't cut time usage in half, or vice versa. The construction presented in the paper is near a local minimum for the amount of hardware time used (this is the product of time used and space used), and moving away from it will generally increase the energy cost of the computation.

In general, Shor's algorithm is amazingly amenable to depth reduction by paying space. You can get all the way down to polylogarithmic depth in the number of bits of the number being factored (this is less than the best known asymptotic depth of the classical postprocessing that finishes the algorithm!). Just don't ask how many magic state factories need to be running in parallel for that to work, or how many physical qubits those factories covered, because you won't like the answer.