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. 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 for some integer x. We need two ingredients. First, can be represented as a binary number . Second the natural representation of is . Two together give nice representation of the period as a solution of the system of polynomial equations.
Following Scott presentation, we can write , where
To encode properties of we need following equations
To encode we need additionally
and the final equations encoding periodicity
We can write many equations of the form (3) as many as we need using different seed values . (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 if it is written as
Next, we peel the onion. We first are interested on the action of the on
So if we choose we will obtain form 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).
We are going to act on 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
The differences between two is
In order to avoid possible multiplication to 0 . Let . Than
—— >>> Still needs update <<< —-
Applying this twice for second line in (4) with different constants we get
From which we can eliminate terms and . 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 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 ), 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)