Sigbovik Conference Proceedings 2025 [pdf]

> Falling with Style: Factoring up to 255 “with” a Quantum Computer

is brilliant in a straightforward way, and I also learned something about Shor's algorithm. The first paragraph of intro and the abstract say:

> Historically, most papers that claimed they “ran Shor’s algorithm” didn’t run Shor’s algorithm. It’s unfortunately common to run circuits inspired by Shor’s algorithm, but with key pieces replaced by trivial pieces.

> In this paper, I explain how I factored all numbers up to 255 using Shor’s algorithm on a real quantum computer. I performed exactly the classical preprocessing specified by Shor’s algorithm, exactly the quantum circuit requested by Shor’s algorithm, and exactly the post-processing specified by Shor’s algorithm.

and this is true! He used IBM's quantum service (https://quantum.ibm.com/services/resources?tab=systems) with:

> my circuit for factoring 15 weighs in at 44405 two-qubit gates. And my circuit for factoring 253 weighs in at 245750 two-qubit gates. Amazingly, despite the fact that they vastly exceed the allowed size, the system accepted these ridiculous circuits.

What's the catch? Well, it's that:

> I’ll quickly review the classical and quantum steps of Shor’s algorithm. Before talking to a quantum computer, Shor’s algorithm performs some classical preprocessing. First, it checks if n (the number to factor) is even, because even numbers would cause trouble later. If so, it succeeds by returning the factor 2. Second, it checks if n is prime. Prime numbers can’t be factored, so in this case the method returns an error saying no factor exists. Third, the algorithm picks a random number g between 2 and n − 2, and computes the greatest common divisor (gcd) of g and n. If gcd(g, n) ≠ 1, then it happens to be a factor of n and so is returned as the result. Fourth, it’s finally time to actually use the quantum computer (whether it be real, simulated, or replaced by a random number generator). This is the expensive step, and the step that I’m counting in order to compare the different samplers. A quantum circuit based on g and n is generated, and executed, producing a sample m. Fifth, Shor’s algorithm classically computes the fraction that’s closest to m/4^{⌈log_2(n)⌉}, limiting the fraction’s denominator d to be at most n. Sixth, a candidate factor is generated by computing gcd(n, 1 + g^{⌊d/2⌋} mod n). If the candidate is actually a factor of n, it’s returned as the answer. Otherwise the algorithm restarts.

because of which:

> In other words, for small numbers, Shor’s algorithm succeeds quickly regardless of how well your quantum computer works.

It also cites a serious 2013 paper in Nature that made the same point: Oversimplifying quantum factoring, DOI 10.1038/nature12290.

Note the 2013 paper wasn't making the same point. They weren't pointing out that Shor's algorithm succeeds quickly regardless of how well the quantum computer works when factoring small numbers. They proved the period-matching "precompilation" tricks experimentalists were doing at the time weren't okay, because those tricks could turn any factoring problem into a trivial two qubit circuit (and were equivalent to knowing the factors).