Shor's algorithm and period finding

Scott Aaronson give interesting interpretation of Shor’s quantum algorithm for factoring integer for the layman like me. What I do not find is the reason why period finding is difficult classically. The only implicit reason is that many smart people have tried it, and did not find an algorithm. Here I want to check the ideas in the Shor’s algorithm for the classical approach. $N$ is the number we want to factor to be consistent with Scott notation.

The main purpose for the quantum algorithm is to find the period of the function $x^r \mod N= x$ for some integer x. We need two ingredients. First, $r$ can be represented as a binary number $r= \sum_k 2^k b_k, b \in \{0, 1\}^n$ . Second the natural representation of $x \in \mathbb{Z}/N$ is $e^{2 \pi i \frac{x}{N}}$ . Two together give nice representation of the period as a solution of the system of polynomial equations.

Following Scott presentation, we can write $e^{ 2 \pi i \frac{x}{N} }= e^{ 2 \pi i \frac{x^r}{N} } = e^{ 2 \pi i \frac{x ^{ \left( \sum_k 2^k b_k \right) } }{N} } = \prod_k e^{ 2 \pi i \frac{x ^{ \left( 2^k b_k \right) } }{N} } = \prod_k c_k$ , where

$c_k= \left \{ \begin{array}{cc} 1, & b_k= 0 \\ e^{ 2 \pi i \frac{x ^{ 2^k } }{N} }, & b_k = 1 \end{array} \right.$

To encode properties of $b_k$ we need following equations

(1) $b_k (b_k-1)= 0$ .

To encode $c_k$ we need additionally

(2) $C_k(x)= \left( e^{ 2 \pi i \frac{x ^{ 2^k } }{N} } -1 \right) b_k + 1$ .

and the final equations encoding periodicity

(3) $\prod_k C_k(x_m) - c_{0,x_m} = 0$ .

We can write many equations of the form (3) as many as we need using different seed values $x$ . (and of cause we need to check if the period is archived by the consecutive squaring). Otherwise we need to solve complicated system of equations.

The first thing is we a re going to rewrite eqns (3). We would call product term in normal form for some set of indices $S$ if it is written as

$\phi_{0} \prod_{k \in S} (b_k-\phi_k)$

Next, we peel the onion. We first are interested on the action of the $b_k+\xi$ on $b_k+\phi_k$

$(b_k+\xi)( b_k+\phi_k)= (1+\phi_k+\xi) b_k+ \phi_k \xi = (1+\phi_k+\xi) ( b_k+ \frac{\phi_k \xi}{1+\phi_k+\xi})$ .

So if we choose $\xi= \zeta_k \frac{1+\phi_k}{\phi_k-\zeta_k}$ we will obtain form $b_k+\zeta_k$ with some global multiplier. Therefore, we can convert any form to any form by this action applied to all variables.

Now consider two equations of the form (3).

$\begin{array}{ll} \phi_{0,1} \prod_k (b_k-\phi_{k,1}) - 1 & =0 \\ \phi_{0,2} \prod_k (b_k-\phi_{k,2}) - 1 & =0 \end{array}$ .

We are going to act on $b_1$ in the first equation in order to obtain the corresponding term in the second equation, and we are going to act on all the rest variables in the second equation in order to obtain the terms in the first equation. At the end we get

$\begin{array}{ll} \phi'_{0,1} (b_1-\phi_{1,2}) \prod_{k \neq 1} (b_k-\phi_{k,1})- (b_1-\xi_1)&=0 \\ \phi'_{0,2} (b_1-\phi_{1,2}) \prod_{k \neq 1} (b_k-\phi_{k,1})- \prod_{k \neq 1}(b_k-\xi_k)&=0 \end{array}$

The differences between two is

$\phi_0 \prod_{k \neq 1}(b_k-\xi_k) - (b_1-\xi_1)=0$

$\left \{ \begin{array}{lll} b_p \left( c_{0,2} \prod_k c_k(x_1) + c_{0,1} \prod_k c_k(x_2) \right) &= c_{0,2} \frac{ 1+c_{1,p} }{c_{1,p}} \prod_k C_k(x_1) - c_{0,2} \frac{ 1+c_{1,p}}{c_{1,p} } \prod_{k \neq p} C_k(x_1) - c_{0,1}\frac{ 1+c_{2,p} }{c_{2,p}} \prod_k C_k(x_2) + c_{0,1}\frac{ 1+c_{2,p}}{c_{2,p} } \prod_{k \neq p} C_k(x_2) & = 0\\ b_q \left( c_{0,2} \prod_k c_k(x_1) + c_{0,1} \prod_k c_k(x_2) \right) &= c_{0,2} \frac{ 1+c_{1,q} }{c_{1,q}} \prod_k C_k(x_1) - c_{0,2} \frac{ 1+c_{1,q}}{c_{1,q} } \prod_{k \neq q} C_k(x_1) - c_{0,1}\frac{ 1+c_{2,q} }{c_{2,q}} \prod_k C_k(x_2) + c_{0,1}\frac{ 1+c_{2,q}}{c_{2,q} } \prod_{k \neq q} C_k(x_2) & = 0 \\ c_{0,2} \prod_k c_k(x_1) - c_{0,1} \prod_k c_k(x_m) & =0 \end{array}\right.$

$\left \{ \begin{array}{ll} c_{0,2} \left( \frac{ 1+c_{1,p} }{c_{1,p}} - \frac{ 1+c_{2,p} }{c_{2,p}} \right) \prod_k C_k(x_1) - c_{0,2} \frac{ 1+c_{1,p}}{c_{1,p} } \prod_{k \neq p} C_k(x_1) + c_{0,1}\frac{ 1+c_{2,p}}{c_{2,p} } \prod_{k \neq p} C_k(x_2) & = 0 \\ c_{0,2} \left( \frac{ 1+c_{1,q} }{c_{1,q}} - \frac{ 1+c_{2,q} }{c_{2,q}} \right) \prod_k C_k(x_1) - c_{0,2} \frac{ 1+c_{1,q}}{c_{1,q} } \prod_{k \neq q} C_k(x_1) + c_{0,1}\frac{ 1+c_{2,q}}{c_{2,q} } \prod_{k \neq q} C_k(x_2) & = 0 \\ c_{0,2} \frac{ 1+c_{2,q} }{c_{2,q}} \prod_k c_k(x_1) - c_{0,1} \frac{ 1+c_{2,q} }{c_{2,q}} \prod_k c_k(x_m) & =0 \end{array}\right.$

In order to avoid possible multiplication to 0 $a \neq \{0,-1\}$ . Let $\phi_{k,m}= e^{ 2 \pi i \frac{x_m ^{ 2^k } }{N} } -1$ . Than

$(b_k +a) C_k(x_m) = \left( 1+a+\frac{1}{\phi_{k,m}}\right) C_k(x_m) - \left( 1+\frac{1}{\phi_{k,m}} \right)$ ,

$(b_n+a_1) \prod_k C_k(x_m) = \left( 1+a_1+\frac{1}{\phi_{k,m}}\right) \prod_k C_k(x_m) - \left( 1+\frac{1}{\phi_{k,m}} \right) \prod_{k \neq n} C_k(x_m)$ ,

$(b_n+a_2) (b_n+a_1) \prod_k C_k(x_m)$ $= (b_n+a_2) \left( 1+a_1+\frac{1}{\phi_{k,m}}\right) \prod_k C_k(x_m) - (b_n+a_2) \left( 1+\frac{1}{\phi_{k,m}} \right) \prod_{k \neq n} C_k(x_m)$ $= \left[ \left( 1+a_2+\frac{1}{\phi_{k,m}}\right) \left( 1+a_1+\frac{1}{\phi_{k,m}}\right) - \frac{1}{\phi_{k,m}} \left( 1+\frac{1}{\phi_{k,m}} \right) \right] \prod_k C_k(x_m)$ $- \left[ \left( 1+\frac{1}{\phi_{k,m}} \right) \left( 1+a_1+\frac{1}{\phi_{k,m}}\right) +\left( a_2+\frac{1}{\phi_{k,m}} \right) \left( 1+\frac{1}{\phi_{k,m}} \right) \right] \prod_{k \neq n} C_k(x_m)$

—— >>> Still needs update <<< —-
Applying this twice for second line in (4) with different constants $a_1, a_2$ we get

$\left \{ \begin{array}{ll} \mbox{const}_1 \prod_k c_k(x_1) +\mbox{const}_3 \prod_k c_k(x_m) + \mbox{const}_2 \prod_{k \neq n} c_k(x_1)+ \mbox{const}_4 \prod_{k \neq n} c_k(x_m) & = 0\\ \mbox{const}_5 \prod_k c_k(x_1) + \mbox{const}_7 \prod_k c_k(x_m)+ \mbox{const}_6 \prod_{k \neq n} c_k(x_1) + \mbox{const}_8 \prod_{k \neq n} c_k(x_m) & =0 \\ \mbox{const}_9 \prod_k c_k(x_1) - \mbox{const}_{10} \prod_k c_k(x_m) & =0 \end{array}\right.$

From which we can eliminate terms $\prod_k c_k(x_1)$ and $\prod_k c_k(x_m)$ . Therefore, we left with the system of second line in (4) with one variable less. Applying it recursively we can get equation on a single variable find the solution and back substitute.

I leave details for experts, what values of $a_1, a_2$ should be chosen at each stage, the precision one have to keep for const values (solving it exact may require exponential number of terms), the possible linear dependencies in eliminating variable (e.g. the choice and the number of seed values $x_m$ ), etc. Don't forget I may have simple mistake, and this is bullshit.

[Update] since there is no interest, I unroll some statements. (19 Oct 2012)

About these ads

One Response to Shor’s algorithm and period finding

Paul B. says:

October 31, 2012 at 2:55 pm

Hey, you might want to know that your description of “inertial confinement drumming” controlled fusion reactor on Scott’s blog is pretty close to what is actually being tried by General Fusion (google them), right here, on Earth (actually, about 8 km from where I am now ). Needless to say, I’m a great fan of them!

(totally unrelated to Shor’s algorithm, I know, except in very, very long and convoluted way).

Sincerely,

Paul B.

Shor’s algorithm and period finding

One Response to Shor’s algorithm and period finding

Leave a Reply Cancel reply

Recent Posts

Archives

Meta

Follow “Crackpot Trisector Notes”

Shor’s algorithm and period finding

Share this:

Like this:

One Response to Shor’s algorithm and period finding

Leave a Reply Cancel reply

Recent Posts

Archives

Meta

Follow “Crackpot Trisector Notes”