8
$\begingroup$

I've been trying to mess around with Qiskit's implementation of Shor's algorithm, and while trying I've noticed that Shor(33), for example, would not output a solution (even with an absurd number of attempts). Qiskit's implementation would retry by itself, so I went on to find an implementation which would give me more control over what's happening and I found this one (https://oreilly-qc.github.io/?p=12-1).

The thing I'm struggling to understand is why, for a given value of a in the modulo function of which Shor attempts to find the period r, and assuring that a has no common factors with the number we're factoring, the period should be found (given a number of tries) and thus the algorithm should succeed. However, Shor(33), with a = 2, does not output any result - just like what happened with Qiskit's implementation. It outputs the correct result, however, when a=5 (33 = 11 * 3). Is there a mathematical explanation for why this happens?

Thank you in advance, I'm quite new to this whole new concept and am just trying to understand this algorithm properly!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

If $f(x) = a^x \pmod{N}$ passes through $-1$, that value of $a$ won't work. For example, $a=2$ fails for $N=33$ because $2^5 = 32 \equiv -1 \pmod{33}$. This should have been mentioned in whatever explanation of Shor's algorithm you were following.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes, that makes sense, I've seen several explanations of Shor and none of them referred that. Could you refer me to some link where that is explained or mentioned in some way? Thank you! $\endgroup$
    – Nuno Costa
    May 15, 2022 at 18:10
  • $\begingroup$ @NunoCosta Well it's one of the section titles in the wikipedia article that you need to find a non-trivial square root of 1, instead of -1 or +1: en.wikipedia.org/wiki/… $\endgroup$
    – Craig Gidney
    May 15, 2022 at 18:23
5
$\begingroup$

What you should have seen in texts is the statement that you have to pick $a$ at random from the numbers that are coprime to $N$. There are then certain claims about the order, $r$ that you get:

  • with high probability, $r$ is even
  • with high probability $a^{r/2}$ is not $\pm 1\text{ mod }N$.

If either of those conditions fail, you have to start again with a different $a$.

The second point here is critical to your case, because what you're wanting is that the factors of $N$ are split between the two terms $a^{r/2}\pm 1$, not all lumped into one of them.

So, all that's happened is that your not very random choice of $a=2$ as failed the high-likelihood conditions.

Improve this answer
$\endgroup$

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.