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:
- 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?)
- 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.