0:00

[MUSIC]

Hi everyone.

We are here at the University of Illinois and we are talking

with Professor Paul Kweeot, who is a professor here in the Physics department.

And this is us playing ten question, or twenty questions about quantum computing.

Thank you Paul for talking with us.

>> You're welcome.

>> Please introduce yourself for our audience.

>> So yes, I'm Paul Kweeot.

I'm in the Physics and also Zero-Time Appointment and

Electrical Engineering Department here.

I've been here since 2013.

And my area of specialty is quantum information,

experimental quantum information mostly with with optics, with photons, and

a lot of things with quantum communication and a little bit with quantum computation.

But I teach a quantum information course here.

So I guess I'm hopefully qualified to at least tell you what other

people know about this topic.

>> And you've been here since 2003, right?

>> 2001.

>> 2001, right.

So you work in quantum computing, obviously.

And I'm wondering if you can tell us what the differences are between quantum

computing and the traditional computing that have been around for many decades.

>> Yeah. So I guess I'd

say that there are two sort of main differences one could think about.

So first of all main, the classical computing was based on bits,

things that can be zeroes or ones.

And I happen to have brought here and example of something that could be a nice

bit, something that could be a zero or a one.

Obviously in a normal computer, it might be some voltage on a com,

on some capacitor plate or something like that.

1:55

Okay we'll come back to that in a minute [LAUGH] because that's a problem.

So that's one very different thing.

And so there's a lot more information in a quantum bit than in a classical bit.

You can think of, sorry, I don't have too many of these props.

But, there,

we can write a general quantum state of as a combination of a zero and a one.

And it can have arbitrary complex coefficients

as long as the sum of the squares of these two coefficients is equal to one.

And so you can think of that as being represented on a because I have two,

two coefficients here, and because the sum of the squares is equal to one,

that corresponds to two random, two parameters, basically.

So you can think of a quantum bit as represented like a longitude and

a latitude somewhere on a sphere.

So if you're at the top of a sphere, for example, you could call that a zero,

and if you're at the bottom, you could call that a one.

And you can have, 0 plus 1 or 0 minus 1 or 0 plus i1,

basically anywhere on the surface of this sphere.

So that's a lot of information compared to classic.

3:42

And also if you combine different gates together,

qubits together, where we have two qubit gates, or something like that.

Then you can generate much more interesting states,

so-called entangled states.

And so, just as an example of that,

if you had a classical computer that had three registers there.

We'll do three registers.

With three registers in a classical computer, you would have one of eight

numbers because you could have 000 or 001 or 010 or 011.

Okay, 2 times 2 times 2.

One of eight numbers.

But in the quantum case, you actually get.

I can do this.

You'll actually get all eight numbers simultaneously in

the computer at the same time.

Again ignore the fact that these are decohering.

These are dropping out of that, for the moment.

So, with just three registers, that's not so impressive.

But if instead you had 300 registers which, you know, a normal,

your iPad or something has millions of registers in it.

But with just 300 quantum registers,

you can encode up to simultaneously 2 to the 300 numbers.

And 2 to the 300 is like 10 to the 100 or something like that and

that's more than the number of particles in the universe.

So even if you were to count every electron,

you've run out of particles before you get to the number of states you could

simultaneously put into into a quantum register.

And, so that's going to enable a tremendous speed-up in solving

certain types of problems.

And, in particular I, I guess the funny way of putting it is

that there's an exponential speed-up on an exponentially

small number of problems because it's not, it's not good for everything.

But for some things, it definitely has a, has a huge, a huge benefit.

>> So, essentially when we do pattern computing say with four processors,

it might get sp, sped up four times.

It might be four times faster.

Essentially what you're saying is with a quantum computer, you could be as fast as,

as you possibly can because its essentially an exponential speed-up.

>> Yeah.

It would be, well, it would be like 2 to the 4 times faster.

>> 2 to the 4 times faster.

So we hear this term called qubits-.

>> Yes.

>> In quantum computing, can you say what it is?

>> Well a qubit is just the term of a quantum bit.

So any, any representation of this two-level system, so bit,

but that can be in superpositions of the two at once.

And so maybe I'll talk about how you might get that physically in a physical

thing, yeah?

So the simplest example maybe is

I guess there are sort of two that are pretty easy.

One is if you from chemistry, you know, there in atoms, there are electrons, and

electrons have these different orbitals.

And so, for example, you could call, if the electron is in it's lowest orbital,

you could call that a zero, and if it's in some excited orbital,

you could call that a one.

And you can put the electron so that it's in a superposition of zero and

one at the same time.

It's in a superposition at both of these locations at the same time.

If that seems really impossible or weird to you, I would say yes, true.

