Steps to Shor's Algorithm

Shor's algorithm for factoring a given integer $n$ can be broken into some simple steps.

1. Determine if the number $n$ is a prime, a even number, or an integer power of a prime number. If it is we will not use Shor's algorithm. There are efficient classical methods for determining if a integer $n$ belongs to one of the above groups, and providing factors for it if it does. This step would be performed on a classical computer.

2. Pick a integer $q$ that is the power of 2 such that $n^{2} \leq q < 2n^{2}$. This step would be done on a classical computer.

3. Pick a random integer $x$ that is coprime to $n$. When two numbers are coprime it means that their greatest common divisor is 1. There are efficient classical methods for picking such an $x$. This step would be done on a classical computer.

4. Create a quantum register and partition it into two sets, register one and register two. Thus the state of our quantum computer can be given by: $left\vert$reg1, reg2$\rangle$. Register one must have enough qubits to represent integers as large as $q - 1$. Register two must have enough qubits to represent integers as large as $n - 1$.

5. Load register one with an equally weighted superposition of all integers from 0 to $q - 1$. Load register two with the 0 state. This operation would be performed by our quantum computer. The total state of the quantum memory register at this point is:
   
   $$\frac{1}{\sqrt{q}}\sum_{a = 0}^{q - 1} \left\vert a, 0 \right\rangle$$
   
   

6. Apply the transformation $x^{a} \bmod n$ to for each number stored in register one and store the result in register two. Due to quantum parallelism this will take only one step, as the quantum computer will only calculate $x^{\left\vert a \right\rangle } \bmod n$, where $\left\vert a \right\rangle$ is the superposition of states created in step 5. This step is performed on the quantum computer. The state of the quantum memory register at this point is:
   
   $$\frac{1}{\sqrt{q}}\sum_{a=0}^{q-1}\left\vert a,x^{a} \bmod n \right\rangle$$
   
   

7. Measure the second register, and observe some value $k$. This has the side effect of collapsing register one into a equal superposition of each value a between 0 and $q - 1$ such that
   
   $$x^{a} \bmod n = k$$
   
   
   This operation is performed by the quantum computer. The state of the quantum memory register after this step is:
   
   $$\frac{1}{\sqrt{\left\vert\left\vert A\right\vert\right\vert}}\sum_{a'=a'\in A}\left\vert a', k \right\rangle$$
   
   
   Where $A$ is the set of $a$'s such that $x^{a} \bmod n = k$, and $\left\vert\left\vert A\right\vert\right\vert$ is the number of elements in that set.

8. Compute the discrete Fourier transform on register one. The discrete Fourier transform when applied to a state $\left\vert a \right\rangle$ changes it in the following manner:
   
   $$\left\vert a \right\rangle = \frac{1}{\sqrt{q}}\sum_{c=0}^{q-1}\left\vert c \right\rangle *e^{2\pi iac/q}$$
   
   
   This step is performed by the quantum computer in one step through quantum parallelism. After the discrete Fourier transform our register is in the state:
   
   $$\frac{1}{\sqrt{\left\vert\left\vert A\right\vert\right\vert}}... ...}\sum_{c=0}^{q-1} \left\vert c,k \right\rangle *e^{2\pi ia'c/q}$$
   
   

9. Measure the state of register one, call this value $m$, this integer $m$ has a very high probability of being a multiple of $q / r$, where $r$ is the desired period. This step is performed by the quantum computer.

10. Take the value $m$, and on a classical computer do some post processing which calculates $r$ based on knowledge of $m$ and $q$. There are many ways to do this post processing, they are complex are are omitted for clarity in presentation of the quantum core of Shor's Algorithm. This post processing is done on a classical computer.

11. Once you have attained $r$, a factor of $n$ can be determined by taking $\gcd(x^{r/2} + 1, n)$ and $\gcd(x^{r/2} - 1, n)$. If you have found a factor of $n$, then stop, if not go to step 4. This final step is done on a classical computer.

Step 11 contains a provision for Shor's algorithm failing to produce the factors of $n$. Shor's algorithm can fail for multiple reasons, for example the discrete Fourier transform could be measured to be 0 in step 9, making the post processing in step 10 impossible. At other times the algorithm will sometimes find factors of 1 and $n$, which is correct but not useful. (Williams, Clearwater)