5 ms·

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

84 points by teddyh 1y ago

rahimnathwani 1y ago
Previous: https://news.ycombinator.com/item?id=44538693 https://news.ycombinator.com/item?id=44538693
cbm-vic-20 1y ago
> We verified this by taking a recently-calibrated reference dog, Scribble, depicted in Figure 6, and having him bark three times, thus simultaneously factorising both 15 and 21. This process wasn’t as simple as it first appeared because Scribble is very well behaved and almost never barks.
- trhway 1y ago
  one can always press the door bell button - works like a charm with my Chihuahua. Though he prefers to factorize numbers more like 529 than 21.
tomgag 1y ago
I guess I'll post it here as well. This is my personal take on the whole story: https://gagliardoni.net/#20250714_ludd_grandpas 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 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"
- jgeada 1y ago
  Except that factorization is exactly what is needed to break encryption, and so knowing what QC can do in that realm of mathematics and computing is exactly the critical question that needs to be asked. And a reminder that in the world of non-QC computing, right from its very roots, the ability of computers improved in mind boggling large steps every year. QC records, other than the odd statistic about how many bits they can make, have largely not made any strides in being able to solve real world sized problems (with exception of those that use QCs purely as an analog computer to model QC behavior)
  - tomgag 1y ago
    I beg you to read the full story and to not extrapolate from the quote. Also, in the world of QC, right from its very roots, the ability of QC improved in mind boggling large steps every year. It's only that you cannot see it if you only look at the wrong metric, i.e., factorization records. It's a bit like saying "classical computing technology has not improved for 50 years, it's only recently that we finally start to have programs that are able to write other programs".
    - madars 1y ago
      A great resource for visually seeing progress is https://sam-jaques.appspot.com/quantum_landscape https://sam-jaques.appspot.com/quantum_landscape (click "Prev"/"Next" to see other years) - it makes very clear that incredible progress is happening - this is a log-log plot.
    - jgeada 1y ago
      There is a reason QC factorization records haven't shifted much over the past years. Number of qubits by themselves isn't enough. You to be able to do computation on them and for long enough to run Shor's algorithm till it produces a solution. How the qubits are connected, how reliable the logic gates are and how long you can maintain the quantum coherence with enough fidelity to get results is equally important. That no significant factorization milestones have moved is a huge critical black eye to this field. Even worse, that no one has ever even been able to truly run Schors algorithm on even trivial numbers is a shocking indictment of the whole field.
- kevinventullo 1y ago
  A better measure of progress (valid for cryptanalysis, which is, anyway, a very minor aspect of why QC are interesting IMHO) would be: how far are we from fully error-corrected and interconnected qubits? I don't know the answer, or at least I don't want to give estimates here. But I know that in the last 10 or more years, all objective indicators in progress that point to that cliff have been steadily improving: qubit fidelity, error rate, coherence time, interconnections... At this point I don't think it's wise to keep thrashing the field of quantum security as "academic paper churning". I think the problem is that “objective indicators pointing to the cliff” is pretty handwavy. Could there be a widely agreed-upon function of qubit fidelity, error rate, coherence time, and interconnections that measures, even coarsely, how far we are from the cliff? It seems like the cliff has been ten years away for a very long time, so you might forgive an outsider for believing there has been a lot of motion without progress.
  - wasabi991011 1y ago
    > Could there be a widely agreed-upon function of qubit fidelity, error rate, coherence time, and interconnections that measures, even coarsely, how far we are from the cliff? They've tried (like "Quantum Volume"), but it's really hard to summarize an entirely new computing paradigm into a single number, especially since different hardware platforms will make wildly different tradeoffs.
- theuirvhhjj588 1y ago
  That's a cop out. I agree with what you're saying, but what you're also essentially saying is that QCs are so useless at the moment that the granularity of integers is not enough to measure progress on the hardware.
- ethan_smith 1y ago
  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.
  - spr-alex 1y ago
    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)
- adgjlsfhk1 1y ago
  The thing that still feels off to me is that you should be able to run 8 bit Shors algorithm without error correction, right? Sure we don't have reliable error corrected q-bits, but being able to factor a number that small should be possible (even if it had a fairly high error rate) with current computers. Sure it won't be 100% reliable, but if we had published results that in 2010 it got the right answer 10% of the time, and in 2025 it gets the answer write 25% of the time, that would at least be a measure of progress.
hagbard_c 1y ago
After having read this paper I'm busy working on the replication of String Theory with a plate of Spaghetti, a packet of instant Ramen noodles and a pair of Octopuses. I would have used a single octopus but those 8 arms don't cover the 12 dimensions in String Theory. Technically a single squid might suffice - it has 8 arms, 2 tentacles and 2 fins which makes 12 - but that wouldn't be fair to the dimensions which get stuck with the fins while others get to walk away with those tentacles.
OhMeadhbh 1y ago
Ha! Peter Gutmann is always fun.
spr-alex 1y ago
on a related note the search space for https://www.qdayprize.org/curves https://www.qdayprize.org/curves seems far too small to be a meaningful contest and the rules dont seem to address how they judge the validity of the "quantumness" when sifting such small groups.
mycall 1y ago
Call me crazy but I love this. Thanks teddyh.
brontitall 1y ago
I think there’s a bug in Figure 3. The unsigned m will always be >= 0 so the while loop will not terminate.

