MASOUD MOHSENI: Good

afternoon, everyone. It’s my pleasure to

introduce Seth Lloyd, who’s our first speaker in

Quantum AI series in 2014. Seth Lloyd is considered

as one of the founding fathers of quantum

information science and he’s done

major contributions to a broad range of any of those

in quantum computing, quantum control, quantum simulation,

transport, illumination sensing, and quantum

communication. So he’s been in many

groundbreaking research over the last 25 years. And so he’s actually a

theoretical physicist who happen to be a professor of

mechanical engineering at MIT and would like to consider

himself as a quantum mechanic. SETH LLOYD: Your

Quanta are broke. We fixed them. MASOUD MOHSENI: I happen

to have the opportunity to work with him

over the last six, seven years while I

was at Harvard and MIT. We worked on a number

of interesting projects such as developing material

of noise-assisted quantum transport with applications

to biological systems. And also more recently,

developing new quantum algorithms with applications

to machine learning. This is actually the topic that

he’s going to discuss today. And we are very happy that

he accepted our invitation to come here and

present his results. SETH LLOYD: Great. Thank you very much, Masoud. MASOUD MOHSENI: Seth Lloyd. [APPLAUSE] SETH LLOYD: Yeah,

it’s a good idea to clap now, because

after I’m done who knows what’s

going to happen. So thank you very much

for bringing me here, Masoud was a postdoctoral

fellow with me. And then he was

working so well, I hired him as a

research scientist. And everything was doing great

and then Google hired him away. And actually it’s OK,

because I miss Masoud telling me what to do, so now he

can tell you what to do. And my advice is do it, because

it always seemed to work out. All right, so it’s great

pleasure to be here. I lived in Santa Monica

like 20 years ago and used to come

to the Rose Cafe all the time which

is around the corner. I don’t think this

building was here then. But I have a question. So I know this is a

very general audience. So I’m going to talk about

quantum mechanics and machine learning algorithms. But my first

question is who here has studied quantum mechanics

at some point in their lives? Who here has not study

quantum mechanics? All right, and the

remainder of people who are people who have and have

not studied quantum mechanics. And those are the

real– those are the people who know

it intuitively. OK, good. So let me just start off

with a really brief course in quantum computing. So the exam will

be easy, I swear. So the thing to remember

about quantum mechanics is that quantum

mechanics is weird. This is a technical term. My brother who’s

sitting right here told me he once saw James

Brown at a concert and somebody said, so James, what

you’re going to play next? And James said, I don’t

know, but whatever it is it’s gotta be funky! And quantum mechanics

is the funky science because it’s

strange, it’s weird, it goes against your intuitions. And it’s hard to

understand what’s going. So then if I say

things that sounds strange and weird and against

your intuitions, that’s good. Because as Niels Bohr

once said, anybody who can contemplate quantum

mechanics without getting dizzy hasn’t properly understood it. Except he said in Danish,

which was more impressive. So the key thing about

quantum mechanics, here’s a key feature. If I have something

like a particle– so this is a particle. By the way, I apologize. I don’t do PowerPoint unless

I have signed a government grant that requires me

to deliver PowerPoint. And the reason is that

PowerPoint is a form of Satan and I object to the

government requiring me to perform satanic rituals. But that’s the way it is. Life is too short

for bullet points. OK, so key features

about quantum mechanics. If I have a particle

such as an electron– now we’re normally

accustomed to thinking of particles like little tiny

basketballs or something. They can sit in one

place at a time. But a particle such

as electron, if you get to things that

are that small, particles can be in

two places at once. Now I know this sounds

kind of strange. So how can a particle be

in two places at once? Well the thing is in

quantum mechanics, a particle has a wave

that’s associated with it. So particle over here has a

wave associated with over there. Particle over there

has a wave that’s associated with it over there. The wave tells you what’s

the probability of finding a particle in a particular spot. But quantum mechanics has a

feature that waves add up, just like waves on

the beach out there. So if this is an OK wave

and if this is an OK wave, then this is also an OK wave. So it’s OK to have a

wave for the electron where the electron is both

here and there simultaneously. Now I know this

sounds weird and it does contradict our

intuitions about what things do microscopically. Because I’m from Boston, I can’t

talk about basketball here. So let’s talk about soccer. Even if Lionel Messi

makes the soccer ball look like it’s two places at

once, it isn’t really. However, quantum

mechanically things are like this all the time. Everybody OK with this? You shouldn’t be OK. This is wrong. It’s like absolutely wrong. Einstein hated this crap. He said this is awful. I hate this. My intuition tells

me this is wrong, and he never believed

in quantum mechanics. Well, he was wrong. I mean, he was wrong. So this kind of wave particle

duality, is what it’s called, when you translate

this into a situation, some device is performing

computation like a computer. Well, in an ordinary

computer, a zero is stored by having a whole

bunch of electrons here, capacitor uncharged. And one is stored by having

a whole bunch of electrons over here, capacitor charged. And if you go down to a

single electron transistor, you could have one

electron over here as zero. And one electron

over here is one. So electron over here is one. And the same electron being

here and there at the same time is zero and one

at the same time. So if you look at quantum

mechanics and logic, or just bits, quantum bits, or Q bits

as they’re whimsically called. I mean, I don’t know,

when I was a kid a Q bit was this distance

right here from your elbow to your finger. I still think of

that as a Q bit. But a quantum bit is now

a Q bit spelled with a Q. So a Q bit, quantum bit, or a

Q bit– spelled differently, too– can be zero and

one at the same time. So that’s the primary

feature of quantum mechanics. And quantum computers

operate by trying to take advantage of this. For many years being a

professor of quantum mechanical engineering, I used to

say I was at a wedding and I was seated with– this

is at our cousin’s wedding. She’s a cultural

anthropologist and I was seated at this table of all

these cultural anthropologists. They asked me what I did

and I said, oh, I take atoms and I exploit their intrinsic

information processing power to make them compute. And they’re like, oh my god,

that’s the most politically incorrect thing I’ve ever heard. So Barbara Ehrenreich

was at this table. She’s a wonderful

social commentator. And she actually has a degree

