Tag: mathematics

Detailed Briefing: Replicating Quantum Factorisation Records

I. Executive Summary

This paper presents a critical re-evaluation of current quantum factorisation records, arguing that these achievements are largely based on “sleight-of-hand” techniques rather than genuine demonstrations of quantum computing’s power for complex factorisation problems. The authors successfully replicate and, in some cases, exceed these “quantum records” using a 1981 VIC-20 8-bit home computer, an abacus, and even a dog. The core argument is that published quantum factorisations leverage pre-selected numbers or significant classical pre-processing, rendering the “quantum” contribution trivial. The paper concludes by proposing stringent evaluation criteria for future quantum factorisation claims to ensure genuine computational advancement.

II. Main Themes and Key Arguments

1. Quantum Factorisation Records are “Sleight-of-Hand” or “Stunt Factorisations”:

• The central premise is that current quantum factorisation achievements are misleading, akin to “stage magicians perform[ing] sleight-of-hand tricks” using “specially constructed decks called force decks.”
• “Quantum factorisation is performed using sleight-of-hand numbers that have been selected to make them very easy to factorise using a physics experiment and, by extension, a VIC-20, an abacus, and a dog.”
• These numbers are often chosen such that their factors “differ by only a few bits,” allowing factorisation through “a simple search-based approach that has nothing to do with factorisation.” This is exemplified by the RSA-2048 number discussed, whose factors differ by only one or two bits, enabling factorisation via an integer square root calculation.
• A critical observation is that such numbers “would never be encountered in the real world since the RSA key generation process typically requires that |p-q| > 100 or more bits.”
• “Instead of waiting for the hardware to improve by yet further orders of magnitude, researchers began inventing better and better tricks for factoring numbers by exploiting their hidden structure.”
• Another “sleight-of-hand” technique involves “preprocessing on a computer to transform the value being factorised into an entirely different form or even a different problem to solve which is then amenable to being solved via a physics experiment.”
• The “compiled form of Shor’s algorithm,” used for factoring 15 and 21, “uses prior knowledge of the answer to merely verify the (known-in-advance) factors rather than performing any actual factorisation.” The paper quotes criticism that “it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language.”
• Some “quantum factorisations go even further… working backwards from the known answer to design a physis experiment that produced the known-in-advance solution.”
• These are collectively termed “stunt factorisations,” where the “main effort… consisted of finding a value with the special properties required that allowed it to be ‘factorised’ by a physics experiment.”
• The “Smolin-Smith-Vargo Algorithm” is a “tongue-in-cheek name” for a “factorisation mechanism” that can factor “any composite number p × q on a very small physics experiment.”
• “So far as we have been able to determine, no quantum factorisation has ever factorised a value that wasn’t either a carefully-constructed sleight-of-hand number or for which most of the work wasn’t done beforehand with a computer.”

1. Replication with “Vintage” Technology Outperforms Quantum Experiments:

• The paper demonstrates that classical, even antiquated, methods can easily replicate and surpass the purported achievements of quantum factorisation.
• VIC-20 8-bit Home Computer (1981):The authors assert that a 6502 microprocessor (used in the VIC-20) is “as much a quantum device as is a D-Wave ‘quantum computer’” because “transistors work by using quantum effects.” This highlights their redefinition of “physics experiments” for quantum computers to avoid “confusion with actual computers like the VIC-20.”
• The VIC-20 successfully factored 15, 21, and 35 using a simple pre-computed multiplication table.
• For RSA-2048 numbers (which were “specially chosen so that their prime factors p and q are either 2 or 6 apart”), the VIC-20 used an integer square root algorithm (originally for abacus, adapted by von Neumann for EDVAC in 1945).
• This algorithm, exploiting the N = (x-d)(x+d) = x^2 – d^2 relationship, allowed factorisation by checking if N+d^2 (where d is 1 or 3) is a perfect square.
• The VIC-20 factored all ten RSA-2048 moduli from the D-Wave paper in “roughly 16.5 seconds” each, using only 538 bytes for code and 1792 bytes of RAM.
• “We have thus broken, or at least also replicated, all quantum factoring records, and have additionally replicated a 2025 result with 1981 technology using an algorithm for a 1945 computer.”
• Abacus:The abacus trivially factored 15, 21, and 35 using trial multiplication/division.
• The paper notes that the integer square root algorithm used for RSA-2048 on the VIC-20 “was apparently originally created for use with an abacus.”
• While factorising the 616-digit RSA-2048 number on a physical abacus is deemed impractical due to its size, the algorithm itself is abacus-derived.
• Dog:A dog named Scribble was “trained to bark three times” to factor 15 and 21, and “five times” to factor 35, thus “exceeding the capabilities of the quantum factorisation physics experiments mentioned earlier.”
• For RSA-2048 values, the dog “factorisation” is performed by having the dog bark “three times” if N+9 is a perfect square (meaning d=3) or “once” if the remainder from N+9 is 8 (meaning d=1). This leverages the pre-computation and the simplified nature of the “sleight-of-hand” RSA-2048 numbers.
• “Canine-based factorisation technology outperforms current physics-experiment based factorisation technology.”

