Dear viewer, these subtitles were generated by a machine via the service YouTube and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/2848 Thanks!
[Music]
with that I would love it for you to
welcome alesandro and his great
[Music]
talk can everybody hear me okay yes okay
so quantum
computers Dear Community dear hackers it
was December of 14 years ago that I
attended my first CCC in Berlin and it's
also because of that experience in that
community that I made a series of choice
that led me uh here as a researcher
studying Quantum algorithms and Quantum
computation and there are certain
similarities that we can draw between
hacking and writing Quantum algorithms
um the idea is that uh writing Quantum
algorithms is like hacking nature why
well because uh we can think of nature
as a quantum mechanical system and
programming it is like a way to make
nature behave in way that is not meant
to be
used so uh writing Quantum algorithms is
a lot of fun is a lot of fun in games
but how do I feel today well today I
feel a little bit
me why well because the impact of
quantum computers is not communicated
very well in the Press today there is a
lot of hype so we are here today to
understand better what's the impact of
quantum computers especially in cyber
security so how do we measure impact
well we can say that a new paradigm for
doing computation has impact if it's
faster than the classical computers that
we have or if it can gives us better
results right like imagine we are
approximating some um solution of a
problem like the price of a derivative
for example and our quantum computers
can gives us a better estimate of the
price in the same amount of time of a
classical computer or maybe it's just
cheaper to compute the same result in
the same amount of
time another way that we can expect one
computers to impact our society is if
they can allow us to do something that
before we couldn't do right and an
example is exponential speed UPS or big
polinomial
speedups and I know you have in mind
sh's algorithm for factory
but uh it's not that easy right because
we know from high school that
asymptotically an exponential function
will dominate a polinomial or a linear
function imagine that this is the cost
of your computation and you can imagine
to measure the cost in hours okay so
asymptotically if we have a Quantum
algorithm that is uh exponentially use
polom faster than a classical algorithm
then we know that it will be faster but
but maybe we have to look at regimes
that are relevant for us and as you can
see from this picture there are cases
where um you know a linear time
algorithm is slower than an exponential
time
algorithm
okay so how do we measure the cost of
quantum computation
well in theoretical computer science
what we do even for classical
computation we measure the size of a
circuit right and the size of a circuit
is basically the number of logical Gates
that we execute or maybe we can measure
the depth of a
circuit that is also know as parallel
time or we can measure the space right
the number of bits the size of a memory
that we use in our
computation or we measure the number of
queries that we uh perform to an
oracle but we also care about more
practical things and these practical
things are maybe the money that it cost
to run some computation the energy that
I use to run uh this computation and
more specifically in Quantum uh circuits
we care about the number of to Gates
which are a particular kind of 3 Cubit
Gates and we also care obviously about
the workclock time um of our computation
and the number of physical Cubit so
there is a difference between physical
and logical Cubit I won't get into the
details of this because it's related to
error correction a very difficult topic
but you just have to know that in order
to obtain something that we call
physical Cubit we need to uh something
that we call a logical Cubit we need to
use a certain amount of physical Cubit
and now the ratio is 1 to
1,000 so how do we estimate this more
practically and in measures we do what's
called a resource estimation and a
resource estimation is basically a
procedure where we take the uh
theoretical complexity of an algorithm
we look at the real problem that we have
to solve perhaps we use some tricks to
optimize uh the circuit and then we can
count the number of resources that we
really need to solve the problem that we
care
about um Okay so what are we going to
see today is three topics the first the
impact of the quantum Computing in the
cryptography that we use today so RSA
and lip of curve crypto and there the to
Long didn't read uh is that uh there is
a long way to go but we will eventually
get
there we will see uh if there is an
impact in postquantum
cryptography so we'll show some resource
estimation of post Quantum uh of quantum
attack on postquantum
cryptography and there the result is
that uh latis based crypto is safe even
when considering practical
implementations of the
attacks and then we will see uh the
impact of quantum machine learning why
because machine learning is used in
cyber security and we will just uh try
to explore a little bit this area with
um
methodology and the conclusion there and
this is not just in cyber security but
is that we will see a speed up only for
massive data sets but we have a lot of
good ideas and a lot of
hopes so in this part I'm going to
present some uh results of uh the
internship that ADI did in invariant
with and uh with me and Daron and also
um Antonio joined later this project
so factoring
right the state-ofthe-art on factoring
is this paper by uh Craig gy and
basically in this work he's showing how
to break RSA 2048 using 20 million
physical cubits and approximately 8
hours of quantum
computation so his um assuming to uh
work with a particular kind of Hardware
made of superc conducting cubic bits
with a gate error of 10 the minus 3 and
he's using concatenated surface code to
achieve these estimates
right um so in order to perform a
resource estimation you have to do some
assumption on the hardware that you
expect to have in the
future
um what he's using in his circuit is
this idea of a window arithmetic so in
his circuit he needs to perform let me
be very technical for 5 second phase
estimation on an oracle that is
performing modular exponentiation so
basically he needs to perform arithmetic
in his circuit to perform arithmetic
he's using this idea called window
arithmetic and window arithmetic is
basically a way to have SpaceTime
trade-offs so instead of uh running a
circuit that is Computing the function
that you want to compute you pre-compute
this function classic Bally and you
store some results in memory and you
just quy the memory when you run the
quantum
computation and in order to look up the
memory at some point since the
computation is quantum and um it needs
to be reversible at some point you need
to uncomp compute some garbage and for
uh that he is also using a trick that
allows him to save um some uh gates in
these settings
so our contribution is that we can do
some improvements in the way this UNL up
is done especially when we have uh
nested Loops in uh the circuit and in
model exponentiation you do window of
arithmetic using nested loops and
therefore you can have a little bit of
saving in the number of
gates so the performance improvements
that we were able to H get is around 1%
for uh cryptographic uh
relevant uh numbers so RSA keys of um
2048 basically
0.7% is a modest Improvement but it's
still non- negligible and we hope to do
more in the near
future and it's basically saving 15
minutes over 8
hours
there is another uh problem that you
face uh when you're trying to do short
algorithm which is implementing bullan
functions in general
so imagine you have a buan function you
can write your classical circuit for
implementing this bullan function using
some tricks from classical computer
science you can make this circuit
reversible and then you can obtain a
Quantum circuit for this bullan function
but again you will see that you have a
problem of Performing and computation
but in literature we have this SLE
measurement based on computation which
allows you to have Savings in
expectation when you run uh the UN
computation of the circuit and applying
this trick to something that we thought
was very well analyzed and optimized but
we realized that uh you can have um
Savings in the circuit that is
performing modular
okay and where is the circuit for
modular addition used well is used also
in the circuits that's um used for
breaking elliptic C cryptography and
here the uh state-ofthe-art for resource
estimation of ACC is this paper by
litinsky is again another um corollary
of shore algorithms is using some
particular kind of archit Ure called
active volume which um is assuming
basically to work with photonic cubits
with a similar gate error and the number
of logical Cubit that he is using is
6,000 logical
cubits so after our trick we were able
to uh save again a little bit less than
1% but we have other tricks under our
sleeves to um improve this result
further and the Mage year is that there
is a lot really really a lot to do in
the whole stack of uh Quantum Computing
to improve his attacks and uh and
algorithms so in the second part I'm
going to present briefly some um results
of our team at
cqt uh where me and joa are super lucky
to have gorgio and Adia helping us uh
studying the resource estimation of
postquantum
cryptography so we are focusing on ltis
attack and this is the only uh math part
of this talk I promise so a ltis is
basically the set of all integr linear
combination of a set of n linearly
independent vectors and the problem that
you have to solve here is I give you the
basis and you have to find the shortest
Vector of this basis
shortest Vector in let's say Ean
Norms why this is important because if
you know how to find the shortest Vector
then you are able to break postquantum
cryptography fortunately we don't have
polinomial time
algorithms we don't have polinomial time
Quantum algorithms and classical
algorith for breaking uh for solving
this problem so theoretically we know
that at some point for big ltis
Dimension we are safe but the question
is are we safe even when we look at the
constant Factor um of the attack when uh
we implement it and there are already
Works in this direction H namely uh the
first one is studying uh some uh version
of an algorithm called gaus and the
second one is implementing and studying
enumeration
attacks um so what we did well we
implemented the gaus and here you can
find the code online of uh the
attack that's great but let's look at
the results so what's the real
complexity of of the
circuit well from this plots you see the
following thing well the dotted green
line is the cost of the classical
algorithm and the dotted red line is the
cost the asymptotic cost the theoretical
cost of the quantum
algorithm the two non- doted lines are
the number of tofo gates a particular
kind of gates in um the circuit and the
blue line is the duration in
hours so you can see that the slope of
the two non- doted lines is uh
compatible with the um red dotted
lines and um yes so it means that we are
safe from Quantum attacks unless someone
finds a new Quantum algorith that is
more efficient ASM totically and then we
have to repeat this study
again
okay in the last part uh we study
Quantum machine learning and
applications in cyber security as I said
before why are we doing this well
because machine learning is ubiquitous
in cyber
security and we want to see if quantum
has something to
say so the idea of quantum machine
learning is that you want to use a
Quantum machine for training a model so
the training part and or the predict
phase of um a machine learning
algorithm let me say that there are two
ways of doing quantum machine learning
one stems from the thetical computer
science community and there you have a
theem staying stating I can do this
computation with certain probability and
certain approximation error and the
other community is saying okay we have
very small devices let's see what we can
build on top of
those and this is very similar to what
people are doing in deep learning and
with neural networks I belong to the
first community so what I do is I take a
classical machine learning algorithm and
try to come up with a Quantum version
for
it and in our work what we do is we
study the query complexity of an
algorithm why well because if we know
the number of queries that we do to the
input then we just need to understand
what's the cost of performing a query
and we know the final cost of performing
the whole
algorithm so this problem is basically
reducing to understanding when the left
hand side of this equation is smaller
than the right hand
side let's not delve into details of the
meaning of all these symbols but the
only important thing here is that on the
left hand side we don't have
n and n is the number of samples in our
data
set so there is hope that a Quantum
algorithm should uh scale much better
than a classical algorithms in terms of
number of sample right but what about
the other
parameters so in order to understand
that we developed this methodology to
try to see for data sets that we care
about what are the parameters in the
runtime of the quantum algorithm so we
can compare the runtime with a classical
runtime
results what do you
expect so we tested this on a few data
set that are standard in cyber security
and the result is that we need 10 to the
seven elements in our data set in order
to start to feel a little bit of quantum
advantage in terms of query complexity
so without taking into account the cost
of uh a query to the
cam okay so maybe there are other data
sets and problem that we can look at um
to get
advantage and
so well the answer is there is some hope
and there is this particular problem
that I found many years ago and the
problem is related to malware detection
so uh DGA a domain generation algorithm
is an algorithm that malware is using in
order to contact the common and control
server they are basically generating
random
domains and they're trying to uh connect
to a web server that is answering behind
one of these randomly generated domains
and the randomly generated domains are
very different from the domain that we
humans generate take for example
google.com versus random letters.com
so I took as a training set the top 1
million
domains and I did some pre-computation
and I obtained an engram Matrix where
the number of rows is 1 million and in
the columns you have uh the engrams that
you build out of the training set and in
any row you have one if the uh engram in
the column you are considering is
appearing in the domain in that row okay
so what's interesting here is that this
Matrix is very sparse and I tell you
later why it's
interesting but then uh when you build
this engram Matrix with a classical
computer uh you can only afford to pay
linear time to process it so you cannot
do linear algebra on this Matrix on a
classical
computer
and my idea was hey let's use a Quantum
algorithm to extract something out of
his
metrix great so I wrote uh my first
paper was a Quantum algorithm for
something called slow feature analysis
which is exactly equivalent to something
called Fisher linear discriminant you
might know this and um and so I wrote a
classical simulation of a Quantum
algorithm to extract this feature out of
this very big and very sparse
Matrix and then I used this feature in a
classification
step so the game is the following you
give me a domain I have a classifier a
machine learning
classifier I use the feature I just
extracted from the Matrix to as to add a
new input to this classifier and I
looked at the results and I compared the
classic
uh results with Quantum results and you
can see that this feature is improving a
little bit the um results of a
classification so the moral of the story
is that if you think hard enough maybe
there is some hope to get Quantum
advantage in the
future so conclusions well um the
results and the paper that we see
nowadays are kind of the uh following
the the following script we know how to
perform linear algebra we find a problem
where linear algebra is needed or is a
bottleneck and we write a Quantum
algorithm for it is interesting but
maybe we want to understand and we want
to get new algorithmic paradigm for
writing new Quantum algorithms different
kind of speedups a common Trend that is
uh
limiting uh the quantum advantage in
practice is uh something called curum so
the quantum version of random access
memory and there is a lot of research to
do to do
there and uh if you're asking me when
this will happen I really do not have
the answer you have to ask a
physicist there are many other topics in
uh uh Quantum Computing that might
impact uh cyber security namely the uh
delegation of quantum computation so the
idea that um not only you can do
encrypted computation over the cloud but
you can only you can also delegate and
encrypt the computation that you are
delegating Quantum key distribution uh
there are uh there were other talks at
CCC previous years about qkd something
called position based
cryptography and if you want to learn
more about the computational aspect so
the algorithmic aspect of uh Quantum
Computing um you can find uh open source
project set of lecture notes on Quantum
algorithms.
org and last thing I'm hiring at cqt um
postdoc internship for phds and uh
research assistant positions so thank
you so
[Applause]
[Music]
much
so we actually have a lot of time for
questions uh please people who are
leaving leave very very
quietly uh and please take your trash
but questions uh do we have any
questions we have four microphones on
the floor and we have uh the signal
Angels on the
internet uh you have to go to the
microphone
sorry
so so if you have a question step up to
the microphones
All Right microphone one hi hello um you
mentioned that you were speeding up the
Tiff gates with some enhancements were
these enhancements um for letters
general or was it specific to learning
with errors or short integer Solutions
or was
it can you repeat the beginning of the
question yeah um the announcements on
the tiil gates that you showed earlier
was it on all letters um algorithms or
was it specific to with a or short
integer Solutions was for General laes
yeah but the algorithm is uh uh not done
by us we just implemented it
okay so uh microphone number
three hi hi Alexandro thank you for your
time um I have somewhat of a more
different question so you've shown a lot
of resource estimation where we look
into how much does it cost to compute
this um do you also have work where you
look into the cost of the ad Arial cost
as in how much does it cost to do this
in an attack as in compared to a
classical attack path where you do for
example if Shorts algorithm you usually
decrypt things so you look into um um an
attack on a on crypto and usually it's
you know at the end of the attack chain
after exfiltration to decrypt certain
things um can you more elaborate maybe
how the attack path looks like in
comparison um the adversary cost to use
a quantum computer versus versus a
classical thing and what the timeline
would be that
that's a great question and I'm afraid I
don't have an answer for that um there's
probably more research to do to to
understand that yeah so we have a
question from the internet yes thank you
um the internet is wondering if you
could go into more details about the
differences and the synergies between a
classical neural network and a Quantum
neural
network to answer properly this question
it takes more than one PhD for
sure
um what can I
say
well I mean the similarities is that you
have a Quantum circuit and a Quantum
circuit is composed of gates and the
quantum gates are somehow more General
than classical Gates so you have a angle
of
rotations and the idea is that you can
do gradient descent or other
optimizations algorithms on these
parameters and this is similar to the
weights of a neural network so that's
similarity and the difference well the
difference is that one is quantum the
other is classical
so um we still don't know if one is more
powerful than the other if one is
trainable if it's trainable maybe it's
classically simul so it's a very open
area of research okay microphone number
three sorry one sorry one uh hi thank
you for the talk uh I was wondering if
you could quickly explain the
similarities and differences between
time complexity classes for classical
versus quantum
algorithms is a another great
question
um it requires more than a PhD but
um I mean
complexity
theorists try to take complexity classes
and add Quantum
somehow um and then they try to compare
these classes between Quantum and
classical
so there are a lot of open
questions um if you have any more
precise thing maybe we can discuss it um
later but uh yeah it's a big big topic
of
research thank you thank you uh
microphone number three hi thanks for
the great talk first of all um I wonder
if you heard about the um first um
thetical practical approach research of
Harvard University and a logic based um
co-processor um they they found with Nal
atoms where with um where they found a
method methodology to to build up a um a
processor um for quantum computers with
less physical cubits than it's foreseen
because it's um it's held for the next
yeah threat let's say so I wonder if you
know about it and I wonder if you could
could use this approach for um for this
open research themes as the thing of the
um memory based problems and challenges
thanks thank you great question and um
are you referring to this recent result
of few weeks ago I think I mean it seems
to be solid research so I'm very happy
um but again I'm not a physicist so like
between me and them there's a whole
stack of people that needs
to connect our results basically um but
yeah I'm hopeful that's great that's
great so we have a question from the
internet
thank you the internet is wondering if
um what you showed is also applicable to
special quantum computers especially
Quantum anas um and they're referring to
an announcement made by loit Martin a
couple of years back here that they were
able to do something like Shaw's
algorithm
here great question
um I usually do gate based Quantum
Computing
um so the thing is that you can put
whatever you want in an aner because the
thing that the aner is solving is very
general and it's very simple to see that
you can reduce factoring to an
optimization problem right you have n
the number you want to factor equal p *
q and you do n minus P * q and uh you
are trying to minimize the difference
between these two things so the differ
in zero for the right p and Q
right but if you try to do this on an
aler you don't have a proof that the
runtime is polinomial so the run time of
an aning thing it's like quadratic or
cubic in something called spectral Gap
and for factoring on aner we don't have
any bound on on this
thing so microphone to right
Jordan uh thanks for your talk uh what
what I want to uh know is uh what the
well I know quantum computers are still
experimental and
uh how well do your algorithms break
break or scale or break up to uh the the
currently available systems physical
system
or well they is a great question and
unfortunately the answer is they don't
run very well because they really
require a lot of Q bits a lot of gates
so I need error correction
to to to run anything
meaningful um question from microphone
three yeah hello my question also
relates to this and I want to be a bit
more specific so um it's really hard as
you mentioned to judge how how well
things are going and how well are things
progressing apart from all the hype
that's being going on so um one thing
that I was asking myself is so how far
are we actually with uh factoring
numbers and despite the progress that
we've been seeing in uh Quantum
processes in the past years I believe
that except for certain uh Publications
that maybe happen once or twice a year
where they fractured a really long
number but like they've pre-chosen that
number to optimize for it so and I
believe the the current record still is
more or less Factory 15 and that has
been since
2012 why hasn't anything happened since
then I think they may have got up to 21
by
now um a great question I don't know I
don't
know um well maybe because also the
attention shifted to other
topics maybe yeah thank you I think we
have another question from the
internet yes thank you um and the
question is um if you have ever had the
chance to look into the cyber security
um application for Quantum certified
deletion so quite special um maybe but
maybe you have some
experience Quantum certified
deletion yes um never heard of that okay
yeah I just Googled it it's uh it's a
paper May so okay cool uh microphone
three hey so when you talked about uh
Quantum machine learning you made a
distinction between predictive model and
variational model uh I was wondering how
do they def in terms of uh what happens
when you need to measure in intermediate
steps or uh the wave function collapse
in general what is the difference
between those and if there is more than
that um cuz you name two but maybe there
is
more um yeah good question
um
so as far as I know you don't measure
much during the computation in
variational algorithms but you can
measure intermediate things in uh
provable
algorithms
um there are other
models
um for example aning is one of those um
also there are two three papers where
they try to do something in between
variational and
provable
um works by kenis and prash recent some
recent results from them um but no this
is what I know
so just these two three
things so we still have a little time
and we have a question yet again from
the internet yes internet is on fire
today um so the question is is there an
equivalent for um in quotes gigahertz or
speed measure for quantum computers
absolutely yeah yeah yeah yeah
absolutely
um I think depending on the hardware you
have different clock
speeds um I didn't mention that but but
like it's really platform
dependent um some architecture are
faster than others but in general for
super conducting I think the clock uh
speed is uh in
megahertz so this is also why we are
very slow to get practical Quantum
Advantage because the clock for quantum
computers is much slower than the clock
of classical
computers um question from microphone 3
um I'm come from a math background so
maybe the question is stupid but um the
metrices where you said you need linear
time with classical algorithms to
process it how do you get the metric
metrix in sub linear time into your
quantum computer to process
it no you you so imagine you no it's
very good question um you build the
Matrix
classically and then in linear time you
can build Quantum access to this Matrix
and then the quantum algorithm is poly
time or whatever time it
is okay yeah so one I get maybe final
question for microphone
one so this is more of a general
question um you said that there's a lot
of hype I mean there is a lot of hype
around Quantum Computing in general and
I'm curious what are your opinions on
not the hype but uh what is the most
promising application that Quantum
Computing uh can bring and if any or are
there some things currently being
overhyped or what do you think what's
your general opinion uh great
question
um okay
so I mean for the crypto that we're
using nowaday I'm sure it will
eventually
work uh maybe Quantum Finance is
slightly
overhyped um
so Quantum algorithm for pricing
derivatives and these kinds of things
estimating the risks of something uh but
maybe quantum chemistry is something
where we
can have advantage in the next years
so new new molecules new material
estimating ground state of
things
um yeah maybe that
okay thanks thank you I don't see any
further questions so let us thank
Alexandro for this fantastic Quantum
talk thank
[Music]
you