in chemistry, as it turns out. So she got me to

explain it better and finally they

were OK, they figured I wasn’t really exploiting

elementary particles too badly. And afterwards

her companion, who was the older African

American activist from Greensboro, North Carolina,

he put his arm or my shoulder and said, “Seth, I

suggest the next time you describe what

you do that you say you empower

atoms to compute.” And it was a transformational

moment in my life because I went just like

that, in a nanosecond, from being an exploiter of

atoms to an empowerer of atoms. So how can we empower

quantum bits, Q bits, atoms and electrons, that

we can manipulate at this subatomic scale– atomic

and subatomic scale– how can we empower them to compute? And if we can do so, how can

we exploit– I mean, sorry, how can we use this feature that

quantum bits can effectively read or register zero and one at

the same time to do things that ordinary classical

computers can’t. So, any questions so far? Yes. AUDIENCE: What’s the

difference between [INAUDIBLE]? SETH LLOYD: What’s the real

advantage of it, I’m sorry? AUDIENCE: [INAUDIBLE]. SETH LLOYD: I’m not

exactly sure I understand. I mean, you accept

immediately that it can be zero and one

at the same time. So you obviously lived

with us for a long time. Let me just say more

precisely how this can be so, because actually there’s a

little bit of mathematics has to take place now. So how many people have a

background in computer science? All right. How many people don’t have a

background in computer science. All right, how many people

do and–no, never mind. OK. All right, there we go. Yeah, me too. So let me give you a little

bit of the mathematics of how this works and

then actually this will help with your question. So the way that the

mathematics works is that actually

this state, zero, suppose we have something that

can have two states, a quantum bit. It corresponds to a vector in

a two-dimensional vector space. And one corresponds to

an orthogonal vector in a two-dimensional

vector space. And a general Q bit,

so a generic Q bit, corresponds to something which

is a generic complex vector in this two-dimensional

complex vector space. This is just mathematically

what they correspond to. And the way that this works–

and so this of course, this is just equal to alpha

times this plus beta times this. And often there’s a

quantum mechanical notation right here where this

vector is called zero. This means this

funny little thing, this brackety-like thing,

means that whatever’s inside it is quantum mechanical. That’s what it means. It’s called a Dirac bracket. That’s this notation. But I’m just defining

it to mean this vector. And it just means it’s a

quantum mechanical dookickey, another technical term. So this is equal to alpha

times zero plus beta times one. So this means these

alphas in the beta represent basically the

relative height of these. And because they’re complex

numbers, there’s a phase. And you demand that the modulus

squared of alpha squared plus a modulus squared of

beta squared is equal to one, because alpha squared is equal

to probability of finding– if I make a measurement on this

cube and then I say, electron, are you over here? Are you zero? Or are you over there? Are you one? Then this modulus

squared of alpha is the probability of getting

zero and data squared is the probability of getting one. And when you add them up,

they have to add up to one. And why should this be true? Nobody knows, OK? This is just the way it is. You’ve got to suck it up. No, in fact, it’s the

square of this amplitude, this complex number

that’s a probability. This is footnoted in the paper

written by Max Born in 1929. He says, oh, look,

this amplitude is proportional to

the probability. It says that in the paper. But then in the

footnote, it says, “Under more

consideration, I realized that the probability is

the amplitude squared.” Note added in proof. It’s the most famous footnote

in physics, actually. OK, so nobody knows why

this is the case actually. If I had longer time,

I could give you some arguments for

why it might be, but the real answer

is nobody knows. So are people OK with this? This is what a quantum bit is

in the formulation of quantum mechanics. AUDIENCE: [INAUDIBLE]. SETH LLOYD: As OK as you’ll

ever be, that’s right. The great thing about this is

that computer scientists know not only about algorithms

and computation than I do, but they know a whole bunch

of stuff about linear algebra. Because what is

computer science besides glorified linear algebra? Or at least much

computer science. And actually this fact

that linear algebra is very, very, very

important in computer science is what I’m now

going to exploit. Oh sorry, not exploit. I’m not supposed

to exploit things. This is what empowers

quantum systems to be able to do

interesting things that classical systems can’t do. Because quantum

mechanics at it’s very guts, at the very

bottom of quantum mechanics, it’s about vectors. It’s about vectors in complex

Hilbert spaces they’re called, because there’s actually

a norm for this, but it is in complex

vector spaces. And quantum computers

when they’re flipping bits and

moving things around are actually performing linear

operations on these vectors. So if you look at the

mathematical formalism of quantum mechanics

to people who are taking quantum

mechanics know, it’s all about linear algebra,

matrices, eigenvectors, eigenvalues, blabitty,

blah, blah, blah. Which is what our family

uses for et cetera. It’s OK if you

don’t write a paper. All right, so that’s

what we’re going to use. This in fact is this feature

that quantum mechanics is about vectors, matrices,

linear operations– the way that we’re going to construct

quantum machine learning algorithms is to map ordinary

machine learning algorithms when they have to do with

manipulating vectors, figuring out inner products, performing

linear transformations, inverting matrices,

stuff like that. We’re going to map all

those transformations on the things we can do at

the quantum mechanical level. And that’s the basic

intuition for why this whole method works. And I should say that the

reason I got involved in this is that Masoud’s

and my colleagues, Patrick Rebentrost–

he’s a post-doc at MIT right now, he was a graduate

student of Harvard– he came to office a

year ago in November and he said, Seth, we should

work on quantum machine learning. And I said, machine learning? What’s that? He said look, it’s like

all about this manipulation of vectors and things like that. I said, oh, I see. Anyway, so the dumbass

intuition is that lots of machine learning tasks about

linear manipulations of vectors in large vector spaces. And quantum mechanics is all

about vectors and large vector spaces. And so maybe you can do

these manipulations quantum mechanically. And that dumb ass

intuition turns out to be correct in a

large number of cases. And also not correct in

other cases and that’s very interesting. And so one of the things

I’d like to explore here since we have a group of people

who I bet know I hell of a lot more about machine

learning than I do, is maybe we can cook up

some examples of things where this works, might work,

that we haven’t thought of. And Masoud and

[INAUDIBLE] and these guys are working on trying to figure

