# Expected repetitions of the quantum part of Shor's algorithm

Shor's algorithm to factor a number $$N$$ goes as follows:

1. Pick a random value $$b \in (0, N)$$.
2. Use a specific quantum computation to a sample a value $$v$$ that should be close to $$2^{m} k/p$$ where $$m$$ is a precision parameter of the quantum computation, $$p$$ is the period of $$f(x) = b^x \pmod{N}$$, and $$k$$ is an unknown integer resulting from the sampling process.
3. Convert $$v$$ into a potential period $$p$$ using an algorithm based on continued fractions.
4. If $$b^p \neq 1 \pmod{N}$$, goto 1. The period finding process failed (e.g. maybe you got $$v=0$$).
5. If $$p$$ is odd, goto 1. You got a useless period. Try a different $$b$$.
6. If $$b^{p/2} \equiv -1 \pmod{N}$$, goto 1. You got a useless period. Try a different $$b$$.
7. Output $$\gcd(b^{p/2} - 1, N)$$

My question is: how often do steps 4, 5, or 6 fail? Assuming an ideal quantum computer with no error, how often do you just get unlucky and pick a bad $$b$$ or sample a bad $$v$$? How many times do you expect to repeat step 2 before the factoring succeeds?

References giving numerical upper bounds on the 4-5-6 failure chance would be especially appreciated.

The number of runs required is arbitrarily close to 1, using the correct post-processing. See "On the success probability of quantum order finding" by Martin Ekerå from Jan 2022:

We prove a lower bound on the probability of Shor's order-finding algorithm successfully recovering the order r in a single run. The bound implies that by performing two limited searches in the classical post-processing part of the algorithm, a high success probability can be guaranteed, for any r, without re-running the quantum part or increasing the exponent length compared to Shor. Asymptotically, in the limit as r tends to infinity, the probability of successfully recovering r in a single run tends to one. Already for moderate r, a high success probability exceeding e.g. $$1-10^4$$ can be guaranteed. As corollaries, we prove analogous results for the probability of completely factoring any integer N in a single run of the order-finding algorithm.

This self-answer gives a not-very-good worst case analysis. I'd really rather have a proper distribution of repetition counts.

Probability of a period resulting in factoring

In Shor's original paper, you can find the following statement:

The multiplicative group (mod $$p^α$$) for any odd prime power $$p^α$$ is cyclic [Knuth 1981], so for any odd prime power $$p_i^{a_i}$$, the probability is at most 1/2 of choosing an $$x_i$$ having any particular power of two as the largest divisor of its order $$r_i$$. Thus each of these powers of 2 has at most a 50% probability of agreeing with the previous ones, so all k of them agree with probability at most $$1/2^{k−1}$$, and there is at least a $$1 - 1/2^{k-1}$$ chance that the $$x$$ we choose is good. This scheme will thus work as long as $$n$$ is odd and not a prime power; finding factors of prime powers can be done efficiently with classical methods

(Oddly, I also found an older version of the paper with a bound of $$1-2^{-k}$$ instead of $$1-2^{1-k}$$. Might be an error that was corrected?)

This implies a 50% chance of success of getting a good period (steps 4+5), since all numbers have at least two distinct factors or else can be factored classically.

Probability of a sample determining a period

For getting a good sample (step 3), Shor gives a more complicated bound. If you sample a value with a $$k$$ that's not relatively prime to the period, the period you recover will be wrong. But integers have a limited number of divisors, and Shor cites a bound:

There are also $$r$$ possible values for $$x^k$$, since $$r$$ is the order of $$x$$. Thus, there are $$r \phi(r)$$ states which would enable us to obtain $$r$$. Since each of these states occurs with probability at least $$\frac{1}{3r^2}$$, we obtain $$r$$ with probability at least $$\frac{\phi(r)}{3r}$$. Using the theorem that $$\phi(r)/r > k/\log \log r$$ for some fixed $$k$$ [17, Theorem 328], this shows that we find $$r$$ at least a $$k/ \log \log r$$ fraction of the time.

[17]: G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, Fifth Edition, Oxford University Press, New York (1979).

We know $$r < N$$, so this proves step 3 introduces at most $$O(\lg \lg N)$$ repetitions. It seems likely to me that this can be improved (e.g. if you keep replacing $$b$$ by $$b^p$$ when you get a bad $$p$$ that would presumably keep reducing $$r$$, or maybe that's bad?), and I'm sure someone has explained how to do this in great detail, but I don't know the reference.

"On Shor's Quantum Factor Finding Algorithm: Increasing the Probability of Success and Tradeoffs Involving the Fourier Transform Modulus" seems promising. It discusses using the lcm of two samples in order to get a constant probability of successfully recovering a period (~60%).

I also did some simulation of how many repetitions are needed when the two factors are similarly sized primes, using some basic post-processing, and it appears to converge to 1.5. The following plot is showing a blue dot for each factoring attempt, with a random +-0.5 on each dot's X and Y position so you get a sense of the density in each area. The thick black line is the average.