Shor's Algorithm for factoring integer numbers is the big threat to cryptography (RSA/ECC) as it reduces the complexity from exponential to polynomial, which means a Quantum Computer can reduce the time to crack RSA-2048 to a mere 10 seconds. However current noisy NISQ type quantum computers are very limited to something like 16 bit RSA keys. And the quality of the current qubits is so bad that error-correction comes at a massive cost of at least 100 times the amount of qubits.
While the world is pre-occupied whether we have universal quantum computers big enough for Shor's algorithm, Quantum Annealing is stealing the show with having factored a 20-bit number just in January this year using 97 qubits. And these qubits are actually good enough to factor bigger numbers. If we assume a linear scalability, we'd "only" need around 10,000 qubits to factor a 2048bit RSA key. D-Wave announced a quantum computer with 5,640 qubits, so that puts it within reach soon.
So, could Quantum Annealing be more of a threat to cryptography than Shor's algorithm on universal quantum computers? How do these algorithms work? How do they achieve a polynomial complexity to what traditional computers need exponential time? What impact will this have on the competition from NIST for the design of post-quantum-cryptography algorithms?
Andreas Baumhof is Vice President Quantum Technologies at Quintessence Labs. He is responsible for all developments relating to Quantum Technologies such as Quantum Random Number Generator, Quantum Key Distribution or Quantum Computing in general. Before this role, Andreas was CTO for ThreatMetrix Inc, the global leader in digital identities, where he was responsible for software engineering. He helped lead the company to a very successful exit and a 830m USD acquisition by Lexis Nexis/RELX. Andreas holds a mathematics degree from the University of Munich. In his spare time he enjoys mountain biking, snowboarding and spending time with his family. Twitter: @abaumhof LinkedIn: https://www.linkedin.com/in/abaumhof/