We'll have QCs running Shor's algo before next US election - Scott Aaronson \ stacker news ~crypto

pull down to refresh

We'll have QCs running Shor's algo before next US election - Scott Aaronson scottaaronson.blog/?p=9325

369 sats \ 1 comment \ @Scoresby 17 Nov crypto

Scott Aaronson writes the blog Shtetl-Optimized about quantum computing (and has been doing so for twenty years). I usually find him a reasonable voice in QC - not fully a booster, despite earning his bread from the quantum computing world.

His most recent update included the following statement:

given the current staggering rate of hardware progress, I now think it’s a live possibility that we’ll have a fault-tolerant quantum computer running Shor’s algorithm before the next US presidential election.

Now a QC running Shor's algorithm doesn't necessarily mean breaking public key cryptography, it does seem like progress. Certainly, I hadn't noticed Aaronson making such optimistic prognostications before.

In looking for more detail, I found this response from Aaronson to a comment on the post:

Which is a nice clarification. Running Shot's algorithm to factor the prime number 15 does not spell the imminent demise of public key cryptography, but as Aaronson says, the path forward appears to have few obstacles.

view all related items

100 sats \ 0 replies \ @Scoresby OP 20 Nov

UPDATE: Aaronson apparently felt that his initial remark about hardware progress was taken out of context by...pretty much everybody and has published a second blog post entirely devoted to clarifying the comment:

It’s like this: if you think quantum computers able to break 2048-bit cryptography within 3-5 years are a near-certainty, then I’d say your confidence is unwarranted. If you think such quantum computers, once built, will also quickly revolutionize optimization and machine learning and finance and countless other domains beyond quantum simulation and cryptanalysis—then I’d say that more likely than not, an unscrupulous person has lied to you about our current understanding of quantum algorithms.

On the other hand, if you think Bitcoin, and SSL, and all the other protocols based on Shor-breakable cryptography, are almost certainly safe for the next 5 years … then I submit that your confidence is also unwarranted. Your confidence might then be like most physicists’ confidence in 1938 that nuclear weapons were decades away, or like my own confidence in 2015 that an AI able to pass a reasonable Turing Test was decades away. It might merely be the confidence that “this still looks like the work of decades—unless someone were to gather together all the scientific building blocks that have now been demonstrated, and scale them up like a stark raving madman.” The trouble is that sometimes people, y’know, do that.