out things that have worked and also to figure out

places where it doesn’t work. Because failure, though

less fun than success, is often more illuminating. Everybody ready for–

good question time. Because– yes? AUDIENCE: [INAUDIBLE]. SETH LLOYD: Complex numbers. AUDIENCE: [INAUDIBLE]. SETH LLOYD: So the alpha and

beta, the way they show up, is that they’re moduli

squared our probabilities. So you never actually measure

their complex features directly. The way that you actually see

their kind of complex features are in famous things like

the double split experiment where you send these waves,

which are complex waves. This is now a single

electron, right? It corresponds to a wave

that spreads out here. It shows up on a screen and then

you get interference patterns between these different waves

coming through these slits. And so these

interference patterns come from adding up

these complex amplitudes. But you only end

up having access to experimental

information that’s like, did the electron show

up in someplace here? So actually your question

is a very good one because though often you

want to have information about these complex amplitudes,

what you’re going to do is you need to massage

your problem in order to actually extract the

information that you need. And that’s often a difficult

and complex thing to do. AUDIENCE: [INAUDIBLE]. SETH LLOYD: It will

be a bit like that. Yeah, absolutely, it

will be like that. In fact, We’ll start with

this mapping of these states onto these kinds of

onto kinds of problems that we’re interested

in in machine learning just right now. Unless there are more

questions at this point. OK, good. Oh, yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: Sure, yeah. You could. In fact, for

elementary particles, the number of internal states

depends upon those spin. So a massive spin one

electron, for instance, could be spinning

up or spinning down. Or actually you

could just imagine to have three

different places, let’s us imagine it like

that since that’s way you were describing it. Sure. You could have a ternary

system or quaternary system. So, yeah, it often in the

case of quantum computing– as in the case of

classical– it’s easier to manipulate things that

just have two different states. But there’s nothing preventing

you from doing that. And in fact, in

quantum mechanics we often refer to

qudits, where you have D different

possible states. And this is a very useful way

for manipulating information on that scale. So suppose I have a

qubit and it can be and it can have two different

states, like zero or one, and this is one electron. Then I could have

another electron that could also be

in different states. Like this could be in

two different states, use a third electron. I have n different electrons. So each one of

these belongs in c2, this two-dimensional

complex space. I put them together,

it’s in actually what’s called the

tensor products space. And if you don’t know the tensor

product space is, don’t worry. It’s just what we have

when we put together a whole bunch of copies of c2. It’s in c2 to the n,

which is basically a2 to the n dimensional space. So there are 2 to the n

different possible space here. And so the key feature

here– and this is the key place where all our

quantum speedups will come– is that if I have n

qubits, they live in this 2 to the n dimensional space. So when we’re going to

manipulate our vectors, the nice thing is if we

have some if we have data and our data is in the

form of, let’s say, some gigantic vector which is a

2 to the n dimensional vector. Now, the classical

representation of this data takes 2 to the end bits,

or these could be words. So 2 to the n times

32 for 32 bit words. But the thing is that

our quantum state, we can have a quantum

state of n qubits, and this has 2 to the n

different components in it. So I can write

this as I can make a quantum version

of this vector. And this is going to be equal

to the sum over I. x of i, this state i, where

i is like i is an n bit– this is

an n bit number. So this is an important

place to be annoyed or ask questions

or get confused. This is sort of like

a wedding, but instead of having one place where you

have to speak now or forever hold your peace, there are

like 10 places along the way. So if the bride

and groom actually end up getting married here

it’s going to be a miracle. So there are n bit

numbers, this is n qubits, but there are 2 to the

n different components. So because these quantum

mechanical objects are vectors, I can have a small

number of quantum bits that represents a

huge honking vector. People are looking at

me closely like I’m trying to pull the

wool over their eyes. This is just a feature

of quantum mechanics that the states are

vectors, I put together n two-dimensional vectors. They live in a 2 to the n

dimensional vector space. And so a state of n quantum

bits is a vector on a 2 to the n dimensional space. And so, this mapping

is very important because this is the source of

all of our quantum speedups. We’re going to be manipulating

these huge honking vectors. Things that would take a very,

very large amount of power classically if these were all

just numbers in a computer. So these were just like 2 to the

n real numbers in a computer. It would take me a

long time to do things like invert matrices

multiplied by this number or taking our products

of two of these vectors. But quantum

mechanically, it’s going to be basically

exponentially faster for all of these operations. That will be the

source of our speedup. Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: Yeah, this

is a very good point. So here, if these

are complex numbers, we’re actually demanding for

it to be a legitimate vector that the square of these

numbers sum to one. So there’s one constraint,

so it’s actually 2 to the n minus 1 vector. So you’re absolutely right. You’re exactly right. But it only reduces

the constraint. It only constraints

it by one constraint to make sure that all

these squares add up to one so that these modulus squared

are a legitimate probability. And that’s actually

a very good point. having. Mentioned it, I

will proceed to try to ignore it for the rest of

the talk because, of course, we’re often interested in

the norm of this vector. So we actually have

to have techniques for dealing with these norms,

moving the norms around and manipulating them. But actually the

norms all end up turning out to be probability. So we end up

estimating these norms by when we make measurements, we

find the probability of success will be like one over

the norm of the vector. So that’s more than

I wanted to say, but since you brought

up a rather deep point, I thought I’d address it. Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: Exactly. Exactly. That’s exactly right. And in fact, we have to

take a lot of trouble. So I hope everybody’s

hearing these questions. These are all extremely

important questions. The idea here is that

quantum computers work because you’re representing

all these bits simultaneously. The information

you’re manipulating are that of these amplitudes,

these complex amplitudes here. And classical computers simply

don’t have that in them. They could have

one of these, they could have a list of all

these components right here. So yeah, but you said

it better than I, so the answer to

your question is yes. Since you expressed

it so eloquently. Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: Yeah,

let me tell you what we need to do this, OK? Because one of the reasons

I’m making this claim that if we can manipulate

these relatively small vectors quantum mechanically,

we should be able to find out very

interesting features of these vectors. And if we have large

collections of vectors, we ought to be able to do