84 points by teddyh 1y ago

Previous: https://news.ycombinator.com/item?id=44538693 https://news.ycombinator.com/item?id=44538693

> We verified this by taking a recently-calibrated reference dog, Scribble, depicted in Figure 6, and having him bark three times, thus simultaneously factorising both 15 and 21. This process wasn’t as simple as it first appeared because Scribble is very well behaved and almost never barks.

trhway 1y ago
one can always press the door bell button - works like a charm with my Chihuahua. Though he prefers to factorize numbers more like 529 than 21.

tomgag 1y ago

I guess I'll post it here as well. This is my personal take on the whole story: https://gagliardoni.net/#20250714_ludd_grandpas 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 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"

jgeada 1y ago
Except that factorization is exactly what is needed to break encryption, and so knowing what QC can do in that realm of mathematics and computing is exactly the critical question that needs to be asked. And a reminder that in the world of non-QC computing, right from its very roots, the ability of computers improved in mind boggling large steps every year. QC records, other than the odd statistic about how many bits they can make, have largely not made any strides in being able to solve real world sized problems (with exception of those that use QCs purely as an analog computer to model QC behavior)
- tomgag 1y ago
  I beg you to read the full story and to not extrapolate from the quote. Also, in the world of QC, right from its very roots, the ability of QC improved in mind boggling large steps every year. It's only that you cannot see it if you only look at the wrong metric, i.e., factorization records. It's a bit like saying "classical computing technology has not improved for 50 years, it's only recently that we finally start to have programs that are able to write other programs".
  - madars 1y ago
    A great resource for visually seeing progress is https://sam-jaques.appspot.com/quantum_landscape https://sam-jaques.appspot.com/quantum_landscape (click "Prev"/"Next" to see other years) - it makes very clear that incredible progress is happening - this is a log-log plot.
  - jgeada 1y ago
    There is a reason QC factorization records haven't shifted much over the past years. Number of qubits by themselves isn't enough. You to be able to do computation on them and for long enough to run Shor's algorithm till it produces a solution. How the qubits are connected, how reliable the logic gates are and how long you can maintain the quantum coherence with enough fidelity to get results is equally important. That no significant factorization milestones have moved is a huge critical black eye to this field. Even worse, that no one has ever even been able to truly run Schors algorithm on even trivial numbers is a shocking indictment of the whole field.
kevinventullo 1y ago
A better measure of progress (valid for cryptanalysis, which is, anyway, a very minor aspect of why QC are interesting IMHO) would be: how far are we from fully error-corrected and interconnected qubits? I don't know the answer, or at least I don't want to give estimates here. But I know that in the last 10 or more years, all objective indicators in progress that point to that cliff have been steadily improving: qubit fidelity, error rate, coherence time, interconnections... At this point I don't think it's wise to keep thrashing the field of quantum security as "academic paper churning". I think the problem is that “objective indicators pointing to the cliff” is pretty handwavy. Could there be a widely agreed-upon function of qubit fidelity, error rate, coherence time, and interconnections that measures, even coarsely, how far we are from the cliff? It seems like the cliff has been ten years away for a very long time, so you might forgive an outsider for believing there has been a lot of motion without progress.
- wasabi991011 1y ago
  > Could there be a widely agreed-upon function of qubit fidelity, error rate, coherence time, and interconnections that measures, even coarsely, how far we are from the cliff? They've tried (like "Quantum Volume"), but it's really hard to summarize an entirely new computing paradigm into a single number, especially since different hardware platforms will make wildly different tradeoffs.
theuirvhhjj588 1y ago
That's a cop out. I agree with what you're saying, but what you're also essentially saying is that QCs are so useless at the moment that the granularity of integers is not enough to measure progress on the hardware.
ethan_smith 1y ago
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.
- spr-alex 1y ago
  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)
adgjlsfhk1 1y ago
The thing that still feels off to me is that you should be able to run 8 bit Shors algorithm without error correction, right? Sure we don't have reliable error corrected q-bits, but being able to factor a number that small should be possible (even if it had a fairly high error rate) with current computers. Sure it won't be 100% reliable, but if we had published results that in 2010 it got the right answer 10% of the time, and in 2025 it gets the answer write 25% of the time, that would at least be a measure of progress.

hagbard_c 1y ago

After having read this paper I'm busy working on the replication of String Theory with a plate of Spaghetti, a packet of instant Ramen noodles and a pair of Octopuses. I would have used a single octopus but those 8 arms don't cover the 12 dimensions in String Theory. Technically a single squid might suffice - it has 8 arms, 2 tentacles and 2 fins which makes 12 - but that wouldn't be fair to the dimensions which get stuck with the fins while others get to walk away with those tentacles.

OhMeadhbh 1y ago

Ha! Peter Gutmann is always fun.

spr-alex 1y ago

on a related note the search space for https://www.qdayprize.org/curves https://www.qdayprize.org/curves seems far too small to be a meaningful contest and the rules dont seem to address how they judge the validity of the "quantumness" when sifting such small groups.

mycall 1y ago

Call me crazy but I love this. Thanks teddyh.

brontitall 1y ago

I think there’s a bug in Figure 3. The unsigned m will always be >= 0 so the while loop will not terminate.