# Quantum Computing Day 1: Introduction to Quantum Computing

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

Woops, I meant to vote up, but my mouse slipped and I voted down 🙁

I agree, MOAR!

Says the guy with the name Family Guy

ty you very much for helping me understand

at least a little bit anyway

at least a littlt bit anyway

I'm on my way to get that degree, and I'm FASCINATED!!

wow, my physics proff tried to teach me all this today… good times good times

good thing he brought his sunglasses

wow.. Arnold is very smart xD

Quantum Mechanics seems to hold it's cards close to it's chest. "wait you peeked ha,ha now I'm a particle"I love this stuff.

They exist….made of 5 or 7 atoms…im not sure…

7 atoms tottal

Im completely lost..Its just too hard. Better leave it to the smart ppl. LOL

I'm no good at physics and such but the concept of quantum computers fascinates me greatly.

Am I wrong in assuming that he's trying to explain the Heissenburg Uncertainty Principle effects measurement & thus causes infinite outcomes at the quantum level?

Жаль не на русском. Тяжело такое воспринимать на англ

)) :))))))))))))))))))

he's german, not eastern european

Could it be that the speaker is german?

lost me at 11:00 🙁

based on his name Hartmut and his accent I'd guess so, too ^^

needs to be higher quality

This is excellent.

Nonclassical physics is just a scam to try and bring antideterminist creationist nonsense into science. Why do we spend money on physics research? All physics research does is give us new ways to destroy the planet and oppress womena and minorities. We need to spend more money on research for evolutionary biology so we can learn more about ourselves and our flaws so we can hopefully learn to live in peace and to care about each other.

Because physics is the science upon which biology and chemistry are based, and is the science that is the most interesting.

i was literally trying to create a topology today: physics > chemistry > biology but it seemed that somewhere i needed to make a bigger table.

software engineers are professionals in any field in which they need to create an application. their greatest talent is learning. dumbass. and physics isnt that advanced. sorry.

I'm actually a computer scientist, most engineers have to be computer scientists. IT is something else, more like guys checking your cables and installing Oss. I find it boring and redundant. Electronic engineers make the hardware and software engineers in concert with them create the layers of interface that make up software topology. application programmers then utilize these layers in every field to come out with the software that each has become so reliant upon.

Software "engineers" as you call them are not maintainers. They are essentially higher level system designers. Granted a software "engineer" will not do much coding however they perform as important job as coders and the other computer scientists who work on developing individual algorithms, they coordinate the design and implementation of a computer system. Without them there would be almost no complex computer systems, at least not any that work correctly (not that many work right anyway) 🙂

I have a part time job as a programmer and my experience has been all but what you say. Every bit of knowledge helps you do your job better. Software Engineers DO work on problems that require an understanding of CS theory such as algorithm design and analysis. You are generalizing the Job of a systems administrator with that of a programmer. A software Engineer can certainly work in both positions.

I used to think I was intelligent but then I was introduced to quantum mechanics.

part2themovie

will learning mathematics help me in becoming a computer scientist ?please reply

At 09:47 into the talk, he shows a slide with the title/subtitle:

"Quantum Mechanics Formalism"/"Quantum Mechanics Cheat Sheet"

I can't read it. Anybody know where to find a copy?

@treeandplant computers are all matematics

one of the missin links

If you think about it, its impossible to reach Human-level intelligence because it is impossible to determine if something is actually thinking. The only thing you know that is thinking is yourself.

what if every basic thought could be defined mathematically/electromagnetically and then a new form of programming and engineering could derive from that

Think of the underlying law of nature. The way of all things.

Consider its astounding inferences and implications.

The single, underlying law … of nature! Not merely of physics, chemistry, psychology, biology, etc., but of all known fields of inquiry. The law we can all relate to, identify, understand and apply.

Ask yourself. What is the underlying law of nature?

Delight in the question. Have fun in the process of finding the answer firsthand for yourself.

Google it, as a start.

i've got me a quantum computer right here, it uses the pauli exclusion principle to affect the condutivity of silicon wafers,

i'm thinking of putting together some technoballble in order to get a huge physics grant

Where is it possible to find the presentation slides used in this video?

Thanks in advance.

I think he gets to the point around minute 30…

It's not computer engineering, its all quantum physics. Once you get into Schrodinger cat and Hindenburg uncertainty. you'll start to understand the difficulties and power

@ericharris666 "Hindenburg uncertainty"? Is that where you can't know both the exact position and the exact velocity of an enormous burning German airship?

@MrBurstingfoam Precisely, 😛

Oh my.. please learn speaking englisch without accent… I can't listen to this =/

Google needs to re-upload these videos in HD.

Not being able to see the equations behind the theory puts a damper on any understanding.

@vality1 ask your brain 🙂

@vality1

A computer is only ever as intelligent as it's creator.

Humans can think and make judgements, so in the future, it is inevitable that computers will have evolved to this level as well.

Fascinating stuff.

@ObserversParadox yo mama

@ObserversParadox

"A computer is only ever as intelligent as it's creator."

That's a claim, proof please.

@DasKrabbe Computers can't be more intelligent then humans because we program them to learn in the same way that we ourselves learn as humans. Therefore their 'virtual capacity for thought' will never exceed our own as long as they are programmed by us. If they were programmed by monkeys, then the computer would only be as intelligent as the monkeys mental capacity allows it to be due to the monkeys limited intelligence. This is not proof, but it is my logic, so think about it yourself.

@ObserversParadox

Computers clearly already exceed us in several areas, such as chess, which seems to contradict that, no?

