Coding Shor's Algorithm

Let’s discuss the code for Shor's Algorithm and use it to factor the number 15.

We'll cover the following

Qiskit

This is Qiskit's code for Shor’s Algorithm. In this example, we factorize N=15N=15 with k=8k=8 counting qubits. Remember that we need roughly 2n2n qubits for obtaining a good accuracy, where nn is the number of bits needed to represent NN. Also, notice the implementation of QFTQFT^\dagger that allows us to reconstruct the period rr of the function by transferring the phase information into our qubits for measurement. You can find further details at the Qiskit Textbook here. The code below uses exponentially many gates to apply the UROTUROT operations. The polynomial-gates implementation is given in the references section of Qiskit on the link provided earlier.

Get hands-on with 1200+ tech skills courses.