00:00:00.100,00:00:05.172
>>How many people know about uh
quantum physics? Eh, yeah? So I
was looking at this uh I was
00:00:05.172,00:00:11.545
looking at this this this talk
synopsis and I’m like maybe this
is gonna be a good talk. >>Maybe
00:00:11.545,00:00:16.550
Not >>Maybe it won’t. [laughter]
I guess I won’t really know
until I take a look at the talk,
00:00:19.453,00:00:24.458
yeah? Learned that from a baby
book. Yeah. Awesome Alright so
let’s all give Andreas a big
00:00:26.526,00:00:31.131
round of applause for coming all
the way to Vegas from Sydney
Australia to talk to us about
00:00:31.131,00:00:38.005
quantum cryptography. [applause]
Have a good time man. >>Thank
you very much. Alright. Welcome
00:00:38.005,00:00:44.511
everybody. Yeah after that
introduction hopefully you walk
away and learn something in this
00:00:44.511,00:00:50.651
talk. So, um quantum computing
if you read whatevers in the
press you either think we are
00:00:50.651,00:00:55.088
completely doomed and you know,
the internets gonna end. Or uh
nothings gonna end because they
00:00:55.088,00:00:59.126
will never exist so I thought I
would explore this topic a
little more from an algorithmic
00:00:59.126,00:01:03.196
point of view and really see
where we are. Not so much on the
hype but more really what are
00:01:03.196,00:01:09.436
the algorithms uh that we talk
about right now. So um I started
various companies in the
00:01:09.436,00:01:15.175
securities space you know
starting in 2002 which um makes
me feel slightly old um right
00:01:15.175,00:01:19.580
now, but first I am speaking at
Defcon I am very happy about
this y’know long term attendee
00:01:19.580,00:01:25.185
but never spoke here so let’s
get right into this. So when you
talk about cryptography we
00:01:25.185,00:01:30.390
mainly y’know look into two
different um types of
cryptography. One is a symmetric
00:01:30.390,00:01:37.331
cryptosystem which is a
symmetric shared key y’know kind
of AES for example. Both sides
00:01:37.331,00:01:42.736
encrypt and talk to each other
with the same key and with
asymmetric uh cryptosystems
00:01:42.736,00:01:46.974
which use public key
infrastructure you would
basically use a public key to
00:01:46.974,00:01:52.045
encrypt the message and a
private key to um decrypt it. Um
there’s various forms of this uh
00:01:52.045,00:01:57.050
obviously for the digital
signatures as well. And um in in
this realm um virtually every
00:01:59.186,00:02:04.291
cryptosystem right now that is
deployed anywhere is what we
call computationally secure.
00:02:04.291,00:02:10.430
They are secure in the sense
that there are known algorithms
that can break them but all the
00:02:10.430,00:02:16.737
algorithms that can break them
are not easy to in the sense
that y’know that if I wanna
00:02:16.737,00:02:21.742
break in a y’know 2048-bit RSA
key with a normal computer takes
me a couple trillion years which
00:02:24.111,00:02:30.417
means I am secure even though
there’s known algorithms that
can break them. There are
00:02:30.417,00:02:35.722
information-theoretic algorithms
out there most notably an
algorithm called um a
00:02:35.722,00:02:40.694
one-time-pad or vernam ciphers
but they're really tricky and
not really practically usable
00:02:40.694,00:02:46.233
for example a one-time-pad you
do need to use the same amount
of keys as you want to transmit
00:02:46.233,00:02:49.936
so for example if you want to
transmit a one megabyte file you
need to have a one megabyte key
00:02:49.936,00:02:55.142
basically for every byte you
need a different um uh for every
byte data you need uh one byte
00:02:55.142,00:03:00.013
key so you would have to manage
massive amount of uh key
material which is not really uh
00:03:00.013,00:03:05.052
practically but I mean they do
exist but outside of this
virtually every uh cryptosystem
00:03:05.052,00:03:11.558
is just computationally secure.
And um uh when you look at this
uh quantum algorithm and I’ll go
00:03:11.558,00:03:17.264
into quite some detail about
this for those two different
types of algorithms. It is much
00:03:17.264,00:03:22.235
more interesting to look at the
asymmetric part of the uh of the
cryptosystems because in the
00:03:22.235,00:03:28.008
symmetric part there is a
quantum algorithms as well
called uh Grover which basically
00:03:28.008,00:03:33.013
looks into um a provided
quadratic speed up to the
classical um uh version.
00:03:35.148,00:03:38.285
Basically in the classical
version if I want to look for
the shared key I need to
00:03:38.285,00:03:43.123
basically brute force every
combination which obviously
takes forever. I get a squared
00:03:43.123,00:03:48.662
root up um a squared speed up in
the quantum version which is a
fantastic speed up y’know if I
00:03:48.662,00:03:52.866
can speed up a hundred fifty
trillion years but it is
obviously a hundred fifty
00:03:52.866,00:03:57.604
trillion years uh to break so
that’s not really that
interesting. So we want to focus
00:03:57.604,00:04:02.843
here on the asymmetric part
where um uh the speed ups that
quantum computers can provide
00:04:02.843,00:04:08.949
are massive and um we’re going
to go into quite some detail uh
why uh their speed up is so big
00:04:08.949,00:04:15.755
as it is and uh how they work.
So let’s revisit just a little
bit of how RSA encryption works
00:04:15.755,00:04:21.194
and it's really just a basic
introduction so we can use them
uh to understand how the quantum
00:04:21.194,00:04:26.199
versions of these algorithms
works. Basically, I choose two
prime numbers p and q and um uh
00:04:28.201,00:04:33.907
with those I just multiply them
get the number n. Now with the
number n I can calculate this
00:04:33.907,00:04:39.012
lambda function which is a
carmichael function which just a
function I can easily calculate
00:04:39.012,00:04:44.818
this and once I have this I just
chose another parameter e which
is smaller than the lambda and
00:04:44.818,00:04:51.558
the value. And then this n
together with the number e is my
public key. I can give this to
00:04:51.558,00:04:57.264
everybody out there who I wanna
choose to do um uh the
asymmetric encryption. And I
00:04:57.264,00:05:03.937
basically retain my private key
which is this uh um number d
here which is just the modular
00:05:03.937,00:05:08.942
inverse of the number e which is
the uh public key. Obviously mod
lambda n. There is always mod
00:05:13.380,00:05:19.286
lambda n in this uh scenario
which is a private key that I
retain. And with this private
00:05:19.286,00:05:23.890
key now with this scenario. I
can now look into hey I can now
encrypt something and send
00:05:23.890,00:05:30.864
something um from Alice to Bob
and as everybody knows with
asymmetric encryption I can only
00:05:30.864,00:05:35.869
encrypt something that is
smaller than my key so if I have
a two four, um 2048 width key I
00:05:37.971,00:05:44.778
can only encrypt something that
is smaller than uh 2048 um so I
need to pad my plain text into
00:05:44.778,00:05:51.751
um a number n so I turn this big
M into small number m um uh
there is various way for this
00:05:51.751,00:05:55.455
ways for this. Um I don’t go
into too much detail but this is
where the padding scheme uh
00:05:55.455,00:06:01.661
comes in and then I basically
end up with this number uh small
m. In my ciphertext my encrypted
00:06:01.661,00:06:08.435
version’s really I just take uh
this number m to the power of e.
Mod n and thats basically my
00:06:08.435,00:06:13.440
ciphertext. And this is what I
encrypt with a public key. I can
now send this number c to uh to
00:06:15.875,00:06:20.880
Bob. Uh um receive this and um
if you have the private key you
can easily decrypt this as well
00:06:23.016,00:06:28.588
on the other side. And uh you
can easily see how this works.
It is really very
00:06:28.588,00:06:33.893
straightforward if someone has
the c and the ciphertext and the
d the private key by definition
00:06:33.893,00:06:40.300
c is m to the power of e. So you
see um uh the definition of d
was it is actually the inverse
00:06:40.300,00:06:45.305
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
00:06:47.607,00:06:53.580
private key, I can easily
recover um uh the uh the small m
and obviously by just reversing
00:06:53.580,00:06:58.585
the padding scheme I now have my
message again. So this basically
how RSA encryption works into
00:07:00.553,00:07:05.558
some detail. So my task is now I
do have a public key because its
public everybody knows what it
00:07:08.495,00:07:13.933
is. How do I turn this into
private key. Now from the
definitions it is really pretty
00:07:13.933,00:07:18.938
straightforward and simple. Um I
need to find those prime numbers
that make up this number n. This
00:07:22.342,00:07:29.049
number n is known it is part of
the public key. And if I can do
this I can easily calculate
00:07:29.049,00:07:35.655
lambda n which is really uh the
least common multiplier of
lambda p and lambda q and from
00:07:35.655,00:07:40.660
there I can easily derive the
private key d and uh I’m done.
So all I need to do to basically
00:07:43.029,00:07:50.003
go from a public key to private
key is to find those two prime
factors p and q and um that I
00:07:50.003,00:07:55.141
chose in the very beginning when
I set up my key um uh then I
have everything that I need to
00:07:55.141,00:08:00.080
do to basically derive a private
key from a public key. Um while
that sounds pretty easy and
00:08:03.283,00:08:09.356
straightforward actually to do
this and to factor this number n
into the uh prime parts p and q
00:08:09.356,00:08:15.595
is um is uh really really hard
and all of the classically known
algorithms are all from
00:08:15.595,00:08:21.334
exponential complexity. Which
means they are really really
hard uh to solve even y’know the
00:08:21.334,00:08:26.773
GNFS uh algorithms is uh
slightly sub-exponential but
still massive in style so that
00:08:26.773,00:08:32.712
gives you those assurance that
if you use any of the asymmetric
algorithms uh people will need
00:08:32.712,00:08:39.185
trillions of years to decrypt
them so they’re fairly secure
for generations to come. But in
00:08:39.185,00:08:44.657
1984 a guy called Peter Shor he
was um uh a theoretical
physicist came up with this
00:08:44.657,00:08:51.297
algorithm. If we were to use
quantum computers. Obviously in
1984 it was all just a theory
00:08:51.297,00:08:57.737
quantum computers didn’t exist
and they hardly exist today um
but the theory says he came up
00:08:57.737,00:09:02.842
with an algorithm of how to
factor those numbers in just
polynomial time. And in just
00:09:02.842,00:09:09.416
polynomial time really is a
difference that is really almost
incomprehensible. Because it
00:09:09.416,00:09:14.788
really means instead of taking a
trillion years on a classic
computer with a trillion
00:09:14.788,00:09:19.459
operations per second. Suppose
we have a quantum computer which
just does a million operations
00:09:19.459,00:09:25.165
per second. I can actually do
the same thing in just ten
seconds. So the difference
00:09:25.165,00:09:30.570
between exponential complexity
and polynomial complexity is
just out of this world and then
00:09:30.570,00:09:35.842
obviously if we could run this
algorithm it would pose a big
threat to um basically the whole
00:09:35.842,00:09:40.847
cryptosystems as it is deployed
because the base of this whether
it is um for RSA or elliptic
00:09:44.417,00:09:50.190
curves or for digital signatures
ECDSA which is using bitcoin or
for uh a key exchange like
00:09:50.190,00:09:55.195
Diffie-Hellman which is mainly
used in everywhere you go uh on
SSL or TLS exchanges so the base
00:09:57.197,00:10:01.835
foundation of this is used
virtually everywhere in today’s
internet. So they would be a big
00:10:01.835,00:10:08.808
threat. So let’s explore a
little bit um how Peter Shor
came up with his algorithms.
00:10:08.808,00:10:15.248
What is actually needed and how
they work in uh in reality. So
now we need to a did a little
00:10:15.248,00:10:21.187
bit of an introduction into
quantum computing and it only
gets as deep as I thought we
00:10:21.187,00:10:26.759
need to go to understand how
Shor’s algorithm works and uh
what we need to understand and
00:10:26.759,00:10:31.798
um uh so hopefully it-its not
its not too bad. So basically
there are two main types of
00:10:31.798,00:10:37.604
quantum computers right now. One
is called gate based quantum
computers. That’s a big chunk
00:10:37.604,00:10:42.909
what everybody’s working on. All
the big guys IBM, Intel,
Microsoft, Alibaba they all
00:10:42.909,00:10:47.714
working on gate based quantum
computing which is called
universal quantum computing
00:10:47.714,00:10:52.452
because I can solve virtually
any problem similar to a
classical computing on this
00:10:52.452,00:10:58.958
computer. There is a different
computer um uh called quantum
annealers or Adiabatic quantum
00:10:58.958,00:11:03.997
computing which is was the first
quantum computer that was
available was from D-wave. And
00:11:03.997,00:11:09.002
D-wave computer this adiabatic
quantum computer is not a
general quantum computer. You
00:11:09.002,00:11:15.008
cannot solve every problem on
this quantum computer. It is
only specialized to solve a
00:11:15.008,00:11:21.447
particular optimization problem
so it’s very much um you can
look at this basically as a
00:11:21.447,00:11:27.186
physical system and physical
systems tend to always end up in
the lowest energy state which we
00:11:27.186,00:11:34.060
call the ground state in this
system. So if I can now define a
function that I want to solve
00:11:34.060,00:11:39.065
and I basically define those
function in a way that the
lowest energy state is basically
00:11:42.001,00:11:48.207
the same as the solution to the
optimization problem I can use
this physical system to solve
00:11:48.207,00:11:52.812
the problem that I have because
I know this physical system will
end up in the lowest energy
00:11:52.812,00:11:59.252
state in the ground state. And I
know then this also tends this
also represents the state when
00:11:59.252,00:12:05.525
my optimization problem reaches
the lowest state. And there is
this really cool um theorem
00:12:05.525,00:12:10.997
which actually guarantees to me
that I end up in the lowest
state that there is. You can
00:12:10.997,00:12:15.568
really this of this kind of like
mountains and valleys. And you
can end up in a valley that is
00:12:15.568,00:12:20.640
just halfway through and you are
not really in the lowest state.
But there is a theorem um uh we
00:12:20.640,00:12:23.977
are gonna explore that’s a
little bit which guarantees
which gives me a way how we can
00:12:23.977,00:12:29.215
really be at the lowest state so
we can solve or I can find the
optimum solution to this
00:12:29.215,00:12:34.053
optimization problem. But it is
really just solving optimization
problems. The gate based quantum
00:12:34.053,00:12:40.426
computing is really a general
quantum uh general computing um
uh architecture where you start
00:12:40.426,00:12:45.898
with an input. You apply all
sorts of different calculations
to it. Technically these are all
00:12:45.898,00:12:50.970
gate based calculations. You do
an end gate. You take two qubits
and do something to it you get a
00:12:50.970,00:12:55.642
result. But essentially you have
an input you calculate something
and you have an output. And it's
00:12:55.642,00:13:00.380
basically uh you can calculate
uh every uh everything you want
to calculate with these
00:13:00.380,00:13:07.186
universal quantum computers
while quantum computers like
D-wave’s can only solve
00:13:07.186,00:13:12.792
optimization problems. But
actually, as it turns out both
approaches can be used to solve
00:13:12.792,00:13:17.797
the factorization problem. And
uh we have Shor’s algorithm from
1994 which uh uses gates to uh
00:13:22.001,00:13:26.606
solve this problem. And in
Quantum Annealing we have
various approaches since 2002
00:13:26.606,00:13:31.110
and I’m going to explore those a
little bit in uh in the next
couple slides as well how they
00:13:31.110,00:13:37.350
work to actually um uh solve the
factorization problem as an
optimization problem. So uh
00:13:37.350,00:13:43.089
let's dive a little bit into
quantum computing and what I
need to understand to to explore
00:13:43.089,00:13:48.695
a little bit Shor’s algorithms
and really with the idea of
giving you an understanding of
00:13:48.695,00:13:55.334
how can someone derive an
algorithm that gives me now such
a dramatic improvement over an
00:13:55.334,00:14:00.273
classical algorithm which takes
um exponential time uh to solve
So the basic building blocks for
00:14:03.409,00:14:08.815
uh quantum computers are what we
call qubits. qubits is the
equivalent of uh classical bit.
00:14:08.815,00:14:15.321
Classical bit is either zero or
one. A qubit is now a you can
almost think of it as a quantum
00:14:15.321,00:14:20.660
mechanical system which can be
in any state you want it to be.
And you actually don’t really
00:14:20.660,00:14:25.765
know what state it is. But once
you measure this quantum
mechanical system it is either
00:14:25.765,00:14:30.970
gonna be zero or one. And this
is an uh this is something that
we are going to explore it later
00:14:30.970,00:14:36.676
on that why before we measure
this system we don’t know which
state it is but it can actually
00:14:36.676,00:14:43.583
be in a superposition. It can be
in a state where all of these
qubits can um interact with each
00:14:43.583,00:14:49.455
other and only at the very end
of my processing step I will
measure the system and all of
00:14:49.455,00:14:54.527
those superpositions state will
basically terminate and I know
it is either zero or one. But
00:14:54.527,00:14:58.931
it's really a quantum mechanical
system you don’t really know
what it is. It’s neither zero.
00:14:58.931,00:15:03.870
It’s neither one. It is
something in between. Uh Quite
often we assign variables to it
00:15:06.672,00:15:11.010
and here you can see a
representation of one of those
qubits. We have two bases zero
00:15:11.010,00:15:16.015
and one which basically
represent. Uh this zero means if
I represent the qubits in one
00:15:19.652,00:15:25.057
hundred percent of the cases I
will get the measurement outcome
of zero. The one means in one
00:15:25.057,00:15:29.195
hundred percent of the cases of
measurement it will give me the
measurement outcome of one. And
00:15:29.195,00:15:34.834
now qubit is in the
superposition of those two with
alpha and beta. The two complex
00:15:34.834,00:15:41.240
numbers I can represent those
and uh that uh can now define
the state of this particular
00:15:41.240,00:15:47.580
qubit. Now we call alpha and
beta probability amplitudes
because if I measure this
00:15:47.580,00:15:52.585
particular um uh qubit I will
now get the probability of the
measurement outcome for uh to
00:15:56.489,00:16:01.460
get the measurement outcome zero
the probability is going to be
alpha squared. And the
00:16:01.460,00:16:06.265
probability of getting the
measurement outcome of one is
going to be beta squared.
00:16:06.265,00:16:09.535
Remember when I measure this
particular thing even though it
is two complex numbers
00:16:09.535,00:16:15.975
associated with it it is going
to be either zero or one with a
certain probability associated
00:16:15.975,00:16:21.047
with it and the probabilities
really are defined by those two
numbers and basically to the
00:16:21.047,00:16:26.052
square for uh um alpha and beta.
Uh we know right now is going to
end up in zero and with those
00:16:28.120,00:16:33.392
two numbers I can represent
those qubits it's basically a
mathematical representation of
00:16:33.392,00:16:39.398
the quantum mechanical system uh
that the quantum computers are
operating. But remember all of
00:16:39.398,00:16:43.302
these measurements and
everything we do in the quantum
world is probabilistic.
00:16:43.302,00:16:50.009
Everything’s just a probability.
I can put a quantum in a state
where I can tell you in exactly
00:16:50.009,00:16:53.946
half of my measurement is gonna
be zero and half of my
measurement is gonna be one.
00:16:53.946,00:16:57.583
Which is perfect for random
numbers for example because I
can tell you, hey, you don’t
00:16:57.583,00:17:01.454
really know whether it’s zero or
one. It’s exactly equal
probability of getting zero and
00:17:01.454,00:17:06.392
one so I just take one qubit.
Measure it five trillion times
and I get five trillion random
00:17:06.392,00:17:11.430
bits. But obviously I don’t
really know whether I get zero
or one. It’s all defined by
00:17:11.430,00:17:16.502
probabilities. Which has a big
implication on the algorithms
because the algorithms will also
00:17:16.502,00:17:21.774
only give me probabilities.
There’s no algorithm that can
give me I run through this
00:17:21.774,00:17:27.780
algorithms once and it will give
me yes it is this answer. It
will always only give me yeah I
00:17:27.780,00:17:31.884
think with 83 percent
probability it is going to be
this answer for example. So
00:17:31.884,00:17:36.889
quite often you run these
algorithms multiple times to
really see um uh uh uh where you
00:17:36.889,00:17:42.995
end up with. The second um uh
principal that we need for
Shor’s algorithm is the concept
00:17:42.995,00:17:48.801
of entanglement and uh that gets
slightly philosophical. Um I
wanna focus a little bit more on
00:17:48.801,00:17:53.639
the mathematical part of this.
Entanglement is basically a
property where I can have two
00:17:53.639,00:17:58.678
qubits and I know that there is
some correlation between those
two qubits. In the classical
00:17:58.678,00:18:02.181
world I have two bits and the
two bits are completely
independent of each other.
00:18:02.181,00:18:05.751
Neither of those bits will
interact with the other and if
this bit is one it doesn’t
00:18:05.751,00:18:07.753
matter what this is. In the
quantum world I can have a a
relationship a correlation
00:18:07.753,00:18:09.755
between those two qubits. And a
simple example is a bell state
of two qubits. So this state is
00:18:09.755,00:18:14.760
here a state where you have two
qubits. In this funny notations
the first zero is the value of
00:18:26.272,00:18:30.977
the first qubit. The second zero
is the value of the second
qubit. But if I would measure
00:18:30.977,00:18:37.249
this qubit here and suppose I
measure the first qubit as being
zero it cannot be the second one
00:18:37.249,00:18:43.422
because y’know the first one the
first qubit was zero. So the
second qubit has to be zero as
00:18:43.422,00:18:48.627
well. I know that the second
qubit is gonna be zero simply
because I measure the first
00:18:48.627,00:18:54.000
qubit. And there’s no way
because I don’t have zero ones
or one zero in there that the
00:18:54.000,00:18:59.905
second qubit could something
different than zero. So I take
basically two qubits. Give them
00:18:59.905,00:19:04.677
into this quantum mechanical
system. Prepare this bell state
and now I have two qubits that
00:19:04.677,00:19:10.249
are separate from each other but
in this quantum mechanical
system those qubits are now
00:19:10.249,00:19:16.255
correlated or what we call
entangled. And now I could give
one qubit to Alice and send her
00:19:16.255,00:19:21.260
to the moon and one qubit to Bob
and send him to Mars. And I know
that if Alice looks at her qubit
00:19:23.496,00:19:30.403
and says “oh I got a zero” I
know Bob has a zero as well.
Even though there is no
00:19:30.403,00:19:35.674
communication between those
simply because there is this
correlation these properties now
00:19:35.674,00:19:40.479
I need obviously those two
qubits I need to prepare them
together and then I can send
00:19:40.479,00:19:46.819
them anywhere I want and they
are now correlated without any
communication in between those
00:19:46.819,00:19:52.858
two. There is lots of
philosophical implications
because I can give I could put
00:19:52.858,00:19:58.731
those two qubits light years
away from each other and did I
really find a way of
00:19:58.731,00:20:04.003
communicating faster than light?
No I didn’t because if Alice
measures its gonna be zero. If
00:20:04.003,00:20:08.240
she wants to tell Bob “Hey I
measured zero” she needs to
communicate this information to
00:20:08.240,00:20:14.213
uh Bob which obviously uh she
needs uh a few light years uh to
do so. But it's an important
00:20:14.213,00:20:19.719
principle we gonna use in Shor’s
algorithm as well. And the main
thing for you to understand is
00:20:19.719,00:20:26.358
the um exponential large size. I
can look into when dealing with
these quantum systems. Let’s
00:20:26.358,00:20:31.764
suppose I take two classical
bits. I can uh represent four
possible states with two
00:20:31.764,00:20:37.570
classical bits. But only one of
them at a time so y’know if uh
you see the four states there.
00:20:37.570,00:20:43.175
My system with those two bits is
in one of those states at any
one point at point in time. In a
00:20:43.175,00:20:48.914
quantum world I can take two
qubits and basically at the end
when I measure this system it’s
00:20:48.914,00:20:53.385
also gonna be in one of those
four states. But before I
measure this system because of
00:20:53.385,00:20:58.390
superposition those qubits can
be in all four states at the
same time and only when I
00:21:00.960,00:21:06.999
measure the system the system
will collapse one of those four
states. And this is exactly now
00:21:06.999,00:21:12.905
a situation we are gonna explore
it. If you have n qubits I can
represent two to the power of n
00:21:12.905,00:21:18.811
state while I do calculations I
still at the end of the day need
to know what the result is uh of
00:21:18.811,00:21:24.550
my calculations so I need to
measure at some stage and the it
will collapse obviously to um uh
00:21:24.550,00:21:29.989
those end states but during
calculations I have two to the
power of n states which is a
00:21:29.989,00:21:35.327
massive amount of uh um uh
states that I can represent with
just a few amount of uh of
00:21:35.327,00:21:40.332
qubits. So now I now I have
everything kind of to look into
Shor’s algorithm and how it and
00:21:42.434,00:21:47.439
how it works. Um uh and we are
gonna look into this. So the
main idea for that Shor had is
00:21:47.439,00:21:52.478
actually that if I want to look
into how to factor uh N into p
and q into hose two prime number
00:21:52.478,00:21:57.550
I don’t actually have to solve
that problem. That problem is
equivalent to a different
00:21:57.550,00:22:04.123
problem. And basically he looked
into number sequences and he
realized from number theory that
00:22:04.123,00:22:10.029
you have a number sequence for
example uh you look at the
number sequence here you
00:22:10.029,00:22:17.036
multiply the previous number by
two. So you have 1, 2, 4, 8, 16,
32. If you now do if you now use
00:22:17.036,00:22:23.509
this number sequence and do this
mod 15 for example in this
example. You end up with this
00:22:23.509,00:22:29.181
number sequence 1, 2, 4, 8, 1,
2, 4, 8, 1, 2, 4, 8. This is
what we call a periodic um uh
00:22:29.181,00:22:35.487
sequence. So it is always gonna
be the same uh um kind of
sequence of 1, 2, 4, 8, and we
00:22:35.487,00:22:42.361
can now define a um uh uh a
number which is called a period.
Which is four which is basically
00:22:42.361,00:22:49.168
the number of the amount of
numbers before it repeats itself
and um uh the underlying
00:22:49.168,00:22:56.141
algorithm from Shor is that if I
want to find out the factors for
this number N. If I want to find
00:22:56.141,00:23:02.748
this p and q I can actually
transform this into problem of
finding the period R and that
00:23:02.748,00:23:09.355
turns out for that problem I can
run very easily on a quantum
computer. So basically um uh if
00:23:09.355,00:23:13.792
I look into this and the cool
thing is and I’m gonna show you
on the next slide the
00:23:13.792,00:23:18.530
mathematics behind it is
actually basically very trivial
basic level of linear algebra
00:23:18.530,00:23:22.434
gives you everything to
understand how this works. So
the only thing you need to
00:23:22.434,00:23:26.272
accept is that out of number
theory there’s a theory which
basically says this theory this
00:23:26.272,00:23:31.277
function f(a) x to the power of
a mod N is a periodic function
um if x has um particular
00:23:34.580,00:23:39.585
properties and now I only need
to find uh the number uh the
period R and with this I have my
00:23:42.121,00:23:46.258
algorithm Shor which we run
through in quantum detail
actually but essentially it's
00:23:46.258,00:23:52.097
comprised of three phases. First
I turn this factoring problem
into a uh period finding problem
00:23:52.097,00:23:57.102
and that's actually trivial.
Then I use a quantum computer to
actually give me this period R
00:23:59.405,00:24:04.410
to solve this period R the
classical computer is again,
really really hard actually on
00:24:04.410,00:24:10.282
the classical computer still is
of exponential complexity which
mean that this algorithm on a
00:24:10.282,00:24:16.689
classical computer does not give
me any advantage whatsoever. But
I can use a quantum fourier
00:24:16.689,00:24:21.160
transform and that gives me the
speedup and then by once have
the period. R you can really
00:24:21.160,00:24:27.099
very trivially um uh use this to
find the factor so stage one or
step one and step three are
00:24:27.099,00:24:30.836
really trivial. Step two is
where all the magic happens and
that’s really where the main
00:24:30.836,00:24:37.609
speedup um comes. Don’t wanna go
into two much detail but it is
really very simple so I think
00:24:37.609,00:24:44.049
you can uh download the slides
and you can look through this. I
know that f(a) is periodic. I
00:24:44.049,00:24:49.188
know that x to the power of zero
is one. I mean, everything to
the power of zero is one. And if
00:24:49.188,00:24:55.661
R is now my period I know
because the function’s periodic
that x to the power of r mod n
00:24:55.661,00:24:59.965
equals one two. Equals the same
what it was before because is
one period. And really with
00:24:59.965,00:25:04.203
basic linear algebra I can use x
to the power of r equals x to
the power of uh a half to the
00:25:04.203,00:25:09.208
power of two. And i can uh um uh
just write this in a different
form which gives me this um uh
00:25:13.846,00:25:18.851
this multiplication of two
numbers that gives me xero uh
mod n. So if I can use this if I
00:25:23.322,00:25:28.327
had this R I ha- I have these
two numbers so but if those two
numbers um uh mod N is uh uh
00:25:31.397,00:25:37.903
those aren’t integers of
multiple of N because their
product is zero mod n so that
00:25:37.903,00:25:44.109
means that they’re integers
multiple of n so either those
are directly factors or if they
00:25:44.109,00:25:50.616
are not directly factors each
one of those has a factor in
common with a number I want to
00:25:50.616,00:25:56.588
look at. So the greatest common
divisor which is actually um not
too hard to computer um
00:25:56.588,00:26:01.693
classically it is just an n
squared complexity so by
computing the greatest common
00:26:01.693,00:26:06.698
divisor for each of those
numbers with n I have my factors
uh for uh for n and uh that is
00:26:09.001,00:26:14.873
really simple. But to get to
this R is really really hard.
But I can put this together uh
00:26:14.873,00:26:19.878
in a really quick example. Let’s
suppose I have N equals 15. Now
everybody can calculate in their
00:26:19.878,00:26:24.883
head that prime numbers are 3
and 5. Basically I choose any
integer between 1 and 15 and
00:26:27.352,00:26:33.725
really lets for the sake of
simplicity let's use x equals
two. So you can see my period
00:26:33.725,00:26:39.698
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
00:26:39.698,00:26:44.703
part to uh calculate But with a
period 4 the greatest common
divisor of x to the power of uh
00:26:47.306,00:26:52.311
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.
00:26:54.913,00:27:01.086
So the greatest common divisor
of 3 and 15 and 5 and 15 so uh
so uh four minus one and four
00:27:01.086,00:27:05.858
plus one is obviously 3 and 5.
And when you calculate the
through action in every case you
00:27:05.858,00:27:11.129
come up with uh 3 and 5. So
that’s exactly what Shor’s
algorithm is all about. But the
00:27:11.129,00:27:16.301
really hard part is uh figuring
out what is this period R and
this is kind of where the
00:27:16.301,00:27:21.373
quantum uh compu- quantum
algorithm comes in. And those
computers, those quantum
00:27:21.373,00:27:26.378
algorithms always work in the
same principal. You basically
you initialize basically the
00:27:28.514,00:27:33.519
result that you want to see and
say let’s think of we want to
get a 256 bit number or 2048 bit
00:27:35.988,00:27:40.659
number and you basically every
bit every bit of this bit
recommendation is either gonna
00:27:40.659,00:27:45.464
be zero or one. So you basically
put this in an equal uh
superposition so every bit you
00:27:45.464,00:27:48.700
basically put at fifty percent
zero and fifty percent one
because you really don’t know
00:27:48.700,00:27:54.473
what it is. So it’s really kind
of like uh at fifty percent.
Then you run through this
00:27:54.473,00:28:00.913
Quantum Fourier transform which
will use amplitude amplification
so with every duration of this
00:28:00.913,00:28:05.918
algorithm those amplitudes will
go toeither one or to zero which
is gonna be the final result.
00:28:08.253,00:28:14.459
And you run this through uh a
number of times and then you
measure it at the end and you
00:28:14.459,00:28:20.065
will see when you end up with.
I’m gonna have an example of
this uh when we run this through
00:28:20.065,00:28:25.571
on a on real quantum computer.
So just to um uh summarize.
Shor’s algorithm altogether is
00:28:25.571,00:28:31.176
fairly simple. You choose any
random number a which is uh
smaller than N. You compute the
00:28:31.176,00:28:35.814
greatest common divisor. If this
is not one. Actually you found a
you found a factor and then you
00:28:35.814,00:28:41.153
are done. But that is uh
obviously uh most likely not the
case. I use my quantum computer
00:28:41.153,00:28:46.692
to find this period R and once I
have R I just need to find the
greatest common divisor of those
00:28:46.692,00:28:51.697
uh two uh two terms and I’m
done. So um uh another example I
choose randomly uh number seven.
00:28:54.900,00:28:59.905
Calculate period r, R equals 4.
I have the greatest common
divisor 48 and 15 and 50 and 15
00:29:02.374,00:29:07.379
gives me uh 3 and 5 so it uh all
works fine. I can now use this
and use uh um a livbrayr a
00:29:10.549,00:29:16.355
toolkit called Qiskit which is
an open source toolkit there’s
now at least 5 or 6 open source
00:29:16.355,00:29:21.593
platforms how you can use
quantum computers and how you
can program quantum computers um
00:29:21.593,00:29:27.599
either on quantum simulators or
on real quantum hardware. And i
gave you some references here
00:29:27.599,00:29:32.604
you can look at those it's
actually kind of fairly easy um
uh to go through. But they also
00:29:32.604,00:29:37.109
have the same and here’s an
example of this amplitude
amplification. Basically in the
00:29:37.109,00:29:42.581
end you see all of the
possibilities what the my prime
numbers could be. They all in
00:29:42.581,00:29:47.819
the same probability of what
they could be. That’s my
starting point. And once I run
00:29:47.819,00:29:53.925
through this algorithm and I ran
through this uh Shor’s algorithm
on from these references. The
00:29:53.925,00:29:59.898
amplitude of the correct results
have now been amplified and the
amplitudes of the wrong results
00:29:59.898,00:30:05.337
have now been kind of like gone
down to zero. And I actually see
that these two results R equals
00:30:05.337,00:30:08.006
0 and R equals 4. R equals zero
is obviously trivial um uh
probability so I discard this
00:30:08.006,00:30:13.011
and I end up with R equals 4. So
this was now executed on a
quantum simulator. Quantum
00:30:17.482,00:30:21.787
simulator I can simulate a
quantum state on my normal
computer. But remember in
00:30:21.787,00:30:26.391
quantum computing we exploiting
this fact that I have this
massive large space of 2 to the
00:30:26.391,00:30:32.197
power of N so I’m gonna really
travel simulate more than
hundred qubits or so on a normal
00:30:32.197,00:30:37.269
computer and um uh uh but for
smaller ones uh for
demonstrations it is actually
00:30:37.269,00:30:43.442
quite cool. So the cool thing is
IBM has a quantum computer that
you can publicly access you can
00:30:43.442,00:30:49.514
write a uh a quantum computer
program executed towards their
cloud. It's very simple you just
00:30:49.514,00:30:55.320
change hey my backend is the
simulator you change the backend
to uh IBMs quantum computer. Um
00:30:55.320,00:31:00.025
and if you execute this against
a real quantum computer. It is
just a 5 qubit quantum computer
00:31:00.025,00:31:05.964
um uh right now. I still get R
equals 4 with the highest
probability. But you see there's
00:31:05.964,00:31:11.369
lots of other probabilities and
those probabilities are
representative of all the errors
00:31:11.369,00:31:15.874
you have in the system simply
because those quantum computers
that we have right now are
00:31:15.874,00:31:20.879
really pretty bad. What they are
what we call noisy. They don’t
produce the correct result.
00:31:22.948,00:31:28.353
Because they’re noisy they
produce lots of wrong results.
Now repeat- by repeating my
00:31:28.353,00:31:33.892
algorithms lots of times I can
still get around this fact and
obviously in this case I still
00:31:33.892,00:31:38.130
have R equals 4 the highest
probability. But obviously that
has big implication of
00:31:38.130,00:31:43.101
performance because I need to
now repeat these um these
algorithms much more and
00:31:43.101,00:31:49.307
obviously I will end up in debt
cases because obviously the
noise will basically um uh
00:31:49.307,00:31:55.480
reduce the speedup in the
quantum effects to zero and it
basically collapses to um uh a
00:31:55.480,00:32:00.418
um a classical computation that
I have. But the cool is actually
with Qiskit as well there there
00:32:02.954,00:32:07.893
is libraries for every quantum
algorithm that y’know that
people know and they kind of uh
00:32:07.893,00:32:12.998
provide these libraries. If you
wanna run Shor’s algorithm to
factor a prime uh to factor any
00:32:12.998,00:32:19.070
numbers. You just import Shor’s
algorithm from Qiskit aqua which
is a which is a library. You
00:32:19.070,00:32:24.442
just say alright I want to
factor this number N equals 15.
I use a simulator. I do this uh
00:32:24.442,00:32:31.016
1,000 times and uh off I run.
It’s instant and I get a result.
How cool is this that you can
00:32:31.016,00:32:34.619
run this uh run this against a-
against a Quantum computer and
the only thing you need to do in
00:32:34.619,00:32:39.024
this example is if you run this
against real quantum computer is
you change the backend from the
00:32:39.024,00:32:44.830
simulator to a different backend
and now there’s a callout to
IBMs uh quantum computer to run
00:32:44.830,00:32:49.935
this uh on their backend. It's
actually really really cool and
this feeling when you run a
00:32:49.935,00:32:55.440
quantum computing software for
the first time is actually quite
cool. So I encourage everybody
00:32:55.440,00:33:01.446
to look at Qiskit or various
quantum computer libraries and
to play around with this. So the
00:33:01.446,00:33:07.319
problem obviously is and you
guessed it is in order to do
anything meaningful I need lots
00:33:07.319,00:33:12.557
of qubits. So in order to use uh
Shor’s algorithm to um uh to
break RSA 2048 I need 4,000
00:33:12.557,00:33:14.626
qubits and I need 4,000 proper
qubits meaning without any
noise. I need for the time of
00:33:14.626,00:33:19.631
the computation there can’t be
any noise on the computation as
well. And it's not really a
00:33:26.538,00:33:31.409
surprise because when Shor came
up with this in 1984 there
weren’t any quantum computers.
00:33:31.409,00:33:35.747
He didn’t have to worry about
hey can I really implement my
algorithm or not. He really just
00:33:35.747,00:33:40.785
came up with this system and
method. So um it was never
really meant to run on a quantum
00:33:40.785,00:33:42.787
computer and um right now lots
of people look at Shor’s
algorithm and they say alright
00:33:42.787,00:33:45.991
uh kind of right now we have 70
qubit so its every the qubit
count doubles every year
00:33:45.991,00:33:47.993
whatever so it's gonna be
another ten years before um we
have Shor’s algorithm. Nobody’s
00:33:47.993,00:33:50.929
gonna run Shor’s algorithm
because it was just a theory. So
let’s look at some of the-the uh
00:33:50.929,00:33:53.765
research where people took
people took Shor’s algorithm and
modified them and optimized them
00:33:53.765,00:33:56.601
to run on real quantum uh
quantum hardware. So the first
one was Fowler in uh in 2012.
00:33:56.601,00:33:59.838
Basically the first approach was
really kind of I need to tweak
this algorithm so it can be so
00:33:59.838,00:34:04.776
it can sustain errors. Because
Shor’s Algorithm was really
under the assumption there’s no
00:34:12.017,00:34:17.022
errors or the qubits are
fantastic uh no errors so
basically they used what is
00:34:27.799,00:34:34.239
called the surface codes to
allow for errors to occur and
the error rate is 0.1 percent of
00:34:34.239,00:34:40.812
the uh of the gate error rate
and um uh Fowler came up I can
run Shor’s algorithm and I can
00:34:40.812,00:34:47.218
factor 2048 bit number but I
need one billion qubits to do so
which is obviously a massive
00:34:47.218,00:34:53.491
amount uh in terms of over it um
to run this. So that was in
2012. Not to long a- not too
00:34:53.491,00:34:59.998
long ago. And then in 2017 with
further optimization from O’
Gorman we suddenly kind of like
00:34:59.998,00:35:04.936
had uh had an algorithm where it
reduces one billion qubits to
230 million qubits uh in 2017.
00:35:09.274,00:35:13.411
And that’s really an
optimization the physical
connectivity of those qubits.
00:35:13.411,00:35:18.483
And uh then Gheorghiu kind of
reduces further to 170 million
qubits so you can see there’s
00:35:18.483,00:35:23.955
algorithmic improvement without
any hardware improvements
obviously that’s happening at
00:35:23.955,00:35:28.426
the same time as well but
obviously I get down from 1
billion qubits to right now 170
00:35:28.426,00:35:34.899
million qubits. And the biggest
um uh contribution was from
Gidney and Ekera from uh um uh
00:35:34.899,00:35:40.872
Google and uh University in
Stockholm where they uh provided
paper just not long ago earlier
00:35:40.872,00:35:46.211
this year where they uh looked
into how they could do the same
thing that everyone else is
00:35:46.211,00:35:51.216
doing with just 20 million
qubits. Now we went in 2012 with
1 billion qubits to 2019 to 20
00:35:53.685,00:35:59.658
million qubits and we are far
from the end of the research
there in terms of optimization
00:35:59.658,00:36:06.131
uh to this problem. Now I won’t
go into too much detail of this
uh of uh what they do but
00:36:06.131,00:36:11.102
basically they also look into
lots of optimization of how
things work. And that basically
00:36:11.102,00:36:16.107
also similar to Shor not really
look into factoring the numbers
directly so that basically
00:36:18.710,00:36:23.982
convert this factoring problem
into Shor Discreet Algorithm uh
problem and um uh they have a
00:36:23.982,00:36:30.855
part that is computed
classically and a part that is
computed um quantumly on a
00:36:30.855,00:36:37.629
quantum computer. And they can
show that in order to find p and
q they can come up with
00:36:37.629,00:36:43.234
obviously they know what n is
which is uh the multiplication
of those two. They can come up
00:36:43.234,00:36:47.472
with a number where they know
that the addition of these
numbers is these or these known.
00:36:47.472,00:36:53.344
Sol if they have two uh
equations for two variables
which they can fairly easily
00:36:53.344,00:36:56.781
solve fairly easily is obviously
an overstatement because they
still need uh 20 million uh
00:36:56.781,00:37:03.655
qubits uh to do so. Um uh but
obviously the uh the um
reduction from 1 billion qubits
00:37:03.655,00:37:08.193
to 20 million qubits is uh
massive and uh I expect in the
next couple of years there’s
00:37:08.193,00:37:12.931
gonna be lots of optimization
through Shor’s algorithm and
especially to Gidney and Ekera’s
00:37:12.931,00:37:19.304
um uh algorithm where this is
gonna be uh reduced uh further
on. Obvuiously 20 million qubits
00:37:19.304,00:37:25.610
is still a long way away from uh
quantum computers that are
accessible today um uh where we
00:37:25.610,00:37:30.615
are in the realm of slowly below
100 qubits um uh at this point
in time. So I want to spend the
00:37:32.951,00:37:36.855
next you know or the last ten
minutes of my presentation on
the process of quantum
00:37:36.855,00:37:42.026
annealing. This is the second
type of quantum computer and uh
that is actually what is quite
00:37:42.026,00:37:45.797
surprising to me even though
everyone is talking about Shor
and the implication of
00:37:45.797,00:37:50.935
cryp-cryptography. Actually
quantum annealing right now is
much much further ahead in terms
00:37:50.935,00:37:55.406
of solving this factorization
problem. And we are going to
look into a little bit how uh
00:37:55.406,00:38:00.378
these algorithms work. So as
mentioned before quantum
annealing those computers are
00:38:00.378,00:38:05.049
really computes where it can
solve optimization problem. I
need to I need to define my
00:38:05.049,00:38:09.788
problem as an optimization
problem and then basically
quantum annealing computer can
00:38:09.788,00:38:16.060
take this problem and then find
uh minimum of this uh problem
because it represents a physical
00:38:16.060,00:38:20.732
state and I know the physical
state will always end up in the
ground state and I can read in
00:38:20.732,00:38:25.003
this ground state and I will
have the solution to my problem.
And there is really a cool a
00:38:25.003,00:38:31.976
cool theorem um uh where you’re
gonna find you wanna go into the
lowest point. You wanna find
00:38:31.976,00:38:36.047
this lowest point on the right
hand side. So how do we find
this lowest point and not get
00:38:36.047,00:38:41.920
caught up in those uh minimums
uh in between. And there’s lots
of ways how you can do this from
00:38:41.920,00:38:47.992
the uh from the physical system.
And there’s really cool case on
this quantum annealing case
00:38:47.992,00:38:52.997
where there is a theorem that
says if I start in a really in a
very easy quantum mechanical
00:38:55.500,00:39:01.506
system. In this really easy
quantum mechanical system I know
the ground state. So this is my
00:39:01.506,00:39:06.711
problem I want to solve is here.
I am starting here and I really
know where I am. I can now
00:39:06.711,00:39:13.384
slowly evolve and adiabatic
means slowly evolving this state
from this here to the state
00:39:13.384,00:39:19.958
where I really wanna be and now
this theory gives me a guarantee
or physical proof that I will
00:39:19.958,00:39:26.231
end up in the in the maximum in
the optimal minimum of the
problem that I wanna solve. And
00:39:26.231,00:39:31.502
it’s really cool so I have
Hamiltonians or functions that
define a physical system but
00:39:31.502,00:39:36.174
basically if you look at the
first function if you put in s
equal zero you end up in this
00:39:36.174,00:39:41.179
high H zero which is my easy to
understand system where I know
the local minimum and in my
00:39:43.214,00:39:49.454
calculation I slowly moves from
zero to one and if I am at one I
am in the stage high H one which
00:39:49.454,00:39:54.859
is the problem that I really
want to solve. But this uh
adiabatic theorem guarantees to
00:39:54.859,00:40:00.598
me that I will end up in the
maximum minimum for the problem
that I really want to solve.
00:40:00.598,00:40:05.403
Which is really really cool
because it gives uh I know I’m
not going to be caught in some
00:40:05.403,00:40:09.474
local minimum. But still
essentially I wanna solve for
optimization problem. How do I
00:40:09.474,00:40:15.813
do this. And the first research
came from Burges in 2002 from
Microsoft. Where you know he
00:40:15.813,00:40:21.552
provide a foundation of hey I
wanna solve basically I wanna
look into the problem n equals p
00:40:21.552,00:40:27.992
times q. I am looking for p and
q um uh so that this equation is
true. So I just need to solve
00:40:27.992,00:40:32.897
this I need to write this as
optimization problem. And
basically he rewrote this as N
00:40:32.897,00:40:38.369
minus pq squared and this is
always a positive function. Is
always greater than zero. And
00:40:38.369,00:40:43.374
this is obviously only zero if N
equals pq. And if you write this
way you have what's called a
00:40:45.877,00:40:51.716
QUBO a Quadratic unconstrained
binary optimization problem
which you can happily run on any
00:40:51.716,00:40:56.354
quantum annealer that is out
there. And you basically use
binary representation that is
00:40:56.354,00:41:00.992
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
00:41:00.992,00:41:02.994
one. And you basically now write
this down and it's a very simple
example. My example 15 is 5
00:41:02.994,00:41:04.996
times 3. Now um uh in binary
notation p equals x1,1. The last
bit always has to one because
00:41:04.996,00:41:07.432
the prime number can’t be an
even number. And I just you
know, n minus pq squared I just
00:41:07.432,00:41:13.905
write it through and kind of by
hand say oh this function I need
to minimize now. And I can run
00:41:13.905,00:41:20.545
this against D Wave’s quantum
computer and if I find the
minimum I know n equals pq
00:41:20.545,00:41:23.181
because that’s by definition a
positive function. So I can use
quantum’s uh D’wave’s quantum
00:41:23.181,00:41:26.351
computer they provide a library
as well and you see the link
here you can download it. It’s
00:41:26.351,00:41:29.987
basically same thing you just
call factor P. P is my uh my
product and I can run this on uh
00:41:29.987,00:41:34.993
D’wave’s quantum computer. The
problem is if I run this without
any optimization I need n
00:42:00.885,00:42:06.524
squared qubits for this so I
mean the number of qubits that I
need really kind of like grow
00:42:06.524,00:42:11.529
quite heavily and for larger
numbers is not sustainable uh to
do. But I wanted to show you
00:42:13.531,00:42:18.536
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
00:42:20.605,00:42:26.511
my two prime numbers is one and
seven which is obviously wrong
so I run this once and I didn’t
00:42:26.511,00:42:31.382
really end up in the uh in the
right spot. But I run this five
times and now I already have 5
00:42:31.382,00:42:36.621
and 3 is already 60 percent um
uh you know probabilities. And
if I run this fifty times you
00:42:36.621,00:42:42.560
know I know my prime numbers are
already 3 and 5 so I know I need
to run those quantum algorithms
00:42:42.560,00:42:47.899
more and more often to make sure
I end up in the same results. Um
I’m gonna skip over some of
00:42:47.899,00:42:54.338
those things because virtually
all optimizations of now this
base you know of of Burgess’s
00:42:54.338,00:42:59.477
work where he basically looked
into hey my multiplication
matrix that you write out as a
00:42:59.477,00:43:05.516
function to be minimized there
can be lots of optimizations
virtually all of the work that I
00:43:05.516,00:43:12.290
present here now is based on
optimizations of how you do the
multiplications down below here.
00:43:12.290,00:43:16.928
If you’ve ever done
multiplications by hand you know
you start on the right and you
00:43:16.928,00:43:21.799
kind of multiply the lowest
numbers and it carry overs to
the left and virtually all of
00:43:21.799,00:43:28.372
those optimizations um uh go
through this how I can do this
multiplications much easier.
00:43:28.372,00:43:33.377
Dridi and Alghassi did some work
in 2016 where they used some of
these uh optimizations to remove
00:43:35.379,00:43:41.419
some of the all of the degrees
so they were already able to
factor a number greater than
00:43:41.419,00:43:46.424
200,000 with almost 900 qubits
now D waves qubits on quantum
annealing are not as don’t have
00:43:48.526,00:43:53.998
to be as good as universal
quantum computer qubit so D wave
announced a system with uh I
00:43:53.998,00:43:59.003
think around 5,000 qubits for
next year. So 900 qubits is what
was available back then on
00:44:01.939,00:44:07.912
universal quantum computers. The
biggest prime number is less
than 100 and they these guys in
00:44:07.912,00:44:13.851
2016 could already now factor a
number that was over 200,000.
The big breakthrough was from
00:44:13.851,00:44:18.856
Jiang et al in Indiana in uh
April 2018 and it is really kind
of mindblowing uh you see the
00:44:21.292,00:44:26.430
next one which was really just
uh two months after really
around optimization of this
00:44:26.430,00:44:32.603
multiplication map and they have
now raised. They could factor a
number which is greater than
00:44:32.603,00:44:39.076
350,000 with just 94 qubits.
Remember D-wave comes up with
5,000 units quantum computer
00:44:39.076,00:44:44.081
next week um next year. Um uh
and it's all based on this
optimization uh problem that we
00:44:46.517,00:44:51.889
solve called factoring and with
optimization to the
multiplication table. And then
00:44:51.889,00:44:57.161
Peng in two thousand uh in uh
earlier this year really um uh
and you can see this uh
00:44:57.161,00:45:01.999
submission was received in July
while the previous submission
was I think uh submitted in
00:45:01.999,00:45:07.338
April or something it was just
months after. Optimizes even
further and they’ve been able to
00:45:07.338,00:45:11.976
factor a number that was greater
than one million with just 90
qubits. So that’s already 20 bit
00:45:11.976,00:45:17.381
number. So right now when you
look into the problem of hey can
I use a quantum computer to uh
00:45:17.381,00:45:24.255
factor prime numbers. Universal
computers and Shor’s algorithms
are nowhere compared to uh
00:45:24.255,00:45:30.027
quantum annealers. And with
quantum annealers I can already
um uh um do this with uh 20 bit
00:45:30.027,00:45:32.029
numbers. So um there’s three
things really interesting. So
they they can run this on
00:45:32.029,00:45:34.031
already existing hardware today.
And all of those algorithm
that’s a really big takeaway um
00:45:34.031,00:45:39.036
uh that you have. To do this I
don’t just have one quantum
problem that I wanna solve. It’s
00:45:48.179,00:45:53.317
always a hybrid model of some
classical compu-computation and
some quantum computation. I
00:45:53.317,00:45:57.321
really use classic computer what
he’s good at and quantum
computer what a quantum computer
00:45:57.321,00:46:02.259
is um is um good at. So um my
point is quantum annealers are a
thousand fold better right now
00:46:06.530,00:46:11.569
than Shor’s algorithm and
universal quantum computers. But
because they are too noisy right
00:46:11.569,00:46:18.476
now we are far away from
breaking anything that is uh in
used in practical terms. Right
00:46:18.476,00:46:24.882
now the biggest number is a 20
bit number. But obviously we
know uh those two uh kind of
00:46:24.882,00:46:29.520
like converging curves here. The
algorithms are getting better
and better. At the same time the
00:46:29.520,00:46:34.592
quantum hardware gives me more
and more qubits as well. So both
of them will actually have a big
00:46:34.592,00:46:39.397
impact. I can’t just rely on my
predictions saying hey the
number of qubits grow by 15
00:46:39.397,00:46:43.601
percent every year so I’ll be
fine for the next 50 years.
You’re neglecting the
00:46:43.601,00:46:48.506
improvements that the algorithms
uh will make over the next uh
over the next uh couple of years
00:46:48.506,00:46:54.578
too. So a couple of uh myth and
reality. Shor, nobody is gonna
implement Shor on any quantum
00:46:54.578,00:47:00.918
computer whatsoever. Um uh Shor
was a theoretical work. There
are practical work um uh you
00:47:00.918,00:47:07.258
know derivations of this work
that will be implemented. Um at
some point obviously on the on
00:47:07.258,00:47:13.030
the base of Shor’s algorithms
people will break um uh the uh
the RSA encryption. It is a
00:47:13.030,00:47:17.401
matter of time. Now we can argue
whether its ten years, twenty
years, fifty years. But we are
00:47:17.401,00:47:22.673
only arguing about the time. We
are not arguing about arguing
about that it will happen. And
00:47:22.673,00:47:27.378
obviously there’s lots of cases
where this is already has an
impact right now. If I have
00:47:27.378,00:47:33.050
bitcoins right now and my public
key is known. I don’t care
whether it takes me 20 years to
00:47:33.050,00:47:37.888
uh get the private key to those
uh to those bitcoins. I figure
in 20 years there’s you know one
00:47:37.888,00:47:42.727
and a half million bitcoins from
Satoshi flying around which is
around 12 billion dollars right
00:47:42.727,00:47:46.997
now. Hey if someone come to me
and say Hi Chris you know can
you bring me quantum computer.
00:47:46.997,00:47:50.735
Hey it’s really hard it takes me
12 billion dollars you know. Hey
here’s 12 billion dollars right
00:47:50.735,00:47:55.740
there. [laughter] So um um so
anyway uh it takes it will be
quite a while but I want to
00:47:58.309,00:48:02.913
[inaudible] off the algorithms
started this talk talking about
how I trust the asymmetric word
00:48:02.913,00:48:07.284
of the RSA word. But there’s
plenty of work and this is uh
kind of you know from this
00:48:07.284,00:48:13.457
Chinese paper in the very end.
That’s the that’s the uh uh the
end statement. There’s plenty of
00:48:13.457,00:48:19.397
work on the way right now to use
quantum annealers or to look
into symmetric uh encryption. So
00:48:19.397,00:48:24.468
if you say hey I just use
symmetric encryption I find that
might not be holding up for too
00:48:24.468,00:48:29.874
long and I thank you very much I
am out of time. Thank you very
much for your time. [applause]
00:48:29.874,00:48:34.879
Do we have time for questions?
We don’t have time for
questions. You can find me
00:48:36.981,00:48:40.684
anywhere if you have some
questions. Happy to engage with
you. Thanks so much!