1. Proposed Quantum Factorisation Evaluation Criteria:

• To address the pervasive “sleight-of-hand numbers and techniques and stunt factorisations,” the authors propose strict evaluation criteria for future quantum factorisation claims:
• Nontrivial Size: Factors should be “64 or 128 bits” to prevent simple search techniques.
• Randomly Distributed Prime Factors: Factors must be “two prime values with a large difference between them and containing a 50:50 mix of 0 and 1 bits, randomly distributed.” This prevents “sleight-of-hand numbers that are readily amenable to factorisation.” This specifically avoids issues like the “Callas Normal Form” where p = 2^n-1 and q = 2^m+1.
• No Preprocessing: “No preprocessing of the value to be factorised using a computer is permitted.” This prevents transforming the problem into an “easily-solved sleight-of-hand problem.”
• Unknown Factors: “The factors are unknown to the experimenters” to prevent “short-circuiting the factorisation process by taking advantage of knowing the answer before the process has even begun.”
• Repeatability: “The factorisation is performed on ten different values” meeting the above criteria to demonstrate repeatability.
• These criteria are designed to “move the problem out of the space in which it is readily solvable using a VIC-20.”
• The authors acknowledge that researchers may “construct more sophisticated sleight-of-hand manipulations” in the future, necessitating updates to these rules.

III. Key Concepts and Definitions

• Shor’s Algorithm: A quantum algorithm for integer factorisation, proposed by Peter Shor in 1994.
• Quantum Factorisation: The act of using quantum computing principles to find the prime factors of a composite number.
• Physics Experiments: The term used by the authors to refer to “quantum computers” to avoid equating them with actual computers, implying they are more akin to scientific apparatus than computational devices.
• Sleight-of-Hand Numbers/Techniques: Numbers or methods specifically chosen or manipulated to make factorisation seem complex when it is, in fact, trivial or pre-determined. Examples include:
• Factors differing by only a few bits (e.g., in the D-Wave RSA-2048 claim).
• Pre-processing the number on a classical computer to transform it into an easier problem.
• Using “compiled form of Shor’s algorithm” which pre-supposes the answer.
• Working backward from a known answer to design an experiment.
• “Stunt factorisations”: deliberately manufacturing values with special properties that simplify factorisation for a physics experiment.
• Numbers consisting almost entirely of zero bits or repeating bit patterns when viewed in binary.
• “Callas Normal Form”: factors are p = 2^n-1 and q = 2^m+1, leading to easily detectable and factorable products.
• RSA-2048: A standard public-key encryption algorithm based on the difficulty of factoring large numbers, typically numbers that are the product of two very large prime numbers. The D-Wave claim of factoring RSA-2048 is specifically targeted and debunked as “sleight-of-hand.”
• VIC-20: An 8-bit home computer released in 1981, used in this paper to demonstrate the triviality of “quantum factorisation records.”
• Abacus: A manual calculating tool, also used to demonstrate the ease of factorising the numbers in question.
• Integer Square Root Algorithm: A classical algorithm for finding the integer part of a square root. The paper highlights its adaptation by John von Neumann from an abacus method.

IV. Important Ideas and Facts

• History of Quantum Factorisation Records:1994: Shor proposes his algorithm.
• 2001: IBM factors 15.
• 2012: Extended to factor 21.
• 2019: Attempted factorisation of 35 (failed).
• 2024: Claim to have factored RSA-2048 (“the D-Wave paper”), which the authors point out has a future publication date (June 2025 at the time of writing, March 2025).
• Nature of “Factorised” Numbers:15 = 3 x 5
• 21 = 3 x 7
• 35 = 5 x 7
• RSA-2048 numbers were specifically chosen such that their prime factors p and q were either 2 or 6 apart, making N = p * q = (x-d)(x+d) = x^2 – d^2, where d is 1 or 3. This reduces factorisation to an integer square root problem.
• Triviality of Current Records: All numbers “factorised” by quantum computers (15, 21, 35) have small factors (less than 16) that are easily found by simple methods. The RSA-2048 “factorisation” is also trivial due to the specific construction of the numbers.
• Computational Resources for Replication:VIC-20: 6502 microprocessor (1975), 1 MHz clock, 3.5 KiB usable RAM. The factorisation code for RSA-2048 was only 538 bytes and used 1792 bytes of RAM. It completed each RSA-2048 factorisation in approximately 16.5 seconds.
• Abacus: Requires only two or three columns for the small numbers (15, 21, 35). A 616-digit abacus for RSA-2048 is physically impractical but the underlying algorithm is classical.
• Dog: A readily available household pet.
• Critique of Quantum Computing Terminology: The authors deliberately use “physics experiments” instead of “quantum computers” for current devices to highlight their perceived limitations and distinguish them from general-purpose computers.
• Ranking of Factorisation Power: “In terms of comparative demonstrated factorisation power, we rank a VIC-20 above an abacus, an abacus above a dog, and a dog above a quantum factorisation physics experiment.”