Why Haven’t Quantum Computers Factored 21 Yet?
If you are to believe the glossy marketing campaigns about ‘quantum computing’, then we are on the cusp of a computing revolution, yet back in the real world things look a lot less dire. At least if you’re worried about quantum computers (QCs) breaking every single conventional encryption algorithm in use today, because at this point they cannot even factor 21 yet without cheating.
In the article by [Craig Gidney] the basic problem is explained, which comes down to simple exponentials. Specifically the number of quantum gates required to perform factoring increases exponentially, allowing QCs to factor 15 in 2001 with a total of 21 two-qubit entangling gates. Extrapolating from the used circuit, factoring 21 would require 2,405 gates, or 115 times more.
Explained in the article is that this is due to how Shor’s algorithm works, along with the overhead of quantum error correction. Obviously this puts a bit of a damper on the concept of an imminent post-quantum cryptography world, with a recent paper by [Dennish Willsch] et al. laying out the issues that both analog QCs (e.g. D-Wave) and digital QCs will have to solve before they can effectively perform factorization. Issues such as a digital QC needing several millions of physical qubits to factor 2048-bit RSA integers.