Uploaded by GoogleTechTalks on 14.12.2007

Transcript:

>> NEVEN: Thanks for coming to the first part of the three part TechTalk on quantum computing.

The first is about introduction to quantum computing. And actually what I'm trying to

do is to take an unusual look at quantum computing. We want to take a look from the vantage point

of synthetic intelligence. Essentially a notion I would like to promote is the idea that in

order to create artificial intelligence, and by this I mean, tasks like pattern matching,

machine learning, has a lot to gain from employing quantum computers. Actually what I would claim

is if you were to have a working quantum computer of sufficient size on your table today, the

business of doing, let's say a machine with a learning algorithm, would entirely change.

And since this has such dramatic effect you might want to know, "Okay, do I have to bother

or worry about quantum computing before I retire?" Actually is another thing I would

like to get across. Working quantum computers will may--are probably or may be only a few

short years out. Actually in the next talk, we would go as far as this computer here,

this little laptop, has actually a MATLAB program on it that ties via Webservice and

Java and Webservice into a quantum chip that is admittedly still small, but despite of

what you have maybe read in the blogs or popular press, this is a real quantum chip that exists

today. And actually what we have done with it is take a human level task, object recognition,

and build a pipeline, a mix of classical and quantum algorithms to break this task down,

map it unto the quantum chip and bring it all the way back. And I think this type of

task will--I have a feeling that quantum computing might be the missing link that brings true

human level intelligence to machines. So, [INDISTINCT] this--my idea are not very farfetched,

as so does the brain have anything to do with quantum computing? So actually today the answer

would be bluntly, no. Neurobiology as the current paradigm has it that in order to understand

higher brain function, all we need to look at is an organizational level above the single

neuron and beyond. So essentially looking at neurons as classical devices that cooperate

or compete with each other, bringing about the neuro-dynamics that this is all you need

to understand higher cognitive function. But something I would like to predict is that,

sort of the pipeline of the nature I have described before and our increased understanding

how we might harness quantum processes to perform meaningful computation, this paradigm

might get challenged or is ripe for review. So probably, quantum computing will inform

our search for the quantum box as John Ekards [ph] would call it. Okay. So, after this introduction

to the introduction, let me jump to the first part, the basics of quantum mechanics. Again,

the intended audience is computer scientists and I realize it's a tall order to bring the

base concepts of quantum mechanics across in less than an hour which normally is taught

within a semester. But, let me try. First, let's look at a few base experiments. And

I kind of assume that everybody of you knows to various degrees about quantum mechanics.

I'm sure you have seen something on TV or read a book. You're an educated audience.

So first thing, an experiment from which--which likely shows the property of nature from which

quantum mechanics got its name, the so called Stern-Gerlach Experiment. And how this works,

and I'll try to use the mouse instead of my hands. You have a little furnace out of which

silver atoms come. And silver atoms have a magnetic moment so you can think of it classically

as a little, sort of compass needle coming out of your furnace. And of course they are,

sort of randomly organized, so there's this cloud of little compass needles flowing out

of your furnace. And then there this big inhomogeneous magnet that pulls and pushes on these magnets

depending on their orientation. And then, what you would expect because it's random,

some get pulled up, some get pushed down but it's essentially a random mix. So what you

see here on a classical prediction, if you put a photo plate behind it, this elongated

patch is what you would expect to see. Now what you really find is you only see two patches.

So this is, if you would have a little compass would mean, if you look at it you will only--two

things, compass needle up or compass needle down. So this is contrary to our, sort of

microscopic experience, and shows sort of first fundamental effect or a fact. Physical

observables are quantized. So it's like money, it comes sort of, in the smallest denomination,

as you one cent of nature. Actually this is--typically this cent of nature is typically denoted by

h--hbar, the Planck constant. And this [INDISTINCT] observable, it's like quantized is true for

energy, for angular momentum, for many important physical observables. So first effect. But

this effect has an important impact on how we observe nature. So let's look at something

that physicists do all day long, speed measurement. Essentially you can think of a speed measurement

in the following way: I have a little radar gun here in my example, and you shoot little

photons towards a car to measure its speed. So if you think about it, really those photons

have momentum and they push the car a little bit. But you would agree, you will not get

away with the excuse saying, "Hey officer, I wasn't that fast. [INDISTINCT] really pushed

my car." The reason you won't get away with this excuse is obviously the momentum of the

photons is so small that it doesn't really affect the system on the observation. But

now assume we want to observe something microscopic. So the car gets smaller and smaller, and given

that nature is quantized, I cannot always--or I do not always have the luxury of having

a probe fine enough that it is much smaller than the system on the observation. Or a different

way of looking at it, if sort of your probes would get larger, and here in this example

you would shoot bowling balls at the car, then obviously this measurement will affect

the state of the system, yeah? And this is in the microscopic world generally true that,

"observation affects the state of the system," okay? Second important fact. The third important

fact, here's sort of the quintessential experiment in quantum mechanics, is the double-slit experiment.

I'm sure you have heard of it in various ways. Now think of it in the following way, there's

a light wave coming through the first screen here, screen one, and it spreads out, think

of it like a water wave and now you have thrown a stone into a lake that was calm before.

So this wave spreads out, reaches the second screen and then, sort of two waves, come out

from there. So it's like throwing two stones into a lake. And we all know that the effect

in sort of these waves interfere, they can be superimposed and you have constructive/destructive

interference. And it creates an interference pattern like shown here, these black and white

stripes. But now if you would take a closer look, essentially again realized by a photo

plate, and you look at this picture here on the right side, the abc, and we look, we--it

gives a photon stream, make it very weak so that only one photon per time unit comes through.

Then we see a build up like this, sort of, you get little impacts on the photo plate,

and essentially you get this wavy pattern here. So essentially what we see if you take

closer look, that this wave pattern only gives us a probability where we might find the impact

of a particle. And this is also called the wave particle duality. And you can do this

with photons, meaning with light, or you can do the same thing with electrons. And again,

you can do it even if only one electron at a time goes through the slits. So it interferes

with itself. So the important lesson here, in superposition, a sort of a fancy word of

this wavelike behavior is that you can superimpose the states. So superposition, again it worked

for electron and photons, is a general principle in nature. Those three important facts. So

here comes the big jump, I don't want you to go home without formulas. So the philosophy

of these talks will always be give some intuitions and then jump to the formulas and I cut out

the middle piece. So here's pretty much all quantum mechanics, the kind of we'll ever

need, or you can derive the rest from this one single sheet. So how does quantum mechanics

formalism describe nature? First, if you describe the system, you want to know what its state

is. So, its state is here denoted by psi and these funny brackets around psi and the so

called Dirac Notation. So, this is just a way how a quantum physicist denote a vector.

So psi is just a vector and the funny thing around is the vector sign. And the state of

a system lifts in a Hilbert space. A Hilbert space, essentially for all purposes you can

think of it as a linear vector space with a scalar product over it. It's a complex vector

space. And moreover, we wanted to norm of the state vector is 1. And we will see in

a second why this is. Okay, now we know what a state is in quantum mechanics. Next thing

you want to know; how does my state change? So how the temporal evolution--fancier word

for it--comes about is essentially in non-relativistic contacts through the so called Schrödinger

equation. You see, the Schrödinger equation is basically a differential equation that

shows his changes--the first derivation according to time of the change of your state dependent

on what’s here on the right side, and what's on the right side is called an operator acting

on the state and this operator is called the Hamiltonian. The Hamiltonian essentially has

to do with the overall energy that's in your system. So depending on how much energy is

in your system and how it's structured spacial temporally, the state will change in different

ways. And actually, there's an equivalent way of writing it. If you go here to the right

side, essentially here the Hamiltonian is put into evolution operator. So basically,

you have a state here, psi as in time to zero. Then you--evolution operator think as a black

box and now you push your state in at time T and then you get the state at time T out

of there. So, state and temporal evolution. Now, it's important to see the differential

equation here was linear, the states base is linear, so we have a linear theory. And

this allows for an important fact that in particular means, if I have two possible states,

psi 1 and psi 2, then any linear combination, for example, like psi 1 plus psi 2 is a solution

as well. So here you see the super position reflect it. So two states, I can superimpose

them and again I have a valid state. Now comes the third part, how do I measure the state?

And here in classical mechanics you wouldn't find much, you know, as the position of the

car, yes sure I measure the position of the car. So there's the state of the system and

what you observe is kind of the same thing. But earlier in the speed measurement example,

we discussed that in quantum mechanics this is more involved. So in quantum mechanics

you describe an observable, like energy, magnetic momentum, through a matrix your A, an operator,

and this operator self-adjoined which basically means it allows for a spectral decomposition

into eigenvalues of this nature, that where the eigenvalue is m as a possible measurement

outcomes. And because this operator is self-adjoined, it guarantees that those measurement outcomes

are real numbers. Remember, everything before was complex numbers and you don't really see

complex number too observable to nature. You only see real numbers. The fact that this

observable is described by self-adjoined operator ensures this. So basically--and it has a complete