machine learning on them. So suppose our data

set consists of 2 to the m vectors of this form–

so it’s some huge honking set of data– and we want to

perform manipulations of those. And basically what I’m going

to argue is that we can. And I will probably

not have time to sketch out– I’m relying on

you to tell me how much time I have, Masoud, because

I don’t have a watch. Oh, I see. It’s a digital clock. I see. No wonder. No, I see it now. I can see the clock just fine. So everything everybody

said is correct right now. So let me say how you

do these kinds of things and let me tell you the

necessary ingredients we need to make this happen. So the first component–

well, zero is just the idea that quantum mechanics

allows manipulation of vectors in c to the 2 to

the n using only n qubits. That’s the basic features,

I’m just putting out there. So what do we need? First of all, if we have

classical data of this form– I guess I could just

write it as x– we need to create this vector x. So that we have this

gigantic list of bits and we need to

create this vector. So we need to be able to do

this mapping from this large set into some kind of

quantum mechanical state. Now this actually sounds like

it might be very hard to do. But actually, merely to

map a very large amount of information to a

quantum mechanical state is a rather easy thing to do. And I’ll do it right now. So here I have a CD. It’s got like a couple

billion, 10 billion bits on it. Something like that. It consists of a very large

number, 10 billion very small, either mirrors for a one, or

a lack of a mirror for a zero. And the way you normally read

it is that you just have a laser focused at one point. It spins very rapidly. You look at the

reflections of this point. However, if I want to map

this gigantic vector of bits onto a quantum state,

of some quantum system, I can do that very simply. I take a single photon, a

single particle of light. I send it through a

lens, it spreads it out. It’s in a circle that

just encompasses the CD. It bounces off of it. There’s one photon. In the case where

there’s a mirror, the photon gets

reflected into the mode of the electromagnetic

field that corresponds to this

little tiny mirror. And there’s a case

where there’s no mirror, the photon is absorbed. And the state of the single

photon after it’s bounced off this CD is now a

quantum superposition of being in all the different

modes where there’s a one, and not being in all

the different modes where there’s a zero. So it’s actually not so

hard to create a quantum state that has this funny form. I mean this one photon just

created this quantum state. Basically if these x’s

are zeroes and ones, then I end up with

a superposition of photon in all the states

where they were ones. So it’s not hard to do. What’s hard is to get

the information in a form where you can manipulate it. OK? I know this sounds like

this like a cheap trick, but it’s really true. I mean, if you actually go

to quantum optics people and then say, OK,

describe to me the state of a single photon going

off, they’ll write something with a whole bunch of

annihilation creation operators that will be that state. Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: That’s an

extremely good point. And actually the analog with

holography is a good one. There’s one thing that’s

actually quite different. So, in fact, our

goal here is not to take our

classical information and to expanded it

into a quantum state where there’s more information. It’s to take our

classical information and to compress it

into a quantum state where there’s way

less information. Actually, if you have

n qubits and you just want to store

classical bits, you can only store n classical its. And our data set had

2 to the n bits in it. So in fact these

vectors that we’re creating, when I create this

bounce of single photon off of this, the single

photon in itself does not possess

10 billion bits. In fact, if I go and

measure it, I can hold it and say, is it in

this mode or it’s not? It’s only going to possess,

like basically, a bit. So my quantum state is

much more compressed than the classical state. That’s the first thing. And then your second question,

which is well what about noise? That’s a very important

question because as we all know, quantum systems are

much more susceptible to noise than classical systems. Systems that involves

waves like analog systems are more susceptible to

noise than digital systems. So the question is is this

susceptible to noise or not? And I’ll address that in a bit. Sorry, it’s a little

while down the road. Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: Right. In fact, in just in the same way

that if you were to read this out one photon at a time with

a conventional laser, right? You could read it out one

photon, one pixel at a time, one mirror at a time. If you expanded on

all the photons, if you took 10 billion photons

and balanced it off of this, then you’d have enough

information of those photons to recreate what happened here. Of course, it might

be a little hard. You’d have to have a pretty

fancy optical system together. But that’s just so. So there’s a story about this. So now, so we need to create x. Creating this is OK, and we

have to put it in digital form. That is to say qubit form. And for this, the

device that does this is what’s called a quantum

random access memory. And because this is Google,

I have to tell the story. All right, so the

spring of 2004, I was at a dinner in Monterey

associated with an early TED Conference and it was called

the Billionaire’s Banquet. And you might ask me what I

was doing at a dinner called the Billionaire’s Banquet

and I was basically the guy who jumped out of

a cake wearing a bikini. That was basically

my role there. And there I met the founders

of your glorious organization, Sergery Brin and Larry Page. And it turned out they

were extremely interested in quantum computing,

because they had actually been graduate students at

Stanford with Ike Chuang who’s now a professor at MIT who was

one of the main people quantum computing. And so we spent a long time

talking to this banquet, and at the end of it we agreed

that my postdocs and I would come up with

something that would be called quantum

internet search. We didn’t know what

it was because it’s much better to come

up with a name first. And of course, the reason

is to have something which could be trademarked

as Quoogle, right, for quantum internet search. And it turned out to

be very hard to come up with something that

was good for this. But we realized that–

after like three years, OK– we realized that

if you could build a quantum random access

memory, which is a device that basically takes this

information and it codes it in a digital form– a

quantum digital form– then you can do the following thing. If you included a database

in quantum mechanical form, then someone could

access the database. So to access Quoogle, you

would ask Quoogle a question, and you would get

the answer back. And when you’re done, you

know for absolute sure, guaranteed by the

laws of physics that Quoogle doesn’t

know the question. This seems impossible,

because actually, classically to do

this, you actually have to recode your

entire database for the person who’s

making the private query. So Google would have to recode

their entire database according to someone who gives

them a private code, and they’re not

going to do that. That’s a bit expensive. But quantum

mechanically, it’s easy. It actually has to do with the

so-called no cloning problem. The solution is when Quoogle

sends back the answer, they also send

back the question. And in quantum mechanics

there’s something called the no cloning theorem. Which says, if you don’t

know a quantum state, you can’t make a copy of it. So if Quoogle sends

