Comment by svat

The paper by Craig Gidney:

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