basis. So the eigenfunctions of A are complete basis for the Hilbert space where the state

lives in. So you can express any state in a decomposition like this, as sum c i over

the difference states. So again, as a large linear com--super position of the individual

eigenstates of your operator under consideration. And then the probability of finding a measurement

outcome is essentially the modulus square of the coefficient in front of the eigenstate

where you find your system, okay? This is called the Boen rule. And after the measurement,

your system would be in state a i corresponding to what you measured, okay? So that's my--the

trickiest part to understand. Observable corresponds to self-adjoined operator meaning it has a

set of revalued eigenvalues. These are the possible measurement outcomes and essentially,

if you decompose a state the way it’s written here the Boen rule gives you the probability

of finding the system in a certain state. Okay. So the last part that traditionally

was not taught as an important fact is how do you compose two quantum systems? You have

one and you have a second. But you can imagine if you want to build a quantum computer this

will often happen that it would be built or composed out of subsystems. So subsystem composition

is actually not that difficult. What you do is you take two Hilbert spaces, H1 and H2,

and you form the outer product of those Hilbert spaces. So this is now the total space your

system lives in and then you can--and the simplest way, take a state out of--one of

those two spaces and, like here, it says psi, and then you take a second state out of the

second system and you build the outer product, the tensor product of these two vectors and

you get a new state. So these special states are called separable states. But again, we

can build super positions; we can put a sum in front of sub states and get what this so-called

entangled state. So just in case--so here's sort of an important off ramp, if you ever

have heard about the Einstein Prodosky Rosen South Experiment or about quantum teleportation,

the ingredient you need to do things like quantum teleportation are entangled states

and we're not going to explain those today just sort of, if you study literature this

is sort of the off ramp. You have to get to--you have to understand what an entangled state

is, then you can proceed understanding what is quantum teleportation is. Okay. So, wow,

this--might be a little bit too much on this one sheet. Let's try to break it down. I think

in the next slides it will, sort of--I see a lot of shocked faces. I hope, sort of applying

this a little bit will make things simpler. So let’s a look at a very simple situation,

let’s take what's called a potential well. We take a particle that's an electron and

we put it into a box and we don't want to let it out. And here's a classic analogue

would be, let's say you go into a hole or let's say you have a large bucket and you

put a basketball in there and it bounces around, in such a situation you want to look at. So

the Schrödinger equation for this situation is written up here, and again, you recognize

it here was the Hamiltonian we have to use in this. And the Hamiltonian was, sort of

associated with the total energy of the system and you might know if you have something like

a bouncing ball, you have essentially two types of energy, the kinetic energy, how fast

this ball is flying around, and the potential energy, how high is it above the ground. So

these two terms together make up the total energy of this particle. So here we have now

differential equation. At first glance for the non-mathematicians thinks, "Oh, damn it.

Looks difficult to solve," but from here on, it's only mathematics. And it's a little bit

simplified by the fact that because the potential doesn't change in time, the Hamiltonian is

time independent. And then this allows for a solution that's down here, where the main

thing I want you to look at, is that this solution is again, a linear superposition

of this states psi, and psi are the eigenstates to the Hamiltonian. So this is how you can

compose a general solution for your Schrödinger equation. And here let's look at a special

case where our potential, you know, is sort of infinitely large then what you see here,

you know, in your little box, the wave functions, was the name for those solutions, for different

eigenvalues E, different amount of energy your particle can have. So that is how they

look, you know, you little bend it like a parabola, wavy, sort of wave with a shorter

wavelengths. So these are solutions. So now, more interesting, let's go to a situation

where the box is not infinitely high, it's not an infinitely deep well but it’s only

finitely deep well. So this is here shown in the right side. So what you see here is

something very important and we get the first sense of how this can help us in computation.

You see that the wave functions don't go down to zero right away where the border of the

potential well is. Actually they--there is still a finite probability of finding your

particle outside of the well and this is called the tunnel effect. So then I could use it--imagine

it would not be in the well but just sort of a barrier. So essentially, a potential

well but with a thin barrier. So then this particle could escape there even though it

doesn't have enough energy to jump over the barrier, it goes through, hence tunnel effect.

So think of it, here's this basketball, denotes a situation classically. If this basketball,

if I throw it in, if it doesn't have enough kinetic energy at that point to jump over

this wall, it will never get out of this potential well. So now for--and this is for computer

science. Everybody of you who has worked let's say with optimization problems will know that

getting stuck in a local energy minimum is a major curse whenever you express your problem

as an energy optimization problem. So, I think you will have a taste for the fact, "Hey,

I have a new mechanism here to get out of a local minimum." And that's indeed an effect

that we will harness for computation. Actually, adiabatic quantum computers do basically this;

they help you finding the global minimum and then the energy function by exploiting the

tunnel effect. Okay. So, let's sort of go through this one more time. Again, we have

learned that a state of the quantum system described at T-zero by a state function psi

of a T-zero, and then we have essentially two ways how this state can change. The first

one is continuous severe unitary evolution or via the Schrodinger equation, sort of a

continuous change over time of your state. And then, some nasty physicist comes along

or any human and will do a measurement. And then, oops, after this measurement, sort of

I drastically disturb my state and I come out in this state a i one of the possible

measurement outcomes in my measurement. And then, from there on, if nobody interferes

again, it will continue to evolve again like a unitary evolution via the Schrodinger equation.

So, that's basically what's--was on the cheat sheet, but as--it's like an ugliness this

is, you wonder when does a measurement really occur? Shouldn't the measurement instrument--I

mean, those are part of reality, too. It's a box with some pointers and some iron and

cables; shouldn't this obey quantum mechanics as well and shouldn't it sort of, follow an

unitary evolution along Schrodinger equation also? So, what does really constitute a moment

where measurement happens? And as the original--so when quantum mechanics came up, the first

complete formulation, the Copenhagen formulation of quantum mechanics, unfortunately failed

to do--give a clear definition of what is a measurement. And this--and at least, in

two cases, you can imagine that this yields problematic or paradoxical results. One is

a closed system. So, you have a box and you have some things in there, like let's say,

decaying nucleus and a cat. And we saw that when the state evolves--actually, we didn't

show this, but the Schrodinger equation sort of likes your preposition. So, it takes a

clean state and sort of spreads it out and then creates those super-positions we saw

about. So, what does this then exactly mean for a cat when it's in a superimposed state,

in particular if we would just think of it as a cat that is alive or dead. So, I'm sure

you have heard about the Schrodinger paradox. In this situation, essentially a cat in the

box and no observer involved. And this essentially has to do with the fact that we don't have

a clear prescription of what a measurement is. And this leads us to--and this is a key

question when it comes to interpreting quantum mechanics. What constitutes a measurement?

And again, in 1927, when the Copenhagen interpretation was formulated, again, it unfortunately failed

to give a clear definition of what is a measurement. So--and in '32, for Von Neumann came and said,

"You know what, I do it much cleaner. I also treat the measurement apparatus as a quantum

mechanical object. And I use only quantum mechanics to describe the whole thing end-to-end;

essentially of my state, I have my measurement device and I have sort of an observer that

looks at it. And then I analyze it in those terms." And essentially, what you see and

you have a state here in a superposition, a general situation, then you bring it in

contact--please remember existing composition. You bring it in contact with the measurement

apparatus here--and let's say and the state ready and you also bring them in contact with

an observer, again, in state ready. And now, here is this little arrow. Arrow essentially

denotes Schrodinger evolution again. Then, what will happen? What Schrodinger equation

does, it will bring about--it's like a zipper. Anything that the state touches goes into

a superposition as well. So, as soon as the system we want to observe, which is in a superposition

gets in contact with the measurement device, causes the measurement device to go into a

superposition as well. And then even worse, if the observer looks at it, it will go into

superposition as well. So, this is contrary to our everyday experience. Let's say, here's

this water bottle, it seems to be only at one position. It's not in a superposition

of multiple states, and we rarely see somebody in a superposition between life and death.

So, essentially the Von Neumann program, depending on how you look at it, failed. Essentially,

the way out that Von Neumann suggested is to say the final wave function collapse so

that you get sharp real states measurement outcomes as we experience them, this only

occurs--this final measurement occurs in the observer's mind. And I just--so, what happened

at that point is that essentially the observer's mind becomes a primitive notion that is foundational

to constructing physical reality. And I'm just mentioning this. This was '32. So Von

Neumann is not a new age kind of guy, you know. He was a very--I mean, as you are really

familiar with his career. What I want to point out is that quantum mechanics by its very

nature is very suggestive of bringing, of giving the observer special status, you know.

And this will of course be very important in the third talk when we look at the brain

in quantum mechanics. So, the last way to deal with what constitutes a measurement and

a very radical one, but one that's very popular among people who do quantum computing is Hugh

Everett's many world interpretation. So, what he essentially said is essentially a very

beautiful and very symmetric idea of it. He’d say, "You know what? It's not only one measurement

that comes out. There are thousand possibilities. All possibilities will occur eventually. Just