back the question, then the person who asked the

question in the first place can check to see if the same

question is the same question, and Google didn’t

keep a copy, and so this is guaranteed to be secure. So provably secure given

the laws of physics. OK, fine, three years passed. We patented it because I’d

had a terrible experience because my graduate student,

Bill Kaminsky and I in 2001 and 2002, wrote a

series of papers about how you build an

adiabatic quantum computer using superconducting

systems with base qubits and tri-layer

niobium lithography with inductive couplings. And we didn’t

patent it because we did a back of the

envelope calculation. We realized that once you’ve got

more than a few hundred qubits, it wouldn’t be

adiabatic anymore. It wouldn’t work. So we didn’t patent it. Then D-Wave spent $100 million

building a superconducting adiabatic quantum computer

with tri-layer and niobium lithography with flux qubits

and inductive couplings, and we felt pretty dumb. So we patented this, quantum

random access memory, and then at some other boutique kind

of conference in Napa Valley, I met Sergey and Larry again. And in the hot tub at

like 2:00 in the morning, I said OK, you guys

just bought YouTube. We’ve got this

great thing for you. No, we worked really

hard, it took three years, it’s yours if you want it. For the first access to it, you

don’t want it to become Quahoo. And they’re like wow, this

is like really super cool. So after the next day, they

came around and they came to me and they looked

really sorrowful. And they said, Seth, we

talked with our business guy. We just agreed that our

corporate philosophy is to know everything

about everybody and we just couldn’t possibly

invest in a technology that involved not knowing

about people. I said look, you’re

not getting this right. There’s the European Court

of Justice is like suing you. You’ve got all these problems. And so I’m like, look,

let’s do it this way. You give me $10 million,

and I won’t do anything. So I’m not creating a

competitor for Google because I’m not doing

anything, so that’s fine. Meanwhile, you tell the

European Court of Justice look, we care so much about

people’s privacy. We’ve invested $10 million

in this brand new technology. It’ll absolutely

guarantee people’s privacy with internet search. And then the European Court

of Justice will be happy. European Court of

Justice is happy. You’re happy. I’m really happy. But they didn’t see it that way. It was very sad. Anyway, so these

quRAMs can now be used for these

kinds of processes. So it’s a very interesting

question of how you build them. If you look at our

patent, you can find out you could build them

with optical methods, you could build them using

superconducting circuits. I know that actually

there’s a effort here to build things that are

much more ambitious and more interesting than a quRAM. But for this, it’s just

quantum random access memory which allows us to

create these vectors. Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: Yeah that’s

a very good question. And this actually shows

insight into something that somebody

asked earlier about it’s often very hard

in a quantum computer to figure out how to

get the information out. So what we have to

do is not only show that you can do the

kinds of manipulations we need to do to do things

like clustering algorithms to build support vector

machines, that kind of thing, or the stuff that I’m

doing with Paolo here to do quantum versions of

topological big data analysis. We have to show that

having done that analysis, that the information in the

quantum states is at the form we need to actually get

the information out. So let me actually

address that in what I’m going to talk about right now. So having constructed

these datas, and now using,

basically, techniques from quantum computation and

quantum information processing, exploiting– I mean, empowering,

empowering those atoms, the superconducting

circuits in those photons to do these

manipulations, we need to construct things

such as, for example, things like interproducts. x dot y overlaps

between vectors. That’s easy. This is takes time order n. So this is logarithmic in

the size of the vector. So that’s the first step

you might want to do. We might want to do

things as we might want to compare some vector

x with the mean value of some other vectors. This is a basic step in the

clustering algorithm, k-means. And k-means, your job is to

take a whole bunch of vectors and divide them

up into clusters. And the idea is you assign

the standard algorithm– which by the way, happens to be

called Lloyd’s algorithm– but it was made by

Stuart Lloyd in the 1950s and I think he’s any relation

to us so far as I know. Anyway, so you have

a bunch of vectors. The way that Lloyd’s

algorithm works is you take a bunch

of seeds– guesses for the centers of the clusters. You assign each vector

to the nearest cluster. And then, when

everything’s done, you calculate the mean

values of the clusters. And then you just do it again. You reassign to

the nearest mean. And then you keep on

going until it converges. So that’s the kind

of thing you’d want to do is calculate

the distance of a vector to a cluster of a vector. And this also

takes time order n. So logarithmic in the

dimension of the Hilbert space and logarithmic in the number

of vectors in the Hilbert space. So j equals 1 to m. This goes s order n, log of m. So these are all–

if you actually compare these with

the exact versions of the classical ones–

you may notice something. That these things,

calculating this exactly for classical vectors

takes time to the n. Because you’ve got a sum of

all 2 to the n components. Approximating it by

various sneaky techniques by Monte Carlo or sampling

can take time order n, but not always. So there’s very

interesting questions about how much better we’re

doing then good heuristic algorithms. But if I’m comparing

this algorithm that we’re making to just the

straight up classical versions of these algorithms, the quantum

versions of these algorithms are exponentially faster

than the classical ones. The straight up classical ones. I’m not saying that they’re not

excellent heuristic clustering algorithms, of course there are

excellent heuristic clustering algorithms. Just saying that these quantum

algorithms that we have are exponentially faster than

the corresponding classical ones. OK? So, for instance, we can

do things like k-means. If you do the quantization

of this Lloyd’s algorithm, then you end up with something

like k n log m, which in order to do the k-means Lloyd’s

algorithm versus the quantum– this is quantum– versus k

times 2 to the n times m. This is the classical,

k squared, sorry, for the classical. So when you actually start

quantizing these algorithms, what you find is

that what you get is assignments of

vectors to clusters that are a lot faster

than you had previously. And now this starts to attempt

to answer these questions that have been raised about

how you measure stuff. What the output of this

algorithm is is it says, OK, it gives you a

quantum superposition of a list of vectors

that are assigned to a particular cluster. So of course it could be

very, very, very large number of those vectors and if

you want to know all of them, you’d have to do the

algorithm many, many times. But if all you want to do is

sample representative members of this cluster,

then these algorithms are exponentially faster

than the classical versions. Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: I’m not sure. So what this is

