Replication of Quantum Factorisation Records with an 8-bit Home Computer [pdf]

https://eprint.iacr.org/2025/1237.pdf

by sebgan • 1 year ago

137 32 1 year ago

eprint.iacr.org

fcpguru• 1 year ago

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• 1 year ago

This is probably one of the first academic papers I've ever read completely from beginning to end in one go.

wasabi9910114• 1 year ago

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• 1 year ago

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• 1 year ago

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.

wasabi9910114• 1 year ago

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).

upofadown3• 1 year ago

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.

qualeed• 1 year ago

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• 1 year ago

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• 1 year ago

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• 1 year ago

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.

KingFelix• 1 year ago

Just read this as well, best footnote I've read all day

tromp• 1 year ago

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}.

adgjlsfhk12• 1 year ago

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.

dreamcompiler3• 1 year ago

Thanks. The flawed superscripting was bugging me too. Easily detectable but a reviewer should have caught it before publication.

earleybird• 1 year ago

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.

adgjlsfhk12• 1 year ago

I have some ethical concerns here. footnote 6 clearly states that Scribble did not do enough work to merit coauthor credit, but if he was one of the primary researches for section 5 of the paper and was responsible for typesetting the entire paper, denying such a good boy sufficient credit for his work is a serious breach of scientific standards.

Arcorann• 1 year ago

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

wasabi9910114• 1 year ago

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.

upofadown3• 1 year ago

...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• 1 year ago

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".

rnrn2• 1 year ago

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?

upofadown3• 1 year ago

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.

adrian_b2• 1 year ago

If you go deep enough in the details, everything is a "quantum effect".

However, in order to design and simulate a MOS transistor and most of the other semiconductor devices you do not need to use any quantum physics.

This should be made obvious by the fact that both the metal-semiconductor transistor (i.e. MESFET, patent filed on 1925-10-22) and the depletion-mode metal-insulator-semiconductor transistor (i.e. depletion-mode MOSFET, patent filed on 1928-03-28) have been invented at a time when quantum theory was just nascent, not yet applicable to semiconductors and certainly unknown to the inventor (Julius Edgar Lilienfeld; despite the fact that the FET operating principles were obvious, the know-how for making reproducible semiconductor devices has been acquired only during WWII, as a consequence of the development of diode detectors for radars, which generated the stream of inventions of semiconductor devices after the war ended).

For designing MOSFETs, you just need to use classical electrodynamics, together with several functions that provide the semiconductor material characteristics, like intrinsic free carrier concentration as a function of temperature, carrier mobilities as functions of temperature and impurity concentrations (and electric field at high fields), ionization probabilities for impurities, avalanche ionization coefficients, dielectric constants, and a few others.

It would be nice if instead of measuring experimentally all the characteristic functions for a semiconductor material one could compute them using quantum theory, but that is currently not possible.

So for semiconductor device design, quantum physics is mostly hidden inside empirically determined functions. Only few kinds of devices, e.g. semiconductor lasers, may need the use of some formulas taken from quantum physics, e.g. from quantum statistics, but even for them most of their mathematical model is based on classical physics.

dreamcompiler3• 1 year ago

This paper is both a hilarious parody and a genuinely valuable contribution to the literature.

(Beware of typo pointed out by tromp here.)

Replication of Quantum Factorisation Records with an 8-bit Home Computer [pdf]

Related Stories