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.
underlying article: https://algassert.com/post/2500
The linked paper, “Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog” is also a great breakdown of how much the quantum factoring is more of a parlor trick and not practical for factoring RSA Keys, mainly since the prime factors are only a few bits off of each other and from the square root of the number being factored.
Omg, I simply cannot! Thanks for brightening my day with this paper XD
a well trained dog outperforms current quantum-made calculations 👍🥳
Seriously recommend this. I saw it a while back and found it highly informative.
The talk is on YT… Id link but at work atm