Spaces:
Sleeping
Sleeping
File size: 5,504 Bytes
6a86ad5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 |
"""Shor's algorithm and helper functions.
Todo:
* Get the CMod gate working again using the new Gate API.
* Fix everything.
* Update docstrings and reformat.
"""
import math
import random
from sympy.core.mul import Mul
from sympy.core.singleton import S
from sympy.functions.elementary.exponential import log
from sympy.functions.elementary.miscellaneous import sqrt
from sympy.core.intfunc import igcd
from sympy.ntheory import continued_fraction_periodic as continued_fraction
from sympy.utilities.iterables import variations
from sympy.physics.quantum.gate import Gate
from sympy.physics.quantum.qubit import Qubit, measure_partial_oneshot
from sympy.physics.quantum.qapply import qapply
from sympy.physics.quantum.qft import QFT
from sympy.physics.quantum.qexpr import QuantumError
class OrderFindingException(QuantumError):
pass
class CMod(Gate):
"""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
"""
@classmethod
def _eval_args(cls, args):
# t = args[0]
# a = args[1]
# N = args[2]
raise NotImplementedError('The CMod gate has not been completed.')
@property
def t(self):
"""Size of 1/2 input register. First 1/2 holds output."""
return self.label[0]
@property
def a(self):
"""Base of the controlled mod function."""
return self.label[1]
@property
def N(self):
"""N is the type of modular arithmetic we are doing."""
return self.label[2]
def _apply_operator_Qubit(self, qubits, **options):
"""
This directly calculates the controlled mod of the second half of
the register and puts it in the second
This will look pretty when we get Tensor Symbolically working
"""
n = 1
k = 0
# Determine the value stored in high memory.
for i in range(self.t):
k += n*qubits[self.t + i]
n *= 2
# The value to go in low memory will be out.
out = int(self.a**k % self.N)
# Create array for new qbit-ket which will have high memory unaffected
outarray = list(qubits.args[0][:self.t])
# Place out in low memory
for i in reversed(range(self.t)):
outarray.append((out >> i) & 1)
return Qubit(*outarray)
def shor(N):
"""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 is not, 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.
"""
a = random.randrange(N - 2) + 2
if igcd(N, a) != 1:
return igcd(N, a)
r = period_find(a, N)
if r % 2 == 1:
shor(N)
answer = (igcd(a**(r/2) - 1, N), igcd(a**(r/2) + 1, N))
return answer
def getr(x, y, N):
fraction = continued_fraction(x, y)
# Now convert into r
total = ratioize(fraction, N)
return total
def ratioize(list, N):
if list[0] > N:
return S.Zero
if len(list) == 1:
return list[0]
return list[0] + ratioize(list[1:], N)
def period_find(a, N):
"""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.
"""
epsilon = .5
# picks out t's such that maintains accuracy within epsilon
t = int(2*math.ceil(log(N, 2)))
# make the first half of register be 0's |000...000>
start = [0 for x in range(t)]
# Put second half into superposition of states so we have |1>x|0> + |2>x|0> + ... |k>x>|0> + ... + |2**n-1>x|0>
factor = 1/sqrt(2**t)
qubits = 0
for arr in variations(range(2), t, repetition=True):
qbitArray = list(arr) + start
qubits = qubits + Qubit(*qbitArray)
circuit = (factor*qubits).expand()
# Controlled second half of register so that we have:
# |1>x|a**1 %N> + |2>x|a**2 %N> + ... + |k>x|a**k %N >+ ... + |2**n-1=k>x|a**k % n>
circuit = CMod(t, a, N)*circuit
# will measure first half of register giving one of the a**k%N's
circuit = qapply(circuit)
for i in range(t):
circuit = measure_partial_oneshot(circuit, i)
# Now apply Inverse Quantum Fourier Transform on the second half of the register
circuit = qapply(QFT(t, t*2).decompose()*circuit, floatingPoint=True)
for i in range(t):
circuit = measure_partial_oneshot(circuit, i + t)
if isinstance(circuit, Qubit):
register = circuit
elif isinstance(circuit, Mul):
register = circuit.args[-1]
else:
register = circuit.args[-1].args[-1]
n = 1
answer = 0
for i in range(len(register)/2):
answer += n*register[i + t]
n = n << 1
if answer == 0:
raise OrderFindingException(
"Order finder returned 0. Happens with chance %f" % epsilon)
#turn answer into r using continued fractions
g = getr(answer, 2**t, N)
return g
|