- So let's take a look
at how the algorithm is actually built.
Shor's algorithm (laughs) (mumbles)
(upbeat music)
Welcome back to coding with Qiskit.
I'm your host Jin.
If this is your first time joining us
check out our previous episodes where each week we talked
about quantum algorithms
and be sure to like and subscribe.
In this final episode,
we'll be talking about encryption and implementing one
of the most famous algorithms in the field,
Shor's Algorithm.
Shor's algorithm is the premier example
of a quantum algorithm that shows the power
of quantum computation
compared to classical computation today.
This is because Shor's algorithm
provides a nearly exponential speed-up
over the fastest known classical algorithm
in finding prime factors of large numbers.
But why is this so pertinent?
Finding factors for large numbers
is the basis of RSA encryption,
which is a public key sharing scheme
used for secure data transactions,
like credit card transactions.
Under RSA encryption, messages can be encrypted
with a code called a public key, which can be shared openly.
Once a message has been encrypted with the public key,
which is a very large number,
it can only be decrypted by a private key,
which is the prime factor of that large number.
The larger the number, the more computational power
it takes to find a prime factor
and the more secure the encryption is.
So the security of RSA relies on the fact
that finding a prime factor of a large number,
takes an extremely long amount of time.
To give you an idea of how long this would take,
let's take the example of a 232 decimal digit
semi prime number.
A semi prime number is just the product
of two prime numbers
and it's the hardest type of number to factorize.
To factorize this number, you need roughly a 1,000 years
of processing time on a typical laptop.
Quantum computers running Shor's algorithm,
could one day shorten this way significantly
but quantum processors today,
are far from being able to do this.
So you don't need to worry
about your credit card transactions anytime soon.
In this episode we'll focus
on how to implement Shor's algorithm in Qiskit.
But if you wanna learn more
about the theory of Shor's algorithm,
check out the links in the description below.
So let's actually implement Shor's algorithm now in Qiskit.
All right.
So first as always, I'm gonna activate
my Qiskit environment, coming with Qiskit.
This is where I have Qiskit installed.
I'm gonna open up a Jupyter notebook.
Open up a new Python three notebook.
All right.
So the easiest way to run Shor's algorithm
is to use the Shor class in aqua,
so from the Qiskit aqua algorithms.
I'm gonna import Shor,
I'm going to also import quantum instance from aqua
and this is gonna run my experiment.
Import numpy.
And let me also import QuantumCircuit,
Aer and execute.
These are all the things that will run my experiment
and from qiskit.tools.visualization,
impor, plot_histogram.
So I can look at my results.
Oops, import.
Okay, so let me set my backend to the qasm_simulator.
I'm gonna set up my quantum_instance to run my experiment,
plugging my backend, say shots is 1000.
Let's set my Shor's algorithm.
And so for this example, I'm gonna factorize
the number 15 and is equal to 15.
This is just a really simple example, just to show you
what's going on.
I'm gonna talk about what this a number is
in a little bit.
All right.
Now let's run this.
All right.
So, my simple Shor's algorithm has factored 15
into three and five.
So that was easy, but let's unpack what
this class is actually doing.
Let's take a look at how the algorithm is actually built.
Shor's algorithm can be broken up into three parts.
Number one, we can convert the factoring problem
into a period finding problem using what's called
the modular exponentiation function.
What this boils down to is dividing our number
by a guest number a, and computing the remainder.
For good guesses of a, this function is periodic
as we increase the power of a.
The second part finds
the period of the modular exponentiation
function using the Quantum Fourier Transform.
And this is responsible for the quantum speed up
of this algorithm.
And finally, number three, once we found the period
of our modular exponentiation function
we can use this number to efficiently compute the factors
of our original number using the following magic formula.
So remember a is our guess number
and r is the period
of our modular exponentiation function.
And these are two magic numbers.
p is equal to a to the r over two minus one
and q is equal to a to the r over two plus one.
And N is our
number that we're trying to factor.
So these two magic numbers, p and q,
are not necessarily the factors of N
that we're looking for, but with high probability
they'll have co-factors
with N which we can compute efficiently.
And if our magic numbers aren't integers
we can just use another guess for a.
So the first thing I'm gonna do is code up
my modular exponentiation function.
And this is hard coded for factorizing 15
and also a hard-coded for a guess number of seven.
Generally you can construct circuits efficiently
for whatever guess you're trying to use.
For iteration in range power.
And all this circuit involves us doing a few swaps.
Swap one, two
U swap, zero one, and then for q in range four.
To your next gate.
Okay, I'm gonna turn this circuit into a gate
so we can plug it in to our Shor's algorithm later.
Let me just name the circuit it's equal to,
i mod 15.
And 15 is once again
the number that we're gonna be factorizing, a.power.
Okay (mumbles) control.
Okay.
So we're gonna specify that we have eight qubits that are
going to be counting our exponent
and our guess number a is gonna be seven.
All right.
So now I'm gonna define my quantum
for a transformed circuit.
So my quantum circuit will take
n qubits.
For qubit range,
n,
qc swap.
Swap these qubits around.
N minus qubit minus one.
For j in range n,
for m in range j,
qc.cu1 minus mp.pi
2 to the j minus m,
m,j.
And then (mumbles)
equals, we'll call this QFT dagger,
return qc.
Okay.
All right so now let's put everything together
in my Shor's algorithm.
So I'm gonna set up a new QuantumCircuit.
n_count plus four (mumbles).
I'm going to initialize my counting qubits
into a superposition state.
Just to some how (mumbles) on each cubit
I'm gonna initialize my first insula in the excited state.
I'm just gonna flip it with an x, x gate.
(upbeat music)
All right.
So now let's add my modular exponentiation function.
Qc.append is my modular exponentiation function.
This is hard-coded for a is equal to seven
and there's other circuits for other guesses of a,
q plus i plus n,
count for i in range for four.
Okay?
Then I'm gonna do my quantum for a transform.
(upbeat music)
Okay, and finally, I'm gonna measure my circuit.
Okay let's see what this looks like.
All right, good.
So I've initialized my counting qubits
into the superposition state.
I'm applying my modular exponentiation function,
then I do my quantum fourier transform
at the end and measure.
So now let's actually execute this on one of the simulators.
I'm gonna use the qasm_simulator.
Results equals execute,
execute my circuit,
use this backend,
shots let's say 2048.
Get the results out of this.
Then get the counts back from my experiment.
Let's see what this looks like.
Beautiful.
Okay, so let's look at the states
that we get back in this histogram.
So this gives us back in binary
the phases zero out of 256,
64 out of 256,
128 over 256,
and 192 over 256.
So by simplifying these expressions
and looking at the denominator,
we can get values of the period r
or the modular exponentiation function.
So this gives us three guesses for r, one, two and four,
just by looking at the denominators of our four phases.
So let's look at the value r is equal to four
and plug it into our magic formula,
which remember is p is equal to
a to the r over two minus one.
And q is equal to a to the r over two plus one.
Now remember that p and q are not necessarily
the factors of our original N is equal to 15
but I claimed that they have co-factors
with N which we can find efficiently.
So if we plug r into our formulas,
p is equal to seven squared,
minus one,
a remember is equal to seven.
This gives us p is equal to 48
and q is equal to seven squared plus one,
q is equal to 50.
So with my magic number q is equal to 50,
we see that we have a common factor
with our original N equals 15 of five.
And with our magic number p is equal to 48,
we have another common factor, which is three.
So there we have it.
We found our two factors of 15.
So now that we built Shor's,
why don't you try to factor N is equal to 25
using the Shor's class
and let's know what you get in the comments below.
This is the last episode
of the season of coding with Qiskit.
Thanks so much for tuning in.
Be sure to subscribe so you don't miss next season
of coding with Qiskit,
and so you don't miss out on our weekly Qiskit videos.
I've been your host Jin-Sung Kim, see you later.
(trumpet blowing)
(laughing) (upbeat music)