Replication of Quantum Factorisation Records with an 8-bit Home Computer [pdf](eprint.iacr.org)
eprint.iacr.org
Replication of Quantum Factorisation Records with an 8-bit Home Computer [pdf]
https://eprint.iacr.org/2025/1237.pdf
33 comments
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.
I really hope he eventually gets the recognition he deserves, outside of just experts in the field.
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."
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."
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.
>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.
Brilliant.
> 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}.
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}.
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.
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.
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.
Thanks. The flawed superscripting was bugging me too. Easily detectable but a reviewer should have caught it before publication.
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).
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?
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?
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.
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).
Or as another example, I'm currently at a conference listening to a PhD student's research on biomolecular structure prediction (for protein design).
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/oco...
Its a device that makes and analyzes at the same time, check out this primer:
https://warwick.ac.uk/fac/sci/chemistry/research/oconnor/oco...
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?
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?
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.
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.
> 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.
It's of interest to governments, for national security reasons. Quantum computing is an arms race.
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.
PQC is as much a tool to reduce funding for QC as it is a tool against an actual eventual quantum computer.
>...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...
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...
> 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?
Forming a conductive channel in silicon in any FET and semiconductivity in general is an inherently quantum effect too, right?
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.
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.
> 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,
I don't think that makes it obvious at all, given that the none of these invented devices actually worked, and the first working MOSFETs weren't until the late 50s after a research program of a few additional decades by a bunch of solid-state physicists at Bell Labs (who did know and develop quantum theories of solids - Shockley, Bardeen, Brattain - not successful in making a FET -Atalla, Kahng, many others)
"Electrons and Holes in Semiconductors" was published almost a decade before any functional MOSFET was constructed.
> 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 sounds like you are describing what's required to parameterize some of the traditional semi-classical models of MOSFETs and understand the operating principles at that level.
but FETs work by bending the energy levels of the conduction band so there needs to be a band to bend, and if there's no band gap at the fermi level you can't have a FET, which makes it seem pretty dependent on quantum effects to me even without going deeper than necessary to understand how it can work.
Maybe one could have been engineered with no idea why silicon has the special material properties that it does and why doping changes those properties but AFAIK it never was, and being able to explain and understand band structure seems pretty important to build a working device.
I don't think that makes it obvious at all, given that the none of these invented devices actually worked, and the first working MOSFETs weren't until the late 50s after a research program of a few additional decades by a bunch of solid-state physicists at Bell Labs (who did know and develop quantum theories of solids - Shockley, Bardeen, Brattain - not successful in making a FET -Atalla, Kahng, many others)
"Electrons and Holes in Semiconductors" was published almost a decade before any functional MOSFET was constructed.
> 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 sounds like you are describing what's required to parameterize some of the traditional semi-classical models of MOSFETs and understand the operating principles at that level.
but FETs work by bending the energy levels of the conduction band so there needs to be a band to bend, and if there's no band gap at the fermi level you can't have a FET, which makes it seem pretty dependent on quantum effects to me even without going deeper than necessary to understand how it can work.
Maybe one could have been engineered with no idea why silicon has the special material properties that it does and why doping changes those properties but AFAIK it never was, and being able to explain and understand band structure seems pretty important to build a working device.
The transistors described in the patents, i.e. MESFETs and depletion-mode MOSFETs were perfectly functional as described.
However, before WW2 one could have made such transistors that worked only by great luck, and they would have stopped working soon after that.
The reason is that before WWII it was not understood how greatly the properties of a semiconductor device are influenced by impurities and crystal defects.
During WWII there was a great effort to make semiconductor diodes for the high frequencies needed by radars, where vacuum diodes were no longer usable.
This has led to the development of semiconductor purification technologies and crystal growing technologies far more sophisticated than anything attempted before. Those technologies provided high-purity almost perfect germanium and silicon crystals, which enabled for the first time the manufacturing of semiconductor devices that worked as predicted by theory.
The publication of Shockley's theory has been necessary for the understanding of the devices based on carrier injection and P-N junctions, like the BJT and the JFET invented by Shockley.
However you can do very well electronics using only devices that are simpler conceptually, e.g. depletion-mode MOSFETs, Schottky diodes and MESFETs, for whose understanding Shockley's theory is not necessary, which is why they were reasonably well understood before WWII.
Before WWII the problem was not with the theory of the devices, but with the theory of the semiconductor material itself, because a semiconductor material would match the theory only if it were defect-free, and no such materials were available before WWII.
Before having such crystals, making semiconductor devices was non-reproducible, you could never make two that behaved the same.
"FETs work by bending the energy levels of the conduction band" is something used in textbooks, together with some intuitive graphs, with the hope that this is more intelligible for students.
I do not think that it is a useful metaphor. In any case this is not how you compute a MOSFET. For that you use carrier generation rates, carrier recombination rates, carrier flow and accumulation equations.
Instead of mumbo-jumbo about "band bending", it is much simpler to understand that a MOSFET is controlled by the electric charge that is stored on the metal side of the oxide insulator. That charge must be neutralized by an identical amount of charge of opposite sign on the semiconductor side of the gate. Depending on the sign and magnitude of that electric charge, it will be obtained by various combinations between the electric charges of electrons, holes and ionized impurities, which are determined by a balance between generation and recombination of electron-hole pairs and transport of electrons and holes to/from adjacent regions.
All the constraints lead to a unique solution for the concentrations of holes and electrons on the semiconductor side of the gate, which may be higher or lower than when there is no charge on the gate, and which may have the same sign or an opposite sign in comparison with the case when there is no net charge on the gate. This change in the carrier concentrations can be expressed as a "band bending", but this, i.e. the use of some fictitious potentials, does not provide any advantage instead of always thinking in carrier concentrations. (The use of some fictitious potentials instead of carrier concentrations had a small advantage in computations done with pen and paper, but they have no advantage when a computer is used. The so-called "Fermi level" is not needed anywhere, it just corresponds to the rate of thermal generation of electron-hole pairs, which is what is needed.)
However, before WW2 one could have made such transistors that worked only by great luck, and they would have stopped working soon after that.
The reason is that before WWII it was not understood how greatly the properties of a semiconductor device are influenced by impurities and crystal defects.
During WWII there was a great effort to make semiconductor diodes for the high frequencies needed by radars, where vacuum diodes were no longer usable.
This has led to the development of semiconductor purification technologies and crystal growing technologies far more sophisticated than anything attempted before. Those technologies provided high-purity almost perfect germanium and silicon crystals, which enabled for the first time the manufacturing of semiconductor devices that worked as predicted by theory.
The publication of Shockley's theory has been necessary for the understanding of the devices based on carrier injection and P-N junctions, like the BJT and the JFET invented by Shockley.
However you can do very well electronics using only devices that are simpler conceptually, e.g. depletion-mode MOSFETs, Schottky diodes and MESFETs, for whose understanding Shockley's theory is not necessary, which is why they were reasonably well understood before WWII.
Before WWII the problem was not with the theory of the devices, but with the theory of the semiconductor material itself, because a semiconductor material would match the theory only if it were defect-free, and no such materials were available before WWII.
Before having such crystals, making semiconductor devices was non-reproducible, you could never make two that behaved the same.
"FETs work by bending the energy levels of the conduction band" is something used in textbooks, together with some intuitive graphs, with the hope that this is more intelligible for students.
I do not think that it is a useful metaphor. In any case this is not how you compute a MOSFET. For that you use carrier generation rates, carrier recombination rates, carrier flow and accumulation equations.
Instead of mumbo-jumbo about "band bending", it is much simpler to understand that a MOSFET is controlled by the electric charge that is stored on the metal side of the oxide insulator. That charge must be neutralized by an identical amount of charge of opposite sign on the semiconductor side of the gate. Depending on the sign and magnitude of that electric charge, it will be obtained by various combinations between the electric charges of electrons, holes and ionized impurities, which are determined by a balance between generation and recombination of electron-hole pairs and transport of electrons and holes to/from adjacent regions.
All the constraints lead to a unique solution for the concentrations of holes and electrons on the semiconductor side of the gate, which may be higher or lower than when there is no charge on the gate, and which may have the same sign or an opposite sign in comparison with the case when there is no net charge on the gate. This change in the carrier concentrations can be expressed as a "band bending", but this, i.e. the use of some fictitious potentials, does not provide any advantage instead of always thinking in carrier concentrations. (The use of some fictitious potentials instead of carrier concentrations had a small advantage in computations done with pen and paper, but they have no advantage when a computer is used. The so-called "Fermi level" is not needed anywhere, it just corresponds to the rate of thermal generation of electron-hole pairs, which is what is needed.)
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.
So only a quantum effect to the extent all effects are at some level quantum.
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".
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.
The dog is funny but it just means, pick actually "random" numbers from a bigger range than the staged phony numbers quantum factorisation uses.
This is probably one of the first academic papers I've ever read completely from beginning to end in one go.
This paper is both a hilarious parody and a genuinely valuable contribution to the literature.
(Beware of typo pointed out by tromp here.)
(Beware of typo pointed out by tromp here.)
[deleted]
> 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