they happen in different parallel universes, in different classical universes." So, in

this notion to give you a feeling for this, I tried to use this, a time-proven allegory

of Plato, where Plato discusses human perceptual abilities in a situation where you have a

fire and prisoners in the cave only watch sort of two-dimensional projections of really

a three-dimensional world. And he discusses their limitations and how--what--picture of

realities that would construct, you know. So, in the "Many Worlds" or maybe better called

"Many Minds Interpretation," is a similar situation. The wave function psi is this enormously

high-dimensional beast. And what we seem--and this is sort of reality. However, what we

perceive as reality are low-dimensional projections. So essentially, our classical world as we

see it in this view would be only a tiny sliver of the much richer reality. So, this is the

Many World/Many Minds Interpretation which from an epistemological--or sort of an internal

consistency view, if it is correct that quantum mechanics is a linear theory, then this is

probably the cleanest interpretation of quantum mechanics. Okay. So, these were the basics

of quantum mechanics. So, you can take a ten seconds breathing. And we go now to quantum

computing. How can we use this now to build better mousetraps for our trade? Let's quickly

review classical computing. I don't have--I think this audience doesn't need any explanation

what a Turing machine is as a model for computing. And you probably know that any Turing computable

function can essentially be brought into form, where you have a function f that goes from

a binary, an n dimensional binary space to an m dimensional binary space. And basically,

you have the option for a physical, logical realization. That's those gates like Ngates,

Orgates, Notgates. And basically a program on its lowest level can be broken down as

you have a bunch of zeros and ones. And then you push those through a set of gates. And

at the output side, you--essentially here in the space, and the n-dimensional binary

space you look at your result. And you also know that I don't really need all those gates.

Subsets are enough to construct everything like, for example, a FANOUT gate and a NAND

gate as a universal set of gate. So this is pretty much all you need to represent any

Turing computable function. And so this is essentially the gate model using logical gates

for classical computation. Now let’s look how this looks in quantum computing. Actually

very similar. You start with a state. Here, denoted 100. This is actually--I simplified

from [INDISTINCT] notation. I had explained what a composed system is using this tens

of product symbol. I sometimes leave it out and just concatenate the individual vectors

like this or just write a vector like this. So these are all just different ways of notation.

So the main story here is you start with a state and you push it into a gate--actually

in quantum mechanics, the way to think of a gate is just Schrödinger equation doing

its job for, let's say, a fraction of a second. Now, again--or as a way of saying it, you

have an evolution operator that acts for a finite time on the state and then you get

some result. It's a very analogous in a way to a classical computation. And now comes

the--a trick. Let's replace the state by a superposition state. And if I had, let's say,

three cubits acting here, you can, let's say, use a state like this and push it through

the gate. And the gate doesn't care. The gate again is represented by a unitary operator

that it doesn't care whether it got just sort of a single basis state or a superposition

state like this. It will do its same job. And hey, that's cool. So it was one gate operation.

I can act on all these guys with one clock cycle. And I need to do this more. So you

go make a more radical superposition and you realize if you had sort of in binary notation

and digits, then the number of basis states that you have available grows as two to the

power of N. In one clock cycle, you can act on two to the N basis states. Now, it's fun.

I think it's obvious that you can expect some computational gains from this. Unfortunately,

superposition states, as you make larger, they're fragile. They tend to break. This

is one of the engineering challenges and we'll discuss on the next talk how to keep this

decaying of superposition states at bay. We have some of the intuition phase. A different

way of understanding the power quantum computers is as follows. And I mentioned it earlier.

You know that many problems can be expressed as finding sort of the minimum in some objective

function, you know. Or if--in the physics context, if this would be some energy landscape,

I want to find the minimal point. And again, doing this--now this is some computationally

expensive proposition--and doing this with classical [INDISTINCT] like--probably familiar

with gradient descent or simulated annealing or genetic algorithms; they are essentially

all flavors of gradient descent and they're all bound in some way or the other to get

stuck in a local minimum because there's this fundamental limitation. But remember the tunneling

effect, this can help us in certain conditions to get out of this local minimum and find

the deepest. In some ways, the quantum mechanical particle can see, if you want to allow this

metaphor, where the lowest state is and has--you have--in a gradient descent approach essentially

gets its quantum boost that comes from tunneling. And this is the second model of quantum computing.

There was gate model we looked at earlier, the adiabatic quantum computing principle,

which I will show actually in the second talk. They're equivalent, the adiabatic quantum

computing. So thinking about quantum computing in this picture and the gate picture we looked

at before, so those are equivalent. >> MAN: Remind us what adiabatic means.

>> NEVEL: Adiabatic means slow. And I will--the next talk will be extensively about adiabatic

quantum computing. So we'll explain this why the term slow enters there. Last, intuition.

And I actually wanted to take this slide out initially and take it with a grain of salt.

But still, I find it a powerful metaphor. That's not too wrong. Let's put it like this.

If you--again you know that many problems can be posed in form of a decision tree. And

if you are sort of a person confronted with decisions, so you have a classical particle,

then finding, let's say where the longest branches in your decision tree. The way how

you go, you go down one branch and check its length and then you go back and to take the

next branch down. And we have all these different algorithms how to do this in a smart way.

But at the end of the day, you have to always try one branch and come back. A quantum mechanical

particle, again by virtue of exploiting super positions, has a much easier time sort of

grasping all possible states a system can be in and sort of explore this decision tree

in a much more economic way. So this is--again, with a grain of salt. But I gave you--the

two first intuitions were exact and this is sort of a little bit metaphorically speaking.

So, now again, jump in to the calculus. At first, introduce this qubit, which the name

suggests it's a quantum bit. It's a quantum generalization of a bit. And the--like sort

of the bit in classical computation, it's a simple two-level system you can think of.

Essentially it--we are in a Hilbert space that is isomorphic. Meaning it looks like

C2, C being the complex numbers. So basically, I have two states here denoted as zero and

one. These are two linearly independent states. And again, you have heard it again, super

proposition, super position, super position. We can have a general state psi, you using

a general linear superposition of these two base vectors. And then what you heard earlier

also was that a state vector needs to be normalized; meaning the norm of this vector, which is

shown here, needs to be one. Actually, I still owe you the explanation why this is--you heard

me talking several times about the Born Rule and how quantum mechanics, the calculus essentially

doesn't tell you exactly what's the outcome is, in general. It only gives you probabilities.

But in order to properly speak about probabilities and have a probability calculus, it just needs

to be normed. Then hence sort of—-quantum mechanical states need to be normalized so

that probability interpretation makes sense. And then there's one more thing. So actually,

when you look at the state, you would say, "Okay, my quantum bit basically is described

by a complex number alpha and the complex number beta." And, you know, each complex

number can be represented with two real numbers. You would say, "Okay, I get this qubit. It's

essentially equivalent to four real numbers." Not quite. Again, we had already one knocked

out of this equation here. It takes one of the four out. And there's actually a second

one that goes out and you cannot understand why. As we said earlier, all measurements

results are always modulus square of the coefficients in front of a state. So essentially a phase

factor whose modulus square is one just makes it to be multiplied by one, so it has no physical

meaning in the sense it wouldn't change you're measurement outcome. So you can take any quantum

state and multiply it by a phase factor of this form and your measurement predictions--that's

all what quantum mechanics does; gives you measurement predictions--wouldn't change.

So actually there's a second parameter that goes down to drain. So once we've realized

this, we can essentially express by doing some--bit of massaging and expressing the

complex numbers by angles. And you see that the general state--it's actually a general

qubit psi can be represented like this with two angles; theta and phi. And essentially

qubit hence can be visualized as a unit vector moving on a sphere. And this sphere is called

the Bloch Sphere. So maybe another thing to take away from here is that a qubit instead

of--is not an analogue nor a digital thing. It's something in between. Before it's measured,

the state itself is obviously an analogueue entity but when I measure it, I will only

get two outcomes, it's in state zero or one which is eminently digital. So this is something

beyond digital or analogue. It's not either or; it has properties of both. So, going to

the general gate model of quantum computing, I think you can already imagine how this goes.

Again, various--we looked at it already. It's just sort of repeat. Essentially, how it works,

you have--you prepare your state with--let's say you have a bunch of qubits here, those

of size, initial qubits and you have gates, single qubit gates or multi qubit gates. Again,

these are little evolution operators acting for some finite time and they massage your

qubits into some final state of your qubit and then you measure it and, hopefully, you

get the result you are looking for. So now let's--and one more time, three steps for

a quantum computer. First, prepare your quantum computer in a well-defined state like, let's

say, 000 and a bunch of qubits. Then manipulate the state using unitary transformations and

it will lead to some final state, psi F, and then you measure the state F and read out

the result. And that's how quantum computer works. So now let's see what you're kind of

probably waiting for, show us that the quantum computer does something more powerful than

a classical computer. So the first algorithm to illustrate is the so-called the Deutsch

Josza Algorithm. It's a very artificial example. It doesn't do anything beyond showing. Actually,

historically, it was the first example where it could show that quantum computer does something

