# 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!

This was an awesome talk!

Don't release that many videos in one go, You've totally spammed my sub page

Me: Gets notification

Also me: Entire subbox is spammed ree

Also great recording this time thx

Unlistenable

You guys posted like 75 videos at once??? Are you fucking kidding me? My entire inbox is filled with them – now I will miss at least 60 of them, because I'm not going to sit down and watch 80 fucking hours of the same channel. So I have two choices: go through and hide every single one of them, or just unsub. Guess which one is easier? Dumbasses…

I so need to review the math. College was too long ago.

Oh look.. AN ENTIRE FUCKING YEAR WORTH OF VIDEOS IN A FEW MINUTES… Unsubscribed -_-

Its called .SUPPLY AND DEMAND! Might wanna do some research into that whoever is running this fucking channel!!!

I'm curious to know if noisy results obtained from a universal quantum computer would help to reduce the search space at all. For example, given the noisy results of the RSA 2048 factorisation problem, would they reduce the search space to something more manageable for a classical computer? In other words, despite the noise, would a subsequent classical algorithm be able to rule out a portion of the search space?

tl;dr Shor's algo is utopia, we need 20 million qubits, we have only 70 qubits quantum computer at the moment.

This is further above me than I'm used to w defcon. lol

Something about qubits and maths…. Amazing stuff, this did my head in. 🙂

+1 because we love Hamiltonians! Yet joke aside, a valuable talk!

nope. Brain esploded.

See; this is what i've been saying for years. Can I get a hell yeah?