3
$\begingroup$

After reading through Shor's algorithm, I have a few questions about the probability of factoring semiprime number out. Here is some background of the question.

To factor a semiprime number $N$ such that $N = pq$ (where $p$ and $q$ are prime numbers) efficiently, Shor's algorithm is employed with the following steps (roughly):

  1. Register 2 sets of qubit $\overbrace{\vert00...0\rangle}^{\text{t qubits}}\overbrace{\vert00...0\rangle}^{\text{n qubits}}$ where $N^{2} < 2^{t} < 2N^{2}$ and $n = \log_{2}{N}$
  2. Randomly choose $x$ such that $1 < x < N$ and check if $\gcd(x,N) = 1$ if not here is a factor
  3. Finding a period $r$ (or order) of a modular exponentiation sequence, $f(x) = x^{a} \mod N$ where $a = 0,1,2,3,...$ with quantum fourier transform (QFT) (I have skip many details about operation after initialize a qubits, if interested then I suggest this Qiskit tutorial)
  4. Measure the first set register which contain an information in form of

$$\vert\psi\rangle = \frac{1}{2^{t}}\sum_{a=0}^{2^{t}-1}\sum_{z=0}^{2^{t}-1}e^{(2\pi i)(\frac{aj}{2^{t}})}\vert j \rangle \vert x^a \bmod N \rangle \hspace{0.2cm} ;\text{where} \hspace{0.3cm} \frac{j}{2^{t}} = \frac{k}{r} \hspace{0.3cm}, 0 < k < N$$

  1. After obtaining $z$ by using continued fraction to approx $\frac{j}{2^t}$ close to $\frac{k}{r}$ which is irreducible, so the denominator is a period $r$
  2. Check if $r$ is even and is period of $x$ by using $2^{r} = 1 \mod{N}$ if not then run 2.) again ,if yes then $r$ is period of $x$ and the prime factor can be compute by $\gcd(x^{r/2} \pm 1, N)$

Now consider an example $N = 21$ and $x = 2$ follow this tutorial (which I follow from Qiskit tutorial).

By following the above step until 4, the probability density of state becomes:

$$\rm{Probability} \ (j) = \frac{1}{512 \times 86} \bigg\vert \sum_{a=0}^{85}e^{-2 \pi i \frac{6ja}{512}} \bigg\vert^2$$

Note: Normalization factor is different from 4 (which is more general) because the example does a measurement on the second register before QFT to simplify an expression.

So then consider the possible outcome $j$ corresponding probability and period compute from continued fraction approximation of a measurement which are

  • $0$ $(16.66\%)$ ; algorithm fail, retry
  • $83 \leq j \leq 87$ $(16.66\%)$ $r = 6$
  • $168 \leq j \leq 172$ $(16.66\%)$ $r = 3$
  • $254 \leq j \leq 257$ $(16.66\%)$ $r = 2$
  • $339 \leq j \leq 343$ $(16.66\%)$ $r = 3$
  • $425 \leq j \leq 429$ $(16.66\%)$ $r = 6$

the expected result, period of $2^a \text{mod} N$ is $6$. From the above result, it is easily seen that a probability of obtaining the right answer is around $33\%$

Here is the beginning of the question from Shor's original paper, which says:

when applied to a random $x \ (\text{mod} \hspace{0.1cm}n)$, yields a factor of n with probability at least $1 - \frac{1}{2^k}$ , where k is the number of distinct odd prime factors of $n$

After looking through other possible value $x$ there are $2, 8, 10, 11, 13, 19$ that return an even period such that I can use them to successfully compute prime factors of $N$. And for $3, 6, 7, 12, 14, 15, 18$ that returns a prime factor in step 2 above.

So the question is if we consider $x = 2$ (follow the above example) then the consecutive probability is $\frac{1}{19}\times\frac{1}{3}$ which is less than $\frac{1}{2}$. So what about such a probability that is stated in Shor's original paper? Does it just mean the probability of encountered $x$ that "may return the right answer" does not include its consecutive probability?

