Practical implementation of Shor and other factoring algorithms

Question

I explore the realm of open-source quantum computers, particularly those available in the current or near-term future. My goal is to implement the largest possible integer factorizations. I would greatly appreciate, if you could provide clarification on the following inquiry:

What is the largest integer successfully factored using a real quantum computer, across different methods? Say Shor algorithm or quantum annealing based ones. I am particularly interested in identifying the best implementation for various methods. If possible, kindly share relevant papers references.

Answer 1

I would say that it is not possible to give a proper answer to this question since the problem instances that may potentially be tractable by present-day quantum computers are too small:

• As explained in [E24], see in particular Lemma 4.3, and [Knill95] (reference [20] in [E24]), it is possible to decrease the control register length by some $\Delta$ qubits below what Shor originally proposed whilst still being able to solve successfully in the classical post-processing by performing a limited search.

  Here, $\Delta$ is a constant, but for small orders $r$ we can select $\Delta$ sufficiently large so as to cut down the control register length to the point where there is almost no constructive interference, and nothing interesting happens, in the quantum algorithm. This without comprimising the practicality of the limited search in the post-processing.

• For the small problem instances that may be tractable by present-day quantum computers, the post-processing in [E24] and [E21b] (or a slightly modified version thereof) can find the order $r$, and then factor $N$ completely via $r$, more or less irrespectively of which frequency $j$ that you throw at it — except possibly for $j = 0$ (without modifications). This because small problem instances that may potentially be tractable by present-day quantum computers are also classically tractable.

A more relevant question to ask from my perspective is hence to what extent you can make present-day quantum computers approximate the distribution induced by e.g. Shor's order-finding algorithm [Shor94] [Shor97] for a given set of parameters. Not whether the computer can factor given small integers.

A further comment is that it is of little interest to consider algorithms that do not scale.