faster with less clock cycles than a classical computer. So the problem goes as follows.

You have a so-called function F that goes from zero one to zero one. This function happens

to be called an oracle. So you have the oracle function F. And essentially, here's a little

table that shows there are only four possible functions. If you give it a binary variable

X which can be a zero or one, then this oracle function you have four realizations of it.

Two of them was a function that's constant, so whether the input is X or one, its output

is zero and here F0 and F3 are constant oracles and F1 and F2 are not constant or in this

context called balanced. So the think about it, classically, how many runs of the oracle

would you have to do in order to find out whether your function is constant or balanced

now then? >> Four?

>> NEVEN: Four? That's actually only two, you know? You apply your oracle to zero and

you apply oracle to one and then you can see which of the four functions it is. So classical,

two runs. But now shows that with the quantum algorithm, we can do with only one run. And

this works as follows; here's our gate model. We prepare two qubits, one in state zero and

one in state one. And we have some gates here, two types of gates, one is called the Hadamard

gate and one is called the oracle gate and they bring those qubits into new states. Actually,

we're ignoring what's happening down here. We are only interested in what happened to

the first qubit here, then we will measure it. And even though we present these two qubits

only once, we go through this algorithm only once; we nevertheless get to know whether

F, the oracle, is balanced or constant. And I will show this here. So first, I have to

explain you what a Hadamard oracle gate is. Again, those are just unitary operators acting

on qubits. So essentially, here the--you see how the Hadamard gate acts on a state zero.

Basically, these guys produce superpositions. It takes zero and brings it over to zero plus

one, and as the Hadamard gate acts on a state one, then you get to superposition zero minus

one. So we create superposition, and you saw earlier that it's helpful to have superpositions

because you push one superimposed state through your gates and the eight gates act on all

basis states. And then there's the oracle gate which you see we have put the F in there,

so essentially the oracle gate takes a qubit XY and brings it over to X and here on the

right side, you have Y, X or FX. So if you verify it, the oracle gate is a unitary operator

and we are not concerned at this point how we can physically realize it. And so let’s

assume because it's a unitary operator there's some physical realization for it. Whether

that’s easy or not, different story? So now, let's run it. We start with zero one,

we, let's say [INDISTINCT], so the Hadamard gates act on our state 01, and produce this

state. Then the oracle gate acts on those and you can just punch in those formulas and

you see you get this unwieldy expression here. Then I massage this a little bit and then

I get this expression here, sorry, like here, you see where the mouse is moving? And then

we ignore this portion here. We only look at the first qubit which is in this superposition

state. Actually I pull this out, this piece here, and then we apply a Hadamard gate one

more time, and then we get a state that's down here, that's the state for first qubit,

it's a superposition of zero and one which is here in the last line. And now, if you

take a closer look, you'll see in the exponent F of the value zero, X OR F of the value one.

And this X OR operation if you go back here, if you look at the truth table, this X OR

can only be--will be zero for the constant functions, and will be one for the balance

functions. And then if you, plug this in here, you see that if it's constant, then it’s

zero, then essentially the second term here disappears, and the output of my first qubit

will be zero, and if the function is balanced then this here will cancel itself out and

you get as a result, one. So, it’s either zero or one depending on whether the function

is balanced or not, and again, we have done this by only a single run.

>> Why is it important whether it's balanced or constant?

>> NEVEN: It's not necessarily important. It's a guinea pig problem. It's just an illustrative...

>> [INDISTINCT] possibilities of it’s own? >> NEVEN: Yes, this is just how the problem

is posed. As I have said, it's an artificial, very simple problem, has no application. So,

probably what you think now, "Oh, Hartman is doing a poor job here. This is, oh Jesus,

I mean I cannot get it. We used unitary functions and we go just work off the calculus and then

we get a result. But really, intuitively I don't quite get this." Actually this is part

of the lesson. The lesson is that, the gate model of quantum computing I personally also

don't find terribly intuitive and inventing new algorithms as a framework is not all that

easy. However, in the next lesson, we will talk about adiabatic quantum computing which

has a much nicer geometric meaning, where it’s much easier to design algorithms. It's

a question of taste. I think for people who have a good algebraic mind, they will come

up with good algorithms in this word, but sort of, it is--using the gate model is tricky.

And there are only a few known algorithms that do something useful in the gate model;

might have to do with the fact that it's a bit unwieldy. I'm only a few minutes left,

so we'll rush through the next example which is quantum search. And again, in posing the

problem is very similar. Again, we have an oracle function F but right now it's from

the binary space n dimension binary space to zero and one. Essentially what this function

does, it marks one item in the input space, let's call this item X zero, and it marks

it as one. And this function as zero for all other input possible input values and the

goal is to find X zero. So that's already more meaningful, you know, quantum search.

And, we will just study a very simple case, where we assume that N is two. So finding

one item marked out of four, this is what we would like to do. And in order to calculate

it, I assume that the marked item is--is 1-0, the binary number 1-0, okay? So, finding one

marked item out of a number is a quantum search, and it's solved--its called--solved this so

called Grover Algorithm. Again you have--here's this gate model where you have Hadamard gates,

you have this oracle gate again, you know these guys already. And then there's this

ugly big D-gate in there and if you look closer it gets even uglier, but it does something

very simple. So we will look at this in a second. Again, think about it classically;

if you want to find one marked item in N, then basically, you have not--any of the best

algorithm you cannot come up with will be of big O-N. Basically you have to look at

all your items. With the quantum algorithm you can do this in square root of N. And again,

as the proof of this, all it needs is you construct an oracle gate where again you put

your function F in there, and then you prepare your state, an initial state like 0-0-1, and

then we will go through this now only in a superficial way; we apply the Hadamard gates

that generate a superposition, then I evaluate my function by using the oracle gate, and

then I get the result here. So, in the, before last line, this one here, and you see, what

this did already, out of the four states, remember I have assumed that F marks the state

1-0, you can see after those massages, the state 1-0 is marked with a minus--Oh, I have

marked it already. But unfortunately I haven't marked it good enough because minus one; again

modulos square if you measure it, is the same as one. So I cannot really discriminate minus

one from one here as a pre-factor. So, what this ugly big D does is nothing but essentially

changing the phase factor into amplitude and what--if you apply D, what you get as a result

is the end result, 1-0, okay? And again, what you can show for a larger N, this algorithm

finds a marked item out of N with big O and square root of N. Okay. So here's the last

slide which is another famous quantum algorithm, Shor's Algorithm, this actually is a crowning

achievement so far. And what Shor's Algorithm does it finds the prime factors in a composite

integer. And you have, maybe read in the press about it--this is important because if you

can do this well, many cryptography codes are actually based on the fact that it's hard

to find the prime factors in a large integer. And the best known classical algorithm if

you have a number N is actually exponential in lock N, this more complex expression. And

Shor's Algorithm does the same thing getting, rid of the exponential. So it's essentially

an exponential speed up over what you can achieve classically. And rather than going

against your lengthy how this works is, maybe let's conclude with what's today believed;

it's not proven but it's believed that this is sort of how the complexity classes relate.

You're probably familiar with the class NP which is essentially a complexity class of

problems which I can verify, not solve, but verify in polynomial time. And this class

NP has of course a sub-class; these are the problems I can solve in polynomial time. And

then there are these nasty [INDISTINCT] NP complete problems. These are sort of the hardest

problems in the space. They are essentially characterized by the fact that any other problem

in NP can be mapped in polynomial time onto NP. And then this whole thing is embedded

in P space, this is the complexity class for all algorithms that have polynomial space

requirements. And then here is what we care for, BQP, Bounded Error Quantum Polynomial,

so these guys--he is factorizing. So essentially this class seem--is probably--is believed

to be larger than P but it doesn't necessarily cover NP. And that's also a lot of the controversy

and some of the misunderstandings, so you cannot say that a quantum computer solves

NP complete problems. And so, this is the overall lay of the land, summarizing the computational

gains, you get from a quantum computer over a classical computer. Okay, that was it for

the first session. You might have seen I realized, again, in one hour cramming all this material

and this is tough to follow but there's a lot of literature on quantum computing. You

can see in the talk announcements, there's a list on fish, you can link to this and maybe

I finished with the shameless plug what we going to do next time. Next time, we will

show the image recognition algorithms we have realized on an adiabatic quantum computer.

And the main topics will be decoherence theory, this essentially deals with how do superposition

states, you have seen superposition states were so crucial, but unfortunately they are

fragile. So decoherence is essentially is the process of the superposition state breaking

apart. So we need to understand this if you want to build quantum computers. Then, you

asked it earlier, we will look at the adiabatic quantum computing principle more, then we

will look at a special or hardware implementation of this, done by D-wave. Actually next week

I will be joined by Geordie Rose who is the CTO of D-Wave, and who has built this first

adiabatic quantum computing chip. And then we will show how we did image matching using

this chip, and then I want to conclude with some implications it has for machine learning

and I want--I haven't solved it yet, but I want to entice you looking at some machine

learning problems that I think we should map onto a quantum computer because it's what

