5
$\begingroup$

My understanding of Shor's algorithm is that you have to carry out the following steps if you are trying to factor $N$:

  1. Chose a random number less than $N$. Let's call it $a$.

  2. Calculate the period of $a^x \ \text{mod} \ N$. Let's call the period $r$.

  3. One of the factors is the GCD of $a^{r/2}+1$ and $N$. The other is the GCD of $a^{r/2}-1$ and $N$.

However this does not work in some cases such as if $N=35$ and $a=10$. You should be getting $5$ and $7$ as the prime factors of $35$, but this is not the case. The period of $10^x \ \text{mod} \ 35$ is $6$. The GCD of $10^{6/2}+1$, $1001$ and $35$ is $7$, which is one of the factors. But the GCD of $10^{6/2}-1$, $999$ and $35$ is $1$, which is not what you should be getting. Why doesn't Shor's algorithm work in this case?

Improve this question
$\endgroup$
2
  • $\begingroup$ Notice that Shor's algorithm doesn't need to "always work" in the sense you're asking about. Indeed, suppose you have any probabilistic algorithm which given a number n, outputs either 1 or a nontrivial factor, and if n is not prime it does the latter with probability at least $1/2$. Then we can use this to fully factorize $n$: run it until you get a factor $k$, and then recursively factor $k$ and $n/k$. $\endgroup$
    – Jalex Stark
    May 5, 2018 at 19:35
  • $\begingroup$ Hi! Welcome to Quantum Computing Stack Exchange. Please use MathJax to format mathematical expressions and equations from the next time onwards. I have formatted your question this time. You will find a short MathJax tutorial here. $\endgroup$
    – Sanchayan Dutta
    May 5, 2018 at 19:59

1 Answer 1

Reset to default
6
$\begingroup$

You skipped a step in the algorithm.

  1. First check if $N$ is even. $35$ is not even.

  2. Next determine if $N=a^b$ for $a \geq 1$ and $b \geq 2$. It's not.

  3. Randomly choose $x$ in the range $1$ to $N-1$. If $\text{gcd}(x,N) > 1$ then return the factor $\text{gcd}(x,N)$. This is what you missed. $\text{gcd}(10,35) = 5$ There's no reason to perform order finding if you choose $x = 10$. $x$ should be co-prime to $N$ in order to continue.

For completeness:

  1. Find the order $r$ of $x\bmod N$.

  2. If $r$ is even and $x^{r/2} \neq -1 \pmod N$ then compute the $\text{gcd}(x^{r/2} -1,N)$ to see if one of these is a non-trivial factor. Otherwise, the algorithm fails.

The reason the algorithm could fail is because you don't have enough qubits to perform the order-finding part to enough precision.

These steps came from Section 5.3.2 of Nielsen & Chuang.

Improve this answer
$\endgroup$
8
  • $\begingroup$ \mod seems to produce too much spacing. I tried to fix it using \text{mod}. If anyone has a better fix for the spacing and formatting feel free to edit. For reference: tex.stackexchange.com/questions/137073/… $\endgroup$
    – Sanchayan Dutta
    May 5, 2018 at 20:12
  • $\begingroup$ Yeah that’s right. I usually use {\rm } $\endgroup$
    – Andrew O
    May 5, 2018 at 21:14
  • $\begingroup$ I used \bmod (no brackets) and \pmod (with brackets). Looks reasonable to me, but feel free to roll back cc @Blue $\endgroup$
    – Mithrandir24601 ♦
    May 5, 2018 at 22:40
  • $\begingroup$ @Blue Use mkern before pmod --- Origonal: \$x^{r/2}\ne-1\pmod{\text{N}}\$ - Suggested: \$x^{r/2}\ne-1\mkern-12mu\pmod{\text{N}}\$ --- Result: $$x^{r/2}\ne-1\pmod{\text{N}}$$ $$x^{r/2}\ne-1\mkern-12mu\pmod{\text{N}}$$ $\endgroup$
    – Rob
    May 9, 2018 at 6:17
  • 1
    $\begingroup$ @cssstyler In this case, you've found two factors of N (9 and 5, one of which is prime) - lets be more general and call these $M_1$ and $M_2$ and you've reduced your problem of factorising N to either being solved (if you just want any factors of N) or you've divided it into one of factoring $M_1$ and $M_2$ i.e. split it into two of the same but smaller problems (in this specific case of 9 and 5, it's even easier as 5 is a prime factor and 9 is $3^2$, so you've solved the problem without a single call to the QC) $\endgroup$
    – Mithrandir24601 ♦
    May 5, 2020 at 20:12

Your Answer

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

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