Shor’s Algorithm

Choose your N to factor, as well as qubit sizes and trial alpha

N = integer to factor
m = 2^(number of qubits in first register)
n = 2^(number of qubits in second register)
alpha = number whose period mod N we seek

 

Setting up |x>|f(x)> superposition

This performs the initial QFT to get a superposition in the first register, then computes the value of alpha^x into the second register.
What is graphed is black dots for pure states that are supported in the superposition. The x axis is the classical states of the first register and the y axis is the classical states of the second register. The origin is at top left.

 

Measure the second qubit and then graph the first register

This measures the second qubit and then graphs the first register as classical state (x axis) and amplitude (y axis). The amplitude is not normalized (ignore the scale on the y axis).

 

Compute the QFT and graph result

This applies the QFT to the first register. The result is graphed as classical state (x axis) and |amplitude|^2 (y axis). The colours represent the phases of the complex amplitudes.

 

Measure the first register (QFT output)

This measures the first register, i.e. following the probability amplitudes shown in the last graph. It gives one value, which is the classical state, i.e. an integer y between 0 and m-1.

 

Compute continued fraction convergents

This computes the “convergents” or rational numbers that very well approximate y/m. It returns a list in order of increasing denominator.

 

Guess the period and check for factorization

Put r = your guess!