yield huge gains for this field. Okay, thank you. That's it.

The first is about introduction to quantum computing. And actually what I'm trying to

do is to take an unusual look at quantum computing. We want to take a look from the vantage point

of synthetic intelligence. Essentially a notion I would like to promote is the idea that in

order to create artificial intelligence, and by this I mean, tasks like pattern matching,

machine learning, has a lot to gain from employing quantum computers. Actually what I would claim

is if you were to have a working quantum computer of sufficient size on your table today, the

business of doing, let's say a machine with a learning algorithm, would entirely change.

And since this has such dramatic effect you might want to know, "Okay, do I have to bother

or worry about quantum computing before I retire?" Actually is another thing I would

like to get across. Working quantum computers will may--are probably or may be only a few

short years out. Actually in the next talk, we would go as far as this computer here,

this little laptop, has actually a MATLAB program on it that ties via Webservice and

Java and Webservice into a quantum chip that is admittedly still small, but despite of

what you have maybe read in the blogs or popular press, this is a real quantum chip that exists

today. And actually what we have done with it is take a human level task, object recognition,

and build a pipeline, a mix of classical and quantum algorithms to break this task down,

map it unto the quantum chip and bring it all the way back. And I think this type of

task will--I have a feeling that quantum computing might be the missing link that brings true

human level intelligence to machines. So, [INDISTINCT] this--my idea are not very farfetched,

as so does the brain have anything to do with quantum computing? So actually today the answer

would be bluntly, no. Neurobiology as the current paradigm has it that in order to understand

higher brain function, all we need to look at is an organizational level above the single

neuron and beyond. So essentially looking at neurons as classical devices that cooperate

or compete with each other, bringing about the neuro-dynamics that this is all you need

to understand higher cognitive function. But something I would like to predict is that,

sort of the pipeline of the nature I have described before and our increased understanding

how we might harness quantum processes to perform meaningful computation, this paradigm

might get challenged or is ripe for review. So probably, quantum computing will inform

our search for the quantum box as John Ekards [ph] would call it. Okay. So, after this introduction

to the introduction, let me jump to the first part, the basics of quantum mechanics. Again,

the intended audience is computer scientists and I realize it's a tall order to bring the

base concepts of quantum mechanics across in less than an hour which normally is taught

within a semester. But, let me try. First, let's look at a few base experiments. And

I kind of assume that everybody of you knows to various degrees about quantum mechanics.

I'm sure you have seen something on TV or read a book. You're an educated audience.

So first thing, an experiment from which--which likely shows the property of nature from which

quantum mechanics got its name, the so called Stern-Gerlach Experiment. And how this works,

and I'll try to use the mouse instead of my hands. You have a little furnace out of which

silver atoms come. And silver atoms have a magnetic moment so you can think of it classically

as a little, sort of compass needle coming out of your furnace. And of course they are,

sort of randomly organized, so there's this cloud of little compass needles flowing out

of your furnace. And then there this big inhomogeneous magnet that pulls and pushes on these magnets

depending on their orientation. And then, what you would expect because it's random,

some get pulled up, some get pushed down but it's essentially a random mix. So what you

see here on a classical prediction, if you put a photo plate behind it, this elongated

patch is what you would expect to see. Now what you really find is you only see two patches.

So this is, if you would have a little compass would mean, if you look at it you will only--two

things, compass needle up or compass needle down. So this is contrary to our, sort of

microscopic experience, and shows sort of first fundamental effect or a fact. Physical

observables are quantized. So it's like money, it comes sort of, in the smallest denomination,

as you one cent of nature. Actually this is--typically this cent of nature is typically denoted by

h--hbar, the Planck constant. And this [INDISTINCT] observable, it's like quantized is true for

energy, for angular momentum, for many important physical observables. So first effect. But

this effect has an important impact on how we observe nature. So let's look at something

that physicists do all day long, speed measurement. Essentially you can think of a speed measurement

in the following way: I have a little radar gun here in my example, and you shoot little

photons towards a car to measure its speed. So if you think about it, really those photons

have momentum and they push the car a little bit. But you would agree, you will not get

away with the excuse saying, "Hey officer, I wasn't that fast. [INDISTINCT] really pushed

my car." The reason you won't get away with this excuse is obviously the momentum of the

photons is so small that it doesn't really affect the system on the observation. But

now assume we want to observe something microscopic. So the car gets smaller and smaller, and given

that nature is quantized, I cannot always--or I do not always have the luxury of having

a probe fine enough that it is much smaller than the system on the observation. Or a different

way of looking at it, if sort of your probes would get larger, and here in this example

you would shoot bowling balls at the car, then obviously this measurement will affect

the state of the system, yeah? And this is in the microscopic world generally true that,

"observation affects the state of the system," okay? Second important fact. The third important

fact, here's sort of the quintessential experiment in quantum mechanics, is the double-slit experiment.

I'm sure you have heard of it in various ways. Now think of it in the following way, there's

a light wave coming through the first screen here, screen one, and it spreads out, think

of it like a water wave and now you have thrown a stone into a lake that was calm before.

So this wave spreads out, reaches the second screen and then, sort of two waves, come out

from there. So it's like throwing two stones into a lake. And we all know that the effect

in sort of these waves interfere, they can be superimposed and you have constructive/destructive

interference. And it creates an interference pattern like shown here, these black and white

stripes. But now if you would take a closer look, essentially again realized by a photo

plate, and you look at this picture here on the right side, the abc, and we look, we--it

gives a photon stream, make it very weak so that only one photon per time unit comes through.

Then we see a build up like this, sort of, you get little impacts on the photo plate,

and essentially you get this wavy pattern here. So essentially what we see if you take

closer look, that this wave pattern only gives us a probability where we might find the impact

of a particle. And this is also called the wave particle duality. And you can do this

with photons, meaning with light, or you can do the same thing with electrons. And again,

you can do it even if only one electron at a time goes through the slits. So it interferes

with itself. So the important lesson here, in superposition, a sort of a fancy word of

this wavelike behavior is that you can superimpose the states. So superposition, again it worked

for electron and photons, is a general principle in nature. Those three important facts. So

here comes the big jump, I don't want you to go home without formulas. So the philosophy

of these talks will always be give some intuitions and then jump to the formulas and I cut out

the middle piece. So here's pretty much all quantum mechanics, the kind of we'll ever

need, or you can derive the rest from this one single sheet. So how does quantum mechanics

formalism describe nature? First, if you describe the system, you want to know what its state

is. So, its state is here denoted by psi and these funny brackets around psi and the so

called Dirac Notation. So, this is just a way how a quantum physicist denote a vector.

So psi is just a vector and the funny thing around is the vector sign. And the state of

a system lifts in a Hilbert space. A Hilbert space, essentially for all purposes you can

think of it as a linear vector space with a scalar product over it. It's a complex vector

space. And moreover, we wanted to norm of the state vector is 1. And we will see in

a second why this is. Okay, now we know what a state is in quantum mechanics. Next thing

you want to know; how does my state change? So how the temporal evolution--fancier word

for it--comes about is essentially in non-relativistic contacts through the so called Schrödinger

equation. You see, the Schrödinger equation is basically a differential equation that

shows his changes--the first derivation according to time of the change of your state dependent

on what’s here on the right side, and what's on the right side is called an operator acting

on the state and this operator is called the Hamiltonian. The Hamiltonian essentially has

to do with the overall energy that's in your system. So depending on how much energy is

in your system and how it's structured spacial temporally, the state will change in different

ways. And actually, there's an equivalent way of writing it. If you go here to the right

side, essentially here the Hamiltonian is put into evolution operator. So basically,

you have a state here, psi as in time to zero. Then you--evolution operator think as a black

box and now you push your state in at time T and then you get the state at time T out

of there. So, state and temporal evolution. Now, it's important to see the differential

equation here was linear, the states base is linear, so we have a linear theory. And

this allows for an important fact that in particular means, if I have two possible states,

psi 1 and psi 2, then any linear combination, for example, like psi 1 plus psi 2 is a solution

as well. So here you see the super position reflect it. So two states, I can superimpose

them and again I have a valid state. Now comes the third part, how do I measure the state?

And here in classical mechanics you wouldn't find much, you know, as the position of the

car, yes sure I measure the position of the car. So there's the state of the system and

what you observe is kind of the same thing. But earlier in the speed measurement example,

we discussed that in quantum mechanics this is more involved. So in quantum mechanics

you describe an observable, like energy, magnetic momentum, through a matrix your A, an operator,

and this operator self-adjoined which basically means it allows for a spectral decomposition

into eigenvalues of this nature, that where the eigenvalue is m as a possible measurement

outcomes. And because this operator is self-adjoined, it guarantees that those measurement outcomes

are real numbers. Remember, everything before was complex numbers and you don't really see

complex number too observable to nature. You only see real numbers. The fact that this

observable is described by self-adjoined operator ensures this. So basically--and it has a complete

basis. So the eigenfunctions of A are complete basis for the Hilbert space where the state

