Replication of Quantum Factorisation Records with a VIC-20, an Abacus, and a Dog

(eprint.iacr.org)

81 points teddyh | 2 comments | 18 Jul 25 19:09 UTC | HN request time: 0.003s | source

Show context

tomgag ◴[18 Jul 25 19:57 UTC] No.44609103[source]▶

I guess I'll post it here as well. This is my personal take on the whole story: https://gagliardoni.net/#20250714_ludd_grandpas

A relevant quote: "this is your daily reminder that "How large is the biggest number it can factorize" is NOT a good measure of progress in quantum computing. If you're still stuck in this mindset, you'll be up for a rude awakening."

Related: this is from Dan Bernstein: https://blog.cr.yp.to/20250118-flight.html#moon

A relevant quote: "Humans faced with disaster tend to optimistically imagine ways that the disaster will be avoided. Given the reality of more and more user data being encrypted with RSA and ECC, the world will be a better place if every effort to build a quantum computer runs into some insurmountable physical obstacle"

replies(5): >>44609195 #>>44609761 #>>44611286 #>>44611423 #>>44612270 #

1. ethan_smith ◴[19 Jul 25 00:35 UTC] No.44611423[source]▶

>>44609103 #

Shor's algorithm still requires O(log(N)³) qubits and O(log(N)²log(log(N))log(log(log(N)))) operations to factor N, which is why these satirical "records" highlight the absurdity of focusing solely on factorization milestones rather than addressing the exponential scaling challenges.

replies(1): >>44611799 #

2. spr-alex ◴[19 Jul 25 01:45 UTC] No.44611799[source]▶

>>44611423 (TP) #

there's been advances, at least for RSA work from håstad, ekerå, gidney has brought this to O(N) qubits, on the runtime the papers are a little bit harder to read as they differ in notation but O(log(N)^3) runtime is what i recall. its possible i am wrong on the runtime and its O(log(N)^2)

↑