Bold questions and brilliant minds converge at CIFAR’s Virtual Talks.
Free, and open to the public, join us as we bring high-impact research from CIFAR’s fellows, chairs, scholars and advisors to the forefront.
How does your information stay secure? What makes a “good” quantum algorithm?
Researchers are harnessing the power of quantum computing – by making certain types of classically intractable problems solvable and to develop unprecedented encryption technology to ensure an unhackable future.
Show Transcript
– I welcome everyone to Brilliant Minds, Bold Questions,
a virtual event series exploring questions
being addressed by some of the world’s top researchers.
Each talk pairs speakers and moderators
from across disciplines, sectors,
and the world to explore questions shaping our future.
You are not familiar with us.
CIFAR is a Canadian-based global research organization
that convenes extraordinary minds
to address the most important questions
facing science and humanity.
Today’s event is in partnership with the CNRS,
the French National Centre for Scientific Research,
a publicly funded institution that supports
research in all scientific disciplines.
My name is Fiona Cunningham,
and I’m a director of research at CIFAR.
And it is my pleasure to introduce you
to David Gosset and Eleni Diamanti, our speakers today.
David Gosett is a CIFAR fellow
in our Quantum Information Sciences program,
and a professor at the University of Waterloo
and the Perimeter Institute for Theoretical Physics.
He’s a quantum computer scientist who’s interested
in quantum algorithms and complexity theory.
Eleni Diamanti is a researcher at CNRS,
the French National Centre for Scientific Research,
and a professor at the Sorbonne University in Paris.
She’s also the vice director
of the Paris Center for Quantum Computing,
and specializes in quantum cryptography.
Today, we will be discussing how quantum algorithms
can be used to solve emerging problems.
So today’s session will last about 30 minutes.
As host, I will ask our speakers questions,
and they will also be taking questions from you
joining us today throughout the session.
If you have a question,
please submit it through the Q and A function
at the bottom of your screen.
Lastly, the session is being recorded
and will be available on cifar.ca website next week.
So thank you for joining us.
We really appreciate your time.
And my first pick off question is very simple.
What are quantum information technologies?
– Okay, thank you for the nice introduction, Fiona.
It’s great to be here with all of you today.
Quantum information technologies really encompass
a pretty broad set of technologies that aim
to harness the physics of quantum mechanics
to store and process information.
And one example of that,
which is my research area, is quantum computers.
And in a quantum computer,
you would store information
in the sort of complex quantum many body state
of physical system and process the information
using local operations on subsystems of that state.
But quantum technologies is a broader term
that also encompasses technologies
that can be used for communication,
for cryptography, for sensors,
and other information processing tasks.
And some of those are the sorts of tasks
that Eleni is an expert in.
So Eleni, maybe now is a good time
for me to let you jump in.
– Thank you very much, David.
And thank you very much, Fiona.
So it’s a pleasure to be here with all of you today.
So what are quantum information technology?
So I guess I would add with respect
to what David had just described.
For me, I like seeing the quantum information technologies
as an outcome of what has come to be known nowadays
as the second quantum revolution.
So then obviously, this leads to the question
of what is the first quantum revolution.
So the way we see it is that the understanding
of quantum mechanics at a bit of a microscopic level
has led in the last decades since many years now
to the discovery of new technologies
that we’re using in our everyday life.
This examples include, for example,
the transistor, the hard disk, lasers, MRI.
So these are technologies
that are using collectively,
in a sense, microscopic level, quantum mechanics,
and constitute the output of the first quantum revolution.
So quantum information technologies
has gone further than that.
They actually go to the control and manipulation
of quantum particles at the single particle level,
and at the control between
and interaction between particles,
to produce effects and encoding of information,
information processing and communication tasks,
that cannot be done if you don’t go
at this level of understanding
and of manipulation of quantum objects.
And this leads exactly to a quantum advantage,
a quantum effect in all these categories
of technologies that David just mentioned.
I guess one of the major application areas
where David works is
quantum information processing and quantum computing.
So why don’t we talk about this a little bit further, David?
Do you think you can tell us, what is a quantum computer?
And why is it different?
In what sense is it different from a classical computer?
– Yeah, great.
So maybe we can start by just thinking
about how we often learn about computing
in say a class at university.
You might learn about storing information in bit,
and then processing information using logical gates,
such as the and or the or gate.
And because we often talk about these things
in that sort of abstract level,
we often forget that at the end of the day,
the device that you’ll be using to implement
your or gates or your and gates or whatever it is,
your circuit, your computation,
that device lives in the physical world
and is constrained by physics.
And the fact that we can build a computer
that has bits and implements logical gates is
because classical mechanics,
the physics that was used to implement that device
allows for you to process information that way.
And what was realized by famous physicists,
Richard Feynman and David Deutsch
around the same time in the 1980s,
is that while the computers that they had
at that time and that we continue to have today,
they’ve grown increasingly powerful, those computers,
they don’t actually exploit all of the physics that we know.
And quantum mechanics incorporates effects
beyond classical mechanics,
such as superposition and entanglement.
And the really remarkable thing is
that those effects actually do provide an advantage
in computation for certain specific tasks.
So what Feynman and Deutsch proposed is
the idea of building a computer
where the information is stored using quantum devices,
processed using quantum effects.
And what we’ve come to understand is
that if you do things that way
and you build a computer in this manner,
then there are tasks,
certain specific tasks that you can solve
faster than a classical computer.
And it’s crucially not just running
every step of a procedure to solve a problem faster.
It’s using a fundamentally different set of transformations
that allows you to arrive at the solution using fewer steps.
– Okay, so that makes sense.
So now, this, how does one go,
and I think this is a crucial question, I guess,
as we move closer towards applications,
how does one go from an abstract understanding
of quantum algorithm,
of quantum computing, to real world problems?
So what are types of real world problems
that the quantum computer could really solve efficiently?
– Well, that is a great question.
And I think that if I had
the perfect answer to that question,
I’d be maybe swimming in cash or something like that.
So I think that the way that our field has developed
and our understanding of the power of quantum computers,
it really was in the 1980s, as I mentioned,
Feynman and Deutsch proposed the idea of a quantum computer,
and their motivating example was
that quantum mechanics itself,
many body quantum mechanics, like for example,
what you might see in quantum chemistry,
those types of simulations,
if you wanted to simulate that on a classical machine,
it would be,
we don’t know of a good algorithm for doing that.
But on a quantum computer, it would seem that,
or they showed rather that quantum simulation is
a task that can be performed much more rapidly
and with a quantum advantage on a quantum device.
And then Peter Shor had this major breakthrough
in the 1990s that showed that certain number
of theoretical problems can be solved
more rapidly using quantum computers.
And since then, we’ve also understood
that certain types of optimization problems
can be solved faster using certain types of subroutines.
So at some level, we’re, for a long time,
we understood kind of categories of problems
where certain subroutines could be deployed
where we get a quantum advantage,
but you asked about real world problems.
I think now is a time in our field
where devices are being built,
and those questions are becoming more pressing.
How do we take the idea
of quantum simulation and the abstract,
sort of quantum advantage that we understand
in some kind of general setting?
And how do we map that onto a problem
that matters for a company,
or that matters for all sorts of tasks
that you might imagine
quantum simulation could be useful for.
So for example, people talk about using
quantum simulation algorithms to improve,
to understand better batteries.
Or people talk about sort of speculative ideas
of how we might use quantum simulation in the real world.
And I think really understanding the details
of how that is going to work is
a major challenge for our field,
and something that involves
bringing together subject matter experts
with quantum algorithms experts.
Because most people who work
in quantum algorithms are not also experts, say,
in battery technologies or in the types of quantum chemistry
that might be relevant for other practical tasks.
So I don’t have the perfect answer for you,
but I think this is part of the discovery
that we’re going to see over the next five or 10 years is
really that matching of subject matter experts
with quantum algorithms experts,
and trying to understand how we can take
these kind of more abstract algorithms results
and apply them in the real world.
– Would be exciting.
– So let me, at that point,
let me jump in and ask you a little bit
about the kinds of quantum cryptography technologies
that you’ve been working on.
So in particular, what is quantum cryptography?
And why are researchers so interested?
And if I can add in one more aspect,
what are the potential implications for current crypto,
like classical cryptographic methods,
once a quantum computer is built?
– Good question, so now we’re sifting, I guess,
from quantum computing and quantum information processing
to one of the next big application area
of quantum information technologies.
So that is very pertaining to cybersecurity
and to secure communications,
which is particularly relevant, I guess,
in our society that is becoming more and more digital,
and where very high risk data are being transferred
over the internet, so over big, large networks.
So what are the cryptographic techniques
that we’re using today?
So today we’re relying on a big number.
We’re not going to go into the details
of all the techniques, of course,
that cryptography is using,
modern cryptography is using today.
But the main point behind all of these techniques is
that they do need to make some sort of assumption
about the computational power of an adversary.
We have to assume that there is somewhere,
this is what is common in cryptography
and malevolent party,
an adversary who wants to eavesdrop, to hear,
to obtain information that he’s been communicating
over the information channel,
and this eavesdropper, this malevolent party,
we have to assume something
in all modern cryptography algorithms
about their computational resources.
So the point now is that some
of the most common cryptographic algorithms
that we’re using today are vulnerable
to future developments, technological developments.
It can come from a quantum computer,
like the one that we’re just discussing,
when it will become powerful enough
to break such cryptographic technologies.
It can come also for other technological developments.
The point is that once you make assumptions,
it means that you have in general vulnerability.
So what quantum cryptography comes there
to offer is filling up this gap and saying, okay,
so because of quantum mechanics,
we’re going to operate our cryptographic system,
not at the mathematical level, but at the physical level.
We’re going to come with a quantum physics principle
that we just mentioned before, superposition, entanglement,
so the main principles of quantum information theory.
And this protects, in an intrinsic way, our communication.
So essentially what’s happening in quantum cryptography is
that any attempt of malevolent party
and adversary to obtain information
about the communication that is being transferred
necessarily leads to error, detectable errors.
And when the legitimate parties
of the communication channel actually treat,
process this information, they can detect this error,
and then do everything that is necessary
to bound this information.
To bound, to basically make it negligible,
to make sure that they can produce
a cryptographic sequence that will be protected
against such adversarial effect.
So the effect is obvious, I guess, to answer your question.
I guess this has important implications,
direct implications in security and communication,
because it means at one level
that we’re offering a security guarantee,
a security level that would not be available
in classical cryptography.
Of course, the story is never easy.
If the world would be perfect,
there is, quantum cryptography is not perfect either.
First of all, it cannot do everything.
So we don’t know how to do
with quantum cryptography authenticated (indistinct),
so know we’re talking to the right person.
So we also, also has physical requirements.
We can talk about it later, some limitations,
because we’re working at the physical level
and not at the mathematical level.
One needs to pay a lot of attention
as well in practical security once you go
from an abstract protocol to a real implementation.
And I think, but it does have
a clear added value in cybersecurity.
And the vision today is that we have
to make hybrid techniques exactly like in computing,
where I believe,
and I’m sure you can confirm this as well, David,
when I believe the trend is
that quantum processing machines
will probably be combined
with high performance computing and classical machines
in the same way in quantum cryptography
will not function alone.
It needs to be hybridized and bring
a very specific and well defined,
added value to classical cryptographic technique.
So I think the main challenge today is
to make classical and quantum cryptography’s work
hand in hand to come with viable solutions,
offering maximal security.
– Right, and if I can ask, can you paint a picture of,
how does a quantum cryptographic protocol work?
Just in layman’s terms, say.
– Sure, sure, sure, I can tell you.
So essentially,
the point is so I can mix a little bit of protocol,
abstract description, and a bit of physical description.
So because I’m an experimentalist,
I feel comfortable making this link.
So maybe if it can help you,
you can picture the protocol
thinking about physical objects,
like the photons in our case.
Photons is the particle of light,
is the fundamental particle of light.
And this is the carrier of information
for quantum communication and cryptography.
So in the hardware for quantum computing, has not been,
we don’t know yet exactly
what will be the carrier of quantum information.
It can be several, there are many candidates,
physical systems to be candidates,
but for quantum communication and cryptography,
we know it’s light, it’s photons,
because light has been transferred,
that can be transferred nicely over long distances.
And it’s less subject to noise.
So how would the protocol work?
So you take your photons,
you are encode information on them.
So they send it somehow in every protocol, it needs to,
what does it mean encode information?
You basically take a property of your quantum object.
For a photon, it can be polarization.
The way the waves,
it translates, doesn’t matter really.
And then we put on the photon, these zero and ones.
The zero and ones or intermediate states,
the superposition states are the fundamental basis
of quantum information randomly.
So you pick among these states randomly.
So random, this is an inherent property
of any quantum information protocol,
for computing, for communication and everything.
Then you send it over your quantum channel,
which can be, for example,
an optical fiber or a satellite link.
And then the receiver receives these quantum objects,
and they- – I could be the receiver,
so you can-
– You can be the receiver, exactly.
And so you pick the correct measurement.
So this, you can also,
another way of doing it is to use entanglement,
the other properties.
So you share entangled photos between these two parties,
and they both measure.
These are equivalent ways of looking at your protocol.
And then from the measurement results,
there are, the two parties,
they correlate, they communicate.
They see what they have measured,
what they have generated.
They calculate.
They examine these results.
And they see how much information potentially
eavesdropper could have acquired out of this.
And essentially, because they can trick noise,
and any noise can be attributed to adversary,
they can somehow extract the secret information
that they were looking for.
This is in, so any,
so this is the main idea behind these protocols.
– Great. – But why don’t we go back,
if you have a little bit of time,
why don’t we go back a little bit to computing?
And maybe you can tell us,
what are the recent developments in computing?
What are near-term applications of quantum algorithms?
What do you think the main challenges in the field today?
– Yeah, that’s a great question.
And I think you really touched
upon some of these ideas earlier
when you mentioned the idea of hybrid algorithms
and co-processing with classical computers.
And I think one of the main questions is,
how are we going to move towards useful quantum algorithms
with near-term devices that are not as far along
as the kind of model of computing
that you might hope to have in the future?
So for example, in the future,
we want to have large scale quantum computers
that are capable of correcting errors
in the computation as they occur.
And those quantum computers
you can really think of as like the analog of,
or you should think of the abstract model
of a set of quantum bits
and then a set of logical operations.
And you could imagine writing down on a sheet of paper,
a set of transformations,
and then implementing it on the quantum computer.
And there’s not really much difference
between what is actually implemented
and what you wrote down,
because any errors that occur
in the machine are corrected as the computation proceeds.
And it really is a sort of high fidelity implementation
of the thing that you wrote down,
the algorithm you had in mind.
And that’s kind of the dream,
and the technology is moving in that direction.
But for now the kinds of devices that we have,
and when you ask about near-term devices,
what does that mean?
Well, John Prisco coined the term
noisy intermediate scale quantum.
And that reflects the fact that these devices are noisy.
They don’t currently have the capability
of quantum error correction.
They’re intermediate scale because they have fewer qubits
than you might need to implement Shor’s algorithm,
for example, certainly fewer than you would need
to implement a large scale version of Shor’s algorithm,
but they are quantum.
And they’re quantum in a sense,
not just in the sense
that there are quantum effects going on,
but also they’re sort of computationally interesting,
because we don’t know how to simulate
these devices on a classical machine.
So they’re beyond the range of what can be done,
what can be simulated on classical machine,
which means that at some level,
there’s some kind of quantum advantage,
but we don’t necessarily know
how to harness it in the presence of noise,
and with few qubits and small circuits
that we can implement.
And so people have tried to understand
algorithms that operate in this regime,
but that has been much less well studied
than the kinds of larger scale algorithms
that might be deployable in the future.
And some of the ideas that have been proposed are,
as you say, like hybrid quantum classical algorithms,
variational quantum algorithms
that have a certain robustness
to the types of noise that might occur in these devices.
But the challenge there is that when we talk
about Shor’s algorithm
or some of these kind of pioneering quantum algorithms
that we understand very well, at least in theory,
we have an understanding
of what the run time of those algorithms is,
what the performance guarantee,
what the output of the algorithm will be with a given input.
But when you talk about designing algorithms
for near-term devices,
oftentimes the algorithms that are proposed are heuristic.
Meaning that they don’t have performance guarantees,
but they are something you could try
on a device if you had one.
And so I think a lot of the near-term applications
have yet to be really understood,
because you have to run them on devices of increasing size
to see whether or not there is really an advantage.
They’re not necessarily algorithms
that we can analyze on a sheet of paper and say,
yes, we’re going to get this much advantage
as long as we can build a device with 150 qubits.
It’s really quite a bit more challenging
to understand those algorithms.
Because the analysis also involves looking
at the specific hardware or the types of operation,
the connectivity of your device
and certain other details of your device
that you might not necessarily have to care about
if you’re building a large scale quantum computer.
– And now are these the type of algorithms
you’re working on, or something, what is your work-
– Well, yeah, so in a way, yes.
So I kind of alluded to the fact
that there’s this ephemeral boundary
between what is classically simulatable,
and what is beyond classical
sort of from a computational point of view.
So you may have heard
of the Google quantum advantage demonstration,
where they sampled from a probability distribution
that is thought to not be possible to sample from
in a comparable amount of time using classical computer.
And so my research has tried to resolve
or delineate this boundary more sharply in various regimes.
So for example, I study classical simulation algorithms
for quantum computers.
The ways we can leverage structure
in quantum many body systems
to simulate them better on a classical machine.
Classical simulators can also be used
to benchmark small quantum computers.
So it’s not only useful to understand the boundary,
but also to benchmark these small machines.
And on the other hand,
I also study quantum advantage
with restricted types of quantum computation.
So for example, short depth quantum.
So the depth of a circuit is
sort of the number of time steps,
allowing for a certain amount of parallelism.
And we’ve studied things like,
what kind of quantum advantage
can you achieve with short depth quantum circuits.
– Great, thank you for that.
That was a really great tour of the current state
of quantum computing and quantum cryptography.
So we do have some questions from the audience.
And I’ll just encourage
either of you who feels most equipped to answer,
please fire away.
So this one is from Anuprim Gosh, and his question is,
so people refer to current classical computers
as a Turing machine.
Basically, computation done by these classical computers are
modeled and designed by Turing’s abstract computing machine.
Does the quantum computer also satisfy
the Turing machine model?
– That’s a really great question.
And I think you’re really,
you’ve gotten to the heart
of why we’re so excited about quantum computers.
Because you’re right,
that even though computers keep getting better and better,
the computers that we have, our laptops, our desktops,
they’re all from a perspective
of what kind of algorithms can they run.
They’re all equivalent to the Turing machine model
proposed in the 1930s by Alan Turing.
And the only model that we know of
that really is outside of,
that cannot be simulated
by the Turing machine model efficiently is
the quantum computers.
So quantum computers are thought
to be more powerful than Turing machines,
and they’re the only realistic model of computing
that we believe has that property.
So thanks for the great question.
– Yeah, thanks indeed.
And one last one.
So how, this is from Chris Ford.
So how close are we to being able to apply
an algorithm such as Shor’s algorithm beyond theoretical
to factor a large number and prove
our performance gains over a classical algorithm?
– So Eleni, would you like to take this?
– Shall I answer this as an experimentalist?
So we’re not there yet, Chris.
So I guess exactly like David was discussing
where at the level where we know how to do NIS devices,
noise intermediate scale devices.
It means a few hundreds of qubits in the best case
or roadmaps of big companies or startups
in quantum computing based on different technologies
predict that they should be able to get the device
up to a thousand qubit within the next three or four years.
But you need to understand that implementing
the protocol like Shor’s algorithm requires
a massive number of qubits,
much, much bigger number of qubits.
And why is this true?
It’s because for really implementing algorithms
like Shor’s algorithm,
we need to be able to master
error correction and fault tolerance.
So we need to be able to correct errors and noise,
which we know how to do, we have protocols to do it,
but they require a very big number of redundancy,
of essentially the correspondence
between the physical qubits that makes your device
and the logical cubics that are actually used
for the computation is not very favorable
with the current codes we have,
error correcting codes and fault tolerance algorithms.
So there is a need
for theoretical developments in this direction,
and still milestones to be reached
from an experimental point of view,
mastering noise, for example, in systems,
to be able to see implementation of Shor’s algorithm.
I remain very optimistic.
I think we’ll see it one day.
But it’s very difficult to predict today
without further progress exactly when this will happen.
Don’t know if you agree, David.
This is my- – Absolutely.
I have nothing to add.
It’s a perfect answer.
– No, I think that was a great answer.
And the challenge of quantum computing,
its uses in quantum cryptography is not lost
on both national governments with the (indistinct) huge,
huge swath of national quantum strategies
to support scientific research at the academic level.
It’s very exciting.
So thank you for that, both of you.
I genuinely appreciate your time.
But that is all the time that we have for today.
So I’d like to thank all of you for joining us,
and I’d especially like to thank
David and Eleni for sharing their insights with us.
Please do visit our website at cifar.ca
to find out more about these series
and to view recordings of previous talks.
The recording of this talk will be posted early next week.
Thank you to both of our speakers
and to questions from the audience,
and have a great rest of your week.
– Thank you. – Thank you.
a virtual event series exploring questions
being addressed by some of the world’s top researchers.
Each talk pairs speakers and moderators
from across disciplines, sectors,
and the world to explore questions shaping our future.
You are not familiar with us.
CIFAR is a Canadian-based global research organization
that convenes extraordinary minds
to address the most important questions
facing science and humanity.
Today’s event is in partnership with the CNRS,
the French National Centre for Scientific Research,
a publicly funded institution that supports
research in all scientific disciplines.
My name is Fiona Cunningham,
and I’m a director of research at CIFAR.
And it is my pleasure to introduce you
to David Gosset and Eleni Diamanti, our speakers today.
David Gosett is a CIFAR fellow
in our Quantum Information Sciences program,
and a professor at the University of Waterloo
and the Perimeter Institute for Theoretical Physics.
He’s a quantum computer scientist who’s interested
in quantum algorithms and complexity theory.
Eleni Diamanti is a researcher at CNRS,
the French National Centre for Scientific Research,
and a professor at the Sorbonne University in Paris.
She’s also the vice director
of the Paris Center for Quantum Computing,
and specializes in quantum cryptography.
Today, we will be discussing how quantum algorithms
can be used to solve emerging problems.
So today’s session will last about 30 minutes.
As host, I will ask our speakers questions,
and they will also be taking questions from you
joining us today throughout the session.
If you have a question,
please submit it through the Q and A function
at the bottom of your screen.
Lastly, the session is being recorded
and will be available on cifar.ca website next week.
So thank you for joining us.
We really appreciate your time.
And my first pick off question is very simple.
What are quantum information technologies?
– Okay, thank you for the nice introduction, Fiona.
It’s great to be here with all of you today.
Quantum information technologies really encompass
a pretty broad set of technologies that aim
to harness the physics of quantum mechanics
to store and process information.
And one example of that,
which is my research area, is quantum computers.
And in a quantum computer,
you would store information
in the sort of complex quantum many body state
of physical system and process the information
using local operations on subsystems of that state.
But quantum technologies is a broader term
that also encompasses technologies
that can be used for communication,
for cryptography, for sensors,
and other information processing tasks.
And some of those are the sorts of tasks
that Eleni is an expert in.
So Eleni, maybe now is a good time
for me to let you jump in.
– Thank you very much, David.
And thank you very much, Fiona.
So it’s a pleasure to be here with all of you today.
So what are quantum information technology?
So I guess I would add with respect
to what David had just described.
For me, I like seeing the quantum information technologies
as an outcome of what has come to be known nowadays
as the second quantum revolution.
So then obviously, this leads to the question
of what is the first quantum revolution.
So the way we see it is that the understanding
of quantum mechanics at a bit of a microscopic level
has led in the last decades since many years now
to the discovery of new technologies
that we’re using in our everyday life.
This examples include, for example,
the transistor, the hard disk, lasers, MRI.
So these are technologies
that are using collectively,
in a sense, microscopic level, quantum mechanics,
and constitute the output of the first quantum revolution.
So quantum information technologies
has gone further than that.
They actually go to the control and manipulation
of quantum particles at the single particle level,
and at the control between
and interaction between particles,
to produce effects and encoding of information,
information processing and communication tasks,
that cannot be done if you don’t go
at this level of understanding
and of manipulation of quantum objects.
And this leads exactly to a quantum advantage,
a quantum effect in all these categories
of technologies that David just mentioned.
I guess one of the major application areas
where David works is
quantum information processing and quantum computing.
So why don’t we talk about this a little bit further, David?
Do you think you can tell us, what is a quantum computer?
And why is it different?
In what sense is it different from a classical computer?
– Yeah, great.
So maybe we can start by just thinking
about how we often learn about computing
in say a class at university.
You might learn about storing information in bit,
and then processing information using logical gates,
such as the and or the or gate.
And because we often talk about these things
in that sort of abstract level,
we often forget that at the end of the day,
the device that you’ll be using to implement
your or gates or your and gates or whatever it is,
your circuit, your computation,
that device lives in the physical world
and is constrained by physics.
And the fact that we can build a computer
that has bits and implements logical gates is
because classical mechanics,
the physics that was used to implement that device
allows for you to process information that way.
And what was realized by famous physicists,
Richard Feynman and David Deutsch
around the same time in the 1980s,
is that while the computers that they had
at that time and that we continue to have today,
they’ve grown increasingly powerful, those computers,
they don’t actually exploit all of the physics that we know.
And quantum mechanics incorporates effects
beyond classical mechanics,
such as superposition and entanglement.
And the really remarkable thing is
that those effects actually do provide an advantage
in computation for certain specific tasks.
So what Feynman and Deutsch proposed is
the idea of building a computer
where the information is stored using quantum devices,
processed using quantum effects.
And what we’ve come to understand is
that if you do things that way
and you build a computer in this manner,
then there are tasks,
certain specific tasks that you can solve
faster than a classical computer.
And it’s crucially not just running
every step of a procedure to solve a problem faster.
It’s using a fundamentally different set of transformations
that allows you to arrive at the solution using fewer steps.
– Okay, so that makes sense.
So now, this, how does one go,
and I think this is a crucial question, I guess,
as we move closer towards applications,
how does one go from an abstract understanding
of quantum algorithm,
of quantum computing, to real world problems?
So what are types of real world problems
that the quantum computer could really solve efficiently?
– Well, that is a great question.
And I think that if I had
the perfect answer to that question,
I’d be maybe swimming in cash or something like that.
So I think that the way that our field has developed
and our understanding of the power of quantum computers,
it really was in the 1980s, as I mentioned,
Feynman and Deutsch proposed the idea of a quantum computer,
and their motivating example was
that quantum mechanics itself,
many body quantum mechanics, like for example,
what you might see in quantum chemistry,
those types of simulations,
if you wanted to simulate that on a classical machine,
it would be,
we don’t know of a good algorithm for doing that.
But on a quantum computer, it would seem that,
or they showed rather that quantum simulation is
a task that can be performed much more rapidly
and with a quantum advantage on a quantum device.
And then Peter Shor had this major breakthrough
in the 1990s that showed that certain number
of theoretical problems can be solved
more rapidly using quantum computers.
And since then, we’ve also understood
that certain types of optimization problems
can be solved faster using certain types of subroutines.
So at some level, we’re, for a long time,
we understood kind of categories of problems
where certain subroutines could be deployed
where we get a quantum advantage,
but you asked about real world problems.
I think now is a time in our field
where devices are being built,
and those questions are becoming more pressing.
How do we take the idea
of quantum simulation and the abstract,
sort of quantum advantage that we understand
in some kind of general setting?
And how do we map that onto a problem
that matters for a company,
or that matters for all sorts of tasks
that you might imagine
quantum simulation could be useful for.
So for example, people talk about using
quantum simulation algorithms to improve,
to understand better batteries.
Or people talk about sort of speculative ideas
of how we might use quantum simulation in the real world.
And I think really understanding the details
of how that is going to work is
a major challenge for our field,
and something that involves
bringing together subject matter experts
with quantum algorithms experts.
Because most people who work
in quantum algorithms are not also experts, say,
in battery technologies or in the types of quantum chemistry
that might be relevant for other practical tasks.
So I don’t have the perfect answer for you,
but I think this is part of the discovery
that we’re going to see over the next five or 10 years is
really that matching of subject matter experts
with quantum algorithms experts,
and trying to understand how we can take
these kind of more abstract algorithms results
and apply them in the real world.
– Would be exciting.
– So let me, at that point,
let me jump in and ask you a little bit
about the kinds of quantum cryptography technologies
that you’ve been working on.
So in particular, what is quantum cryptography?
And why are researchers so interested?
And if I can add in one more aspect,
what are the potential implications for current crypto,
like classical cryptographic methods,
once a quantum computer is built?
– Good question, so now we’re sifting, I guess,
from quantum computing and quantum information processing
to one of the next big application area
of quantum information technologies.
So that is very pertaining to cybersecurity
and to secure communications,
which is particularly relevant, I guess,
in our society that is becoming more and more digital,
and where very high risk data are being transferred
over the internet, so over big, large networks.
So what are the cryptographic techniques
that we’re using today?
So today we’re relying on a big number.
We’re not going to go into the details
of all the techniques, of course,
that cryptography is using,
modern cryptography is using today.
But the main point behind all of these techniques is
that they do need to make some sort of assumption
about the computational power of an adversary.
We have to assume that there is somewhere,
this is what is common in cryptography
and malevolent party,
an adversary who wants to eavesdrop, to hear,
to obtain information that he’s been communicating
over the information channel,
and this eavesdropper, this malevolent party,
we have to assume something
in all modern cryptography algorithms
about their computational resources.
So the point now is that some
of the most common cryptographic algorithms
that we’re using today are vulnerable
to future developments, technological developments.
It can come from a quantum computer,
like the one that we’re just discussing,
when it will become powerful enough
to break such cryptographic technologies.
It can come also for other technological developments.
The point is that once you make assumptions,
it means that you have in general vulnerability.
So what quantum cryptography comes there
to offer is filling up this gap and saying, okay,
so because of quantum mechanics,
we’re going to operate our cryptographic system,
not at the mathematical level, but at the physical level.
We’re going to come with a quantum physics principle
that we just mentioned before, superposition, entanglement,
so the main principles of quantum information theory.
And this protects, in an intrinsic way, our communication.
So essentially what’s happening in quantum cryptography is
that any attempt of malevolent party
and adversary to obtain information
about the communication that is being transferred
necessarily leads to error, detectable errors.
And when the legitimate parties
of the communication channel actually treat,
process this information, they can detect this error,
and then do everything that is necessary
to bound this information.
To bound, to basically make it negligible,
to make sure that they can produce
a cryptographic sequence that will be protected
against such adversarial effect.
So the effect is obvious, I guess, to answer your question.
I guess this has important implications,
direct implications in security and communication,
because it means at one level
that we’re offering a security guarantee,
a security level that would not be available
in classical cryptography.
Of course, the story is never easy.
If the world would be perfect,
there is, quantum cryptography is not perfect either.
First of all, it cannot do everything.
So we don’t know how to do
with quantum cryptography authenticated (indistinct),
so know we’re talking to the right person.
So we also, also has physical requirements.
We can talk about it later, some limitations,
because we’re working at the physical level
and not at the mathematical level.
One needs to pay a lot of attention
as well in practical security once you go
from an abstract protocol to a real implementation.
And I think, but it does have
a clear added value in cybersecurity.
And the vision today is that we have
to make hybrid techniques exactly like in computing,
where I believe,
and I’m sure you can confirm this as well, David,
when I believe the trend is
that quantum processing machines
will probably be combined
with high performance computing and classical machines
in the same way in quantum cryptography
will not function alone.
It needs to be hybridized and bring
a very specific and well defined,
added value to classical cryptographic technique.
So I think the main challenge today is
to make classical and quantum cryptography’s work
hand in hand to come with viable solutions,
offering maximal security.
– Right, and if I can ask, can you paint a picture of,
how does a quantum cryptographic protocol work?
Just in layman’s terms, say.
– Sure, sure, sure, I can tell you.
So essentially,
the point is so I can mix a little bit of protocol,
abstract description, and a bit of physical description.
So because I’m an experimentalist,
I feel comfortable making this link.
So maybe if it can help you,
you can picture the protocol
thinking about physical objects,
like the photons in our case.
Photons is the particle of light,
is the fundamental particle of light.
And this is the carrier of information
for quantum communication and cryptography.
So in the hardware for quantum computing, has not been,
we don’t know yet exactly
what will be the carrier of quantum information.
It can be several, there are many candidates,
physical systems to be candidates,
but for quantum communication and cryptography,
we know it’s light, it’s photons,
because light has been transferred,
that can be transferred nicely over long distances.
And it’s less subject to noise.
So how would the protocol work?
So you take your photons,
you are encode information on them.
So they send it somehow in every protocol, it needs to,
what does it mean encode information?
You basically take a property of your quantum object.
For a photon, it can be polarization.
The way the waves,
it translates, doesn’t matter really.
And then we put on the photon, these zero and ones.
The zero and ones or intermediate states,
the superposition states are the fundamental basis
of quantum information randomly.
So you pick among these states randomly.
So random, this is an inherent property
of any quantum information protocol,
for computing, for communication and everything.
Then you send it over your quantum channel,
which can be, for example,
an optical fiber or a satellite link.
And then the receiver receives these quantum objects,
and they- – I could be the receiver,
so you can-
– You can be the receiver, exactly.
And so you pick the correct measurement.
So this, you can also,
another way of doing it is to use entanglement,
the other properties.
So you share entangled photos between these two parties,
and they both measure.
These are equivalent ways of looking at your protocol.
And then from the measurement results,
there are, the two parties,
they correlate, they communicate.
They see what they have measured,
what they have generated.
They calculate.
They examine these results.
And they see how much information potentially
eavesdropper could have acquired out of this.
And essentially, because they can trick noise,
and any noise can be attributed to adversary,
they can somehow extract the secret information
that they were looking for.
This is in, so any,
so this is the main idea behind these protocols.
– Great. – But why don’t we go back,
if you have a little bit of time,
why don’t we go back a little bit to computing?
And maybe you can tell us,
what are the recent developments in computing?
What are near-term applications of quantum algorithms?
What do you think the main challenges in the field today?
– Yeah, that’s a great question.
And I think you really touched
upon some of these ideas earlier
when you mentioned the idea of hybrid algorithms
and co-processing with classical computers.
And I think one of the main questions is,
how are we going to move towards useful quantum algorithms
with near-term devices that are not as far along
as the kind of model of computing
that you might hope to have in the future?
So for example, in the future,
we want to have large scale quantum computers
that are capable of correcting errors
in the computation as they occur.
And those quantum computers
you can really think of as like the analog of,
or you should think of the abstract model
of a set of quantum bits
and then a set of logical operations.
And you could imagine writing down on a sheet of paper,
a set of transformations,
and then implementing it on the quantum computer.
And there’s not really much difference
between what is actually implemented
and what you wrote down,
because any errors that occur
in the machine are corrected as the computation proceeds.
And it really is a sort of high fidelity implementation
of the thing that you wrote down,
the algorithm you had in mind.
And that’s kind of the dream,
and the technology is moving in that direction.
But for now the kinds of devices that we have,
and when you ask about near-term devices,
what does that mean?
Well, John Prisco coined the term
noisy intermediate scale quantum.
And that reflects the fact that these devices are noisy.
They don’t currently have the capability
of quantum error correction.
They’re intermediate scale because they have fewer qubits
than you might need to implement Shor’s algorithm,
for example, certainly fewer than you would need
to implement a large scale version of Shor’s algorithm,
but they are quantum.
And they’re quantum in a sense,
not just in the sense
that there are quantum effects going on,
but also they’re sort of computationally interesting,
because we don’t know how to simulate
these devices on a classical machine.
So they’re beyond the range of what can be done,
what can be simulated on classical machine,
which means that at some level,
there’s some kind of quantum advantage,
but we don’t necessarily know
how to harness it in the presence of noise,
and with few qubits and small circuits
that we can implement.
And so people have tried to understand
algorithms that operate in this regime,
but that has been much less well studied
than the kinds of larger scale algorithms
that might be deployable in the future.
And some of the ideas that have been proposed are,
as you say, like hybrid quantum classical algorithms,
variational quantum algorithms
that have a certain robustness
to the types of noise that might occur in these devices.
But the challenge there is that when we talk
about Shor’s algorithm
or some of these kind of pioneering quantum algorithms
that we understand very well, at least in theory,
we have an understanding
of what the run time of those algorithms is,
what the performance guarantee,
what the output of the algorithm will be with a given input.
But when you talk about designing algorithms
for near-term devices,
oftentimes the algorithms that are proposed are heuristic.
Meaning that they don’t have performance guarantees,
but they are something you could try
on a device if you had one.
And so I think a lot of the near-term applications
have yet to be really understood,
because you have to run them on devices of increasing size
to see whether or not there is really an advantage.
They’re not necessarily algorithms
that we can analyze on a sheet of paper and say,
yes, we’re going to get this much advantage
as long as we can build a device with 150 qubits.
It’s really quite a bit more challenging
to understand those algorithms.
Because the analysis also involves looking
at the specific hardware or the types of operation,
the connectivity of your device
and certain other details of your device
that you might not necessarily have to care about
if you’re building a large scale quantum computer.
– And now are these the type of algorithms
you’re working on, or something, what is your work-
– Well, yeah, so in a way, yes.
So I kind of alluded to the fact
that there’s this ephemeral boundary
between what is classically simulatable,
and what is beyond classical
sort of from a computational point of view.
So you may have heard
of the Google quantum advantage demonstration,
where they sampled from a probability distribution
that is thought to not be possible to sample from
in a comparable amount of time using classical computer.
And so my research has tried to resolve
or delineate this boundary more sharply in various regimes.
So for example, I study classical simulation algorithms
for quantum computers.
The ways we can leverage structure
in quantum many body systems
to simulate them better on a classical machine.
Classical simulators can also be used
to benchmark small quantum computers.
So it’s not only useful to understand the boundary,
but also to benchmark these small machines.
And on the other hand,
I also study quantum advantage
with restricted types of quantum computation.
So for example, short depth quantum.
So the depth of a circuit is
sort of the number of time steps,
allowing for a certain amount of parallelism.
And we’ve studied things like,
what kind of quantum advantage
can you achieve with short depth quantum circuits.
– Great, thank you for that.
That was a really great tour of the current state
of quantum computing and quantum cryptography.
So we do have some questions from the audience.
And I’ll just encourage
either of you who feels most equipped to answer,
please fire away.
So this one is from Anuprim Gosh, and his question is,
so people refer to current classical computers
as a Turing machine.
Basically, computation done by these classical computers are
modeled and designed by Turing’s abstract computing machine.
Does the quantum computer also satisfy
the Turing machine model?
– That’s a really great question.
And I think you’re really,
you’ve gotten to the heart
of why we’re so excited about quantum computers.
Because you’re right,
that even though computers keep getting better and better,
the computers that we have, our laptops, our desktops,
they’re all from a perspective
of what kind of algorithms can they run.
They’re all equivalent to the Turing machine model
proposed in the 1930s by Alan Turing.
And the only model that we know of
that really is outside of,
that cannot be simulated
by the Turing machine model efficiently is
the quantum computers.
So quantum computers are thought
to be more powerful than Turing machines,
and they’re the only realistic model of computing
that we believe has that property.
So thanks for the great question.
– Yeah, thanks indeed.
And one last one.
So how, this is from Chris Ford.
So how close are we to being able to apply
an algorithm such as Shor’s algorithm beyond theoretical
to factor a large number and prove
our performance gains over a classical algorithm?
– So Eleni, would you like to take this?
– Shall I answer this as an experimentalist?
So we’re not there yet, Chris.
So I guess exactly like David was discussing
where at the level where we know how to do NIS devices,
noise intermediate scale devices.
It means a few hundreds of qubits in the best case
or roadmaps of big companies or startups
in quantum computing based on different technologies
predict that they should be able to get the device
up to a thousand qubit within the next three or four years.
But you need to understand that implementing
the protocol like Shor’s algorithm requires
a massive number of qubits,
much, much bigger number of qubits.
And why is this true?
It’s because for really implementing algorithms
like Shor’s algorithm,
we need to be able to master
error correction and fault tolerance.
So we need to be able to correct errors and noise,
which we know how to do, we have protocols to do it,
but they require a very big number of redundancy,
of essentially the correspondence
between the physical qubits that makes your device
and the logical cubics that are actually used
for the computation is not very favorable
with the current codes we have,
error correcting codes and fault tolerance algorithms.
So there is a need
for theoretical developments in this direction,
and still milestones to be reached
from an experimental point of view,
mastering noise, for example, in systems,
to be able to see implementation of Shor’s algorithm.
I remain very optimistic.
I think we’ll see it one day.
But it’s very difficult to predict today
without further progress exactly when this will happen.
Don’t know if you agree, David.
This is my- – Absolutely.
I have nothing to add.
It’s a perfect answer.
– No, I think that was a great answer.
And the challenge of quantum computing,
its uses in quantum cryptography is not lost
on both national governments with the (indistinct) huge,
huge swath of national quantum strategies
to support scientific research at the academic level.
It’s very exciting.
So thank you for that, both of you.
I genuinely appreciate your time.
But that is all the time that we have for today.
So I’d like to thank all of you for joining us,
and I’d especially like to thank
David and Eleni for sharing their insights with us.
Please do visit our website at cifar.ca
to find out more about these series
and to view recordings of previous talks.
The recording of this talk will be posted early next week.
Thank you to both of our speakers
and to questions from the audience,
and have a great rest of your week.
– Thank you. – Thank you.
In collaboration with the French National Centre for Scientific Research (CNRS), join us for a discussion at the interface of quantum computing, cryptography and cybersecurity. Hear from CIFAR Fellow, David Gosset (University of Waterloo), of our Quantum Information Science program, and CNRS researcher, Eleni Diamanti (Vice Director, Paris Centre for Quantum Computing).
David Gosset is a quantum computer scientist who is interested in quantum algorithms and complexity theory. He has worked on theoretical questions relevant to small quantum computers, including understanding the computational power of constant-depth quantum circuits and the limits of classical simulation algorithms.
Eleni Diamanti is an engineer and researcher at the French National Centre for Scientific Research (CNRS). Diamanti’s research focuses on experimental quantum cryptography and the development of photonics sources for quantum networks.