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

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.