Or in Shor's original paper it is mentioned that the outcome that may be a factor of $r$, namely $r = r_{1}r_{2}$ and suggests a tactic: to check $r' = 2r, 3r, ...$ (stop before $r' > N$). Then how can I speak about the probability of obtaining the right answer in this aspect?

Alternatively, if one can obtain a factor of $r$, namely $r_{1}$ (i.e. above example third to fifth a outcome) in tutorial that suggests one to run the quantum part again with $x' = x^{r} \text{mod} N$ which will return $r_{2}$ with some probability again.

There are so many ways to do it. So I am now wondering which way is the most efficient way to perform Shor's algorithm:

  • Not deal with the $x$ such that return odd $r$ or trivial solution.
  • Extracting the period from measured information using continued fraction method which might not return the right period even if it is $x$ that should (i.e. the above example with to say $\frac{256}{512} = \frac{1}{2}$ then return $r = 2$).
  • Retry with a new $x$ every time?
  • Use a tactic that Shor suggests?
  • Retry again with $x'$ to obtain another factor of $r$.
  • Another way that I don't know.

Also, how many times do we need to repeat the algorithm if we want to factor like say 232 digits numbers (or maybe say an order like 10 times is enough. Or 100? 1,000?).

I get that it is still worth run Shor's algorithm again and again. It is still more efficient than the classical factoring algorithm. But with the above statement from Shor's original paper an example in tutorial makes me confused. Did I misunderstand or miscalculate something in the above process?

I have read a similar question, but still not getting it and want to ask for my understanding.

$\endgroup$
2
  • $\begingroup$ In your step 4, the inner sum should run over $j$, and $k$ should be on $[0, r)$. Also it is not an equivalence between $j/2^t$ and $k/r$. Rather we expect to observe $j$ so that when $j/2^t$ is expanded in a continued fraction, we find $k/r$. Also, in step 5, $z$ should be $j$. In step 6, we are not guaranteed that $r$ is the order of $x \text{ mod } N$, nor that we will be able to split $N$. $\endgroup$ Apr 7 at 18:27
  • $\begingroup$ Also, the probability in the gray quotation should be $1 - 2^{1-k}$. This typo is in the 1994 conference version of Shor's paper, but not in the 1997 journal version. $\endgroup$ Apr 8 at 6:11

1 Answer 1

3
$\begingroup$

Shor's lower bound [Shor94] [Shor97] essentially goes as follows:

  • Shor proves that the probability that $r$ is even and that $x^{r/2} \not\equiv -1 \:\: (\text{mod } N)$ is at least $1/2$ when $x$ is selected uniformly at random from $\mathbb Z_N^*$. This is where the factor $1/2$ in the lower bound stems from, and it reflects the probability that we will be able to split $N$ given $x$ and $r$ in your step 6.

  • Shor proves that the probability of observing the optimal frequency $j_0(k) = \lceil 2^t k / r \rfloor$ for any $k \in [0, r) \cap \mathbb Z$ is at least $1/(3r)$, for $t$ as in your step 1.

  • Shor then shows (by referencing Hardy–Wright) that for all of the optimal frequencies, expanding $j_0(k) \, / \, 2^t$ in a continued fraction yields $k/r$. Assuming $k$ and $r$ to be coprime, this yields $r$. Shor shows (via Knuth, Hardy–Wright) that the probability that $k$ and $r$ are coprime is $\Omega(1 / \log \log r)$.

    (In the second step, Shor uses that $k$ may be perceived as having been selected uniformly at random from $[0, r) \cap \mathbb Z$ when using the lower bound of $1/(3r)$ that is independent of $k$.)

So a possible lower bound is $1/6$ times the probability that $k$ and $r$ are coprime, and the expected number of runs of the order-finding circuit is then $O(\log \log r)$. In practice, however, the procedure can be optimized in a number of ways. Shor gives some proposal and pointers in [Shor94] and [Shor97].

More specifically, as shown in [E24] via [E21b] and [Miller76], a single run of the order-finding circuit suffices to find $r$, and also to completely factor $N$ into all of its prime factors, in the worst case, and for $N$ any positive integer, with very high probability of success. So the expected number of runs is essentially one (or zero, if the problem is classically tractable) assuming that one uses more elaborate post-processing. (This is also the answer that Craig Gidney arrived at in the question you reference.)

$\endgroup$
4
  • 1
    $\begingroup$ Dumb question perhaps but how much of [E24] carries over to Regev’s recent improvement? $\endgroup$ Apr 7 at 18:50
  • 1
    $\begingroup$ @MarkSpinelli Regev's analysis is a bit different, but if you look at App. A to [EG23p], Regev's algorithm can be extended to factor via order-finding via the above reference [E21b]. As for Regev's lower bound, it is not tight. Our simulations (github.com/ekera/regevnum) show that the success probability is close to one after $m = d + 4$ runs provided that $C$ is selected appropriately, as described in [EG23p]. You need $C \approx 2$ when using LLL. $\endgroup$ Apr 7 at 18:56
  • $\begingroup$ I also answered a question about the relation between Shor's and Regev's algorithms on the TCS stack exchange recently. It is somewhat related to your question. If you interested, please see: cstheory.stackexchange.com/questions/54114/… $\endgroup$ Apr 7 at 19:03
  • $\begingroup$ (The statement in my first comment that our simulations indicate that you need $C \approx 2$ when using LLL is for RSA-2048.) $\endgroup$ Apr 7 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.