Shor's Algorithm

Shor's Algorithm

Shor's algorithm is the landmark quantum algorithm for integer factorization, famous for threatening the RSA cryptosystem because it factors large numbers exponentially faster than the best known classical methods. Given a composite integer n, it finds a non-trivial factor, and this Cirq example implements the complete algorithm end to end. It combines two parts: a classical probabilistic reduction that turns factoring into an order-finding problem, and a quantum order-finding subroutine that provides the speedup. The classical layer first handles easy corner cases (even numbers and perfect powers), then picks a random base x coprime to n and asks for the multiplicative order r, the smallest positive integer with x^r congruent to 1 modulo n; once r is known, a classical step extracts a factor with high probability. The quantum subroutine finds r using modular exponentiation followed by quantum phase estimation and the quantum Fourier transform, reading the order out of the measured phase via continued fractions. The script ties these pieces together, runs the order-finding circuit on a simulator, and returns a factor of the input. It is a complete, instructive realization of the algorithm that brought quantum computing to the world's attention, showcasing how phase estimation and the QFT enable a decisive computational advantage.

Run it

pip install -r requirements.txt
python shor.py

Source and license

Imported from examples/shor.py in quantumlib/Cirq at v1.6.1, under the Apache License 2.0. Original authors: The Cirq Developers. The upstream LICENSE is included alongside this example.