actually, what you calculate quantum

mechanically is this. Right? This is the true Dirac bracket. This is called a bra, not an

article of women’s clothing. And this is a cat. So this together is a bracket. This is why this notation

is what it’s supposed to be. So this is the inner product

between these vectors. So this is equal to

norm of x, norm of y. Sorry, this is equal to x dot

y over norm of x, norm of y. AUDIENCE: [INAUDIBLE]. SETH LLOYD: But

that’s hard to do. I mean this raises a whole bunch

of interesting, open questions actually. So for instance, just

evaluating x dot y, x dot y is often

very easy to do. You can do this

with order n steps quite accurately by Monte Carlo. But if you take something like

x with some transformation of y, like before you transform

of this vector y, then there’s no known way

and it seems very unlikely you could do this with

classical Monte Carlo. Where this is very easy to

do quantum mechanically. Indeed, what can you do

quantum mechanically? So here are the tools. So what did I describe there? I described this quantum version

of Lloyd’s algorithm, quantum clustering algorithm. Let’s look at the other tools

that– [COUGHS] excuse me, that we actually have. Sorry, it’s too warm here

so it’s making me cough. It was five degrees

when I left Boston. [COUGHS] So we take a vector

x and we can map it– we can do the fourier transform. This corresponds to

taking a quantum vector and doing the quantum

fourier transform. So the classical time

for this takes time order n 2 to the n for the classical

fast fourier transform. Even for the fastest fourier

transform in the West. And this takes time

order n squared. So things that involves

fourier transforms are exponentially faster

quantum mechanically. I mean, these are, you

take a 2 to the n vector, you have 2 to the n by 2

to the n sparse matrix. That’s not easy to do. Here’s another thing

that’s quite useful. If I take x goes to a inverse

x where a is a sparse matrix, this is order again n

times 2 to the n classical. And then the quantum

version of this, once again, this

is actually just, once again, order

n squared, maybe n cubed, depending

on how accurate you want to be

quantum mechanical. So matrix inversion

for sparse matrices is also exponentially

faster than in a quantum mechanical system

then in a classical version. In fact, our third algorithm–

this is our first algorithm right here, this clustering

algorithm we came up. Well, I’ll call her

our second algorithm, even though it’s

our third algorithm. So this actually, if you look

at these kinds of manipulations like this, if I have a bunch

of data points right here, and suppose I want to create

a support vector machine. So what a support

vector machine does, support vector

machine identifies the maximum marginal

hyperplanes that separate these two

data points right here. So if I have this

set of data points it’s a big set of vectors. I have this set of data points

it’s a big set of vectors. You can basically construct

support vector machines by doing linear manipulations

in matrix inversion on the so-called covariance

matrix of this data. And you can actually

show that constructing the covariance matrix and

performing the requisite matrix inversion, solving

the linear equations, you have to find these

kernel operators– blabbidy blah, blah, blah, as they say. And you find that this

quantum support vector machine has exactly the same

kind of features. And then of course, the kind of

question that you want to ask is here’s another data point. Does it belong over here or

does it belong over there? So you can show that

constructing these hyperplanes, finding these vectors

from the data, and then comparing this

data point to find out, is it closer to this side or

was it closer to that side? That can all, again, be

done in time order n where the classical versions all

take time order 2 to the n. And the reason is,

again, just to remind you of why this is,

it’s because you can do these kinds of simple linear

transformations, like quantum fourier transforms

or matrix inversions, solving sets of

linear equations, on very high dimensional vector

spaces is actually quite easy quantum mechanically. It’s because these

transformations, it’s like, what is

this photon doing when it bounces off this CD? A photon is a quantum

mechanical object moving through a humongous

dimensional vector space– the vector space of all

the propagational modes of the electromagnetic field. It bounces off of here and

quantum mechanics automatically does this linear transformation. In fact, just sending a single

photon through a diffraction grating is exactly performing

a fourier transform on the mode labels

of the photon, for people who know

optics kind of stuff. So in fact, these kinds

of transformations, like doing fourier

transforms, there are many quantum

mechanical systems that do things that

look like they would be very hard from a classical

computational perspective. And they just do

them automatically because that’s

just what they do. They’re quantum

things and performing linear transformations on

quantum things like fourier transforms is what happens. So I’m almost out of time. When do you want me to stop? It’s 1:58 right now. I’m going to advertise one more

nice thing because since Paolo Zanardi is here from

USC and this is the work that we’ve been doing recently

that– so was there a question? Or was that just an echo? All right. So this is a very fun topic. Topological big data analysis. You’ve got a whole

bunch of data points. There in some funny shape. But there’s a hole

in the middle. A hole is a topological feature. How the hell do

you find the hole? OK. And this goes under the

name of persistent homology. Who here has heard

of this stuff, these topological methods? They were developed by

Carlson at that UC San Diego, though I found out

from– I’m sorry? He’s now at Stanford. He was at UC San Diego. But I found out from

Michael Friedman, who was this field medalist who

actually does quantum computing stuff, that Michael

Friedman developed a whole method in a secret

DARPA program, or ARPA program, in the 1960s. And he showed me his

recently declassified notes. Anyway, so this is

actually really cool. So what is persistent homology? You think, wow,

topological features. How do we actually find

those kinds of things? So the way persistent

homology works is you basically

tessellate, or triangulate, if you like, this kind

of systems right here. You create what’s called

a simplicial complex. So you create a

topology, an ocean of things that are

close to each other. Topology. And then you create

the simplicial complex. I’m not going to draw

all the simplicies because there’s too many. You see where I’m

going with this, right? So now the great thing is that

now the next step– and this is what I all learned from

Paolo here, right here– the next step in this

homology is each simplex gets mapped to a vector in a gigantic

complex dimensional vector space. Complex vector space

of high dimension. And then finding holes,

voids, connected components, et cetera. This is just linear algebra now. So it was something that looks

like it might have nothing whatsoever to do with things

we quantized that is performing linear algebra operations

on large dimensional vector spaces, excuse me. If you actually go into what’s

called algebraic topology, it turns out that the way

people do algebraic topology is to say, we can’t deal with