But already the fact that when it was in the zero state the electron was already in

all these different locations around the nucleus at once anyway.

So, in some sense, it's not really any, we've already had the weirdness put in and

now the question is, can we use that to do something?

That's one possible way of getting a, of encoding a cubit.

Another, other things that people have looked at is in superconducting coils,

you can have the current going clockwise being a zero and clock,

counterclockwise being a one.

And then you can get the current of electrons to be both going clockwise and

counterclockwise simultaneously.

I deal with optics a lot and so we can use properties of photons

the one that we often use is the polarization of the photon.

You know, whether that's horizontally or vertically polarized.

Just like you would get with 3D glasses in a movie theater.

And you can make superpositions of, say, horizontal and vertical and

that would give, say, something was diagonal, and so

it's real easy to see how you get those superpositions.

Or if there's superpositions where there's a 90 degree face shift,

then you get circularly polarized light.

And that, that's how the not the IMAX 3D glasses, but the other one, the Real 3D or

whatever, they use circular polarization.

So it's basically, the qubit is basically any

quantum system that can be mapped onto a two dimensional space.

8:05

But in a way that's maybe a lot more controlled than you would normally have

with the actual system that you're trying to study.

So certainly, quantum simulation is something that people look at a lot as a,

as a possible application.

And I'll, I'll come back to that in a little bit.

The main one that really started the whole field, though,

is so-called Shor's algorithm.

So Peter Shor,

the theorist I think at IBM at the time, who figured out that you could

factor large numbers into their prime constituents using a quantum computer,

and wouldn't require the exponential speedup that we currently have.

So currently with classical algorithms, it's an exponentially, as you,

as you increase the number of digits then the time to do the factoring increases

exponentially.

And with a quantum computer, it, it doesn't.

It decreases.

It's, it's only polynomially.

And so there's a huge interest in that because,

of course, of that difficulty of that problem, or the perceived difficulty,

is what a lot of our current classical encryption is based on.

Like, RSA encryption is based on the fact that it should be a hard problem

to, to solve.

It's not mathematically proven that it's hard to,

that that's a so-called NP-complete problem, or

that it's a, it's a difficult problem, but it's, it's strongly believed to be.

So at the moment, what's driving this is this factoring sort of thing,

in terms of quantum computing, and this possibility of doing quantum simulation.

>> You mentioned quantum computing

being used to potentially break RSA cryptography, and is, is it possible to

use quantum computing to come up with new ways of encrypting and decrypting data?

9:39

>> There are two answers to that.

The answer is yes, in both cases.

So first of all, people try to find algorithms.

Classic algorithms that are not susceptible to this exponential speedup.

And so if you use, I think it's elliptic curve cryptography?

I think it's that.

I don't know.

You're the computer science person.

And, maybe also Diffie-Hellman en, encoding.

Those, you only get the square root of speed, the square root of N speedup,

because it's like a search algorithm, basically.

So that's not such a big speedup.

So one thing is to try and redo your classical cryptography in ways that

are not so susceptible to quantum computers.

The other thing that you can do is quantum cryptography, which is actually

mostly what my group is involved with, not so much quantum computing.

And that's basically using single photons to,

to generate a random key that you can then use to encrypt information in.

Because you have a single quantum system, and

it's very fragile if you make measurements on it.

So it's very fragile in the sense that this thing doesn't,

you know, doesn't like to stay spinning, in that sense.

[SOUND] you can encode information in a way that you can detect it.

There's an eavesdropper who's been trying to monitor that information.

And then you, you simply never, you never have any transmissions

that are encrypted using a key that an eavesdropper could have

looked at without you knowing that an eavesdropper looked.

So either you know that no eavesdropper looked at it, in which case it's

secure and you can use it, or maybe you know that an eavesdropper did use it,

did look at it, and then you just never use that key to encrypt anything.

So in that sense, it gives you perfect,

perfectly secure encryption that is not breakable by a quantum computer.

Because basically, it's just using simple one time pad encryption,

where you just have your message and you add to each bit of the message.

You have your key, which is a random string of zeros and ones.

And to each bit of the message, you just add, you know, a bit of the key, modulo 2.

This is a, this is a string of zeros and ones that you want to send.

This is a random string of zeros and ones.

When you add these random string to this string,

you get a completely random string.

You just post that on the internet, or you call up the person,

or you, you put it on Facebook, or whatever.

And if the recipient knows the same key, then they can undo the process and

they get the original thing.

Because what's being transmitted over the internet

11:57

is just a random string of numbers, there's no, there nothing to be broken.

There's no code, there's no structure in it at all.

It's just a random string of numbers, so that it's never going to be possible to

to do some sort of processing on that to figure out what the original thing was.