lives in. So you can express any state in a decomposition like this, as sum c i over

the difference states. So again, as a large linear com--super position of the individual

eigenstates of your operator under consideration. And then the probability of finding a measurement

outcome is essentially the modulus square of the coefficient in front of the eigenstate

where you find your system, okay? This is called the Boen rule. And after the measurement,

your system would be in state a i corresponding to what you measured, okay? So that's my--the

trickiest part to understand. Observable corresponds to self-adjoined operator meaning it has a

set of revalued eigenvalues. These are the possible measurement outcomes and essentially,

if you decompose a state the way it’s written here the Boen rule gives you the probability

of finding the system in a certain state. Okay. So the last part that traditionally

was not taught as an important fact is how do you compose two quantum systems? You have

one and you have a second. But you can imagine if you want to build a quantum computer this

will often happen that it would be built or composed out of subsystems. So subsystem composition

is actually not that difficult. What you do is you take two Hilbert spaces, H1 and H2,

and you form the outer product of those Hilbert spaces. So this is now the total space your

system lives in and then you can--and the simplest way, take a state out of--one of

those two spaces and, like here, it says psi, and then you take a second state out of the

second system and you build the outer product, the tensor product of these two vectors and

you get a new state. So these special states are called separable states. But again, we

can build super positions; we can put a sum in front of sub states and get what this so-called

entangled state. So just in case--so here's sort of an important off ramp, if you ever

have heard about the Einstein Prodosky Rosen South Experiment or about quantum teleportation,

the ingredient you need to do things like quantum teleportation are entangled states

and we're not going to explain those today just sort of, if you study literature this

is sort of the off ramp. You have to get to--you have to understand what an entangled state

is, then you can proceed understanding what is quantum teleportation is. Okay. So, wow,

this--might be a little bit too much on this one sheet. Let's try to break it down. I think

in the next slides it will, sort of--I see a lot of shocked faces. I hope, sort of applying

this a little bit will make things simpler. So let’s a look at a very simple situation,

let’s take what's called a potential well. We take a particle that's an electron and

we put it into a box and we don't want to let it out. And here's a classic analogue

would be, let's say you go into a hole or let's say you have a large bucket and you

put a basketball in there and it bounces around, in such a situation you want to look at. So

the Schrödinger equation for this situation is written up here, and again, you recognize

it here was the Hamiltonian we have to use in this. And the Hamiltonian was, sort of

associated with the total energy of the system and you might know if you have something like

a bouncing ball, you have essentially two types of energy, the kinetic energy, how fast

this ball is flying around, and the potential energy, how high is it above the ground. So

these two terms together make up the total energy of this particle. So here we have now

differential equation. At first glance for the non-mathematicians thinks, "Oh, damn it.

Looks difficult to solve," but from here on, it's only mathematics. And it's a little bit

simplified by the fact that because the potential doesn't change in time, the Hamiltonian is

time independent. And then this allows for a solution that's down here, where the main

thing I want you to look at, is that this solution is again, a linear superposition

of this states psi, and psi are the eigenstates to the Hamiltonian. So this is how you can

compose a general solution for your Schrödinger equation. And here let's look at a special

case where our potential, you know, is sort of infinitely large then what you see here,

you know, in your little box, the wave functions, was the name for those solutions, for different

eigenvalues E, different amount of energy your particle can have. So that is how they

look, you know, you little bend it like a parabola, wavy, sort of wave with a shorter

wavelengths. So these are solutions. So now, more interesting, let's go to a situation

where the box is not infinitely high, it's not an infinitely deep well but it’s only

finitely deep well. So this is here shown in the right side. So what you see here is

something very important and we get the first sense of how this can help us in computation.

You see that the wave functions don't go down to zero right away where the border of the

potential well is. Actually they--there is still a finite probability of finding your

particle outside of the well and this is called the tunnel effect. So then I could use it--imagine

it would not be in the well but just sort of a barrier. So essentially, a potential

well but with a thin barrier. So then this particle could escape there even though it

doesn't have enough energy to jump over the barrier, it goes through, hence tunnel effect.

So think of it, here's this basketball, denotes a situation classically. If this basketball,

if I throw it in, if it doesn't have enough kinetic energy at that point to jump over

this wall, it will never get out of this potential well. So now for--and this is for computer

science. Everybody of you who has worked let's say with optimization problems will know that

getting stuck in a local energy minimum is a major curse whenever you express your problem

as an energy optimization problem. So, I think you will have a taste for the fact, "Hey,

I have a new mechanism here to get out of a local minimum." And that's indeed an effect

that we will harness for computation. Actually, adiabatic quantum computers do basically this;

they help you finding the global minimum and then the energy function by exploiting the

tunnel effect. Okay. So, let's sort of go through this one more time. Again, we have

learned that a state of the quantum system described at T-zero by a state function psi

of a T-zero, and then we have essentially two ways how this state can change. The first

one is continuous severe unitary evolution or via the Schrodinger equation, sort of a

continuous change over time of your state. And then, some nasty physicist comes along

or any human and will do a measurement. And then, oops, after this measurement, sort of

I drastically disturb my state and I come out in this state a i one of the possible

measurement outcomes in my measurement. And then, from there on, if nobody interferes

again, it will continue to evolve again like a unitary evolution via the Schrodinger equation.

So, that's basically what's--was on the cheat sheet, but as--it's like an ugliness this

is, you wonder when does a measurement really occur? Shouldn't the measurement instrument--I

mean, those are part of reality, too. It's a box with some pointers and some iron and

cables; shouldn't this obey quantum mechanics as well and shouldn't it sort of, follow an

unitary evolution along Schrodinger equation also? So, what does really constitute a moment

where measurement happens? And as the original--so when quantum mechanics came up, the first

complete formulation, the Copenhagen formulation of quantum mechanics, unfortunately failed

to do--give a clear definition of what is a measurement. And this--and at least, in

two cases, you can imagine that this yields problematic or paradoxical results. One is

a closed system. So, you have a box and you have some things in there, like let's say,

decaying nucleus and a cat. And we saw that when the state evolves--actually, we didn't

show this, but the Schrodinger equation sort of likes your preposition. So, it takes a

clean state and sort of spreads it out and then creates those super-positions we saw

about. So, what does this then exactly mean for a cat when it's in a superimposed state,

in particular if we would just think of it as a cat that is alive or dead. So, I'm sure

you have heard about the Schrodinger paradox. In this situation, essentially a cat in the

box and no observer involved. And this essentially has to do with the fact that we don't have

a clear prescription of what a measurement is. And this leads us to--and this is a key

question when it comes to interpreting quantum mechanics. What constitutes a measurement?

And again, in 1927, when the Copenhagen interpretation was formulated, again, it unfortunately failed

to give a clear definition of what is a measurement. So--and in '32, for Von Neumann came and said,

"You know what, I do it much cleaner. I also treat the measurement apparatus as a quantum

mechanical object. And I use only quantum mechanics to describe the whole thing end-to-end;

essentially of my state, I have my measurement device and I have sort of an observer that

looks at it. And then I analyze it in those terms." And essentially, what you see and

you have a state here in a superposition, a general situation, then you bring it in

contact--please remember existing composition. You bring it in contact with the measurement

apparatus here--and let's say and the state ready and you also bring them in contact with

an observer, again, in state ready. And now, here is this little arrow. Arrow essentially

denotes Schrodinger evolution again. Then, what will happen? What Schrodinger equation

does, it will bring about--it's like a zipper. Anything that the state touches goes into

a superposition as well. So, as soon as the system we want to observe, which is in a superposition

gets in contact with the measurement device, causes the measurement device to go into a

superposition as well. And then even worse, if the observer looks at it, it will go into

superposition as well. So, this is contrary to our everyday experience. Let's say, here's

this water bottle, it seems to be only at one position. It's not in a superposition

of multiple states, and we rarely see somebody in a superposition between life and death.

So, essentially the Von Neumann program, depending on how you look at it, failed. Essentially,

the way out that Von Neumann suggested is to say the final wave function collapse so

that you get sharp real states measurement outcomes as we experience them, this only

occurs--this final measurement occurs in the observer's mind. And I just--so, what happened

at that point is that essentially the observer's mind becomes a primitive notion that is foundational

to constructing physical reality. And I'm just mentioning this. This was '32. So Von

Neumann is not a new age kind of guy, you know. He was a very--I mean, as you are really

familiar with his career. What I want to point out is that quantum mechanics by its very

nature is very suggestive of bringing, of giving the observer special status, you know.

And this will of course be very important in the third talk when we look at the brain

in quantum mechanics. So, the last way to deal with what constitutes a measurement and

a very radical one, but one that's very popular among people who do quantum computing is Hugh

Everett's many world interpretation. So, what he essentially said is essentially a very

beautiful and very symmetric idea of it. He’d say, "You know what? It's not only one measurement

that comes out. There are thousand possibilities. All possibilities will occur eventually. Just

they happen in different parallel universes, in different classical universes." So, in

this notion to give you a feeling for this, I tried to use this, a time-proven allegory

