Andreas Baumhof – Are Quantum Computers Really A Threat To Cryptography? – DEF CON 27 Conference


>>How many people know about uh
quantum physics? Eh, yeah? So I
was looking at this uh I was looking at this this this talk
synopsis and I’m like maybe this
is gonna be a good talk.>>Maybe Not>>Maybe it won’t. [laughter]
I guess I won’t really know
until I take a look at the talk, yeah? Learned that from a baby
book. Yeah. Awesome Alright so
let’s all give Andreas a big round of applause for coming all
the way to Vegas from Sydney
Australia to talk to us about quantum cryptography. [applause]
Have a good time man.>>Thank
you very much. Alright. Welcome everybody. Yeah after that
introduction hopefully you walk
away and learn something in this talk. So, um quantum computing
if you read whatevers in the
press you either think we are completely doomed and you know,
the internets gonna end. Or uh
nothings gonna end because they will never exist so I thought I
would explore this topic a
little more from an algorithmic point of view and really see
where we are. Not so much on the
hype but more really what are the algorithms uh that we talk
about right now. So um I started
various companies in the securities space you know
starting in 2002 which um makes
me feel slightly old um right now, but first I am speaking at
Defcon I am very happy about
this y’know long term attendee but never spoke here so let’s
get right into this. So when you
talk about cryptography we mainly y’know look into two
different um types of
cryptography. One is a symmetric cryptosystem which is a
symmetric shared key y’know kind
of AES for example. Both sides encrypt and talk to each other
with the same key and with
asymmetric uh cryptosystems which use public key
infrastructure you would
basically use a public key to encrypt the message and a
private key to um decrypt it. Um
there’s various forms of this uh obviously for the digital
signatures as well. And um in in
this realm um virtually every cryptosystem right now that is
deployed anywhere is what we
call computationally secure. They are secure in the sense
that there are known algorithms
that can break them but all the algorithms that can break them
are not easy to in the sense
that y’know that if I wanna break in a y’know 2048-bit RSA
key with a normal computer takes
me a couple trillion years which means I am secure even though
there’s known algorithms that
can break them. There are information-theoretic algorithms
out there most notably an
algorithm called um a one-time-pad or vernam ciphers
but they’re really tricky and
not really practically usable for example a one-time-pad you
do need to use the same amount
of keys as you want to transmit so for example if you want to
transmit a one megabyte file you
need to have a one megabyte key basically for every byte you
need a different um uh for every
byte data you need uh one byte key so you would have to manage
massive amount of uh key
material which is not really uh practically but I mean they do
exist but outside of this
virtually every uh cryptosystem is just computationally secure.
And um uh when you look at this
uh quantum algorithm and I’ll go into quite some detail about
this for those two different
types of algorithms. It is much more interesting to look at the
asymmetric part of the uh of the
cryptosystems because in the symmetric part there is a
quantum algorithms as well
called uh Grover which basically looks into um a provided
quadratic speed up to the
classical um uh version. Basically in the classical
version if I want to look for
the shared key I need to basically brute force every
combination which obviously
takes forever. I get a squared root up um a squared speed up in
the quantum version which is a
fantastic speed up y’know if I can speed up a hundred fifty
trillion years but it is
obviously a hundred fifty trillion years uh to break so
that’s not really that
interesting. So we want to focus here on the asymmetric part
where um uh the speed ups that
quantum computers can provide are massive and um we’re going
to go into quite some detail uh
why uh their speed up is so big as it is and uh how they work.
So let’s revisit just a little
bit of how RSA encryption works and it’s really just a basic
introduction so we can use them
uh to understand how the quantum versions of these algorithms
works. Basically, I choose two
prime numbers p and q and um uh with those I just multiply them
get the number n. Now with the
number n I can calculate this lambda function which is a
carmichael function which just a
function I can easily calculate this and once I have this I just
chose another parameter e which
is smaller than the lambda and the value. And then this n
together with the number e is my
public key. I can give this to everybody out there who I wanna
choose to do um uh the
asymmetric encryption. And I basically retain my private key
which is this uh um number d
here which is just the modular inverse of the number e which is
the uh public key. Obviously mod
lambda n. There is always mod lambda n in this uh scenario
which is a private key that I
retain. And with this private key now with this scenario. I
can now look into hey I can now
encrypt something and send something um from Alice to Bob
and as everybody knows with
asymmetric encryption I can only encrypt something that is
smaller than my key so if I have
a two four, um 2048 width key I can only encrypt something that
is smaller than uh 2048 um so I
need to pad my plain text into um a number n so I turn this big
M into small number m um uh
there is various way for this ways for this. Um I don’t go
into too much detail but this is
where the padding scheme uh comes in and then I basically
end up with this number uh small
m. In my ciphertext my encrypted version’s really I just take uh
this number m to the power of e.
Mod n and thats basically my ciphertext. And this is what I
encrypt with a public key. I can
now send this number c to uh to Bob. Uh um receive this and um
if you have the private key you
can easily decrypt this as well on the other side. And uh you
can easily see how this works.
It is really very straightforward if someone has
the c and the ciphertext and the
d the private key by definition c is m to the power of e. So you
see um uh the definition of d
was it is actually the inverse of e so this e to the power of d
just uh equals out. So I end up
with m mod n so uh if I have the private key, I can easily
recover um uh the uh the small m
and obviously by just reversing the padding scheme I now have my
message again. So this basically
how RSA encryption works into some detail. So my task is now I
do have a public key because its
public everybody knows what it is. How do I turn this into
private key. Now from the
definitions it is really pretty straightforward and simple. Um I
need to find those prime numbers
that make up this number n. This number n is known it is part of
the public key. And if I can do
this I can easily calculate lambda n which is really uh the
least common multiplier of
lambda p and lambda q and from there I can easily derive the
private key d and uh I’m done.
So all I need to do to basically go from a public key to private
key is to find those two prime
factors p and q and um that I chose in the very beginning when
I set up my key um uh then I
have everything that I need to do to basically derive a private
key from a public key. Um while
that sounds pretty easy and straightforward actually to do
this and to factor this number n
into the uh prime parts p and q is um is uh really really hard
and all of the classically known
algorithms are all from exponential complexity. Which
means they are really really
hard uh to solve even y’know the GNFS uh algorithms is uh
slightly sub-exponential but
still massive in style so that gives you those assurance that
if you use any of the asymmetric
algorithms uh people will need trillions of years to decrypt
them so they’re fairly secure
for generations to come. But in 1984 a guy called Peter Shor he
was um uh a theoretical
physicist came up with this algorithm. If we were to use
quantum computers. Obviously in
1984 it was all just a theory quantum computers didn’t exist
and they hardly exist today um
but the theory says he came up with an algorithm of how to
factor those numbers in just
polynomial time. And in just polynomial time really is a
difference that is really almost
incomprehensible. Because it really means instead of taking a
trillion years on a classic
computer with a trillion operations per second. Suppose
we have a quantum computer which
just does a million operations per second. I can actually do
the same thing in just ten
seconds. So the difference between exponential complexity
and polynomial complexity is
just out of this world and then obviously if we could run this
algorithm it would pose a big
threat to um basically the whole cryptosystems as it is deployed
because the base of this whether
it is um for RSA or elliptic curves or for digital signatures
ECDSA which is using bitcoin or
for uh a key exchange like Diffie-Hellman which is mainly
used in everywhere you go uh on
SSL or TLS exchanges so the base foundation of this is used
virtually everywhere in today’s
internet. So they would be a big threat. So let’s explore a
little bit um how Peter Shor
came up with his algorithms. What is actually needed and how
they work in uh in reality. So
now we need to a did a little bit of an introduction into
quantum computing and it only
gets as deep as I thought we need to go to understand how
Shor’s algorithm works and uh
what we need to understand and um uh so hopefully it-its not
its not too bad. So basically
there are two main types of quantum computers right now. One
is called gate based quantum
computers. That’s a big chunk what everybody’s working on. All
the big guys IBM, Intel,
Microsoft, Alibaba they all working on gate based quantum
computing which is called
universal quantum computing because I can solve virtually
any problem similar to a
classical computing on this computer. There is a different
computer um uh called quantum
annealers or Adiabatic quantum computing which is was the first
quantum computer that was
available was from D-wave. And D-wave computer this adiabatic
quantum computer is not a
general quantum computer. You cannot solve every problem on
this quantum computer. It is
only specialized to solve a particular optimization problem
so it’s very much um you can
look at this basically as a physical system and physical
systems tend to always end up in
the lowest energy state which we call the ground state in this
system. So if I can now define a
function that I want to solve and I basically define those
function in a way that the
lowest energy state is basically the same as the solution to the
optimization problem I can use
this physical system to solve the problem that I have because
I know this physical system will
end up in the lowest energy state in the ground state. And I
know then this also tends this
also represents the state when my optimization problem reaches
the lowest state. And there is
this really cool um theorem which actually guarantees to me
that I end up in the lowest
state that there is. You can really this of this kind of like
mountains and valleys. And you
can end up in a valley that is just halfway through and you are
not really in the lowest state.
But there is a theorem um uh we are gonna explore that’s a
little bit which guarantees
which gives me a way how we can really be at the lowest state so
we can solve or I can find the
optimum solution to this optimization problem. But it is
really just solving optimization
problems. The gate based quantum computing is really a general
quantum uh general computing um
uh architecture where you start with an input. You apply all
sorts of different calculations
to it. Technically these are all gate based calculations. You do
an end gate. You take two qubits
and do something to it you get a result. But essentially you have
an input you calculate something
and you have an output. And it’s basically uh you can calculate
uh every uh everything you want
to calculate with these universal quantum computers
while quantum computers like
D-wave’s can only solve optimization problems. But
actually, as it turns out both
approaches can be used to solve the factorization problem. And
uh we have Shor’s algorithm from
1994 which uh uses gates to uh solve this problem. And in
Quantum Annealing we have
various approaches since 2002 and I’m going to explore those a
little bit in uh in the next
couple slides as well how they work to actually um uh solve the
factorization problem as an
optimization problem. So uh let’s dive a little bit into
quantum computing and what I
need to understand to to explore a little bit Shor’s algorithms
and really with the idea of
giving you an understanding of how can someone derive an
algorithm that gives me now such
a dramatic improvement over an classical algorithm which takes
um exponential time uh to solve
So the basic building blocks for uh quantum computers are what we
call qubits. qubits is the
equivalent of uh classical bit. Classical bit is either zero or
one. A qubit is now a you can
almost think of it as a quantum mechanical system which can be
in any state you want it to be.
And you actually don’t really know what state it is. But once
you measure this quantum
mechanical system it is either gonna be zero or one. And this
is an uh this is something that
we are going to explore it later on that why before we measure
this system we don’t know which
state it is but it can actually be in a superposition. It can be
in a state where all of these
qubits can um interact with each other and only at the very end
of my processing step I will
measure the system and all of those superpositions state will
basically terminate and I know
it is either zero or one. But it’s really a quantum mechanical
system you don’t really know
what it is. It’s neither zero. It’s neither one. It is
something in between. Uh Quite
often we assign variables to it and here you can see a
representation of one of those
qubits. We have two bases zero and one which basically
represent. Uh this zero means if
I represent the qubits in one hundred percent of the cases I
will get the measurement outcome
of zero. The one means in one hundred percent of the cases of
measurement it will give me the
measurement outcome of one. And now qubit is in the
superposition of those two with
alpha and beta. The two complex numbers I can represent those
and uh that uh can now define
the state of this particular qubit. Now we call alpha and
beta probability amplitudes
because if I measure this particular um uh qubit I will
now get the probability of the
measurement outcome for uh to get the measurement outcome zero
the probability is going to be
alpha squared. And the probability of getting the
measurement outcome of one is
going to be beta squared. Remember when I measure this
particular thing even though it
is two complex numbers associated with it it is going
to be either zero or one with a
certain probability associated with it and the probabilities
really are defined by those two
numbers and basically to the square for uh um alpha and beta.
Uh we know right now is going to
end up in zero and with those two numbers I can represent
those qubits it’s basically a
mathematical representation of the quantum mechanical system uh
that the quantum computers are
operating. But remember all of these measurements and
everything we do in the quantum
world is probabilistic. Everything’s just a probability.
I can put a quantum in a state
where I can tell you in exactly half of my measurement is gonna
be zero and half of my
measurement is gonna be one. Which is perfect for random
numbers for example because I
can tell you, hey, you don’t really know whether it’s zero or
one. It’s exactly equal
probability of getting zero and one so I just take one qubit.
Measure it five trillion times
and I get five trillion random bits. But obviously I don’t
really know whether I get zero
or one. It’s all defined by probabilities. Which has a big
implication on the algorithms
because the algorithms will also only give me probabilities.
There’s no algorithm that can
give me I run through this algorithms once and it will give
me yes it is this answer. It
will always only give me yeah I think with 83 percent
probability it is going to be
this answer for example. So quite often you run these
algorithms multiple times to
really see um uh uh uh where you end up with. The second um uh
principal that we need for
Shor’s algorithm is the concept of entanglement and uh that gets
slightly philosophical. Um I
wanna focus a little bit more on the mathematical part of this.
Entanglement is basically a
property where I can have two qubits and I know that there is
some correlation between those
two qubits. In the classical world I have two bits and the
two bits are completely
independent of each other. Neither of those bits will
interact with the other and if
this bit is one it doesn’t matter what this is. In the
quantum world I can have a a
relationship a correlation between those two qubits. And a
simple example is a bell state
of two qubits. So this state is here a state where you have two
qubits. In this funny notations
the first zero is the value of the first qubit. The second zero
is the value of the second
qubit. But if I would measure this qubit here and suppose I
measure the first qubit as being
zero it cannot be the second one because y’know the first one the
first qubit was zero. So the
second qubit has to be zero as well. I know that the second
qubit is gonna be zero simply
because I measure the first qubit. And there’s no way
because I don’t have zero ones
or one zero in there that the second qubit could something
different than zero. So I take
basically two qubits. Give them into this quantum mechanical
system. Prepare this bell state
and now I have two qubits that are separate from each other but
in this quantum mechanical
system those qubits are now correlated or what we call
entangled. And now I could give
one qubit to Alice and send her to the moon and one qubit to Bob
and send him to Mars. And I know
that if Alice looks at her qubit and says “oh I got a zero” I
know Bob has a zero as well.
Even though there is no communication between those
simply because there is this
correlation these properties now I need obviously those two
qubits I need to prepare them
together and then I can send them anywhere I want and they
are now correlated without any
communication in between those two. There is lots of
philosophical implications
because I can give I could put those two qubits light years
away from each other and did I
really find a way of communicating faster than light?
No I didn’t because if Alice
measures its gonna be zero. If she wants to tell Bob “Hey I
measured zero” she needs to
communicate this information to uh Bob which obviously uh she
needs uh a few light years uh to
do so. But it’s an important principle we gonna use in Shor’s
algorithm as well. And the main
thing for you to understand is the um exponential large size. I
can look into when dealing with
these quantum systems. Let’s suppose I take two classical
bits. I can uh represent four
possible states with two classical bits. But only one of
them at a time so y’know if uh
you see the four states there. My system with those two bits is
in one of those states at any
one point at point in time. In a quantum world I can take two
qubits and basically at the end
when I measure this system it’s also gonna be in one of those
four states. But before I
measure this system because of superposition those qubits can
be in all four states at the
same time and only when I measure the system the system
will collapse one of those four
states. And this is exactly now a situation we are gonna explore
it. If you have n qubits I can
represent two to the power of n state while I do calculations I
still at the end of the day need
to know what the result is uh of my calculations so I need to
measure at some stage and the it
will collapse obviously to um uh those end states but during
calculations I have two to the
power of n states which is a massive amount of uh um uh
states that I can represent with
just a few amount of uh of qubits. So now I now I have
everything kind of to look into
Shor’s algorithm and how it and how it works. Um uh and we are
gonna look into this. So the
main idea for that Shor had is actually that if I want to look
into how to factor uh N into p
and q into hose two prime number I don’t actually have to solve
that problem. That problem is
equivalent to a different problem. And basically he looked
into number sequences and he
realized from number theory that you have a number sequence for
example uh you look at the
number sequence here you multiply the previous number by
two. So you have 1, 2, 4, 8, 16,
32. If you now do if you now use this number sequence and do this
mod 15 for example in this
example. You end up with this number sequence 1, 2, 4, 8, 1,
2, 4, 8, 1, 2, 4, 8. This is
what we call a periodic um uh sequence. So it is always gonna
be the same uh um kind of
sequence of 1, 2, 4, 8, and we can now define a um uh uh a
number which is called a period.
Which is four which is basically the number of the amount of
numbers before it repeats itself
and um uh the underlying algorithm from Shor is that if I
want to find out the factors for
this number N. If I want to find this p and q I can actually
transform this into problem of
finding the period R and that turns out for that problem I can
run very easily on a quantum
computer. So basically um uh if I look into this and the cool
thing is and I’m gonna show you
on the next slide the mathematics behind it is
actually basically very trivial
basic level of linear algebra gives you everything to
understand how this works. So
the only thing you need to accept is that out of number
theory there’s a theory which
basically says this theory this function f(a) x to the power of
a mod N is a periodic function
um if x has um particular properties and now I only need
to find uh the number uh the
period R and with this I have my algorithm Shor which we run
through in quantum detail
actually but essentially it’s comprised of three phases. First
I turn this factoring problem
into a uh period finding problem and that’s actually trivial.
Then I use a quantum computer to
actually give me this period R to solve this period R the
classical computer is again,
really really hard actually on the classical computer still is
of exponential complexity which
mean that this algorithm on a classical computer does not give
me any advantage whatsoever. But
I can use a quantum fourier transform and that gives me the
speedup and then by once have
the period. R you can really very trivially um uh use this to
find the factor so stage one or
step one and step three are really trivial. Step two is
where all the magic happens and
that’s really where the main speedup um comes. Don’t wanna go
into two much detail but it is
really very simple so I think you can uh download the slides
and you can look through this. I
know that f(a) is periodic. I know that x to the power of zero
is one. I mean, everything to
the power of zero is one. And if R is now my period I know
because the function’s periodic
that x to the power of r mod n equals one two. Equals the same
what it was before because is
one period. And really with basic linear algebra I can use x
to the power of r equals x to
the power of uh a half to the power of two. And i can uh um uh
just write this in a different
form which gives me this um uh this multiplication of two
numbers that gives me xero uh
mod n. So if I can use this if I had this R I ha- I have these
two numbers so but if those two
numbers um uh mod N is uh uh those aren’t integers of
multiple of N because their
product is zero mod n so that means that they’re integers
multiple of n so either those
are directly factors or if they are not directly factors each
one of those has a factor in
common with a number I want to look at. So the greatest common
divisor which is actually um not
too hard to computer um classically it is just an n
squared complexity so by
computing the greatest common divisor for each of those
numbers with n I have my factors
uh for uh for n and uh that is really simple. But to get to
this R is really really hard.
But I can put this together uh in a really quick example. Let’s
suppose I have N equals 15. Now
everybody can calculate in their head that prime numbers are 3
and 5. Basically I choose any
integer between 1 and 15 and really lets for the sake of
simplicity let’s use x equals
two. So you can see my period here on mod 15 is 1, 2, 4, 8 uh
so I have the period 4. So I can
see this. That’s the really hard part to uh calculate But with a
period 4 the greatest common
divisor of x to the power of uh uh R half is R is four so R half
is 2. Uh X is 2 so that is two
to the power of 2 which is four. So the greatest common divisor
of 3 and 15 and 5 and 15 so uh
so uh four minus one and four plus one is obviously 3 and 5.
And when you calculate the
through action in every case you come up with uh 3 and 5. So
that’s exactly what Shor’s
algorithm is all about. But the really hard part is uh figuring
out what is this period R and
this is kind of where the quantum uh compu- quantum
algorithm comes in. And those
computers, those quantum algorithms always work in the
same principal. You basically
you initialize basically the result that you want to see and
say let’s think of we want to
get a 256 bit number or 2048 bit number and you basically every
bit every bit of this bit
recommendation is either gonna be zero or one. So you basically
put this in an equal uh
superposition so every bit you basically put at fifty percent
zero and fifty percent one
because you really don’t know what it is. So it’s really kind
of like uh at fifty percent.
Then you run through this Quantum Fourier transform which
will use amplitude amplification
so with every duration of this algorithm those amplitudes will
go toeither one or to zero which
is gonna be the final result. And you run this through uh a
number of times and then you
measure it at the end and you will see when you end up with.
I’m gonna have an example of
this uh when we run this through on a on real quantum computer.
So just to um uh summarize.
Shor’s algorithm altogether is fairly simple. You choose any
random number a which is uh
smaller than N. You compute the greatest common divisor. If this
is not one. Actually you found a
you found a factor and then you are done. But that is uh
obviously uh most likely not the
case. I use my quantum computer to find this period R and once I
have R I just need to find the
greatest common divisor of those uh two uh two terms and I’m
done. So um uh another example I
choose randomly uh number seven. Calculate period r, R equals 4.
I have the greatest common
divisor 48 and 15 and 50 and 15 gives me uh 3 and 5 so it uh all
works fine. I can now use this
and use uh um a livbrayr a toolkit called Qiskit which is
an open source toolkit there’s
now at least 5 or 6 open source platforms how you can use
quantum computers and how you
can program quantum computers um either on quantum simulators or
on real quantum hardware. And i
gave you some references here you can look at those it’s
actually kind of fairly easy um
uh to go through. But they also have the same and here’s an
example of this amplitude
amplification. Basically in the end you see all of the
possibilities what the my prime
numbers could be. They all in the same probability of what
they could be. That’s my
starting point. And once I run through this algorithm and I ran
through this uh Shor’s algorithm
on from these references. The amplitude of the correct results
have now been amplified and the
amplitudes of the wrong results have now been kind of like gone
down to zero. And I actually see
that these two results R equals 0 and R equals 4. R equals zero
is obviously trivial um uh
probability so I discard this and I end up with R equals 4. So
this was now executed on a
quantum simulator. Quantum simulator I can simulate a
quantum state on my normal
computer. But remember in quantum computing we exploiting
this fact that I have this
massive large space of 2 to the power of N so I’m gonna really
travel simulate more than
hundred qubits or so on a normal computer and um uh uh but for
smaller ones uh for
demonstrations it is actually quite cool. So the cool thing is
IBM has a quantum computer that
you can publicly access you can write a uh a quantum computer
program executed towards their
cloud. It’s very simple you just change hey my backend is the
simulator you change the backend
to uh IBMs quantum computer. Um and if you execute this against
a real quantum computer. It is
just a 5 qubit quantum computer um uh right now. I still get R
equals 4 with the highest
probability. But you see there’s lots of other probabilities and
those probabilities are
representative of all the errors you have in the system simply
because those quantum computers
that we have right now are really pretty bad. What they are
what we call noisy. They don’t
produce the correct result. Because they’re noisy they
produce lots of wrong results.
Now repeat- by repeating my algorithms lots of times I can
still get around this fact and
obviously in this case I still have R equals 4 the highest
probability. But obviously that
has big implication of performance because I need to
now repeat these um these
algorithms much more and obviously I will end up in debt
cases because obviously the
noise will basically um uh reduce the speedup in the
quantum effects to zero and it
basically collapses to um uh a um a classical computation that
I have. But the cool is actually
with Qiskit as well there there is libraries for every quantum
algorithm that y’know that
people know and they kind of uh provide these libraries. If you
wanna run Shor’s algorithm to
factor a prime uh to factor any numbers. You just import Shor’s
algorithm from Qiskit aqua which
is a which is a library. You just say alright I want to
factor this number N equals 15.
I use a simulator. I do this uh 1,000 times and uh off I run.
It’s instant and I get a result.
How cool is this that you can run this uh run this against a-
against a Quantum computer and
the only thing you need to do in this example is if you run this
against real quantum computer is
you change the backend from the simulator to a different backend
and now there’s a callout to
IBMs uh quantum computer to run this uh on their backend. It’s
actually really really cool and
this feeling when you run a quantum computing software for
the first time is actually quite
cool. So I encourage everybody to look at Qiskit or various
quantum computer libraries and
to play around with this. So the problem obviously is and you
guessed it is in order to do
anything meaningful I need lots of qubits. So in order to use uh
Shor’s algorithm to um uh to
break RSA 2048 I need 4,000 qubits and I need 4,000 proper
qubits meaning without any
noise. I need for the time of the computation there can’t be
any noise on the computation as
well. And it’s not really a surprise because when Shor came
up with this in 1984 there
weren’t any quantum computers. He didn’t have to worry about
hey can I really implement my
algorithm or not. He really just came up with this system and
method. So um it was never
really meant to run on a quantum computer and um right now lots
of people look at Shor’s
algorithm and they say alright uh kind of right now we have 70
qubit so its every the qubit
count doubles every year whatever so it’s gonna be
another ten years before um we
have Shor’s algorithm. Nobody’s gonna run Shor’s algorithm
because it was just a theory. So
let’s look at some of the-the uh research where people took
people took Shor’s algorithm and
modified them and optimized them to run on real quantum uh
quantum hardware. So the first
one was Fowler in uh in 2012. Basically the first approach was
really kind of I need to tweak
this algorithm so it can be so it can sustain errors. Because
Shor’s Algorithm was really
under the assumption there’s no errors or the qubits are
fantastic uh no errors so
basically they used what is called the surface codes to
allow for errors to occur and
the error rate is 0.1 percent of the uh of the gate error rate
and um uh Fowler came up I can
run Shor’s algorithm and I can factor 2048 bit number but I
need one billion qubits to do so
which is obviously a massive amount uh in terms of over it um
to run this. So that was in
2012. Not to long a- not too long ago. And then in 2017 with
further optimization from O’
Gorman we suddenly kind of like had uh had an algorithm where it
reduces one billion qubits to
230 million qubits uh in 2017. And that’s really an
optimization the physical
connectivity of those qubits. And uh then Gheorghiu kind of
reduces further to 170 million
qubits so you can see there’s algorithmic improvement without
any hardware improvements
obviously that’s happening at the same time as well but
obviously I get down from 1
billion qubits to right now 170 million qubits. And the biggest
um uh contribution was from
Gidney and Ekera from uh um uh Google and uh University in
Stockholm where they uh provided
paper just not long ago earlier this year where they uh looked
into how they could do the same
thing that everyone else is doing with just 20 million
qubits. Now we went in 2012 with
1 billion qubits to 2019 to 20 million qubits and we are far
from the end of the research
there in terms of optimization uh to this problem. Now I won’t
go into too much detail of this
uh of uh what they do but basically they also look into
lots of optimization of how
things work. And that basically also similar to Shor not really
look into factoring the numbers
directly so that basically convert this factoring problem
into Shor Discreet Algorithm uh
problem and um uh they have a part that is computed
classically and a part that is
computed um quantumly on a quantum computer. And they can
show that in order to find p and
q they can come up with obviously they know what n is
which is uh the multiplication
of those two. They can come up with a number where they know
that the addition of these
numbers is these or these known. Sol if they have two uh
equations for two variables
which they can fairly easily solve fairly easily is obviously
an overstatement because they
still need uh 20 million uh qubits uh to do so. Um uh but
obviously the uh the um
reduction from 1 billion qubits to 20 million qubits is uh
massive and uh I expect in the
next couple of years there’s gonna be lots of optimization
through Shor’s algorithm and
especially to Gidney and Ekera’s um uh algorithm where this is
gonna be uh reduced uh further
on. Obvuiously 20 million qubits is still a long way away from uh
quantum computers that are
accessible today um uh where we are in the realm of slowly below
100 qubits um uh at this point
in time. So I want to spend the next you know or the last ten
minutes of my presentation on
the process of quantum annealing. This is the second
type of quantum computer and uh
that is actually what is quite surprising to me even though
everyone is talking about Shor
and the implication of cryp-cryptography. Actually
quantum annealing right now is
much much further ahead in terms of solving this factorization
problem. And we are going to
look into a little bit how uh these algorithms work. So as
mentioned before quantum
annealing those computers are really computes where it can
solve optimization problem. I
need to I need to define my problem as an optimization
problem and then basically
quantum annealing computer can take this problem and then find
uh minimum of this uh problem
because it represents a physical state and I know the physical
state will always end up in the
ground state and I can read in this ground state and I will
have the solution to my problem.
And there is really a cool a cool theorem um uh where you’re
gonna find you wanna go into the
lowest point. You wanna find this lowest point on the right
hand side. So how do we find
this lowest point and not get caught up in those uh minimums
uh in between. And there’s lots
of ways how you can do this from the uh from the physical system.
And there’s really cool case on
this quantum annealing case where there is a theorem that
says if I start in a really in a
very easy quantum mechanical system. In this really easy
quantum mechanical system I know
the ground state. So this is my problem I want to solve is here.
I am starting here and I really
know where I am. I can now slowly evolve and adiabatic
means slowly evolving this state
from this here to the state where I really wanna be and now
this theory gives me a guarantee
or physical proof that I will end up in the in the maximum in
the optimal minimum of the
problem that I wanna solve. And it’s really cool so I have
Hamiltonians or functions that
define a physical system but basically if you look at the
first function if you put in s
equal zero you end up in this high H zero which is my easy to
understand system where I know
the local minimum and in my calculation I slowly moves from
zero to one and if I am at one I
am in the stage high H one which is the problem that I really
want to solve. But this uh
adiabatic theorem guarantees to me that I will end up in the
maximum minimum for the problem
that I really want to solve. Which is really really cool
because it gives uh I know I’m
not going to be caught in some local minimum. But still
essentially I wanna solve for
optimization problem. How do I do this. And the first research
came from Burges in 2002 from
Microsoft. Where you know he provide a foundation of hey I
wanna solve basically I wanna
look into the problem n equals p times q. I am looking for p and
q um uh so that this equation is
true. So I just need to solve this I need to write this as
optimization problem. And
basically he rewrote this as N minus pq squared and this is
always a positive function. Is
always greater than zero. And this is obviously only zero if N
equals pq. And if you write this
way you have what’s called a QUBO a Quadratic unconstrained
binary optimization problem
which you can happily run on any quantum annealer that is out
there. And you basically use
binary representation that is really just a fancy way up here
of writing P i and Q i but just
the i-th bit it’s either zero or one. And you basically now write
this down and it’s a very simple
example. My example 15 is 5 times 3. Now um uh in binary
notation p equals x1,1. The last
bit always has to one because the prime number can’t be an
even number. And I just you
know, n minus pq squared I just write it through and kind of by
hand say oh this function I need
to minimize now. And I can run this against D Wave’s quantum
computer and if I find the
minimum I know n equals pq because that’s by definition a
positive function. So I can use
quantum’s uh D’wave’s quantum computer they provide a library
as well and you see the link
here you can download it. It’s basically same thing you just
call factor P. P is my uh my
product and I can run this on uh D’wave’s quantum computer. The
problem is if I run this without
any optimization I need n squared qubits for this so I
mean the number of qubits that I
need really kind of like grow quite heavily and for larger
numbers is not sustainable uh to
do. But I wanted to show you it’s all probability so if I run
this one time I end up with um
uh my for 15 for the p and q for my two prime numbers is one and
seven which is obviously wrong
so I run this once and I didn’t really end up in the uh in the
right spot. But I run this five
times and now I already have 5 and 3 is already 60 percent um
uh you know probabilities. And
if I run this fifty times you know I know my prime numbers are
already 3 and 5 so I know I need
to run those quantum algorithms more and more often to make sure
I end up in the same results. Um
I’m gonna skip over some of those things because virtually
all optimizations of now this
base you know of of Burgess’s work where he basically looked
into hey my multiplication
matrix that you write out as a function to be minimized there
can be lots of optimizations
virtually all of the work that I present here now is based on
optimizations of how you do the
multiplications down below here. If you’ve ever done
multiplications by hand you know
you start on the right and you kind of multiply the lowest
numbers and it carry overs to
the left and virtually all of those optimizations um uh go
through this how I can do this
multiplications much easier. Dridi and Alghassi did some work
in 2016 where they used some of
these uh optimizations to remove some of the all of the degrees
so they were already able to
factor a number greater than 200,000 with almost 900 qubits
now D waves qubits on quantum
annealing are not as don’t have to be as good as universal
quantum computer qubit so D wave
announced a system with uh I think around 5,000 qubits for
next year. So 900 qubits is what
was available back then on universal quantum computers. The
biggest prime number is less
than 100 and they these guys in 2016 could already now factor a
number that was over 200,000.
The big breakthrough was from Jiang et al in Indiana in uh
April 2018 and it is really kind
of mindblowing uh you see the next one which was really just
uh two months after really
around optimization of this multiplication map and they have
now raised. They could factor a
number which is greater than 350,000 with just 94 qubits.
Remember D-wave comes up with
5,000 units quantum computer next week um next year. Um uh
and it’s all based on this
optimization uh problem that we solve called factoring and with
optimization to the
multiplication table. And then Peng in two thousand uh in uh
earlier this year really um uh
and you can see this uh submission was received in July
while the previous submission
was I think uh submitted in April or something it was just
months after. Optimizes even
further and they’ve been able to factor a number that was greater
than one million with just 90
qubits. So that’s already 20 bit number. So right now when you
look into the problem of hey can
I use a quantum computer to uh factor prime numbers. Universal
computers and Shor’s algorithms
are nowhere compared to uh quantum annealers. And with
quantum annealers I can already
um uh um do this with uh 20 bit numbers. So um there’s three
things really interesting. So
they they can run this on already existing hardware today.
And all of those algorithm
that’s a really big takeaway um uh that you have. To do this I
don’t just have one quantum
problem that I wanna solve. It’s always a hybrid model of some
classical compu-computation and
some quantum computation. I really use classic computer what
he’s good at and quantum
computer what a quantum computer is um is um good at. So um my
point is quantum annealers are a
thousand fold better right now than Shor’s algorithm and
universal quantum computers. But
because they are too noisy right now we are far away from
breaking anything that is uh in
used in practical terms. Right now the biggest number is a 20
bit number. But obviously we
know uh those two uh kind of like converging curves here. The
algorithms are getting better
and better. At the same time the quantum hardware gives me more
and more qubits as well. So both
of them will actually have a big impact. I can’t just rely on my
predictions saying hey the
number of qubits grow by 15 percent every year so I’ll be
fine for the next 50 years.
You’re neglecting the improvements that the algorithms
uh will make over the next uh
over the next uh couple of years too. So a couple of uh myth and
reality. Shor, nobody is gonna
implement Shor on any quantum computer whatsoever. Um uh Shor
was a theoretical work. There
are practical work um uh you know derivations of this work
that will be implemented. Um at
some point obviously on the on the base of Shor’s algorithms
people will break um uh the uh
the RSA encryption. It is a matter of time. Now we can argue
whether its ten years, twenty
years, fifty years. But we are only arguing about the time. We
are not arguing about arguing
about that it will happen. And obviously there’s lots of cases
where this is already has an
impact right now. If I have bitcoins right now and my public
key is known. I don’t care
whether it takes me 20 years to uh get the private key to those
uh to those bitcoins. I figure
in 20 years there’s you know one and a half million bitcoins from
Satoshi flying around which is
around 12 billion dollars right now. Hey if someone come to me
and say Hi Chris you know can
you bring me quantum computer. Hey it’s really hard it takes me
12 billion dollars you know. Hey
here’s 12 billion dollars right there. [laughter] So um um so
anyway uh it takes it will be
quite a while but I want to [inaudible] off the algorithms
started this talk talking about
how I trust the asymmetric word of the RSA word. But there’s
plenty of work and this is uh
kind of you know from this Chinese paper in the very end.
That’s the that’s the uh uh the
end statement. There’s plenty of work on the way right now to use
quantum annealers or to look
into symmetric uh encryption. So if you say hey I just use
symmetric encryption I find that
might not be holding up for too long and I thank you very much I
am out of time. Thank you very
much for your time. [applause] Do we have time for questions?
We don’t have time for
questions. You can find me anywhere if you have some
questions. Happy to engage with
you. Thanks so much!

15 comments

Leave a Reply

Your email address will not be published. Required fields are marked *