Shor’s algorithm is probably the most famous quantum algorithm. It was discovered in 1994 and quite probably ignited the general interest in quantum computation. It provides a method for factoring integers in polynomial time, which is an exponential improvement over the best-known classical algorithm. The factoring problem can be translated (efficiently) to a period finding problem and this is the concrete problem which is tackled by the quantum part of Shor's algorithm.

Considering how the gates in these circuits are being laid out, you should interpret results while working in the Big-Endian convention (endianess check-box in the Toolbar should be checked).

The way the algorithm works is by finding the period for a function: f(x) = a^x mod N which is the smallest non-zero positive number r such that: a^r mod N = 1. The period finding problem can be solved by using quantum phase estimation to find an eigenvalue for the operator U|y⟩ = | a*y mod N⟩. The result of repeated applications of U is: U^n|y⟩ = | (a^n)*y mod N⟩. It can be show that the measured phase of U is s/r where s is a random integer between 0 and r - 1.

In our example the number N which we want to factor is 15 and the number of qubits used for phase estimation is 8. We want to find solutions of all non-zero positive values a where a < 15 and a and 15 do not have a common divisor. The value a = 14 is also excluded because N - 1 and N cannot have a common divisor other than 1.

| a | measured values | phases = values/2^8 | r/s values | correct r |
---------------------------------------------------------------
| 2 | 0, 64, 128, 192 | 0, 0.25, 0.50, 0.75 | 0, 1/4, 1/2, 3/4 | 4 |
| 4 | 0, 128 | 0, 0.50 | 0, 1/2 | 2 |
| 7 | 0, 64, 128, 192 | 0, 0.25, 0.50, 0.75 | 0, 1/4, 1/2, 3/4 | 4 |
| 8 | 0, 64, 128, 192 | 0, 0.25, 0.50, 0.75 | 0, 1/4, 1/2, 3/4 | 4 |
| 11 | 0, 128 | 0, 0.50 | 0, 1/2 | 2 |
| 13 | 0, 64, 128, 192 | 0, 0.25, 0.50, 0.75 | 0, 1/4, 1/2, 3/4 | 4 |

One can see that the algorithm does not always return a correct result. Solutions with r/s = 0 are obviously not useful. Also when r and s have a common divisor guessing the correct r is not so easy. When running an a real quantum computer one should repeat the experiment until a value which proves to be correct is found.