Now, if you don't do the implementation, the, so the whole, quantum cryptography is

all about distributing this key between the two players.

And if you don't do that right, if there, if there are, what will I say?

Loopholes in your experimental setup, then you can hack that kind of a system.

And that's also been done in the last couple years,

where people have started hacking quantum cryptography systems and finding out,

okay, there's a big difference between theoretically drawing the protocol and

then how you actually implement it.

And is, are, you know,

are you leaking extra information when you're implementing it?

>> So, so in all of this, it seems like there's a lot of ideas in quantum

computing and quantum cryptography.

12:47

How far are we from seeing a truly powerful quantum computer, one that is,

say, similar to one of our data centers, or maybe even weaker than that?

>> In terms of that, how, how long is it until we have like a universal quantum

computer, or something like that, or one that could factor some very large number?

Yeah, there's a physicist, Bill Phillips,

who got the Nobel Prize a number of years ago.

He used to say that it's a 50-50 proposition with quantum computers.

There's a 50% chance that in 50 years we'll have one.

So, let me just put that in perspective.

We now have 14 or 15 cubits, that's the world record.

And then you might say a little about this other company, D-Wave,

that's been in the news a lot.

For universally accepted and recognized quantum computing efforts, this record is

about 15, with maybe hundreds of gate operations, something like that.

If you want to do quantum simulation, you need to have of order 30 or 40.

And so, 30 or 40, we're, we're going to have that in, in five years or ten years.

I don't have any doubt about that.

Whether or not we can get to this large number of gates that we need to do

a useful simulation, that's a different question.

And in order to do quantum factoring, then as I say, you need 50,000, or

something like that.

So, you know, there are people working on a lot of different efforts.

A lot of different systems using ions, or superconducting cubits, or photons, or

something like that.

The, the main difficulty, if I can just go back to my example here.

The main difficulty, assuming this doesn't fall off the table,

is that that doesn't like to stay in a quantum superposition.

[SOUND] It interacts with the environment.

In this case, it's interacting with the air in the room, and

also with friction on the table.

And that's causing it to collapse into beating into either a zero or

a one, not the superposition of zero and one.

This, this is obviously just an analogy, but

this happens with every quantum system, that it doesn't like to stay

in this quantum superposition because it's interacting with the environment.

And so, you might say, well, okay, that's fine.

I could certainly, I could put this in some kind of evacuated chamber so

it's not interacting with the environment, and somehow magnetically levitate it, or

something like that.

That's true, you could, but there's another thing you need for cubits to do.

You, they have to be able to talk to each other to do these gates.

So in this analogy,

it would be the, the spinning of this one- [SOUND] impacts how this one spins.

Which, which actually it does, a little bit, but

we need to interact on a really strong level.

So they have to inter, interact really strongly with each other and

not with the environment.

So then they say, okay, well that's fine.

I just take these, I'll put them up in space somewhere,

they're completely isolated, and they just interact with each other, and that's fine.

Except for the fact that there's two more things that you need for any,

any computer at all.

And that's, you have to have input and output.

So you've gotta be able to input into your computer,

15:28

what's the number you're trying to factor, for example,

or what's the, what's the molecule you're somehow trying to simulate?

And then, at the end of the day,

you need to make this read out of a single quantum system out.

And here, it's really easy because I just- [SOUND] stuck my hand down, and I,

and I see this.

But if you're actually trying to read out what the state of a single electron is,

a single photon is, something like that, that tends to be a lot more,

you need to have strong interactions to do that.

So basically, we need to have very strong interactions.

With the qubits to put the information in,

we need to have no interactions with them while they're interacting,

while they're doing their dance and, and running the algorithm.

And then at the end, we need to have very strong interactions again.

And those are just hard, it's hard to do that.

This interaction with the environment that's known as decoherence,

it's the technical term for

that and it happens with any physical system that we know about.

So that fact of decoherence is a problem.

So, you need to do some sort of error correction

16:36

if you, assuming that, if they all three agree, you say that's the right answer.

If two of them agree, you take the two and you say the one was an error.

And then by doing that sort of concatenation of that you can really get

the errors small.

The problem is then in a quantum computer,

you're not allowed to measure what the results are in the middle because that

stops the whole computation.

So you have to do more complicated schemes of encoding, and

it turns out you need to have of order, of let's say seven.

If you can have seven physical qubits,

then you can correct any single logical qubit error.

So whether an error, an error could be a flip error, so

something a zero becomes a one, or it could become the a, what we

would call a phase error which would be that this sort of gets rotated around.

Or if you think about this longitude and then latitude, a flip error would be doing

this and a phase error would be doing a rotation, an unwanted rotation like that.

