# ProjectQ: Shor's Algorithm

Shor's algorithm for factoring, which for a given (large) number N determine the two prime factors $p_1$ and $p_2$ such that $p_1 \cdot p_2 = N$ in polynomial time! This is a superpolynomial speed-up over the best known classical algorithm (which is the number field sieve) and enables the breaking of modern encryption schemes such as RSA on a future quantum computer.

## Implementation

We'll skip the number theory. This example uses the implementation by Beauregard to factor an n-bit number using 2n+3 qubits. In this implementation, the modular exponentiation is carried out using modular multiplication and shift. Furthermore it uses the semi-classical quantum Fourier transform. Pulling the final measurement of the x-register through the final inverse quantum Fourier transform allows to run the 2n modular multiplications serially, which keeps one from having to store the 2n qubits of x.

Simulating Shor's algorithm at the level of single-qubit gates and CNOTs already takes quite a bit of time for larger numbers than 15. To turn on our emulation feature, which does not decompose the modular arithmetic to low-level gates, but carries it out directly instead, we can change the line

if isinstance(g, BasicMathGate):
return False

to return True. This allows to factor N = 4,028,033 in just a few minutes.

The most important part of the code is

for k in range(2 * n):
current_a = pow(a, 1 << (2 * n - 1 - k), N)
# one iteration of 1-qubit QPE
H | ctrl_qubit
with Control(eng, ctrl_qubit):
MultiplyByConstantModN(current_a, N) | x
# perform inverse QFT --> Rotations conditioned on previous outcomes
for i in range(k):
if measurements[i]:
R(-math.pi/(1 << (k - i))) | ctrl_qubit
H | ctrl_qubit
# and measure
Measure | ctrl_qubit
eng.flush()
measurements[k] = int(ctrl_qubit)
if measurements[k]:
X | ctrl_qubit

which executes the 2n modular multiplications conditioned on a control qubit *ctrl_qubit* in a uniform superposition of 0 and 1. The control qubit is then measured after performing the semi-classical. inverse quantum Fourier transform and the measurement outcome is saved in the list *measurements*, followed by a reset of the control qubit to state 0.