of Plato, where Plato discusses human perceptual abilities in a situation where you have a

fire and prisoners in the cave only watch sort of two-dimensional projections of really

a three-dimensional world. And he discusses their limitations and how--what--picture of

realities that would construct, you know. So, in the "Many Worlds" or maybe better called

"Many Minds Interpretation," is a similar situation. The wave function psi is this enormously

high-dimensional beast. And what we seem--and this is sort of reality. However, what we

perceive as reality are low-dimensional projections. So essentially, our classical world as we

see it in this view would be only a tiny sliver of the much richer reality. So, this is the

Many World/Many Minds Interpretation which from an epistemological--or sort of an internal

consistency view, if it is correct that quantum mechanics is a linear theory, then this is

probably the cleanest interpretation of quantum mechanics. Okay. So, these were the basics

of quantum mechanics. So, you can take a ten seconds breathing. And we go now to quantum

computing. How can we use this now to build better mousetraps for our trade? Let's quickly

review classical computing. I don't have--I think this audience doesn't need any explanation

what a Turing machine is as a model for computing. And you probably know that any Turing computable

function can essentially be brought into form, where you have a function f that goes from

a binary, an n dimensional binary space to an m dimensional binary space. And basically,

you have the option for a physical, logical realization. That's those gates like Ngates,

Orgates, Notgates. And basically a program on its lowest level can be broken down as

you have a bunch of zeros and ones. And then you push those through a set of gates. And

at the output side, you--essentially here in the space, and the n-dimensional binary

space you look at your result. And you also know that I don't really need all those gates.

Subsets are enough to construct everything like, for example, a FANOUT gate and a NAND

gate as a universal set of gate. So this is pretty much all you need to represent any

Turing computable function. And so this is essentially the gate model using logical gates

for classical computation. Now let’s look how this looks in quantum computing. Actually

very similar. You start with a state. Here, denoted 100. This is actually--I simplified

from [INDISTINCT] notation. I had explained what a composed system is using this tens

of product symbol. I sometimes leave it out and just concatenate the individual vectors

like this or just write a vector like this. So these are all just different ways of notation.

So the main story here is you start with a state and you push it into a gate--actually

in quantum mechanics, the way to think of a gate is just Schrödinger equation doing

its job for, let's say, a fraction of a second. Now, again--or as a way of saying it, you

have an evolution operator that acts for a finite time on the state and then you get

some result. It's a very analogous in a way to a classical computation. And now comes

the--a trick. Let's replace the state by a superposition state. And if I had, let's say,

three cubits acting here, you can, let's say, use a state like this and push it through

the gate. And the gate doesn't care. The gate again is represented by a unitary operator

that it doesn't care whether it got just sort of a single basis state or a superposition

state like this. It will do its same job. And hey, that's cool. So it was one gate operation.

I can act on all these guys with one clock cycle. And I need to do this more. So you

go make a more radical superposition and you realize if you had sort of in binary notation

and digits, then the number of basis states that you have available grows as two to the

power of N. In one clock cycle, you can act on two to the N basis states. Now, it's fun.

I think it's obvious that you can expect some computational gains from this. Unfortunately,

superposition states, as you make larger, they're fragile. They tend to break. This

is one of the engineering challenges and we'll discuss on the next talk how to keep this

decaying of superposition states at bay. We have some of the intuition phase. A different

way of understanding the power quantum computers is as follows. And I mentioned it earlier.

You know that many problems can be expressed as finding sort of the minimum in some objective

function, you know. Or if--in the physics context, if this would be some energy landscape,

I want to find the minimal point. And again, doing this--now this is some computationally

expensive proposition--and doing this with classical [INDISTINCT] like--probably familiar

with gradient descent or simulated annealing or genetic algorithms; they are essentially

all flavors of gradient descent and they're all bound in some way or the other to get

stuck in a local minimum because there's this fundamental limitation. But remember the tunneling

effect, this can help us in certain conditions to get out of this local minimum and find

the deepest. In some ways, the quantum mechanical particle can see, if you want to allow this

metaphor, where the lowest state is and has--you have--in a gradient descent approach essentially

gets its quantum boost that comes from tunneling. And this is the second model of quantum computing.

There was gate model we looked at earlier, the adiabatic quantum computing principle,

which I will show actually in the second talk. They're equivalent, the adiabatic quantum

computing. So thinking about quantum computing in this picture and the gate picture we looked

at before, so those are equivalent. >> MAN: Remind us what adiabatic means.

>> NEVEL: Adiabatic means slow. And I will--the next talk will be extensively about adiabatic

quantum computing. So we'll explain this why the term slow enters there. Last, intuition.

And I actually wanted to take this slide out initially and take it with a grain of salt.

But still, I find it a powerful metaphor. That's not too wrong. Let's put it like this.

If you--again you know that many problems can be posed in form of a decision tree. And

if you are sort of a person confronted with decisions, so you have a classical particle,

then finding, let's say where the longest branches in your decision tree. The way how

you go, you go down one branch and check its length and then you go back and to take the

next branch down. And we have all these different algorithms how to do this in a smart way.

But at the end of the day, you have to always try one branch and come back. A quantum mechanical

particle, again by virtue of exploiting super positions, has a much easier time sort of

grasping all possible states a system can be in and sort of explore this decision tree

in a much more economic way. So this is--again, with a grain of salt. But I gave you--the

two first intuitions were exact and this is sort of a little bit metaphorically speaking.

So, now again, jump in to the calculus. At first, introduce this qubit, which the name

suggests it's a quantum bit. It's a quantum generalization of a bit. And the--like sort

of the bit in classical computation, it's a simple two-level system you can think of.

Essentially it--we are in a Hilbert space that is isomorphic. Meaning it looks like

C2, C being the complex numbers. So basically, I have two states here denoted as zero and

one. These are two linearly independent states. And again, you have heard it again, super

proposition, super position, super position. We can have a general state psi, you using

a general linear superposition of these two base vectors. And then what you heard earlier

also was that a state vector needs to be normalized; meaning the norm of this vector, which is

shown here, needs to be one. Actually, I still owe you the explanation why this is--you heard

me talking several times about the Born Rule and how quantum mechanics, the calculus essentially

doesn't tell you exactly what's the outcome is, in general. It only gives you probabilities.

But in order to properly speak about probabilities and have a probability calculus, it just needs

to be normed. Then hence sort of—-quantum mechanical states need to be normalized so

that probability interpretation makes sense. And then there's one more thing. So actually,

when you look at the state, you would say, "Okay, my quantum bit basically is described

by a complex number alpha and the complex number beta." And, you know, each complex

number can be represented with two real numbers. You would say, "Okay, I get this qubit. It's

essentially equivalent to four real numbers." Not quite. Again, we had already one knocked

out of this equation here. It takes one of the four out. And there's actually a second

one that goes out and you cannot understand why. As we said earlier, all measurements

results are always modulus square of the coefficients in front of a state. So essentially a phase

factor whose modulus square is one just makes it to be multiplied by one, so it has no physical

meaning in the sense it wouldn't change you're measurement outcome. So you can take any quantum

state and multiply it by a phase factor of this form and your measurement predictions--that's

all what quantum mechanics does; gives you measurement predictions--wouldn't change.

So actually there's a second parameter that goes down to drain. So once we've realized

this, we can essentially express by doing some--bit of massaging and expressing the

complex numbers by angles. And you see that the general state--it's actually a general

qubit psi can be represented like this with two angles; theta and phi. And essentially

qubit hence can be visualized as a unit vector moving on a sphere. And this sphere is called

the Bloch Sphere. So maybe another thing to take away from here is that a qubit instead

of--is not an analogue nor a digital thing. It's something in between. Before it's measured,

the state itself is obviously an analogueue entity but when I measure it, I will only

get two outcomes, it's in state zero or one which is eminently digital. So this is something

beyond digital or analogue. It's not either or; it has properties of both. So, going to

the general gate model of quantum computing, I think you can already imagine how this goes.

Again, various--we looked at it already. It's just sort of repeat. Essentially, how it works,

you have--you prepare your state with--let's say you have a bunch of qubits here, those

of size, initial qubits and you have gates, single qubit gates or multi qubit gates. Again,

these are little evolution operators acting for some finite time and they massage your

qubits into some final state of your qubit and then you measure it and, hopefully, you

get the result you are looking for. So now let's--and one more time, three steps for

a quantum computer. First, prepare your quantum computer in a well-defined state like, let's

say, 000 and a bunch of qubits. Then manipulate the state using unitary transformations and

it will lead to some final state, psi F, and then you measure the state F and read out

the result. And that's how quantum computer works. So now let's see what you're kind of

probably waiting for, show us that the quantum computer does something more powerful than

a classical computer. So the first algorithm to illustrate is the so-called the Deutsch

Josza Algorithm. It's a very artificial example. It doesn't do anything beyond showing. Actually,

historically, it was the first example where it could show that quantum computer does something

faster with less clock cycles than a classical computer. So the problem goes as follows.