So if you can encode in seven physical qubits,

one logical qubit, then you can, it turns out there are ways of then measuring them

in a way that doesn't kill the quantum com, computation, and

you can correct those errors and then you can continue.

>> That's pretty fascinating.

Is if, if one of our audience members is interested in knowing more about quantum

computing, is there a good book or a reference that you might suggest?

>> If you just Google quantum computing, I mean, there's lots of Wikipedia articles,

lots of tutorials on it.

I mean, a quantum computing tutorial and there's tons and

tons of webpages on it about it.

I, I keep wanting to say one more thing about an algorithm thing

17:59

that is relatively new that might be of interest.

So there's a problem called the Boson Sampling Problem,

which is equivalent to finding the permanent of a matrix.

Computer pi, scientists supposedly know what this is.

So, I didn't know what it was, but the permanent is like the determinant of

a matrix, but you make all the minus signs plus signs.

And it turned out that finding the determinant of an n by n matrix is ex,

is something that's exponentially hard.

And it's now known, it's now believed anyway that if you take

that you can map that problem onto a very physical problem.

And the physical problem is,

you've got a bunch of photons which are particles of light and

they come into a network that has a bunch of beam splitters that connects things.

So the beam splitters are just like this piece of plastic that I had where

the light sometimes goes through and sometimes is reflected and

you make this complicated web and it's got maybe n inputs and n, n outputs.

And the question is for given inputs in here, and for

given basically depending on what the reflectivities and

transmissivities of each of the elements in this network are.

What's the distribution of where the things are going to show up?

So what's the probability distribution?

And that is mappable on to this permanent problem which is known to be

exponentially hard.

And yet the quantum case seems to just solve it.

You just send things in and you see where the photons show up, and it solves it.

And the reason that's relevant is supposedly then that would violate

the extended Church-Turing thesis, because you'd be able with the, with the system,

you would have a system that would be able to solve an exponentially hard problem.

And so that is something that's of great interest at the moment,

both from a theoretical point of view, and also that requires

of order maybe 30 photons or something like that, or 40 photons.

And so I guess in the next five or ten years that will also be done.

And I don't know,

either the quantum mechanics will somehow break down which would be impossible, or

the, the Church-Thuring, Church-Turing thesis would break down,

which I think the computer scientists would also say [LAUGH] is, is impossible.

So, so something's going to fall and that's, that's kind of interesting.

>> So I wanted to wrap up with a question that's changing gears a little bit

not really too technical, your technical work.

But you know your, your work in the university for

over a decade now, before that you were at a national lab.

>> Los Alamos National Laboratory.

>> Right.

So I wanted to ask about you know, how do you think what the,

what is the difference between working in these two different environments?

>> So one thing is there's more bureaucracy at a national lab.

There's no question about that.

And we have colleagues who come to us from NIST, National Institute of Standards and

Technology.

You know, and they have also travel restrictions and computer restrictions,

and they have to change their passwords every two months.

There was a talk once where someone couldn't remember the password to

his computer and that was really kind of annoying.

21:27

On the other hand, things are a lot more expensive at a national lab, and a lot of

times you know, you have to get funding to work on whatever project you're doing.

Same thing here, but also as professors we're paid,

you know, to teach during the semester, during the year as I should say.

And that covers a lot of our salary,

whereas if you're really working at a national lab,

you have to find some sponsor who's, unless you're working on whatever,

it kind of depends on what kind of project you're working on at the national lab.

But certainly places, you know, like NIST are really fabulous.

I would, I would love to work at a place like NIST.

Not, I wouldn't really love it more than working here,

but I certainly wouldn't mind recommending you know,

people to go to someplace like that or Sandia National Lab.

It's really a, a good experience.

22:59

But it's certainly an opportunity that's worth looking into.

>> So your advice to students would be don't stop asking questions

even if you think they're, they're stupid questions.

>> I, I, I've very rarely seen stupid questions.

Unless there's procedural things about, is the homework really due, blah, blah, blah,

or something like that.

But in terms of the science things, people I mean the questions might just reveal

that we really haven't given quite enough information in lecture.

And so, you know, people are trying to make some logic jump and

they don't quite have all the pieces, or they misunderstood something.

I mean all of these topics, whether it's, you know, quantum physics, or high end,

you know, computer science, they're not, they're not easy topics.

And so everyone's trying to put this scaffold of knowledge together in their

head, and sometimes it doesn't, you know, it doesn't quite fit.

And a question can really cause it to fit, or it can reveal that oh,

there's this whole other avenue that can, that can be looked at, so.

>> Okay, thank you for talking with us Paul.

>> You're welcome.

My pleasure. >> Thanks.

Professor Paul Kwiat.

[MUSIC]