these topological spaces. Let’s map everything

into vectors on some gigantic,

dimensional vector space. And let us do linear

operations on that. It’s a great field. But it’s a great field

that actually happens to be perfectly

adapted for making these quantum

mechanical algorithms and the quantum

mechanical algorithms. As you might not be surprised

out of this if this is an m, the classical logarithms. Classical goes 2

to the m where m is the dimension of this vector

space and the quantum, go s m. So, these quantum

algorithms, again, give exponential speedup. So Masoud is looking

edgy right there. I know what happens. That means he’s

about to beat me up. I’ll get you a

beer later, Masoud. Don’t worry. So let me just then conclude. So what happened? So that was a short course

in quantum mechanics. Everybody passed. So I was supposed to be here

a few days earlier but then I had to give all these

graduates oral exams. The graduate students just go to

the dentist themselves, I feel. So I’m tired of failing people. So everybody passed. So quantum mechanics

has this weird feature that things we think of as

particles correspond to waves. They can be in two

places, electrons can be in two places at once. Mathematically, this means

that the mathematical structure of quantum mechanics

is that the states of quantum mechanical

systems, these waves are, in fact, vectors in high

dimensional vector spaces. And the kind of

transformations that happened when things

like particles of light bounce off of CDs are just

linear transformations on these high dimensional

vector spaces. Quantum computing is

the effort to exploit– I mean, or empower– quantum

systems to transform, allow these linear

transformations to perform the kinds of

things that we ourselves would like to do for

manipulating data in this quantum mechanical form. And if you have a quantum random

access memory which allows you to map data onto big data

into big quantum data. I know for a fact,

being in Academia, that in order to get

a grant these days, you either have to have the

word big data in your title or graphing. So what we’re aiming for here

is graphing-based quantum random access memory for

quantum big data analysis. It’s a winner, I can just

smell the funds coming in. So you have a quantum

random access memory that maps your classical

data onto a quantum state. This actually turns out

to be something that’s a lot easier technically than

full-blown quantum computing, initial experiments, and proof

of principles have been done. It’s been patented because

I learned my damn lesson with D-Wave the

first time around. Then we have to make

sure that we can actually do the manipulations

that we need to do. The various linear

transformations, evaluating inner products and

distances, looking at means and clustering. These turn out to be all

accessible in a quantum computer and compared with

their classical versions, they are exponentially faster. Then you go to more fancy stuff. You find you can do

fourier transforms, you find that you can

do matrix inversion, you can solve systems

of linear equations. You can do things like

find kernels of operators in high dimensional

spaces, which is the essence of actually

doing this persistent homology. And so what we found

is that once you have this first step of

this dumbass intuition that Patrick Rebentrost

came up with is like, whoa, lots of

machine learning is about manipulating large numbers

of vectors in high dimension vector spaces. Gee, quantum mechanics is about

manipulating large numbers of vectors in high

dimensional vector spaces. Wouldn’t it be fun if we

could bring them together? That’s dumbass intuition

turns out to be correct. And so now we’re working with a

whole variety people, and here, of course, with a few

folks at Google research, to try to make this vision

of actually doing big data analysis in intrinsically

quantum mechanical ways that are potentially

much more efficient than the classical ways

to make that a reality. Thank you. MASOUD MOHSENI: Thanks, Seth,

for that nice introduction to quantum mechanics and

quantum machine learning. So are there any

other questions? SETH LLOYD: Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: Yeah, that’s a

very interesting question. So quantum mechanics on itself

seems to be exactly linear. At a fundamental level,

all the experiments indicate the quantum mechanics

is linear to one part in 10 to the 18th or even better. However, you can actually–

the word linear is used in a variety of ways. So you could certainly

have nonlinear interactions in quantum mechanics. The interaction of light with

matter is nonlinear typically. So like absorption

of light of matter is nonlinear, that’s

a nonlinear reaction. But the waves– the

quantum mechanical waves– still superpose in

a linear fashion. So in some systems,

as in, for instance, Bose-Einstein condensates,

you can actually emulate what would be a

fundamental non-linearity by manipulatively using

these existing nonlinear interactions. But quantum mechanics

is basically, the way that we know it, it

is linear, exactly linear, and so we’re stuck

with that linearity at this fundamental level. Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: And in

the number of vectors. AUDIENCE: [INAUDIBLE]. SETH LLOYD: Well

normally to compare, normal k-means

goes as m squared. Where m is the

number of vectors. And ours goes as log m. I’m sorry, when I take

m and take it to log m, I call that an

exponential speedup. That’s what I mean. Because saying a

logarithmic speedup doesn’t sound– I mean, it’s

true that taking m to log m, going, wow, it’s a

logarithmic speedup, nobody gets very

excited about that. But of course, taking m to log

m is an exponential speedup, so I call it that. It sounds more exciting. It’s also true. AUDIENCE: [INAUDIBLE]. SETH LLOYD: Yeah,

you can, always. We tried lots of stuff. There are many things we

haven’t been able to do. So for instance,

this is things that I want to talk with

people about here. So we can solve linear

equations and even polynomial or

nonlinear equations with equality

constraints, because then a Lagrangian method

turns us into another set of linear equations

that we can solve. But it’s hard. We can’t do that with

inequality constraints. And these show up all the

time in machine learning. You have some convex space. You’re trying to identify the

interior of the convex space. Like the support vector is

lying on the exterior of this and you solve some equation

with inequality constraints. And then you’re stuck with

Karush-Kuhn-Tucker equations. And who knows what

the hell to do then? And we don’t know what to do. We’ve tried really hard,

all kinds of methods. Basically what we’ve

been doing right now is we’ve been doing the stuff we

know how to do well, like solve linear equations, do

fourier transforms, identify kernels

and eigenspaces. Or we can diagnalize

matrices and find eigenvectors and eigenvalues. That’s something you could do

very effectively on a quantum computer. But there’s some

things we can’t do. And so, we certainly–

this is not a magic bullet. Even if you could build a

large scale quantum computer, this wouldn’t be a magic bullet

to solve all machine learning problems by no means. Was there another

question over here? Yes. AUDIENCE: [INAUDIBLE]. SETH LLOYD: Oh, a product. Oh, I don’t have a product