You have a so-called function F that goes from zero one to zero one. This function happens

to be called an oracle. So you have the oracle function F. And essentially, here's a little

table that shows there are only four possible functions. If you give it a binary variable

X which can be a zero or one, then this oracle function you have four realizations of it.

Two of them was a function that's constant, so whether the input is X or one, its output

is zero and here F0 and F3 are constant oracles and F1 and F2 are not constant or in this

context called balanced. So the think about it, classically, how many runs of the oracle

would you have to do in order to find out whether your function is constant or balanced

now then? >> Four?

>> NEVEN: Four? That's actually only two, you know? You apply your oracle to zero and

you apply oracle to one and then you can see which of the four functions it is. So classical,

two runs. But now shows that with the quantum algorithm, we can do with only one run. And

this works as follows; here's our gate model. We prepare two qubits, one in state zero and

one in state one. And we have some gates here, two types of gates, one is called the Hadamard

gate and one is called the oracle gate and they bring those qubits into new states. Actually,

we're ignoring what's happening down here. We are only interested in what happened to

the first qubit here, then we will measure it. And even though we present these two qubits

only once, we go through this algorithm only once; we nevertheless get to know whether

F, the oracle, is balanced or constant. And I will show this here. So first, I have to

explain you what a Hadamard oracle gate is. Again, those are just unitary operators acting

on qubits. So essentially, here the--you see how the Hadamard gate acts on a state zero.

Basically, these guys produce superpositions. It takes zero and brings it over to zero plus

one, and as the Hadamard gate acts on a state one, then you get to superposition zero minus

one. So we create superposition, and you saw earlier that it's helpful to have superpositions

because you push one superimposed state through your gates and the eight gates act on all

basis states. And then there's the oracle gate which you see we have put the F in there,

so essentially the oracle gate takes a qubit XY and brings it over to X and here on the

right side, you have Y, X or FX. So if you verify it, the oracle gate is a unitary operator

and we are not concerned at this point how we can physically realize it. And so let’s

assume because it's a unitary operator there's some physical realization for it. Whether

that’s easy or not, different story? So now, let's run it. We start with zero one,

we, let's say [INDISTINCT], so the Hadamard gates act on our state 01, and produce this

state. Then the oracle gate acts on those and you can just punch in those formulas and

you see you get this unwieldy expression here. Then I massage this a little bit and then

I get this expression here, sorry, like here, you see where the mouse is moving? And then

we ignore this portion here. We only look at the first qubit which is in this superposition

state. Actually I pull this out, this piece here, and then we apply a Hadamard gate one

more time, and then we get a state that's down here, that's the state for first qubit,

it's a superposition of zero and one which is here in the last line. And now, if you

take a closer look, you'll see in the exponent F of the value zero, X OR F of the value one.

And this X OR operation if you go back here, if you look at the truth table, this X OR

can only be--will be zero for the constant functions, and will be one for the balance

functions. And then if you, plug this in here, you see that if it's constant, then it’s

zero, then essentially the second term here disappears, and the output of my first qubit

will be zero, and if the function is balanced then this here will cancel itself out and

you get as a result, one. So, it’s either zero or one depending on whether the function

is balanced or not, and again, we have done this by only a single run.

>> Why is it important whether it's balanced or constant?

>> NEVEN: It's not necessarily important. It's a guinea pig problem. It's just an illustrative...

>> [INDISTINCT] possibilities of it’s own? >> NEVEN: Yes, this is just how the problem

is posed. As I have said, it's an artificial, very simple problem, has no application. So,

probably what you think now, "Oh, Hartman is doing a poor job here. This is, oh Jesus,

I mean I cannot get it. We used unitary functions and we go just work off the calculus and then

we get a result. But really, intuitively I don't quite get this." Actually this is part

of the lesson. The lesson is that, the gate model of quantum computing I personally also

don't find terribly intuitive and inventing new algorithms as a framework is not all that

easy. However, in the next lesson, we will talk about adiabatic quantum computing which

has a much nicer geometric meaning, where it’s much easier to design algorithms. It's

a question of taste. I think for people who have a good algebraic mind, they will come

up with good algorithms in this word, but sort of, it is--using the gate model is tricky.

And there are only a few known algorithms that do something useful in the gate model;

might have to do with the fact that it's a bit unwieldy. I'm only a few minutes left,

so we'll rush through the next example which is quantum search. And again, in posing the

problem is very similar. Again, we have an oracle function F but right now it's from

the binary space n dimension binary space to zero and one. Essentially what this function

does, it marks one item in the input space, let's call this item X zero, and it marks

it as one. And this function as zero for all other input possible input values and the

goal is to find X zero. So that's already more meaningful, you know, quantum search.

And, we will just study a very simple case, where we assume that N is two. So finding

one item marked out of four, this is what we would like to do. And in order to calculate

it, I assume that the marked item is--is 1-0, the binary number 1-0, okay? So, finding one

marked item out of a number is a quantum search, and it's solved--its called--solved this so

called Grover Algorithm. Again you have--here's this gate model where you have Hadamard gates,

you have this oracle gate again, you know these guys already. And then there's this

ugly big D-gate in there and if you look closer it gets even uglier, but it does something

very simple. So we will look at this in a second. Again, think about it classically;

if you want to find one marked item in N, then basically, you have not--any of the best

algorithm you cannot come up with will be of big O-N. Basically you have to look at

all your items. With the quantum algorithm you can do this in square root of N. And again,

as the proof of this, all it needs is you construct an oracle gate where again you put

your function F in there, and then you prepare your state, an initial state like 0-0-1, and

then we will go through this now only in a superficial way; we apply the Hadamard gates

that generate a superposition, then I evaluate my function by using the oracle gate, and

then I get the result here. So, in the, before last line, this one here, and you see, what

this did already, out of the four states, remember I have assumed that F marks the state

1-0, you can see after those massages, the state 1-0 is marked with a minus--Oh, I have

marked it already. But unfortunately I haven't marked it good enough because minus one; again

modulos square if you measure it, is the same as one. So I cannot really discriminate minus

one from one here as a pre-factor. So, what this ugly big D does is nothing but essentially

changing the phase factor into amplitude and what--if you apply D, what you get as a result

is the end result, 1-0, okay? And again, what you can show for a larger N, this algorithm

finds a marked item out of N with big O and square root of N. Okay. So here's the last

slide which is another famous quantum algorithm, Shor's Algorithm, this actually is a crowning

achievement so far. And what Shor's Algorithm does it finds the prime factors in a composite

integer. And you have, maybe read in the press about it--this is important because if you

can do this well, many cryptography codes are actually based on the fact that it's hard

to find the prime factors in a large integer. And the best known classical algorithm if

you have a number N is actually exponential in lock N, this more complex expression. And

Shor's Algorithm does the same thing getting, rid of the exponential. So it's essentially

an exponential speed up over what you can achieve classically. And rather than going

against your lengthy how this works is, maybe let's conclude with what's today believed;

it's not proven but it's believed that this is sort of how the complexity classes relate.

You're probably familiar with the class NP which is essentially a complexity class of

problems which I can verify, not solve, but verify in polynomial time. And this class

NP has of course a sub-class; these are the problems I can solve in polynomial time. And

then there are these nasty [INDISTINCT] NP complete problems. These are sort of the hardest

problems in the space. They are essentially characterized by the fact that any other problem

in NP can be mapped in polynomial time onto NP. And then this whole thing is embedded

in P space, this is the complexity class for all algorithms that have polynomial space

requirements. And then here is what we care for, BQP, Bounded Error Quantum Polynomial,

so these guys--he is factorizing. So essentially this class seem--is probably--is believed

to be larger than P but it doesn't necessarily cover NP. And that's also a lot of the controversy

and some of the misunderstandings, so you cannot say that a quantum computer solves

NP complete problems. And so, this is the overall lay of the land, summarizing the computational

gains, you get from a quantum computer over a classical computer. Okay, that was it for

the first session. You might have seen I realized, again, in one hour cramming all this material

and this is tough to follow but there's a lot of literature on quantum computing. You

can see in the talk announcements, there's a list on fish, you can link to this and maybe

I finished with the shameless plug what we going to do next time. Next time, we will

show the image recognition algorithms we have realized on an adiabatic quantum computer.

And the main topics will be decoherence theory, this essentially deals with how do superposition

states, you have seen superposition states were so crucial, but unfortunately they are

fragile. So decoherence is essentially is the process of the superposition state breaking

apart. So we need to understand this if you want to build quantum computers. Then, you

asked it earlier, we will look at the adiabatic quantum computing principle more, then we

will look at a special or hardware implementation of this, done by D-wave. Actually next week

I will be joined by Geordie Rose who is the CTO of D-Wave, and who has built this first

adiabatic quantum computing chip. And then we will show how we did image matching using

this chip, and then I want to conclude with some implications it has for machine learning

and I want--I haven't solved it yet, but I want to entice you looking at some machine

learning problems that I think we should map onto a quantum computer because it's what

yield huge gains for this field. Okay, thank you. That's it.