Shor's algorithm weaknesses & uniqueness of close rational

Question

I'm working through a problem set, and am stuck on the following problem:

a) What can go wrong in Shor’s algorithm if Q (the dimension of the Quantum Fourier Transform) is not taken to be sufficiently large? Illustrate with an example.

b) What can go wrong if the function, f, satisfies $f(p) = f(q)$ if the period $s$ divides $p − q$, but it’s not an “if and only if” (i.e., we could have $f(p) = f(q)$ even when $s$ doesn’t divide $p − q$)? Note that this does not actually happen for the function in Shor’s algorithm, but it could happen when attempting period finding on an arbitrary function. Illustrate with an example.

c) What can go wrong in Shor’s algorithm if the integer $N$ to be factored is even (that is, one of the prime factors, $p$ and $q$, is equal to 2)? Illustrate with an example.

d) Prove that there can be at most one rational $\frac{a}{b}$, with $a$ and $b$ positive integers, that’s at most $\epsilon$ away from a real number $x$ and that satisfies $b < \frac{1}{\sqrt{2\epsilon}}$. Explain how this relates to the choice, in Shor’s algorithm, to choose Q to be quadratically larger than the integer $N$ that we’re trying to factor.

I've been wrestling with it for a while, and my attempt so far is:

a) When $s$ (the period) does not divide $Q$, a sufficiently large $Q$ ensures that the rational approximation to $\frac{k Q}{s}$ where $k$ is an integer is sufficiently close to determine a unique $s$.

b) There might be more than one period $s$ associated with the function (something like an acoustic beat), so it would be much more difficult to solve for one period individually.

c) Completely lost....

d) I supposed that there existed two different rationals such that $\mid{\frac{a_1}{b_1} - \frac{a_2}{b_2}}\mid> 0$ and tried to force a contradiction using the constraints $\mid\frac{a_\mu}{b_\mu}-x\mid \leq \epsilon$ and $b_\mu < \frac{1}{\sqrt{2\epsilon}}$, but couldn't get it to come out. Either I am making a stupid mistake and/or missing something simple (?).

I am really struggling to gain intuition for Shor's algorithm and its specific steps, so I'm very unconfident when trying to address parts (a) - (c). I'm stumped by (c) especially; isn't Shor's algorithm robust in the sense that it does not matter if $N$ is even or odd? If anyone could point me in the right direction, it would be appreciated. Thanks!

Answer 1

Regarding (c) -

Too see what can go wrong, we'll need to take a step back and look at Shor's Algorithm assumptions.

Basically, the algorithm says we need to pick a random $X$, find its order $r$, and finally calculate $X^\frac{r}{2} \pmod N$ to get information about $N$.

$N$ is of the form $2P$, thus by Chinese Remainder Theorm it will only have two roots modulo $N$, and they will have to be the trivial roots $1$ and $N-1$. That happens because $2$ has only one trivial root, unlike other primes.

Thus for any $X$ you may pick, $X^\frac{r}{2} \equiv \pm 1 \pmod N$, so you will always end up with the trivial roots, which are not enough for deriving factors of $N$ (not even the factor $2$!)

---

Reference - vazirani lecture on Shor's Algorithm

Answer 2

For question c,

c) What can go wrong in Shor’s algorithm if the integer $N$ to be factored is even (that is, one of the prime factors, $p$ and $q$, is equal to $2$)?

In order for the period-finding algorithm to work, there needs to be a period to find in the first place.

Let us do the modular exponentiation (repeated squaring) unitary $U_f$ on the second register:

$$U_{f}\sum^{N-1}_{x = 0}\vert x\rangle\vert 0\rangle = \vert x\rangle\vert a^{x}\text{ mod }N\rangle$$

Suppose we measure the second register and get a number, $y$. It may be the case that, if $N=2p$, because $p$ has to be large, the first register collapses to only one number $x$ such that $y=a^x \mod N$. Thus, there is no "collision" to which the QFT can find a period.

That is, doing a QFT on the pure state $\vert x\rangle$ with only one value, and then measuring, doesn't tell you anything.