How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

algorithm failing is at most R^2. For example, if R is less than 1 degree then the chance of algorithm failure will be less than 0.03%. That's an acceptable retry chance for Shor's algorithm. The QFT circuit on N qubits performs less than N^2 rotations. So, for R to be less than 1 degree, it's sufficient for each rotation's error X to be less than (1°)/N^2. Therefore the required precision only increases polynomially (like N^2) instead of exponentially (like 2^N). Note the required precision can be improved from O(1/N^2) to O(1/N) using techniques like the qubit recycling QFT [4]. Actually, even if the required precision scaled exponentially, that still wouldn't be an insurmountable problem. Quantum error correction achieves exponentially tighter tolerances from polynomially increasing resources. For example, Ross and Selinger proved that continuous rotations can be approximated to a target error of epsilon using O(log(1/epsilon)) gates from the discrete gate set Clifford+T [4]. And Clifford gates with error below epsilon can be achieved in the surface code using O(log(1/epsilon)^2) noisy qubits for O(log(1/epsilon)) time [5]. And T gates can be achieved by using those reliable Clifford gates to perform magic state distillation of log(1/epsilon)^O(1) T states [6]. Since everything scales polynomially in log(1/epsilon), making epsilon exponentially smaller adds polynomial resources. There is no part of Shor's algorithm that requires resources growing exponentially in n (the number of digits of the number being factored). The practical scaling is more like n^3: factoring a number that's twice as large can be done with ~two times as many qubits running for ~four times as long. Even if the qubits are noisy [7]. [1]: https://en.wikipedia.org/wiki/Quantum_Fourier_transform#/med... [2]: https://arxiv.org/abs/quant-ph/0306018 [3]: https://arxiv.org/abs/quant-ph/9601018 [4]: https://arxiv.org/pdf/quant-ph/9903071#page=12 [5]: https://arxiv.org/abs/1208.0928 [6]: https://arxiv.org/abs/1209.2426 [7]: https://arxiv.org/abs/1905.09749

made in our lifetimes, despite optimism/fear/hope, depending on who you are, to the contrary. > What would be required to factor a 1024 bit integer key? I assume you mean a 1024-bit RSA key (if you mean a 1024-bit ECC key, I want to know what curve). You can crack 1024-bit RSA with 2051 logical qubits according to: https://arxiv.org/abs/quant-ph/0205095 In order for it to actually work, it is believed that you will need between 1000 to 10000 physical qubits for every logical qubit, so it could take up to 20 million qubits. Coincidentally, the following paper claims that cracking a 2048-bit RSA key can be done in 8 hours with 20 million physical qubits: https://arxiv.org/abs/1905.09749 That sounds like it should not make sense given the previous upper estimate of 20 million physical qubits for a 1024-bit RSA key. As far as I can tell, there are different ways of implementing Shor’s algorithm and some ways use more qubits and some ways use less. The biggest factor in the number of physical qubits used is the error correction. If you can do better error correction, you can use fewer physical qubits.

paper https://arxiv.org/abs/1905.09749 That goes into a clear discussion of how to build a quantum computer and the associated thresholds that would allow you to do so. There is a minimum number of qubits needed (that work perfectly), but the paper analyzes how many qubits you'd need under realistic assumptions about how many noisy qubits you'd need to get error correcting qubits at the needed reliability.

an error in a quantum computation). For analogy, you can imagine that if you computed a public key using this trick that you would not be comfortable handing an attacker the registers storing your public key before you removed the carry padding that made the computation faster. But it turns out that if you just initialize the carry padding randomly, subtracting out of the next word at the start to ensure everything sums to the correct result at the end, then you can show that the information leakage and chance-of-bad-overflow is exponentially suppressed in the length of the carry padding. Currently the most efficient known way to implement Shor's algorithm uses this technique [4]. 1: https://en.wikipedia.org/wiki/Carry-save_adder 2: https://arxiv.org/abs/1905.08488 3: https://youtu.be/upTipX9yXNg?t=777 4: https://arxiv.org/abs/1905.09749

factor 2048 bit RSA. Symmetric cryptography is already safe against quantum computers. Algorithms for Post-quantum_cryptography are under development and you might expect to see them adopted within next 10 years or so. https://en.wikipedia.org/wiki/Post-quantum_cryptography