An interesting paper was published on arXiv, the preprint server. Titled “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” the paper by Craig Gidney and Martin Ekerå combines previous techniques from Shor (1994), Griffiths-Niu (1996), Zalka (2006), Fowler (2012), Ekerå-Håstad (2017), Ekerå (2017, 2018), Gidney-Fowler (2019), and Gidney (2019) to significantly reduce the cost of factoring integers and computing discrete logarithms in finite fields on a quantum computer. By integrating these approaches, the authors claim that their construction’s spacetime volume for factoring RSA-2048 integers is a hundredfold less than comparable estimates from earlier works.
I find this paper notable because only six years ago, Fowler et al. published their optimization of Shor’s algorithm, estimating the need for 1 billion noisy qubits to factor RSA-2048. The rapid advancement in quantum algorithm development gives us an intriguing data point to predict when quantum computers will be capable of breaking our current cryptography.
See the full paper here: https://arxiv.org/abs/1905.09749
