Shor’s Algorithm¶
Shor’s algorithm and helper functions.
Todo:
Get the CMod gate working again using the new Gate API.
Fix everything.
Update docstrings and reformat.

class
sympy.physics.quantum.shor.
CMod
(*args, **kwargs)[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

property
N
¶ N is the type of modular arithmetic we are doing.

property
a
¶ Base of the controlled mod function.

property
t
¶ Size of 1/2 input register. First 1/2 holds output.

property

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.

sympy.physics.quantum.shor.
shor
(N)[source]¶ 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.