The next presentation this morning is
going to be given by Michele Mosca, a colleague
in C&O as well. So Michele is a Waterloo
alumn. He did his BMath in 1995 and
in C&O and in Pure Math and his doctorate
in Oxford in '99 on Quantum Computer
Algorithms. So he joined Waterloo as a
faculty right after, and is currently a
full professor in C&O.
So Michele has many accomplishments and
that's why I have this cheat sheet here
and as you can also tell from the logos
on this first slide he has done quite a
bit, so he is the co-founder of the world
renowned Institute for Quantum
Computing. He's also a founding member of
the Perimeter Institute. Michele is the
co-founder of his own company evolutionQ.
He is one of Canada's top 40 under
40 in 2010. He received the Queen
Elizabeth II Diamond Jubilee Medal in
2013 and just recently last year he
received a knighthood in the order of
merit of the Italian public and with
that I would like to welcome Michele.
So
just to start things off on a positive
note. You know one of the big challenges
for society is that you know security is
since the beginning of time basically an
afterthought. Wait for a problem to be
very real and then we have motivation to
fix it and that's more or less served as
well, both becoming an increasing problem
as we develop tools and systems that are
instantaneous
you know scalable and essentially free.
We really do need to rethink how we can
be a little more proactive in dealing
with security in this cyber era. So well,
you know we definitely like to reap
the immediate rewards of putting things
online and engaging in this digital
ecosystem which is wonderful it adds a
lot of value.
It does open up a whole new threat
landscape that like we've never seen
before and we haven't really started
experiencing the true risks or you know
the true dangers yet and at the basis of
protecting you know not just our
information but also our you know the
talk about Internet of Things now in
systems so protecting our safety as well
in this digital era its cryptography and
it's one of the pieces we take for
granted because it actually for the most
part has worked. It's not how people hack
into our systems mostly, it's not a few
examples that we know of where people
actually broke the crypto to get in they
break other pieces of the system some
sort of implementation flaw physical
security the person makes a mistake, but
without crypto you can't you can't get
secure anything using untrusted media.
The magic of crypto is it allows you to
use an untrusted infrastructure, like the
Internet, and still get reliable
trustworthy results. How can you possibly
send something through the internet and
know that it was kept confidential and
wasn't tampered with and gets to the
person it's supposed to get to and came
from the person you think it came from?
You can't you know without crypto you
have to trust every single piece of that
system and it'd be astronomically more
expensive and impractical, so it's a
wonderful new tool that's not that new
actually crypto has been around of
course for centuries but modern
cryptography has vastly broadened what
we can do with mathematical methods. Good
crypto means you you you can trust less
yourself to trust something, but you can
get away with a lot you can get a lot
more out of a less trust worthy system
you know cryptography in some sense
needs to be the strongest link because
it's really the only one that where you
know you can send a message through the
internet
somebody could record it so someone who
isn't able to break it now can record
that message and break it later,
right, the other weakness is you can't
really time travel back and compromise a
person.
so it really does need it's an essential
the point I want to get across it's an
essential piece. Art of communication and
any sort of information processing in
the modern era. Now I said do you know
it's rarely and in the modern era we
haven't really seen cryptanalysis be a
problem but of course there are examples
that we just heard of right from Dan
earlier very famous example in the
Second World War
and there was also we heard a bit and
Ron Mullin told us about some work in
the early 80s and these are students and
the students of the students of a fill
tuck not knowing you know they were
doing cryptography at the time you know
as Ron mentioned they're working on this
other math problem with a different
application but when they came up with a
better way to solve this other
problem they realized it could be used
to break codes these new codes that
people were starting to take seriously
implemented in software they were
starting to implement it in hardware
right something that was supposed to take over a
hundred years to break they broke in a
month and I think probably got it down
to minutes with some optimization right
so imagine that these things had been
deployed and we were depending on them
right for safety and security and then
they were broken that would be very very
bad but that didn't happen
so they broke it before we were
dependent on these tools all right and
this got these you know famous
combinatorial lists and coding theorists
they caught the crypto bug and started
working cryptography and created a great
cryptography legacy for Waterloo for
Canada in the world very high impact I
mean the tools we all use today and our
smartphones were developed by Ron Scott
and others and turned into you know
commercially deployed cryptography so
they didn't stop at writing papers about
it they actually saw the opportunity the
practical positive practical
applications and made them become a
reality. And by the late 90s they decided
that this is just as they were learning
about what Bill Todd had done in the
second world
or this the Center for Applied
cryptographic research was founded and
building on the shoulders of giants and
this Center actually so I said I'd
already I was in England at the time
that this Center was started I'd already
finished my undergraduate but I was
Alfred Menezes came and visited me a
couple times and it was encouraging me
to come back and help start and grow
this new center. It already started by
the time I came back but as Scott Vanstone
used to put it they wanted to keep an
eye on me so they wanted me nearby so I
did you know grew the quantum computing
effort into the IQC and the CACR is
now since you fold it into grew into and
fold it into this new cyber security and
privacy Institute which are two great
you know gems of the University and
building on the achievements of
others who built on the achievement of
others and so on going back decades.
So let me jump into what a quantum
computer is and eventually answer
the question what the heck does this
have to do with security okay and there
will be a test at the end but you know
what's a quantum computer well what's a
classical computer so I think we often a
very rigid notion of what a classical
computer is we think it's one of these
but really a computer the fundamental is
what's inside one of these which is just
some chip that can somehow you can store
information code information in it you
process and you get it out and used to
be mechanical electromechanical vacuum
tubes right you know Colossus was a
computer doesn't look anything like this
but it was a computer under the hood it
was exact you know it was the same
implementing the same model pioneered by
Turing and Church and others so it's a
collection of bits two state systems and
again it could be a vacuum tube a
transistor right that's just a matter of
implementation and so what's a quantum
computer? Well what's quantum physics? One
of my high school Mentors
Bruce White and that actually the
Math 3 atrium is named after him. He
used to say mathematics is a language.
Right, and quantum mechanics is a
mathematical language developed to
express physical theories. So it's like
going from a Flat Earth model or
language for talking about the surface
of the earth right 2-dimensional
mathematics Euclidean mathematics which
kind of works but at some point it
doesn't work anymore and the problem
isn't that we're not measuring things
accurately enough or we're not drawing
them well is that we're using the wrong
mathematical language to talk about the
surface of the earth when you switch the
spherical mathematics everything works
because it's a much more accurate it's a
sufficiently powerful language to talk
about what you need to talk about so
physics had a number of paradoxes and
really really smart people tried very
hard to resolve these paradoxes and they
couldn't. It's not because they
weren't good physicists it's because
they were using the wrong mathematical
framework. So quantum mechanics is simply
a language for talking about physics
that doesn't require you to talk about
an electron being here or there, but
somehow being a here and there at the
same time whatever that means now I say
in some meaningful way because that
language can be misinterpreted and so
some of my colleagues don't like saying
it's in two places at once but they
don't have a better you know then they
say well you have to learn what a
Hilbert space is and talk about super
positions I'm like sure that's a great
way to explain to people what it is so
with the caveat with the cav- you know so
yeah I'm not gonna I'm joking I'm not
gonna test your your your Hilbert space
theory there's other stuff on the test
but that won't be on the test
so you know in some meaningful you know
obviously the reason we invented a new
paradigm is because the old paradigm
didn't work so you can't fully explain
it in the old paradigm but in some
meaningful way we needed to talk about
electrons being in several
configurations at the same time it's not
just electrons because it's a language
just these rules apply to everybody
everything okay so that's what quantum
mechanics is it's a people say oh it's
this thick painful textbook no no but
those are those are theories people
developed in this quantum mechanical
framework right and then may
deliberately painful for for the
students but the foundation itself is
really simple and it applies whether
you're down to the plunk scale the tiny
micro micro mic you know beyond nano
scale of quantum gravity or the macro
scale of quantum cosmology or this
beautiful sweet spot in between the Nano
and micro scale where we encode bits
today
and we can encode bits in quantum
mechanical media so these these little
loops up here which I can't tell if
there's a pointer yes there is this
little loop here it's actually pretty
big right it's microns like you can see
it like this is not that big of a
magnification like nano scale precision
but you can have currents going one way
or the other and it's amazingly it's
just amazing you can actually get
quantum mechanical effects and such a
huge thing with thousands of electrons
but I'm you know some physicists would
disagree you know say I'm
oversimplifying well of course I am but
roughly speaking you can have you know
thousands of electrons going this way
represent a zero thousands of electrons
going that way representing a one for
example but the technology's engineered
so well that you can actually have them
doing one or the other you know at the
same time like that just seems really
hard how can the rest of the universe
not know you know which way it's going
and then the Heisenberg uncertainty
principle will you know will kill you
like once you learn if you're going one
way or the other you can't be going both
at the same time anymore you lose the
quantum effects but amazingly they're
able to isolate it so it can be going
one way or the other at the same time
and you don't know which way whether
it's going you know this way plus the
other way this way minus the other way
it's just amazing that you could build
these things
you know this was the first prototypes
of this as a actual quantum bit occurred
about 20 years ago front page of nature
by our colleagues in Japan so what's a
quantum computer well it's the same
thing except the bits could be quantum
so instead of these 128 bits
representing one of the two to the 128
configurations it can actually somehow
embody all of them at the same time now
what's 2 to 128
I remember Scott Ben stone once telling
me and to break this code would take
like 2 to the 200 operations and I was
just you know is it my early 20s I was
like 1 is that a lot like I don't know
just doesn't sound like a big number
like like what if you what if you just
try just try harder you know but now you
know that's just an insane like a 2 to a
few hundred bits like to to you know to
30 or like that's just more than the
amount of atoms in the known universe
like so a few hundred of these things
and it's already an astronomical number
so so what I'm trying to say is if I
tried it so if I want so the physical
reality says these 128 bits can somehow
embody all two to the 128 configurations
that doesn't mean it's useful right like
why should I care and the first jolt to
our you know the emotional jolt for
computer scientists was because we've
had this principle for last few decades
that any device you could realistically
build could be efficiently simulated by
a regular computer okay so like in the
sense that a PC can simulate a Mac and
a Mac can simulate a PC there might be
some overhead like in a practice that
matters but you're not gonna have some
exponential you're not gonna have the
overhead and so to speak the cost of
simulating one with the other might be a
factor of 100 or maybe simulating N
steps might take N squared steps but
it's not going to be N versus 2 to the N
right but that was the thesis we've been
working with for several decades and
then these physicists say oh it's wrong
it's like well look
obviously you don't know what you're
talking about right if A implies B and B
is unpleasant than not A right so so
obviously the physicists don't know what
they're talking about and you know we
should just of course ignore them
which was my initial reaction then my
supervisor said well maybe you should
you know read about it and learn about
it before you reject it and then I started Quantum Computing
Institute so it's a bit a bit ironic I'm
just glad I didn't stick with my guns
you know it's my initial intuition so
this is you know this is kind of jolted
people and said well obviously there
must be something some reason you can't
possibly build this because if you could
you know maybe it's good for something
other than just simulating itself like
cryptography for instance is based on
these codes being hard to break on any
machine not just a Mac or PC right and
the Church-Turing thesis gave us the
assurance that if it's hard on this sort
of universal computer it's going to be
hard on any other one and but then this
comes along and says well actually if
somebody could build a quantum computer
maybe it could break these codes sure
whatever like their quantum computers
are only good at simulating themselves
best-case scenario right that's that's
as my gut feeling. Now it turns out it
was it's actually good for a lot more
than that and I'll elaborate a bit on
what that means but the technology that
you know created an impetus to build and
harness you know quantum mechanics in a
host of information processing
technologies along the way we could we
could potentially build sensor like one
of the reasons we don't have a large
quantum computer now is these devices
are super sensitive and so a lot of
people said well then why don't we make
good sensors out of these bits right and
there are companies found in now looking
at building medical imaging technology
it's still early days but maybe sensing
landmines
or other weak electromagnetic fields
doing better oil exploration and so on
with other quantum technology and I'll
talk a little bit about quantum
communication
because this ultra sensitivity look what
the Heisenberg uncertainty principle
says is that if you extract as much
information you must disturb it this
much which is different from saying if
you're clumsy you know you're inevitably
going to leave a trace but you know you
can get arbitrarily close to zero
disruption if you're careful in a
classical paradigm but quantum mechanics
says no no there's actual fundamental
trade-off so you're gonna actually
probably disturb it even more but
there's like a guarantee that you're
gonna disturb it at least this much and
that's very useful a new tool in the
cryptography tool chest. So the
applications we hear about a lot of them
are closely tied to simulating you know
what's something that is kind of like a
quantum computer? Well, a molecule right?
If you're doing material design if
you're trying to design a new molecule
or a new way to produce fertilizers that
doesn't lead to as many nasty emissions
or design a new mater- a higher
temperature superconductor you know we
don't just go and guess a molecule and
synthesize because that's expensive you
can't do that a trillion times even if
it's $1 a shot and it's a lot more than
$1 but you simulate it in software to
come up with a short list and then you
synthesize and test those but it's hard
to simulate a material if it's quantum
properties or you know if the properties
of it depend on quantum mechanics you
have this 2 to the 100 you know this
exponential overhead so we believe a
quantum computer can help us simulate
it's still early days
there's no I'm not aware of any sort of
billion-dollar business plan ironed you
know here's the customer and it's not
much we're gonna pay them like I want to
get there but we're not there yet but we
do have a host of promising applications
and another you know a few years ago we
organized a quantum optimization
workshop obviously we're in the CNO
Department and actually a couple of the
former faculty Bill Pulleyblank and and
Andy Kahn were at this event in
Toronto this was the kind of thing we
talked about there
what are the problem- what are the
methods we used today in optimization
that could be sped up by a quantum
computer and what would be the important
industrial implications of them it's
actually pretty hard to find some,
but here's one that one of my students
came up with he noticed the algorithms
you know so called derivative free
optimization the more dumb and
brute-force it is the better we are at
speeding it up so the applications where
there's clever methodologies already
it's harder to improve but here there's
a part of it where they use just very
simple method and we- the potential is we
could help design for example buildings
to be better resilient to earthquakes
and still to be seen so why don't we
have a quantum computer yet
what is the path toward a quantum
computer like back in '96 my supervisor
my examiners asked me when are we gonna
have a quantum computer and I did not
want to answer that because I didn't
know but they insisted I guess so I told
them what I thought and I said
definitely not for 20 years and actually
thought I was being pessimistic but I
would you know I'd met a lot of the
pioneers of the field at the time it was
still a small group and they didn't even
have the tool you know that's some vague
ideas for how they might build one and
they didn't have the tools to build the
tools like it was just this is at least
a 20 year project and they were funded
but not that well-funded so I just
didn't see it happening in two decades
and I was right but I think we're a lot
closer now the reason our friends at
Yale wrote this nice article outlining
seven non-trivial stages right so first
you have to encode a bit somehow in a
quantum system and that's often
engineering new systems that have never
existed before
sometimes it's just using an atom right
but then the traps for trapping the
atoms and controlling them is very new
technology there's a funny trade-off
that I've noticed is the more natural
the bit the easier it is to get the bit
to work but the harder it is to
integrate it into a computer with
thousands of them right and the more
synthetic bits that are easy just design
it and print it out print
thousands of them on the chip sure but
then it's hard to get the bit itself to
be stable and then you get problems of
well they're not all the same right
cesium atoms a cesium atom they're all
the same but you know these little loops
a little different by a few nanometers
or a fraction of a nanometer and that
those you know the fact that they're not
perfectly identical does create an
interesting software challenge for us
but anyway we've you know we got to get
multiple qubits we have to be able to
measure the bits figure out what error
occurred and correct it then we this is
the big milestone we finally do error
correction and get a logical bit that
actually much less noisy than
the actual physical error rate so I'll
explain in a minute more what that means
but this is the most important milestone
then we'll enter a new era where we're
scaling these robust logical quantum
bits and today several platforms have
achieved the first three stages and I
think once this fourth stage happens
there'll be a massive order of magnitude
increase in effort investment which is
already tens of billions of dollars so I
don't mean to suggest it's not
significant at this point so a logical
bit- so this is just a cartoon of a
physical bit it could be any one of the
approaches people are currently taking
whether it's one of those
superconducting loops and ion or
anything else you get a collection of
dozens or hundreds of them imagine a
chip with hundreds of little loops on it
these red lines and blue lines are just
cartoons that represent you know if
you're near a red line here it means
apply a certain pulse our RF or
microwave pulse depending on the system
to the neighboring bits so it's it's
dozens hundreds thousands of pulses
you're shining on these bits and if you
do all of this on hundreds maybe
thousands of physical bits you've
implemented what we call a controlled
not a control but not it's very much
like a NAND gate right it's actually
simpler than a NAND gate if this bit is
zero
flip this
that's all it is it's a fundamental
building block of computing and to do
that simple gate you have to engineer
hundreds thousands of these things and
apply hundreds and thousands of gates to
them this is the best-known method we
have today to robustly build one of
these and that's what we're trying to do
and if you notice a few years ago IBM
demonstrated a 4x4 piece of such a thing
Delft five by one Google nine by one and
now they have 49, 50, 72, in some cases
over 100 quantum bit qubit pieces of
this there's it's still not enough to
implement a fault tolerant gate but
they're getting closer but that's what
we're monitoring now I should say along
the way people are saying could we do
something else with these bits can we
still compute with them and not- without
doing full-fledged error correction the
answer is maybe you know we'll see you
know but let's not just talk about
our feelings is demonstrated and I'll
I'll be happy and if it doesn't work
I'll still applaud you for trying but we
don't know it's looking a little it's
looking more promising I would say so
they might be able to get some quantum
speed-up for certain problems with
earlier technology which will be great
but most of my work is on a scalable
fault-tolerant quantum computers where
you can write any computer program and
compile it to run on that hardware you
might want to reconfigure the hardware
for that problem but ultimately you can
do anything a quantum computer can in
principle do which includes you know
designing new drugs optimizing the
production of fertilizers optimizing a
layout of systems and so on and it's
really moved from a physics you know and
I showed when I was summarizing this
state of the art a decade ago it looked
like a physics experiment right and then
in the last five years it started
looking like a chip that was still
largely in a research lab and a
university or maybe IBM research but now
it's there's a much much bigger
investment there looking like computers
they're working with teams of engineering
teams and in organizations that can
quickly attract the capital and
scale and solve the engineering problems
if needed it- many big names all around
the world mostly superconducting qubits
that I alluded to earlier but also some
ion trap so you know Atomic clocks for
example they have a collection of cesium
atoms and the oscillation between zero
and one of the cesium atom is how we
define a second today and our friends at
NIST realized they could leverage that
atomic clock technology to build quantum
computers and that's one of the the
front-running approaches. China has
recently entered the game they've been
in the communication game for many years
but recently you know the government
then Alibaba and then by doing $0.10
like billions of dollars they're just
ramping up but very smart people who are
already starting to do some very
interesting work so already in the tens
of billions of dollars allocated for
this. This perhaps jolted the United
States too so you know people asked me
who's winning right now well right now I
think the US is but China is catching up
very fast so they've actually amazingly
have got a bipartisan bill passed and
signed into law it's not a lot of money
it's I mean it's a lot of it's a lot of
money for us but and compared to the
tens of billions that China's putting in
I think it's a lot it's a billion or so
and but it's it's at least moving things
in the right direction and helping
coordinate and organize things better so
a litmus test for me but whether people
are serious still building a quantum
computer or really just is it an excuse
to do exciting physics is do you have a
software stack? Because if you build a
computer and don't have software for it
it's just a really expensive paperweight
and and in the early days they weren't
they were pretty dis- you know, not dismissive, but it
wasn't a priority let's say and for to
some extent for good reason if you don't
have the architecture then how do you
know what to write the code how to you
know develop compilers and so on but
has changed most of the major vendors
these industry vendors building quantum
computers also have some part of the
software stack from languages down to
compilers and machine code and our
friends in Toronto are coaching
mentoring they're incubating companies
that will use quantum computers so it's
really the full stack is being worked on
and Canada actually has been one of the
leaders in in developing key parts of
that software stack right so a lot of my
personal work in the last decade I mean
in the first my 20 to 10 year- you you know for
the last 20 years I've been working
quantum algorithms in the last 10 years
I've been working i still work in
quantum algorithms at one level below
the stack as well and compiling them
efficiently to run on realistic hardware
because that that's important right
if I- do I need a million bits or a
thousand bits to solve this problem
that's years and years of engineering
between the two so just to give an
example a quick example about- of the
kind of work I do and my team and others
there's an important gate called
Atofolly gate named after a colleague of
ours at Boston, Tom Toffoli it's a three
bit gate which you know if the first
bits are ones flip the third bit so that
actually is a reversible implementation
of a NAND gate okay it's hard to
physically build a toff- like a one-shot
toffoli gate what we do is we break it
up into things we do know how to build
actually the hard part is building it
fault tolerantly okay so we want to
break the toffoli gate and the things I
can actually do in the lab and very
importantly these are you know what
these represent doesn't really- this is a
controlled not- H is a gate a simple gate
T is another math gate right so well
maybe I should say when you look at like
flipping an atom alright flipping a bit
or applying one of these quantum gates
to it mathematically we model it as
taking a vector and multiplying it by a
matrix right so in the lab it's
you know you just shine a laser on
something and effect some linear
operation when we analyze it as computer
scientists and mathematicians it's
multiplying a vector by a matrix so we
work on we take the matr- the design of the matrix and we break it up into something that they
actually know how to implement in the
lab so that's what that's how we help
and this really really important gate
which is basically the building block
for most algorithms breaks up into
something like this but it's it's
actually worse than that if you look at
the actual when you you know remember I
showed you that grid with the red and
the blue lines like a simple C not like
one of these things I said is actually
hundreds of bits with thousands of gates
on them this T gate is like 10 to 100
times uglier even worse so if you blow
this up into the actual cost this is
almost entirely dominated by these T
gates it doesn't matter what they are
but it's it's a matrix that is really
really hard to implement fault-tolerantly and if you want to optimize the
physical cost of implementing an
important algorithm you want to minimize
how many of these T gates you do and you
want to do them as parallel as possible
because that reduces your time you don't
want to do them serially exactly take
forever you want to paralyze them and we
use some very simple brute force methods
like smart brute force method called
meet in the middle it's a very basic
technique in mathematics and computing
we came up with a better implementation
of that and then our friend at Dalhousie
looked at what we came up with and I
said hey I can parallelize that really
simply where they go you're right like
why didn't we see that so then we we
said you know what we can generalize
that we now we see what you've done and
we generalized it to a much bigger class
of things and furthermore we didn't want
you know you don't like time memory
trade-offs are great but memory is also
very expensive and we said what can you
do with a fixed amount of memory and my
student wrote I well this is this is the
optimization problem and I said well
that's a matroid it looks like a matroid
he said what's a matroid I said well
look it up
you know cause that's what I had to do- no
actually I was very lucky my supervisor-
matroids obviously- Bill Tutte was
actually you know I think the foremost
figure in major theory for several
decades in the twentieth century
and my supervisor wrote the classic
textbook for matroid theory and well
late to mid 20th century so I knew what
it was right and it was indeed a matroid
and turns out there was a polynomial time
algorithm developed by Jack Edmonds here
in the early 70s that solves that
problem so we had an efficient algorithm
for optimizing the allocation of T gates
and it significantly improves the cost
of running some quantum algorithms so
it's just it's a very serendipitous
right I kind of doubt that Bill Tutte
and Jack Edmonds and Dominic Walsh and
Bill Cunningham whose was was a jack
student would have anticipated that as
they were just doing this very
fascinating mathematics at the time so
another I'll just cut to the chase with
this one but there's another you know
another you know like I said we wanted
to this physical thing
it's this weird matrix we have to break
it up into things we can actually do as
approximately as we can and there's a
lot of deep mathematics underlying it we
developed a whole new paradigm for doing
this which first said okay what can we
do exactly, right and then how do we
round off to something we can do exactly
so this is what I want to do I can't do
it exactly and so we've broken up into
two steps first let's understand what
can be implemented exactly and then find
something that's as close as possible to
what you want to do well it's not rocket
science but there's a you know hold some
things can be rounded off some things
can't be there's a lot of diy fancy approximation so we talked to our number
theory friends but the point out that
the cool thing I want to tell you about
is we wanted to rigorously show that you
could on poly-time around this thing off
to something you could synthesize
and my student came up with this great
idea he said well what if I had two end
syllabus initialize them to 0 and return
them
I just contribute it back you know I'm
just borrowing those 2 bits, I'm like well that's ok it's better than nothing it's
a constant number of bits and he said
well the round off problem in that
because rounding off to something that
has like Euclidean norm 1 is I said
this is either gonna be really easy
really hard it turned out to be really
hard unfortunately but if you add two
bits the round off question so you can
round sine plus cos something over to
to the end but then it's not going to
have norm 1 there's a tiny little
deviation and we needed to find small
numbers ABCD such that A squared plus B
squared, C squared plus d squared, equal
that deviation M, M is an integer and I'm
like wait a minute I've heard of this
before this is the Lagrange core square theorem- completely, like who would have thought any- like so
there's a theorem in math that says any
integer can be written as a sum of four
perfect squares in at least one way you
think well that's cool, completely
useless, but very cool right and then and
then Jeff Sharlet in our computer
science department and the famous
cryptographer Michael Rabin in the 80s
figured out an efficient way to do that
so we coded it up and we cause this was
you know this is important for
optimizing the compilation of quantum
algorithms now this result itself has
been superseded by other number theory
methods but it was I just was I thought
this really neat but again very deep
mathematics you never know what it could
be used for fundamental undirected
mathematics targeted research they're
both very important and valuable and
very complimentary and we developed all
sorts of other tools for doing
optimizations including the application
of Reed-Muller decoding, Reed-Muller
decoding is useful in communication
theory again we just started saying well
how would you know what does it mean to
optimize this and my student recognized
this is actually a Reed-Muller code so
any improvement in Reed-Muller decoding
which again is a standard method for
communication scientists would give us
better quantum compilers now
this is that what my friend calls happy
quantum there is you know with any new
capability that comes of responsibility
to mitigate any risks it introduces now
sometimes we like things to be hard and
and one of the pillars of our digital
ecosystem the security of it is that
factoring is hard
all right multiplying numbers is easy
factoring numbers is hard and that's
what's called RSA cryptography we use it
all HTTPs that little s relies on this
or elliptic curve crypto-
to be hard except quantum computers
that's just one of the weird things that
happens to be really really good at and
it's just a fluke that Peter Shor
- a combinatorial he did a lot of
really important work in computational
geometry brilliant colleague at 18
T Bell Labs at the time saw like there's
paper one of the seminal papers in
quantum computing was of course rejected
at the time he but he was one of the
referees and he said I think I can adapt
these methods and factor large numbers
unfortunate the devices didn't exist
it's kind of like what Ronon and Scotney
and did work they figured how to break
something before it was deployed right
so nobody died
similarly Peter figured this in '94
before anyone had a clue how to build a
clone computer so there's plenty of time
to procrastinate and not fix the problem
and it's a big problem right because it
underpins the entire digital- our entire
economy basically depends on tools which
use security protocols which use things
like public key crypto or symmetric key
cryptography quantum computers decimate
the public key crypto side of that it
weakens symmetric key crypto easy to fix
in theory not so easy in practice but
with this the most dangerous part is a
public key cryptography now people often
say well look crypto is not the problem
you know who cares there's so many other
threats to our cyber systems like why so
what if this other one you know gets a
little worse it's like you well you're
missing the point I mean
most of these have nothing to do with
mathematics and this is how most hacks
are occurring today but if you order
them from bad to worse it's you know
these are you know with just about
anything what you try to do is you
reduce the chance of something bad
happens if you're responsible you have
some mechanism for detecting if
something bad happens and you have a
protocol for remediating when something
bad happens right you can apply this
to just about anything but that's sort of
the framework we have in cybersecurity
with all these things there's a clearly
if it didn't kill you there's a way to
remediate right user errors well we have
that all the time but you might have to
rebuild you know ransomware there's a
way to remediate you pay it off or you
restore from a backup or you well or you
shut your company down but hopefully but
but the point is we know what happens as
what Paul Kosher said this at RSA
recently we know we kind of know what
happens and 1% of our systems go down at
any one time what we don't want to face
we don't know what happens is they all
go down at the same time with no
remediation in place and fundamentally
vulnerable crypto like there's no what
do you remediated right heartbleed is
sort of in the nasty part of this chain
right implementation error and it you
know it was a buffer overflow so it's
not rocket science to fix that but it
still took many cases a year to get it
through the full supply chain through
all the proper Quality Assurance and
testing and that's a neat that's fixing
a buffer overflow but with the crypto
you can't just implement the same
vulnerable algorithm it'll still be
vulnerable so what has ironically become
my most famous theorem so how soon do we
need to worry cause Scott Vanstone would
say do I really can I wait till I retire
now he was half joking but other people
weren't half joking that they were
totally serious because you know some
information as a shelf life what all has
a shelf life X years and the most
sensitive information like trade secrets
can be many years it takes time to
migrate ask Ron and and the others how
long did it take for ECC
to go from an idea to deploy globally
deployed product decades to do properly
and then what is Z, the collapse time,
how many years for quantum computers
actually threaten these systems and you
know for the next X for the next Y years
we're stuck with these vulnerable tools
because we haven't had a chance to
deploy ones that will resist quantum
attacks we're supposed to provide X
years of security whether it's
confidentiality or integrity but if X + Y
is bigger than Z then worry you know
you have a problem you're already too
late because the information these these
last few encryptions for example won't
be secured for X years they'll be for
sale on a dark web or used against you
in some other way now if it was Y is you
know Y is bigger than so even IBM now
and others are starting to repeat this
message I tried to make it as simple and
graphic as I could so people would get
it and it is you know this approach is
you know I think NIST calls it the
Moscow theorem yeah I don't tell people
what the actual theorem is because it's
really not a deep mathematics but but
it's it's had some impact
now if Y is bigger than Z systems will
collapse that's bad ok we want to avoid
that apocalyptic situation but if we do
avoid it but we do it as a last minute
crisis management there's gonna be a lot
of software like you saw heartbleed
happen because of a buffer overflow
you're gonna have a lot of those so we
don't want to rush it and the other risk
even before we have large-scale quantum
computers is people just lose confidence
in the systems when is this day gonna
happen again I went from saying not for
20 years
- well maybe in 20 years or one percent
chance - 10 % - now I say it's a one in
six chance in under 10 years other
people disagree but we don't know is the
correct answer but that's sort of you
know anyway I won't say the
mathematician joke but so that's um we
don't know but we can't afford to take a
chance so there are solutions so what
I'm alluding to is we have to deploy new
algorithm
new cryptographic methods that resist
quantum attacks and many researchers at
Waterloo are working on those and
another method Co invented by our
colleague of ours at Montreal Joe Posada
and Charlie Bennett IBM is quantum
cryptography so in addition to just
trying to reestablish a status quo the
beauty of quantum mechanics is if you if
you you know get this intrinsic
eavesdropper detectability and they
leverage that into a way to get key
agreement the way to establish
cryptographic keys so you can't
mathematically crypt analyze it and
these work well together so we have a
new set of tools with which to rebuild
the foundations of our cybersecurity the
quantum cryptography
I mean invented by canadian-american
developed with Europe and then first you
know there's an approach to do it in
free space by communicating to
satellites that will help us get global
distances and that was first implemented
by our friends in China and Canada's
aiming to be the second to enter this
new era of quantum communication now my
take is when I first heard a quantum
crypto- actually Scott Vanstone shows you this
article Scientific American I'm like
whatever you know I just this is science
fiction
it was quite ironic then I met Joe
Broussard at a conference in '94 I was
like so I'd read his classical crypto
papers and I'm like oh so what are you
working on now it was like quantum
quantum quantum I'm like man he's really
gone off the deep end that's really sad
you know
ironically then I co-authored a paper
with them later and quantum computing
and but my take when I eventually got it
was you know cryptography that can't be
crypt analyzed that's a useful thing for
protecting people and cyber systems in
the economy against it's not it's not
gonna protect us from all threats but
that's a really valuable tool to have
deployed so it actually helped keep
people safer but what good is it if we
don't use it right you know sitting in
research papers or prototypes and labs
or just proof of concepts so I've been
spending a lot of the last 10 years
figuring out the gaps to getting it into
globally deployed solutions and we have
to do it in parallel
we can't wait until they're built and
then hope somebody adopts it I think we
need to solve we need you know it's a
chicken-and-egg unless there's a
business in use case they're not going
to build the networks and so on so
there's a lot of network flow
optimization here how do you turn
point-to-point key agreement into a
truly global network solution there's a
lot of combinatorics that in there
so we've developed the algorithms
developed the software tools made them
available open source just a few weeks
ago and we're hoping that starts to spur
more deployment we've also made posts
of the classical
algorithms available in open source
again to facilitate testing and
integration into solutions and really
kind of get this show on the road to
bridge the deep mathematical ideas which
I love into actual practical
applications standardization work we've
also been really pushing because one of
the obstacles to having these tools
deployed in practice is they need to be
standardized you can't have everybody
having their favorite algorithm because
we all need to communicate with each
other with a simple set of protocols we
all agree on so that's a very hard thing
to achieve but again talking to my
friends who made quantum who made
elliptic curve cryptography a global
standard we kind of knew what the
template was like so we've been prodding
that along both quantum cryptography
standards and we've been you know
definitely supporting this effort and
they'll standardize something by we
think 2022/23 sounds like a long way
away but we need to be ready to hit the
ground running and very importantly we
don't want to repeat you know just like
Ron and others found out that these
diffie-hellman schemes that were being
deployed we're actually vulnerable we
need to we don't want to deploy them and
then find out there's an easy break for
them so myself and a number of my
colleagues here and around the world
have been trying you know we're working
hard and studying these tools and making
sure they can't be broken by quantum or
classical computer there's many many
research challenges underpinning that
Waterloo has met much of the research
the background knowledge and talent and
students to tackle those problems
alongside others around the world
but there's certainly a long you know
road ahead here but we were fortunate to
be able to you know at Waterloo be
building on the shoulders of giants like
when I was at Oxford in late 90s I mean
I had the chance to stay there basically
but I was you know offered this great
opportunity to try to build something in
Canada and Waterloo was the ideal place
what we were trying to do here not
because we had you know a quantum
computing effort here already there were the seeds of it but because we had
the great potential the great talent
pool expertise in the combinatorics of
cryptography and so on to do something
great and I think we've come a long way
but it certainly didn't happen in a
vacuum
we've also you know the math is
important but one great thing our math
program does is it requires our students
to take a course in communication and
leadership which is an important part of
taking the great things we do and having
them have real-world positive real-world
impact so one of the things I've done
with others is articulate this
cryptographic problem and challenge in
business terms and risk management terms
because ultimately that that's that's
the language most of the you know the
business the decision makers that's how
they analyze it there's a risk and they
have a whole paradigm for doing it so we
tried to reformulate it in a way that
they can plug it into their existing
risk management paradigms so you know
cutting across so we have to mathematics
is a really critical integral part of
meant of tackling many of society's
challenges now and we have to
collaborate with the engineering
sciences the physical sciences the human
and social sciences and we have a long
long history of doing that so just to
wrap up on a positive note because I
open you know there's a great problem
and threat here this quantum threat and
it's it's the solution required to meet
it maybe is a blessing in disguise right
because it might seem like
that was a unfortunate thing that
quantum computers break the tools
underpinning the security of our digital
economy but maybe not you know
maybe because it wasn't per- it was far
from perfect
there's many vulnerabilities just in the
like what we're building on is a
patchwork right it's normal because we
did hindsight's 20/20 so I'm not
criticizing the people who got us here
there's many great tools but then it
there's this hard that it's hard to get
the business or political buy-in to fix
something that isn't broken vulnerable
is not enough you know it's got to be
broken has to be on fire for people to
then say oh maybe we should have fire
trucks but right until it actually
happens once and in somebody you
actually care about suffers it's really
hard but then so then the blessing in
disguise is quote this quantum threat
it's actually fairly simple to articulate the solution is hard but not
insurmountable it's forcing us to retool
them to rebuild the foundations of
cryptography and thus of cybersecurity
something we really realistically would
never have done otherwise right so while
so we have a choice we can we can
rebuild this flimsy flammable foundation
we enough limbs I don't want to under
I'm gonna beat up on it too hard but it
is very vulnerable we can rebuild it
through proper you know proactively
lifecycle management and have a much
stronger foundation that makes us not
just resilient to quantum attacks but
more resilient to other attacks so
that's what we're trying to achieve the
alternative is we procrastinate a new
crisis management we have an even more
vulnerable foundation to our cyber
systems and digital economy of course
we're very hopeful and we're spending a
lot of time doing the research and
spreading the word and we are I believe
building a much stronger foundation to
our digital economy and our society so
thanks so much for your time and
attention I think there's a few minutes
left for questions which I'm looking
forward to
thank you Michele indeed there is time for
questions alright thank you very much
for the presentation again another
presentation with a lot of impact on
human experience going forward in the
future question I have for you is is and
I bear with me with this because there
is a level of abstraction required with
these type of discussions in the
classical of the definition of computer
you can get in I don't want to get into
the details of that but you could see it
where math and science cold build on each
other in different layers and you start
with the actual physical world and then
you do a little bit of math and you try
to control things and then you change
the physical world into something
historically called a bit on/off as you
build on that bit you get into logical
constructs called circuits and then you
you take those circuits and you build
logical constructs with registers and
and and other combinations the key my
question gets into when you start
putting the registers together and you
apply mathematical theory computing
theory in the form of something like the
church-turing thesis as it connects back
into those constructs of engineering I
can you--can from what I'm understanding
of quantum computing I don't think we're
at that level of abstraction we're
probably still working with math at
building some of the circuits and some
of the registers is there something that
is equivalent can you confirm that I
have an understanding my understanding
is somewhat accurate and is there an
equivalent at some point where we get
into the need for architectures like the
von Neumann architecture that applies
church-turing mathematical thesis and
computing thesis thank you yep
so with regards to this church-turing thesis
we don't violate the original john
church-turing thesis because we can
actually simulate a quantum computer but
with exponential overhead we do
challenge a strong church-turing thesis
which talks about the efficiency with
which you can do that so we don't change
what's effectively computable we change
what's efficiently computable but you're
kind of right but maybe five years ago
or ten years ago but because twenty year
ten twenty years ago we were still
working at the low trying to build a bit
right we weren't worrying about well
some people were but we they were
largely ignored to be honest and maybe
was premature but some of them actually
knew what they were they were really way
ahead so so I don't actually know how
it's gonna play out like in my a-
because I was part of a big project that
funded for teams looking at different
types of programming languages quantum
programming languages one of them was
very high level like functional or like
New Age you know approaches to
programming which builds on decades of
experience the others were some of them
were much more low-level circuit
description languages which was more
from the 70s in fact I would I met some
people who wrote WATFOR, so I asked
them like I met with them and I said
like we could probably use your advice
more than the people doing the fancy
modern compilers stuff but ultimately we
want to tap into all that knowledge and
I don't know what the first if the first
generation programming languages will
use will be more like you know the Q
sharp stuff that Microsoft is so
Microsoft has built you know a version
of an F sharp type you know system that
is a little more abstract and others who
are working with more low level circuit
description languages my personal work
is that is it agnostic I encourage that
because I know we need it but we just
any intermediate representation of the
circuits and will optimize it down to
the machine code so we're starting to
get to our we do have a model for the
architecture we do have we do have like
it's still largely manual but we're
starting to automate more and more
pieces of it but the compilation process
we can manually walk through programming
language intermediate representation
down to laser pulses it
it's still growing and I'm trying to
build we want to build that community of
experts who understand all what you were
talking about because initially we
didn't have you know we're still just
the the mathematicians not just but I
mean we also we knew ultimately we would
need to engage more and more people and
it's starting to grow and now the
industry teams have like really smart
people work who-who working on that full
software stack and there's a lot of the
more fundamental work being developed in
universities in Waterloo and across the
world
this is on yes so you're talking about
standards and I'm thinking about
collaboration so right now it seems that
you're drawing from disparate pieces of
mathematics and science and that's good
because they're all in their own pocket
but as you're moving toward a solution
I'm curious to what extent there will be
collaboration which is necessary for
standardization, so do you have a sense that there is collaboratization? Yes so and that's so
hard like quantum mechanics is hard and
math is hard but getting the social
engineering problems is even harder I
find so- when I came here and CNO asked to
working quantum computing so they could
keep an eye on me as Scott said I wanted
to sort of replicate what I helped my
supervisor do at Oxford which was a very
multidisciplinary center because this is
it was still far too you know in the
early days it eventually starts to
segment but in the beginning it didn't
it was the same you know group of people
building and programming everything so
we quickly expanded you know I wanted it
went to science and engineering and so on
so IQC is all about the sort of that
breadth on the fundamental research side
but we also need collaboration across
the different sectors that the
policymakers the government many parts
of the government and industry and
that's happening more and more
so I started seven years ago we start I
started with one of the international
standards bodies called Etsy one of my
business colleagues introduced us to
them and we told them the problem and
she was great she liked well let's have
a workshop and we brought together
handful of believers from industry and
government and standards and and it was
actually a pretty successful workshop in
southern France in Sophia Antipolis
the Etsy headquarter these are the
people who did GSM and look after mobile
communication standards so they know
standards they didn't know much about
quantum computing or anything but we
started this and the next one is in
Canada and then we went to Korea in
Europe and in Canada again and we're in
China last year we're gonna be in
Seattle this year and it's grown into
this massive event with
people who would otherwise never meet
are coming here I work hard on the
program I main part of the program is to
try to make sure people understand the
breadth of the audience and try to cross
speak to the different sectors it's it's
slowly working but there's certainly a
long way to go so there's still many
communities we haven't really fully
tapped into that need to engage but
instead of just having a Babylon with
you know we're kind of growing from a
nucleus and expanding it I hope that
answered your question but well then
we're in dialogue with with the security
folks I mean they're this you
communicate information security people
are very engaged in this process well my
take is let's take the threat side off
the table so you know it's not a weapon
of mass destruction when it happens it's
just you know cool H I perform its
computer which of course will be export
controlled and everything but more the
same and we can do it it's in our
control to get rid of the codes we know
will be broken not get rid of them
just add the additional codes I think
you should still keep elliptic curve
crypto because its your best defense against classical attackers
and include one of these other codes on
top of it to protect us against quantum
attackers make the whole system more
robust against all the knowns you know
attacks and then just take the threat
side of quantum computing off the table
thank you so much for this amazing
lecture I see your lecture in two parts
when you talk about building the
physical layers of the quantum computers
and then coming to the algorithm and
security part so I was wondering like if
the best quantum computer we have is of
hundred qubits so how do we actually
implement the algorithms of like which
can be used in quantum computers and
which can be used to attack security or
save security so I'm not able to connect
those parts
so I'm not sure I fully understood the
question, you said a 100 cubits
yea if the best we have in physical quantum computers is 100 qubits, so are we like implementing those quantum algorithms on those computers?
right so I mean
you could do the algorithmic design like
most of the you know even compiling the
code you don't need the actual computer
there right so we can do a lot of it
almost all of it you know for me except
for the running it without actually
having the device so we have a model for
it we can do full resource estimation we
know what how big of a hypothetical
computer it would take we know how long
it would take and what we're doing in
the short term is we will we will do a
hundred bit version of it as a
proof-of-concept just to validate the
full tool stack that we didn't forget
something or if there isn't some silly
glitch or gap so we can do the the 10 we
can just simulate 25, 30 bits easily but
we can nowadays even try the algorithm
on a 70, 50 that's easy it's not quite
that easy but we're soon at the point
where we can test it on a few dozens
it's still not likely to be useful but
we can sort of validate you know
validate the software in this small
version but otherwise it's a good
there's a whole theory of verification
of your code which still needs to be
developed there's there's still so many
challenges and we're we're still we're
obviously borrowing all the methods
people have developed for classical
computing but some of it doesn't work
look you can't debug you can't have a
debugger where you just stop and look at
the you know because you if you look at
the state of the quantum computer you'll
collapse it so some of the standard
debugging methods don't work some do so
there's still actually some really int- and these are the kind of things you uncover when you try to do the proof of concept.
I mean theres something I'm doing right now where somebody thinks they can do something. Well ya I know you can't, and they're like well here, you know
run this algorithm and tell me if it works, but then if it doesn't work, he's going to say there's a bug in my code, right?
and then well who's right right it's on me
like now I have to somehow prove that no
no my codes right it's your you know
your stuffs wrong so not that we're
encountering now because we're doing
small proof-of-concept things okay so we
let me conclude this this question
session here I maybe have more questions
offline let me thank
Michele again for his engaging talk
thank you