except with a lot of phonons. I am not a company. But in terms of building

quantum computers– so, basically what’s

happening right now is that there are

small scale quantum computers with a few

tens of quantum bits. We’re hoping to have like,

within the next five years or so, there are people

like John Martinez who say they’ll build you a quantum

computer with 100 quantum bits. I don’t know if it’s true. But it’s quite possible. And I think actually

the way to go here is one of the philosophies

behind this approach is the people in

quantum computing– which is a field that’s been

around maybe for almost 20 years as a very young field–

have been talking about trying to build very general purpose

quantum computers that act in the same way that

regular digital computers do but operate in a fully

quantum mechanical fashion. But I think one of the

philosophies that I pursue– and certainly the people

here at Google are pursuing– is to try to construct. Because there’s

this intrinsic power in the way that quantum

mechanical systems behave. Can we actually

construct devices that– I was just about

to say exploit again, it’s like, really hard. Like when your professor

of engineering at MIT. Not to say we exploit the

properties of this materials. Can we find ways of using this

ability of quantum systems intrinsically to

perform operations in high dimensional

vector spaces without actually having to

go through this whole entire digital formalism? The fact that

diffraction grating makes a fourier

transform automatically. Can we use that kind

of thing, actually construct devices that would

do this kind of manipulations without having to go the route

of making a large scale quantum computer. That’s what we’re aiming for. And there I think that

there’s actually– I think there’s very good

possibilities for that. Yeah? AUDIENCE: [INAUDIBLE]. SETH LLOYD: No, actually,

you do see that. In fact, I just last

Thursday and Friday was at a conference at

[INAUDIBLE] Cambridge. It was the first conference

on integrated quantum nano photonics. So one of the big developments

in just switching theory right now, or practice,

is the development of integrated photonics. So you etch waveguides

and silicon, you can put millions of

switches on a silicon wafer. And so for many

years, there have been lots of experiments

in quantum computing that did quantum computation

using interaction of light and

polarization with atoms. And all these

experiments look the same because all optical

experiments look the same. There’s a gigantic optical

table and all these lasers off on the side and a

million mirrors there. And then light beams

are bouncing around all over the place and have

no idea what’s going on. Every single optical

experiment looks like that. So a remarkable thing is now

happening, driven actually by the desire of places

like IBM to build these on chip-switching

arrays is these gigantic interferometers

with interactions between light and matter are now

being miniaturized into individual wafers. So a 3 centimeter–

well, they’re slightly bigger than that. So 30 centimeter silicon wafer

contains an interferometer that would’ve taken five

optical cables previously. So I think there’s a

lot of hope for that. The real problems are

getting strong interactions between light and matter. Superconducting systems are

very good way to go there. In fact, there’s a strong

analog between transmissions of microwaves in

superconducting microwave line and analogs of photons. In fact, it’s so strong

because they’re the same thing. They’re microwave photons. But instead of atoms you can

use these little superconducting quantum bits that now interact

much, much, much more strongly with these microwave photons

than ordinary light interacts with atoms. So there’s a lot of great

quantum technologies out there. And, as usual, a lot of

the progress in this field is being made by the combination

of industrial push creating new technologies and

fabrication technologies that allow us to do things

we couldn’t before. And then pull from application

on both classical and quantum application. But of course, what you’re

saying is completely correct. And I think there’s a lot

of hope in the near future to have much more

powerful devices that use these techniques. MASOUD MOHSENI: Thanks

again, Seth, for coming. SETH LLOYD: Thank you. [APPLAUSE]

26:10

"I hope everybody is hearing these questions. These are all extreamly important questions."

I am crying inside right now.

I wonder what the microphone in the middle is for…. :p

thank you ðŸ™‚ thanks for teaching!

"Seth Lloyd visited the Quantum AI Lab at Google LA" //Quantum AI labs are so trendy these days.

After Seth mentions the footnote from the 1929 paper, about alphaÂ²+betaÂ² = 1, thinking about complex numbers, it comes to mind that he is actually talking about the unit circle. As the total probability is always 1 or 100%, the radius of the complex number representing the total probability of the qubit being 0 or 1 needs to be 1, hence the unit circle, hence the quadratic members.

These silent question-pauses are making me nutts.. Wish Google would bother with microphones or at least texting the questions into their videos.

It would seem we have moved to mapping interference patterns

as Quantum Symphonies. representing Complex Systems.

Lol, it's like hearing 42 over and over again. We get the answers, but not the questions.

missed all the questions

Very interesting talk, too bad you couldn't hear the questions.

"I'll address this in a bit." -SL

Summary at 57:33

2:18

All I want to know is d wave full of shit or not

Mother fucker laughs like Poindexta from Revenge of the Nerds

Next time,Â

Google Hangouts should….21dWill

Be evolvedÂ

So that other's may attack this data

– He considers himself a quantum mechanic.

– Your quanta are broken, we fix them.

The guy is fantastic ðŸ™‚

Pretty sure at 58:35 and 58:37 he is saying "Graphene" not "Graphing"

this guy might be a genius but he has the most annoying laugh I've ever heard

love his laugh…makes him sound like the mad scientist..lol

how lissom this is ðŸ™‚

been watching all this guy's videos, must be the funniest quantum physicist out there, cracks me up every time. The bit about the remainder of the audience having both studied and not studied quantum physics and understanding it intuitively had me on the floor.

Haha. QM is based on an equation that "Nobody Knows"? I think I'll just move over to polytheism now.

You'd hope Google, of all companies, would bring an electronic whiteboard for the guy to use, so that it can be projected overhead and shown clearly in the video. But nope.

A lot of misinformation on this one… Prime example, the James Brown quote isn't from a concert, it's the intro to "Make It Funky":

(Bobby:)

What you gonna play now?

(James:)

Bobby, I don't know. But whatever I play, its got to be funky!

(Bobby:)

Yeah

What a pity that we can not hear the questions.

Are these the same talks?

Very very lucid talk by legendary Seth Llyod! Unfortunately the queries by audiences are not audible.

That whiteboard looks like the Moses Tablets.