Quantum computers could crack a common data encryption technique once they have a million qubits, or quantum bits. While this is still well beyond the capabilities of existing quantum computers, this new estimate is 20 times lower than previously thought, suggesting the day encryption is cracked is closer than we think. The widely used RSA algorithm relies on the fact that multiplying two prime numbers to generate a large encryption key is easy, but finding those original prime factors when all you have is the resulting key is extraordinarily difficult. It has long been known, however, that quantum computers will be capable of easily doing things that classical computers find very hard – like cracking RSA keys. A technique to do just that, known as Shor’s algorithm, was first developed in 1994. Craig Gidney at Google Quantum AI co-authored a paper in 2019 that estimated Shor’s algorithm could be used to crack RSA keys of a certain commonly used size – 2048 bits – in just 8 hours using a quantum computer with 20 million qubits. That would effectively allow the controller of such a machine to break into anyone’s email or bank account that had been secured using that technology, and could potentially give them access to state secrets. Now, Gidney has tweaked his method to slash the required size of the computer to less than a million qubits.

Full analysis : A quantum computer with a million qubits would be able to crack the vital RSA encryption algorithm, and while such machines don’t yet exist, that estimate could still fall further.