@MrBurstingfoam Probably he mixed up Schrodingers Cat there… you know, where you don't know if the airship has blown up yet or not and you can't look because then it goes boom.

@DasKrabbe

It depends how you define intelligence.

If intelligence is being able to run through each of chess's possible manoeuvres and calculating the risk factor associated with each move.. then you are right.

But what you may have missed is that humans can do this also.. just not as fast.

So if intelligence is the speed at which your brain runs then you are correct. But humans programmed computers to perform all of their functions, so they may be faster, but they only do what we tell them.

This guy is definately knowledgeable about Quantum Mechanics, but this presentation is pretty terrible. He's got a million equations on a Powerpoint slide and he explains stuff in such a way that you have basically have to be a physicist to know what's going on. His target audience is suppose to be people without background in quantum physics so he should have boil it down to very simple examples that can relate to in real life.

@fewpeople The problem with quantum mechanics is that nothing in QM has any "real-life" equivalent. Even the best physicists have "wait, what?" days where what they "understand" one day confuses the next. Like Feynman said, until you can explain it to a 10-year-old, you don't understand it, and right now nobody really understands QM in such a deep way. We can do the math, but we can't intuit outcomes.

@AbeChang2 this is a very late reply but o well ….. they all rely on each other !

@AlephAlephNull It's not only due to the counter intuitive nature of quantum mechanics, I've studied it for about a year now and somthing that strikes me is how terrible lecturers can be. I myself know how incredibly hard it is to explain something like this to someone who hasn't studied it. My grandma asked me about a math exam not too long ago and what it actually was about. I didn't get passed the second sentence until she asked "what is algebra?". Explaining this in laymans terms is not easy

@wolvie90 Although I agree explaining to the layman is difficult, the problem is usually when we don't have a deep enough knowledge of the tools we use, for example. An expert in algebra would easily be able to give an explanation that, while not deep, would give your grandma a decent grasp of the concept. QM doesn't have anyone, that I've seen, that can give a layman any idea of what's going on. Hard enough to give understanding to 3rd year phys students.

@ObserversParadox – (part 1) "Computers can't be more intelligent then humans", "It depends how you define intelligence." How about if intelligence has to do with awareness of relevant facts in the process of problem solving within a limited amount of time? The recent Jeopardy/Watson challenge (/watch?v=dr7IxQeXr7g) shows that awareness (quick access and assessment of relevant facts) is a great advantage. Speed has A LOT to do with "how intelligent", even among humans, thus TIMED IQ tests..

@ObserversParadox – (p2) The IBM Blue Brain project (/watch?v=8iDR8Z-e_GU) is working towards emulating a tiny part of a rat's brain. In the US, a full cat's brain. Still others, the human brain. They are all proceeding on a fundamental/modularity approach where any of the fundamentals or module-level components can be experimented with to create many "intelligence" paradigms. These coupled with quantum computers will be well beyond the awareness and intelligence of total humanity in < 100 yrs.

@MrTeaB – A Q computer by itself? No. However, imagine a hybrid (binary/quantum) computer 100 years from now. The conventional (binary) side will be literally HUNDREDS OF THOUSANDS of times faster than today's fastest supercomputer. It alone would whip a Go grandmaster silly. I'll even predict that a conventional computer (at least 100 times today's best) will do so using Chess like algorithms in about 10 to 20 years. In 50 to 100 years, hybrids will be playing games beyond human comprehension.

Lol @ the guy at 47:12… He clearly was not paying much attention.

Quantum computer will be so powerful that it can predict the future >:3

so you only have to send 1 bit through the processor and it runs on all your super positioned bits still in ram ?

did me good! Had been studying the basic quantum mechanics and encountered fascinating terms related to quantum computing frequently..the three days of these talks left me better..

ppt slides available somewhere?

Poor quality lecture. Would have thought that Google could present these topics better.

Definitely not the best introduction…

It's the Heisenberg uncertainty principle, not Hindenburg.

Contrary to some of the other negative comments, I thought this was pretty good. I didn't follow the details of the algorithms he showed at the end, esp. without being able to see the equations. But I understood the idea of that well enough, and overall I thought he covered the ideas well.

can you FEEL the difficulty and POWER of HINDENBURG UNCERTAINTY?!??!!?….

HINDENBURG UNCERTAINTY: THE ONLY CERTAINTY IS THE CERTAINTY OF DISASTER!

You just don't get it Mr. Foam. it's all about the Hindenburg Uncertainty Principle. It's an extremely esoteric physical phenomena, with it's roots in Combusting German Airboat Theory… It describes a lowest limit for German Blimp Navigation and it includes all the major phenomena, and incorporates new and previously incompatible ideas… such as.. Quantized Gravity + weak + strong forces + relativistic revisions of quantum mechanics + the CBF (i.e. Combusting Blimp Force). A complete theory

lol it would've been more helpful if I could see the formulas 😀

haha, is this some kind of joke or are you trying to be serious 🙂

Heisenberg uncertainty. But still. Lawl

You could look them up, or just take a course on the subject. It's not like this information isn't available elsewhere.

So at the end he provides a link to a curated list of literature on Quantum Computing, which I assume all Google employees can access. How are us self learners supposed to access those resources?

Now this is interesting! Good talk!

Could somebody please tell me whats on the slide at 33:01?

31:35

Is it precisely true that a quantum gate job is just to evolve the wave function?

I know it is true. However, how to do such gate in the physics context? or how does a gate works in the physics' sense?

I agree to tearms

I would like To work for google but they never answer there phones

Hey Hartmut Neven!!! Let’s build an atomic computer!!!

He sounds nervous as fuck and really shoudn't have given his presentation in English.

anyone here from 2019?