ProjectQ: Shor's Algorithm

Published by strangeworks (02/14/2021)

Shor's algorithm for factoring, which for a given (large) number N determine the two prime factors p1p_1 and p2p_2 such that p1p2=Np_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.


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.