2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.