[HN Gopher] Replication of Quantum Factorisation Records with an...
___________________________________________________________________
Replication of Quantum Factorisation Records with an 8-bit Home
Computer [pdf]
Author : sebgan
Score : 128 points
Date : 2025-07-12 02:05 UTC (20 hours ago)
(HTM) web link (eprint.iacr.org)
(TXT) w3m dump (eprint.iacr.org)
| fcpguru wrote:
| this was great. I had no idea quantum factorisation was cooking
| their books!
|
| The dog is funny but it just means, pick actually "random"
| numbers from a bigger range than the staged phony numbers quantum
| factorisation uses.
| neuroelectron wrote:
| This is probably one of the first academic papers I've ever read
| completely from beginning to end in one go.
| wasabi991011 wrote:
| Yeah there's a reason that the quantum computing field has moved
| away from attempting factorisations. Not that there's not still
| hype and misleading claims being punished, but the hardware has
| improved a ton since 2001 and ever closer to actual useful
| quantum computation (such as large size quantum chemistry
| calculations).
| thrance wrote:
| Are those useful computations in the room with us right now?
| No, but seriously, I feel like factorization is the one
| application that could justify those massive investments QC is
| receiving (even though it would probably make the world
| strictly worse...).
|
| All those other applications, no matter how neat, I feel are
| quite niche. Like, "simulate pairs of electrons in the Ising
| model". Cool. Is that a multi-billion dollars industry though?
| rgbforge wrote:
| If results from methods with higher electronic structure
| accuracy than DFT (MP2, couple cluster) can be made cheap
| enough, it would hugely disrupt industrial chemistry, medical
| experimentation, pharmaceuticals, the energy sector, etc.
| wasabi991011 wrote:
| Ground state and activation energy estimation for chemistry
| would be really useful. I know chemists are looking
| specifically at nitrogen fixation as one useful example.
|
| Or as another example, I'm currently at a conference
| listening to a PhD student's research on biomolecular
| structure prediction (for protein design).
| DoctorOetker wrote:
| Energy levels and activation energies can be acquired much
| more simply from Fourier Transform - Ion Cyclotron
| Resonance - Mass Spectroscopy...
|
| Its a device that _makes_ and _analyzes_ at the same time,
| check out this primer:
|
| https://warwick.ac.uk/fac/sci/chemistry/research/oconnor/oc
| o...
| wasabi991011 wrote:
| Cool stuff and thanks for the link, I'll have to learn
| about it when I have a bit more time.
|
| I've always heard Qalgs for chemistry compared to
| classical methods though. Why do you think chemists are
| using CCSD and similar methods rather than the FT-ICR
| mass spectroscopy?
| dreamcompiler wrote:
| One of the few _genuinely useful_ accomplishments of modern
| "AI" has been protein structure prediction. I wonder if we
| still even need QC for this.
| upofadown wrote:
| Factorization could have number theory implications I
| suppose. Using quantum effects to break cryptography wouldn't
| have any real long term advantages unless you aspired to be
| some sort of a supervillain.
| LeftHandPath wrote:
| > Using quantum effects to break cryptography wouldn't have
| any real long term advantages unless you aspired to be some
| sort of a supervillain.
|
| It's of interest to governments, for national security
| reasons. Quantum computing is an arms race.
| pclmulqdq wrote:
| If you want O($10 billion per year) of funding, those
| numbers can only come from having $10 billion a year of
| impact balanced against your chance of success. The only
| application of QC worth $100+ billion is breaking
| cryptography.
|
| PQC is as much a tool to reduce funding for QC as it is a
| tool against an actual eventual quantum computer.
| qualeed wrote:
| I remember Peter Gutmann posting about this on the metzdowd
| cryptography mailing list in March. Fun to see this a few months
| later.
|
| It starts here:
| https://www.metzdowd.com/pipermail/cryptography/2025-Februar...
|
| This part is from farther down thread:
|
| _" Just as a thought experiment, what's the most gutless device
| that could perform this "factorisation"? There's an isqrt()
| implementation that uses three temporaries so you could possibly
| do the square root part on a ZX81, but with 1k of RAM I don't
| think you can do the verification of the guess unless you can
| maybe swap the values out to tape and load new code for the
| multiply part. A VIC20 with 4k RAM should be able to do it... is
| there a programmable calculator that does arbitrary-precision
| maths? A quick google just turns up a lot of apps that do it but
| not much on physical devices.
|
| Peter._"
| remcob wrote:
| You can verify in limited memory by repeatedly verifying modulo
| a few small integers. If that works, then by Chinese remainder
| theorem the main result also holds.
| jojobas wrote:
| >We use the UK form "factorise" here in place of the US variants
| "factorize" or "factor" in order to avoid the 40% tariff on the
| US term
|
| Brilliant.
| jfyi wrote:
| Yeah, they are really on point...
|
| >Similarly, we refer to an abacus as "an abacus" rather than a
| digital computer, despite the fact that it relies on digital
| manipulation to effect its computations.
| tromp wrote:
| > In the Callas Normal Form, the factors are integers p = 2^{n-1}
| and q = 2^{m+1}, where n <= m, and p and q are ideally prime, but
| don't have to be.
|
| The paper's formatting clearly went wrong here, as it should have
| read p = 2^n - 1 and q = 2^m + 1.
|
| The "Proposed Quantum Factorisation Evaluation Criteria" are
| excellent, but for measuring progress, the required minimum
| factor size of 64 bits is too large. A good milestone would be a
| quantum circuit that can factor the product of any pair of 5-bit
| primes {17,19,23,29,31}.
| adgjlsfhk1 wrote:
| I think 8 bit primes is probably a better minimum. 5 bits is
| still small enough that randomly choosing a 5 bit factor will
| succeed 40% of the time. This is especially problematic since
| Shor's algorithm only has a 50% success probability per round,
| so you need some extra bits to be able to distinguish a
| correctly working quantum computer from a random number
| generator.
| dreamcompiler wrote:
| Thanks. The flawed superscripting was bugging me too. Easily
| detectable but a reviewer should have caught it before
| publication.
| earleybird wrote:
| I checked in with Scribble as he did the typesetting. He
| apologizes for the error but says working without opposable
| thumbs makes the work more challenging.
| Arcorann wrote:
| Somewhat related is the work done in "Falling with Style:
| Factoring up to 255 "with" a Quantum Computer" published in the
| proceedings of SIGBOVIK 2025 [1]. The author, Craig Gidney [2],
| successfully factored all odd composite numbers up to 255 using
| Shor's algorithm, even though the quantum circuits involved were
| such that any meaningful output would be overwhelmed by noise
| (and indeed, performance was maintained when the circuits were
| replaced by a random number generator).
|
| > To my knowledge, no one has cheated at factoring in this way
| before. Given the shenanigans pulled by past factoring
| experiments, that's remarkable.
|
| [1] https://sigbovik.org/2025/; standalone paper is also
| available in the code repository
| https://github.com/strilanc/falling-with-style
|
| [2] Who has previous experience in cheating at quantum factoring:
| see "Factoring the largest number ever with a quantum computer",
| posted April Fools' Day 2020 at https://algassert.com/post/2000
| wasabi991011 wrote:
| God, I've heard Gidney's name so many times in the QC
| conference I'm attending, and in my research the last few
| months.
|
| I really hope he eventually gets the recognition he deserves,
| outside of just experts in the field.
| upofadown wrote:
| >...6502 microprocessor from 1975. Since this processor uses
| transistors, and transistors work by using quantum effects, a
| 6502 is as much a quantum device as is a D-Wave "quantum
| computer".
|
| I'm not sure that is true in the way it is intended. The NMOS
| transistors used in the 6502 were quite large and worked on the
| basis of electrostatic charges ... as opposed to bipolar
| transistors that are inherently quantum in operation.
|
| Of course it is now understood that _everything_ that does
| _anything_ is at some level dependent on quantum effects. That
| would include the dog...
| jfengel wrote:
| The intention is to say that the D-Wave isn't a quantum
| computer at all. The comparison isn't quite literally true, but
| it's definitely the case that what D-Wave does is very
| different from the general purpose qubits that we mean when we
| say "quantum computer".
| rnrn wrote:
| > The NMOS transistors used in the 6502 were quite large and
| worked on the basis of electrostatic charges ... as opposed to
| bipolar transistors that are inherently quantum in operation
|
| Forming a conductive channel in silicon in any FET and
| semiconductivity in general is an inherently quantum effect
| too, right?
| upofadown wrote:
| Traditionally I don't think it was considered to be specially
| a quantum effect. That, again was because bipolar transistors
| specifically work over a quantum band gap ... and bipolar
| transistors proceeded mosfets.
|
| So only a quantum effect to the extent all effects are at
| some level quantum.
| dreamcompiler wrote:
| This paper is both a hilarious parody _and_ a genuinely valuable
| contribution to the literature.
|
| (Beware of typo pointed out by tromp here.)
___________________________________________________________________
(page generated 2025-07-12 23:01 UTC)