7
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Regarding point c), this should be handled by classic preprocessing. What likely is the case for even $N$, that the period for numbers is off/not correctly computable. I admit that these aren't the easiest questions, even when understanding Shor. $\endgroup$ – nippon Nov 15 '18 at 7:57
  • $\begingroup$ If a/b != c/d then a/b - c/d = (ad - bc) / bd has to be at least +-1/bd. $\endgroup$ – Craig Gidney Mar 2 at 3:05
1
$\begingroup$

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.

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