-
Notifications
You must be signed in to change notification settings - Fork 1
/
shor_algorithm_quantum_qiskit.py
186 lines (160 loc) · 5.22 KB
/
shor_algorithm_quantum_qiskit.py
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
175
176
177
178
179
180
181
182
183
184
185
186
# -*- coding: utf-8 -*-
"""
Programa desarrollado por el Licenciado César Cordero Rodríguez.
Bajo licencia GPLv3.
Puede ser modificado, copiado y distribuido.
Se desarrolló con fines educativos.
"""
#Read more here: https://learn.qiskit.org/course/ch-algorithms/shors-algorithm
#TO INSTALL:
#pip3 install qiskit
#pip3 install matplotlib
#pip3 install pylatexenc
#pip3 install numpy pandas
import matplotlib.pyplot as plt
import numpy as np
from qiskit import QuantumCircuit, BasicAer, Aer, transpile
from qiskit.visualization import plot_histogram
from math import gcd
from numpy.random import randint
import pandas as pd
from fractions import Fraction
print("Imports Successful")
def c_amod15(a, power):
"""Controlled multiplication by a mod 15"""
if a not in [2,4,7,8,11,13]:
raise ValueError("'a' must be 2,4,7,8,11 or 13")
U = QuantumCircuit(4)
for _iteration in range(power):
if a in [2,13]:
U.swap(2,3)
U.swap(1,2)
U.swap(0,1)
if a in [7,8]:
U.swap(0,1)
U.swap(1,2)
U.swap(2,3)
if a in [4, 11]:
U.swap(1,3)
U.swap(0,2)
if a in [7,11,13]:
for q in range(4):
U.x(q)
U = U.to_gate()
U.name = f"{a}^{power} mod 15"
c_U = U.control()
return c_U
def qft_dagger(n):
"""n-qubit QFTdagger the first n qubits in circ"""
qc = QuantumCircuit(n)
# Don't forget the Swaps!
for qubit in range(n//2):
qc.swap(qubit, n-qubit-1)
for j in range(n):
for m in range(j):
qc.cp(-np.pi/float(2**(j-m)), m, j)
qc.h(j)
qc.name = "QFT†"
return qc
# Specify variables
N_COUNT = 8 # number of counting qubits
a = 7
# Create QuantumCircuit with N_COUNT counting qubits
# plus 4 qubits for U to act on
qc = QuantumCircuit(N_COUNT + 4, N_COUNT)
# Initialize counting qubits
# in state |+>
for q in range(N_COUNT):
qc.h(q)
# And auxiliary register in state |1>
qc.x(N_COUNT)
# Do controlled-U operations
for q in range(N_COUNT):
qc.append(c_amod15(a, 2**q),
[q] + [i+N_COUNT for i in range(4)])
# Do inverse-QFT
qc.append(qft_dagger(N_COUNT), range(N_COUNT))
# Measure circuit
qc.measure(range(N_COUNT), range(N_COUNT))
qc.draw(fold=-1) # -1 means 'do not fold'
aer_sim = Aer.get_backend('aer_simulator')
t_qc = transpile(qc, aer_sim)
counts = aer_sim.run(t_qc).result().get_counts()
plot_histogram(counts)
rows, measured_phases = [], []
for output in counts:
decimal = int(output, 2) # Convert (base 2) string to decimal
phase = decimal/(2**N_COUNT) # Find corresponding eigenvalue
measured_phases.append(phase)
# Add these values to the rows in our table:
rows.append([f"{output}(bin) = {decimal:>3}(dec)",
f"{decimal}/{2**N_COUNT} = {phase:.2f}"])
# Print the rows in a table
headers=["Register Output", "Phase"]
df = pd.DataFrame(rows, columns=headers)
print(df)
plt.show()
def a2jmodN(a, j, N):
"""Compute a^{2^j} (mod N) by repeated squaring"""
for _ in range(j):
a = np.mod(a**2, N)
return a
print(a2jmodN(7, 2049, 53))
N = 15
np.random.seed(1) # This is to make sure we get reproduceable results
a = randint(2, N)
print(a)
from math import gcd # greatest common divisor
gcd(a, N)
def qpe_amod15(a):
"""Performs quantum phase estimation on the operation a*r mod 15.
Args:
a (int): This is 'a' in a*r mod 15
Returns:
float: Estimate of the phase
"""
N_COUNT = 8
qc = QuantumCircuit(4+N_COUNT, N_COUNT)
for q in range(N_COUNT):
qc.h(q) # Initialize counting qubits in state |+>
qc.x(3+N_COUNT) # And auxiliary register in state |1>
for q in range(N_COUNT): # Do controlled-U operations
qc.append(c_amod15(a, 2**q),
[q] + [i+N_COUNT for i in range(4)])
qc.append(qft_dagger(N_COUNT), range(N_COUNT)) # Do inverse-QFT
qc.measure(range(N_COUNT), range(N_COUNT))
# Simulate Results
aer_sim = Aer.get_backend('aer_simulator')
# `memory=True` tells the backend to save each measurement in a list
job = aer_sim.run(transpile(qc, aer_sim), shots=1, memory=True)
readings = job.result().get_memory()
print("Register Reading: " + readings[0])
phase = int(readings[0],2)/(2**N_COUNT)
print(f"Corresponding Phase: {phase}")
return phase
phase = qpe_amod15(a) # Phase = s/r
Fraction(phase).limit_denominator(15)
frac = Fraction(phase).limit_denominator(15)
s, r = frac.numerator, frac.denominator
print(r)
guesses = [gcd(a**(r//2)-1, N), gcd(a**(r//2)+1, N)]
print(guesses)
a = 7
FACTOR_FOUND = False
ATTEMPT = 0
while not FACTOR_FOUND:
ATTEMPT += 1
print(f"\nATTEMPT {ATTEMPT}:")
phase = qpe_amod15(a) # Phase = s/r
frac = Fraction(phase).limit_denominator(N)
r = frac.denominator
print(f"Result: r = {r}")
if phase != 0:
# Guesses for factors are gcd(x^{r/2} ±1 , 15)
guesses = [gcd(a**(r//2)-1, N), gcd(a**(r//2)+1, N)]
print(f"Guessed Factors: {guesses[0]} and {guesses[1]}")
for guess in guesses:
if guess not in [1,N] and (N % guess) == 0:
# Guess is a factor!
print("*** Non-trivial factor found: {guess} ***")
FACTOR_FOUND = True