Shor's Protocol - Example Solution

 

 

Finally, we have come to the famous Shor's definition of the algorithm in this article. Before applying this algorithm, we examined in detail the three mathematical operations required for our algorithm. These three necessary mathematical expressions were modular arithmetics, quantum Fourier transform, and quantum phase estimation.

As you may remember, Shor's algorithm is an algorithm that gives prime factor values of large numbers. To show that this protocol works, we will write an algorithm that gives the prime factors of 15.

The binary equivalent of the decimal number 15 consists of 1111 qubits.

Now let's examine Shor's protocol in detail.

If we write it in a regular way, we can write the state vector |ψ₃> as follows.

Now, let's measure the last four qubits. In this case, we would have measured the situations |1>, |2>, |4>, |8> with 25% probability.

Suppose we have reached the state |8> with a probability of 25% in our measurement result. Thus, our new situation becomes as follows.

In our next step, let's apply the QFT^-1 gate to our first four qubits and we get the result as follows.

Now let's do our final measurements to reach the result. In our measurement results, we will see that except for 0 (0 does not give us any information about the prime factors, it makes a measurement again.) 4 and 12 give the full solution, while 8 gives a partial solution.