Shor’s Algorithm

Shor’s algorithm and helper functions.


  • Get the CMod gate working again using the new Gate API.
  • Fix everything.
  • Update docstrings and reformat.
  • Remove print statements. We may want to think about a better API for this.
class sympy.physics.quantum.shor.CMod[source]

A controlled mod gate.

This is black box controlled Mod function for use by shor’s algorithm. TODO implement a decompose property that returns how to do this in terms of elementary gates


N is the type of modular arithmetic we are doing.


Base of the controlled mod function.


Size of 1/2 input register. First 1/2 holds output.

sympy.physics.quantum.shor.continued_fraction(x, y)[source]

This applies the continued fraction expansion to two numbers x/y

x is the numerator and y is the denominator

>>> from sympy.physics.quantum.shor import continued_fraction
>>> continued_fraction(3, 8)
[0, 2, 1, 2]
sympy.physics.quantum.shor.period_find(a, N)[source]

Finds the period of a in modulo N arithmetic

This is quantum part of Shor’s algorithm.It takes two registers, puts first in superposition of states with Hadamards so: |k>|0> with k being all possible choices. It then does a controlled mod and a QFT to determine the order of a.


This function implements Shor’s factoring algorithm on the Integer N

The algorithm starts by picking a random number (a) and seeing if it is coprime with N. If it isn’t, then the gcd of the two numbers is a factor and we are done. Otherwise, it begins the period_finding subroutine which finds the period of a in modulo N arithmetic. This period, if even, can be used to calculate factors by taking a**(r/2)-1 and a**(r/2)+1. These values are returned.

Previous topic


Next topic

Particle in a Box

This Page