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
This entry was posted in Uncategorized and tagged . Bookmark the permalink.

One Response to Shor’s algorithm and period finding

  1. Paul B. says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s