Shor’s algorithm and helper functions.
Todo:
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
This function returns num as an array in binary
It does this with the 0th digit being on the right
>>> from sympy.physics.quantum.shor import arr
>>> arr(5, 4)
[0, 1, 0, 1]
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]
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.