>>Welcome to Quantum Computing

for Computer Scientists. Happy Valentine’s Day. We will learn about

this most romantic of all subjects, Quantum Computing. This is a talk aimed

at Computer Scientists. We will not go over very much, if any, physics

during this talk. We won’t go like

for the Double-Slit Experiment or

Uncertainty Principle. We’re not learning

about any of that. We’re going to cover

the Computation Model which you’ll all be finding, fairly intuitive I think,

is a state machine. And we will run

a Quantum Algorithm on it, show that it outperforms

a classical Computation Model, and then we’ll end

with some demos, including a running program in Q-sharp, Microsoft’s

quantum language. This is the Gate Quantum

Computation Model. It looks a lot

like the classical Computation Model

where you have bits, and you send them

through the logic gates, and transformations

are applied to them. There’s another

Computation Model called the Quantum Annealing Model which is used by D-Wave,

if you’ve heard of that. That’s something

different from what we’ll be going over but people think they

might be equivalent. The jury is still out on that. Anyway, I’m sure you’ll

have a great time. So, I’m sure all of you have your reasons for being

here but here are three reasons I’ve come

up with if you need some additional convincing why you should learn

Quantum Computing. The first is that

quantum supremacy is expected this year,

this very year. Quantum supremacy means we have a real problem running on a real quantum computer

which in real-time, runs faster than

the same problem on a classical computer. So, Google has announced they think they’ll

do it this year. If they do, it’s

a really big thing. So, it might be in

your future. Who knows? Five, 10 years, we

could all be running some really tricky problems

on quantum computers. So, we have lots

of large companies, Microsoft, Google, Intel, IBM, they’re all investing

billions of dollars in quantum computer

developments. There are lots of

really exciting applications. This is the one that everyone’s heard about, Shor’s algorithm. When this paper came out,

it lit the world on fire. People were like, “Wow,

quantum computers could actually have real

economic impact.” We could factor RSA, and undermine our

global financial system, which is pretty cool. Here’s one that

programmers will I think appreciate which is we can search an unordered list

in square root N time. So, you think for

an unordered list, you have to check

every element. That’s ON. You can just get

a nice speed-up, just square root n queries

on a quantum computer, which is pretty, pretty

nifty, generally useful. And here’s the one

which, I think, probably is the best probability

of changing the world. Sorry, Programmers scroll and search probably won’t

[inaudible] too much. Which is, we might

be able to have an exponential speed-up in simulating quantum

mechanical systems. So, things like drug design, if you simulate like

biological molecules interacting, things like that, it could massively speed up a lot of our

biological research, and everyone talks about

nitrogen fixation for this. That’s like part of

the main Microsoft sales pitch. But this is the one that actually motivated

me, the bottom one, which it’s, I think, from talking to couple of

you before the presentation, we can also motivate you. It’s intellectually

interesting, and it’s interesting because it’s just kind of outside my intuition. Like I think all of us, at

this point in our careers, can basically look at any

digital or mechanical system, and have like a ballpark idea

of how it works, right? But if you look at

a quantum computer, like how can a quantum computer outperform classical

computation? It doesn’t make any sense. Like there’s no way I could even start to

guess how it would work. And so, I really

wanted to learn it. And I think there’s a reason

for this, and this is kind of getting

a bit philosophical. But our language, our informal

language that we use developed in

very classical world. It is simply not equipped to

deal with the quantum world, and this is why

any pop science article you’ve read on

quantum phenomena, it doesn’t really ring true. All the metaphors,

they don’t really make sense because we’re trying to express it in

this language which is developed in

the classical world. We need to learn a new language which is

the language of mathematics, and that is the only thing

which will actually let us understand quantum mechanics is to learn it mathematically. All metaphors and analogies

will lead you astray. There’s a famous quote

here by a physicist named David Mermin which

is “Shut up and calculate”, with regard to

quantum mechanics. So, some grad students, maybe they lean back

in their chair and they’re like, “Oh, what

does this all mean?” Shut up and calculate.

Just trust the math. Math is the only thing which

will not lead you astray. Okay, here’s how this

presentation will break down. First, we’re going

to learn how to represent computation using

super basic linear algebra, matrices, vectors,

matrix multiplication. Then we will generalize

that to learn about Qubits, superposition, and

quantum logic gates. And finally, we will use

all those tools we’ve developed to go over the simplest problem where quantum computer

outperforms a classical computer. This is called the

Deutsche Oracle problem. I mean, there are

a bunch of problems, but this is the simplest. And finally, it’ll be almost

negligent to let you get out of here without learning

about Quantum Entanglement and Teleportation just because

with the tools we’ll develop, they’re so easy to understand. So, I’ll have bonus topics, and then we’ll have some demos. All right, let’s get to it. You’ll become very, very

familiar with these two vectors. This is how we

represent a 0 and a 1, the two values of one bit

in classical terms. So, the top one, it’s just 1 over 0, and

the bottom one is just 0 over 1. You can also write them in that weird angle bracket thing. That’s called

Dirac Vector Notation. So, you have a zero

in there. That means this is the value

of that vector. If you have trouble

remembering this, just think of it like

an array indexed from 0, and so, there’s a 1 in the 0th index,

that means it’s a zero. There’s a 1 in the first index,

that means it’s a 1. Okay, everyone’s fine with this? You’ll be very

familiar with this by the end of the presentation. We’re going to go over matrix multiplication

really quickly. So, the way to think about

matrix multiplication, just to review for you. Most of you will have

gone over this in your Linear Algebra courses

the first or second day. So, if we have a matrix

multiplied by a vector, you kind of take

this horizontal row, and then flip it,

and multiply it point-wise with

these vector values. So, a times x, b times y, and that’s how

you get the top one. And you do the same thing

in the bottom row. C times x, d times y, and you get a two vector. The same thing happens

with three-by-three matrix. A times x, b times y, c times z, and you

get this matrix. This vector, you can also

multiply matrices together. We won’t really be

doing much of that. And there’s a very

special matrix called the Identity Matrix which

has zeros everywhere, except for ones along

the main diagonal, and anything multiplied by

the Identity Matrix is itself. It’s just like multiplying by 1. In fact, usually, you refer to the Identity Matrix

by the symbol 1. Now thankfully, for simplicity, a lot of the matrices we’ll be using look a lot like this. They’re mostly 0s

with just some 1s, and you can notice, it’s

a nice rule of thumb, that relative to

the identity matrix, this matrix has the middle

two rows flipped, okay? And that’s actually

the action it has on anything it multiplies. So, it flips

the middle two rows. It’s a nice sort

of rule of thumb to remember how

matrix multiplication works. Does anyone have

any trouble with this? Because you really need to know this in order to go ahead. You got to know it. Okay, great. Operations are actually, I’d

like to make this a quiz. Can anyone tell me what are the four operations on

one bit? There’s four of them.>>One bit.>>One bit.>>AND, OR, exclusive-or.>>That’s around two bits.>>Not identity.>>Identity not.>>Set to 0, set to 1.>>Set 0, set 1. There we go. Good. Yes. So, we have identity, just f of x equals x. Negation fx equals not x. Constant-0, it’s

always set to 0. Constant-1, it’s

always set to 1. You can see with a diagram

how it kind of looks, okay? And we can write

these as matrices. So, the identity is

just the Identity Matrix. This, remember, is

our symbol for zero. Identity multiplied by 0 is 0. Identity multiplied by 1 is 1. Here’s negation. You flip

it from 0 to 1, and 1 to 0. Same thing for

constant-0, constant-1. So, I hope I’ve

convinced you we can represent very simple

functions at least, with matrices multiplied by

our 0 and 1 vectors, okay? And remember

these four functions because I will quiz

you later on them. They’ll come back up. So, let’s talk about Reversible Computing. Reversible Computing is

a neat sort of buzzword. It if you’ve read the popular

sci-fi book Accelerando, it talks about

Reversible Computing, and basically it means

that if I tell you the operation I did and

the output of that operation, you can always tell

the input of that operation, if the operation’s reversible. So intuitively, operations

that just shuffle bits around, like permute them,

they are reversible. But operations that erase bits and then overwrite

them are not reversible. And in our previous slide, identity and negation are both reversible because I

say the output is one, and I put it through

the negation gate. That means the input was zero.

You can always tell that. But if I say the output was 1, and I put it through

the constant-1 operation, you can’t tell

what the input was. It’s not reversible.

It erases information. And the nice thing

about Quantum Computing, which you’re going to remember, is that one of the computers only use

reversible operations. Those are the only ones

we care about. So, the only operation we actually care about on

this slide is really negation. Like also identity but it’s

the same as doing nothing. A further fun fact about

chronic computers is they actually only use operations which are

their own inverses. So, not only are they

reversible but if you apply them twice you’ll just get

back the same input value. And we’re going

to go in a little, this is kind of like going

into pop science but whatever. There’s something called

the Von Neumann Vander Limit, which is the smallest amount of energy physicists

have calculated is necessary for the simplest

possible calculation, which raises is non-reversible. And reversible computing might eventually lead us

go beyond that limit, more efficient than

that theoretical limit. Now, currently, processors needs millions of times more energy than the Von Neumann

Vander Limit but, you know, 5,000 years

from now, who knows? Pretty nifty. All right. This is something you

probably did not go over in linear algebra but don’t worry

it’s still pretty simple. It’s called the tensor product. So if you have the tensor

product of two vectors, it’s kind of like you take

the second vector and you tile it for each element

in the first vector. So, X0 gets its own copy

and X1 gets its own copy. And then, you multiply it

out so you get eventually X0, Y0, X0, Y1, et cetera. It’s maybe easier to look

at this with real numbers. Here we have one times three, one times four, two times three, and two times four to get this. Here’s how it looks

like with three vectors. You get this like giant array. Don’t worry about it too much. And I’d like to point out that if we use R0 and one values you end up with a vector which has a one in

only a single position. Okay. Does anyone have any real trouble

with this concept? If I gave you

two vectors you could probably calculate

the tensor product. It’s not entirely

difficult. All right. But, the final point

animate leads into how do we represent

multiple classical bits? And we represent them

by their tensor product. So, 00 remember we tensor,

this is a zero symbol. 0 tensor with 0 is this, product state, we call it, 01 is this product state

10 is this product state, like 0 times 1, 0, 0 time 0, 0, 1 time 1, 1. One times 0, 0. Okay. And 11 is this product state

and similar to just a single bit

you can think of this is an index in

this vector array. So, this is 0. There’s a one at the zero position.

This is one. There’s value with

the first position coming from zero and, this is two value of

the second position, three value of

the third position. This is the only time

I will tenser three bits together thankfully,

because they us humus. They grow exponentially in

size but it works for this. So, four is 100 you have

01234 is where the one bit is. Okay. Yeah. So, we call

this the product state. We can always factor it out into its individual states and the product state of n bits is a vector of size

of two to the n. Here, we see a sort of whisper of the power of

quantum computing in this exponential term but hold that thought,

we’ll get back to it. So, we’re going to learn

a very important operation, very fundamental to reversible computing

and quantum computing is called CNOT or

conditional not. It operates on a pair of bits. You designate one bit, the control, bit the other bit

is the target bit. So, the control bit if it’s

one it flips the target bit. If it’s zero it

leaves the target bit alone and the control bit

is always left alone. So, if we have

the most significant bit of a 2-bit system as control, the least significant

bit is target, then 00 since this is

the most significant bit, it’s the target bit, and just

goes to 00, 01 goes to 01. Now, 10, since

the control bit is one maps to 11 because

it flips the other bit, and 11 since it again flips, the target bit goes to 10. And this matrix, you can

actually kind of write it, you see there’s a sort

of correspondence here we flip

the bottom two rows, which is the identity matrix, and this I claim which I will show in

the next couple slides, will change our product states according to

the semantics of CNOT. So, does everyone get

the semantics here? We have a control bit

and a target bit, control bit one, we flipped

the other bit. Pretty good? Now, this is a lot of math but don’t panic we’re

gonna go over step-by-step. If we apply the CNOT gate to 10, remember that this is

the control bits one, so we’re going to

flip the other bits, so we expect it to go to 11. Now, let’s expand this

out just step-by-step. So,10 corresponds to

this tensor product. This is the matrix

from the previous slide and we’re applying it

to our product state. Remember, it’s

just going to flip the bottom two rows so we

get to this product state, which when we factor it out, indeed gets us 11. Now, let’s do it

with 11, same thing, we have our familiar matrix, multiply by this product state, we go to here, which

we factor into 10. So, I hope I’ve convinced

you at this point that we can use matrices to represent more interesting logical

operations than just a bit flip. Has anyone eventually, yes?>>Is that factoring always possible or practical

for larger vectors?>>It is practical, yes. Not always possible, which we’ll get into that when we get into

quantum entanglement, basically, but good question. So, this is fine for everyone? Nobody’s lost in

the gigantic equations here? Okay. We’re gonna go over

10 then, or sorry, 00. So, the control bit 0 that means we’re going to leave the other bit alone, right? And we see that indeed this is what we do

and same with for 01. Okay. So, everyone, well, maybe familiar with

how classical computers are like real CPU’s there they’re all

built on the, sort of, NAND gate, like everything is

fundamentally built on NAND and CNOT is kind of the analogous NAND for

reversible computing. It’s like a really basic thing

that is used to build up larger and more complicated

logical statements. So, I’m sure if I

gave you a task, like build some more complicated logical formula with CNOT, you’d probably be able

to do it at this point, you just like stick

them all together and eventually comes out. I will note that it’s

not actually universal. You can’t make every logical

function with the CNOT gate. You need something

called a Toffoli Gate, but we won’t see that

in this presentation. And we’ve learned everything

we need to know about how to use linear algebra to represent

classical computation, and we can now go on

to quantum computing. So, to recap, we learned that we can

represent classical bits in vector form is 10

for 0 and 01 for 1. We can represent

operations on bits by multiplications

on their bit vectors. We know that quantum

computers only use reversible operations and in fact the operations

are their own inverses and multibit states, we write is the tensor product

of our single bit states. Finally, learned

about CNOT which is a very fundamental gate in reversible computing

and quantum computing. So, everyone’s

following along so far? This is pretty simple,

right? And it’s not that bad. Okay. Let’s make

the jump, qbits. And I will surprise

you, we’ve been learned using qbits all along actually. The cbits are just

special cases of qbits. And we represent

the qbit in general by a vector of two elements a, b where a and b are

complex numbers. Don’t worry. We’ll only use real numbers for

this presentation. We’re keeping it simple. Only using real

numbers. And we have the constraint that

a squared plus b squared is one. So, (1,0) and (0,1) fit

this definition because one squared plus zero squared is one and zero squared plus

one squared is one, right? Now, here are

some example qbit values. This is one with which

you’ll become very familiar. It is one over root

two, one over root two. Can anyone tell me what one

over root two squared is?>>One half.>>One half exactly. one half plus one half is

one. So, this is a qbit. What about one half and

root three over two? What’s one half

squared? One quarter. So, one quarter plus

three quarters is one. Here’s an interesting thing. We can actually use

negative numbers now because the negative number squared is a positive number. So, negative one squared is one. One plus zero is one.

And the same thing here, it’s just the same

as this first matrix, but one of the values is

negative. Pretty neat. Not bad so far, right? Okay, but you might say

this is kind of like saying that a qbit has a value

which is not zero or one, but actually both zero

and one at the same time. This is called superposition. Everyone’s probably heard of the Schrodinger’s cat

being both alive and dead. That’s just like a pop science the way of articulating

this concept sort of. And the interesting thing about a qbit being

in superposition, it means we can kind of, I want to really qualify

this kind of compute with the values of both zero

and one at the same time, which again is the sort of whisper of some

quantum speedup power. Okay? Now, how this works is, when we measure this qbit, it collapses to

our familiar values of zero and one with

some probability. And this is what we

usually do at the end of a quantum computation

to get the final result. We send it through

the measurement gate, we see what the result is. So, how the

probability works is, if you have a value (a, b), it collapses to zero

with probability a squared mand one with

probability b squared. So, if we look at our familiar qbit from previous

slide, one over root two, one over root two, it has a one half chance of

collapsing to zero, and one half chance of

collapsing into one. It’s like a coin-flip. Now, if we just measure

our classical qbit, our classical cbits the (1,0) has a 100 percent chance

of collapsing to zero, and (0, 1) has a 100 percent

chance collapse into one. So, it’s sort of item

put in that way. And I found it useful here to give people sort of physical intuition about

what we’re doing, what bit is or a qbit is. If you’ve heard of polarization, you’ve probably bought

fancy sunglasses, says that they’re polarized. So, polarization is actually

sort of quantum phenomenon. You can be polarized like

this way or this way, and your glasses will only

be polarized a certain way so only let light polarized in this way

through basically. It turns out that qbits, you can think of this, yeah, a photon being polarized

this way is a zero, and photon being polarized

this way is a one. Superposition means it’s

actually like both, right? So, it could actually go

through both gradients. And then if you measure it, and a way to measure

it is just to fire it through grating and

see whether it goes through, then you can collapse

it to zero or one. So, that’s our intuition pinning this to

a physical concept. Of course, modern, we found that photons

actually make very, very poor qbits, they tend

to collapse to easily. So, we don’t use those, but

you can maybe think of that. Does anyone have

any confusion here, really, about how this measurement process collapse

probability works? Okay, great. We will learn about

multiple qbits. The same is multiple cbits. We represent them by

the tensor product. Why is it doing that? Okay, hold on, laser pointer. Okay, there we go.

Nope, that’s not. Okay. So, if we have two qbits,

and we multiply them, the sum of squares identity

actually is maintained. And so, if we consider our perfectly balanced 50

percent coin-flip qbit. And we tensor with

another coin-flip qbit, we get this four vector with one half in every single column, and one half squared is

of course, one-quarter. So, one-quarter plus one-quarter plus one-quarter plus

one-quarter is one. This maintains the property. And the way to read this is when you measure

these two qbits, it has a one-quarter chance

of collapsing to (0, 0), (0, 1), (1, 0), and (1,1). This is sort of the probability

of when you measure it, finding a one there, and zero everywhere else. So, we could find, it’s a one-quarter probability

of finding one in this position and

all zeroes everywhere else. Does that make sense

for multiple qbits? Okay great. You guys are just trucking

along and no problem. Should be super easy. Yes?>>I have a question.>>Absolutely.>>So, there’s only

going to be one, one left in the vector?>>Yes.>>There couldn’t be two ones?>>There could not two ones because that would

actually violate our a squared plus b squared

equals one constraint.>>Okay.>>But yeah, after measurement

there’ll only be one, one here in this in four vector, which we can then factor

into two bits actually. Okay. Yes?>>You also find collapsing

for that longer vector?>>Yeah, yeah. So, if you measure

these two qbits at once, you can think of this product

state vector is collapsing. And then that’s

just the probability of finding a one here and

a zero everywhere else. It’ll become useful in

the future when we can’t actually factor out the product

state, but that’s anyway. Okay. How about

operations on qbits? We have these qbits, how do

we actually manipulate them? The same way we do with

the classical bits. And all the matrix

operators we’ve learned also work with qbits. So, for example, negation. If we have our qbit that has a 25 percent chance

of collapsing to zero, 75 percent chance

collapse into one, if we run it through

the bit flip operator, now it has a 75 percent chance

of collapse into zero, and 25 percent chance

of collapse into one. So, we can manipulate

these probabilities actually called amplitudes with gates. And you can think of gates, they correspond to some

device scientists have created which is like manipulate

the qbits with a gentle touch. Not enough to collapse them, but enough to

change their state. So, pretty neat. And there are also a couple

important matrix operators, which we haven’t learned

yet because they only really make sense in

the quantum context. Okay, all right. We’re good. Then the most important one

is the Hadamard gate. And what it does is, it

takes a zero or one qbit, and it takes it to

the coin-flip state where it’s in exactly

equal superposition. The matrix looks like this. It as one over root two in every single entry except for a negative in

the bottom right corner. So, if you multiply

that by this, you get one over root

two, one over root two. If you multiply this by one, we get one over root two,

negative one over two. Pretty neat. So, this is how we actually get into superposition. We use the Hadamard device, which scientists have developed, and we can make much use of. So, quiz time. Can anyone tell me why

we need a negative one in the bottom right corner? Why do we need

a negative sign here?>>It’s like a matrix

on bigger provision. I don’t know exactly why, but it is too big.>>Well, the answer basically

has to be reversible. So, if we didn’t have

this negative number here, then both zero and one

would map to the same value, and it would not be reversible. So, we need this negative sign.

Yes, correct. Okay.>>Question.>>Yes?>>Review of superposition, what does that mean exactly?>>Superposition, yeah. So, superposition

means that a qbit is in both states zero and

one at the same time.>>Okay.>>And I want to be really

clear about something here. This doesn’t mean

the qbit is secretly zero or secretly one,

and we don’t know. It means it’s actually

in both at the same time, this is just quantum weirdness. This is just like what

happens at the very, very small level of our world, which is that things don’t have definite values until

we measure them.>>Here you have (0, 1) in superposition

is one over root two, one over root two. And one and superposition

one over root two minus one.>>Yes.>>So, we seem to have different values but they’re representing conceptually

the same thing.>>Right. So, this comes down to the distinction between the quantum

and classical world,. Which is that from

the classical perspective, these two qbits are the same. Both have 50 percent probability of collapsing to zero or one. But, if we stay within

the quantum realm, this sign information is preserved as long as

we don’t measure it, and it can affect

our computations.>>So, it’s got a 50-50 chance, but it has a sense that

it used to be a one?>>Has a sense that

it used to be one? Not really, it just

ends up in this state, which is different within the quantum realm

than this state. These are two different states.>>Okay.>>Yes.>>Both for the 50-50 chance.>>Yes, exactly. Both when you measure it and convert it into the classical world come

down with a 50-50 chance. Yes. But they are different, and they have different

computational properties. Okay. Now, I’m going

to show you something really cool about

the Hadamard gate, which actually takes us out of superposition into

the classical bits. This should be unsurprising. Everything is

its own inverse, right? If we just apply the Hadamard

gate to our value here, our coin-flip

value, we get zero. And for this one, we get one. So, this suggests to us

a quantum computation structure. We can start with

our classical bit values. We put them into superposition, do a bunch of

quantum stuff to them, and at the end if we’re clever, we can transition

them to zero or one so that our whole computation

was deterministic. Pretty neat, right? Okay. Now, I should say that not all

algorithms work this way. There are algorithms

like Shor’s algorithm, which only gives

the right answer of 50 percent of the time. You can’t be clever and always get the right answers,

just not doable. But the one, the problem

we will look at does give this

deterministic property. So, does anyone have

trouble with this concept? We transition out

of superposition without measurement,

pretty interesting.>>Can you go over

this transition from a classical computation to quantum and then

converting it back?>>Yes.>>That’s correct.

Let’s say two plus two, how would that look like in?>>How-?>>Just the simplest

type of math.>>The simplest type of math. What we’re going to go

over that basically, we’re going to go

over a problem. There are certain problems

where computers are better than classical.

Addition is not one of them. It works the exact

same way in both. It should also be said that

all classical computation can be done on

a quantum computer, all you do is just restrict all the values to zero and one, and it works, but it’s kind of a waste because

you can also use all the extra values

that we found. Okay, and we’ve actually sort of define

a state machine here, which I am sure many

of you will appreciate if you’re software engineers

or computer scientists. This is the unit circle which many of you will remember from high school trigonometry, right? It’s a circle of radius

one around the origin. Here’s the X axis, this is the Y axis. You can think of

the top value is the value of the x-value and

the bottom one is the y-value so our zero value

is at position one, zero which is along the X axis. Our one value is position zero, one which is along the Y axis. And this is

the bit flip operator, it defines transitions

around this unit circle. So zero goes to one,

one goes to zero, zero negative one

goes to negative one, zero which when

you collapse them, this is zero, this is

one, and vice versa. And if we look at the superposition values, here’s

something interesting. The bit flip operator really kind of has

no effect on them. For this one, if you

flip it upside down it’s stays itself same

with this over here. This one’s kind of interesting

and that it transitions you all the way

across the unit circle and we’ll make use of that. But yeah, this is pretty much the full action of the bit flip operator on

the unit circle. I should mention here that if we were using complex numbers, this would actually be a sphere. Much more difficult to sort

of intuitively graphically represent so we’re sticking with real numbers, they

suit us just fine. But it’s nice to know that

additional dimension is always available to us if we want to make our computation

even more powerful. And then here’s the action

of the Hadamard gate, which we saw in

the past couple slides. It takes us from

zero to one over two, one over two, one, two, one over two negative

one over two, and kind of symmetrically, it also works in

this way over here. So, we have a nice state machine

that we’ve developed and now we can start running

things on the state machine. Very nice intuitive

sort of representation, you don’t need to do matrix

multiplication all the time. Everyone kind of gets this? Okay, great. So here’s an example of something we could run through

the state machine. Here, I’m introducing

something called quantum circuit notation. You can think of

the cubit traveling along this line has these

operations applied to it, is it goes through the boxes. So X is bit flip, H is Haddamard, and then

so we go a bit flip, Haddamard, and

bit flip, Haddamard, bit flip and if

we start out here, we go bit flip, Haddamard, bit flip, Haddamard, bit flip. So we start off at one, zero and get to zero, one, we got to cross the circle. And note, this is

reversible so we can also go this way and get back. So this is kind of how we’ll be doing all of our computations

like this basically, just hopping around

the unit circle. It’s pretty simple,

pretty intuitive, right? It’s just a state machine. We use this in classical

computing all the time. Just has a bit of

weird rules with the claps and whatever

but don’t worry. Okay, now we have everything we need to learn

the simplest problem where a quantum computer outperforms

a classical computer. We learn that Cbits are

just a special case of Qbits, and Qbits are two vectors of complex numbers such that a squared plus b

squared equals one. Within the Qbits is going

to be in superposition, they’re probabilistically

collapsed to Cbits by measurement. Multi-Qbits systems we

learned are tensor products of single Qbit systems

same as with Cbits. Matrices, again, represent

operations on Qbits, and we learn about

the Hadamard gate, very important which takes our zero and one bits to

superposition and back. And finally, we learned that we can think of Qbits

in their operations is forming the state machine

on the unit circle or unit sphere if we’re

using complex numbers. It’s actually called

the bloch sphere, if you want to look that up

for the full complex numbers, but unit circle,

just fine for us. Okay, so we’re gonna learn about something

called the Deutsch oracle. This is originally proposed

by David Deutsch in, was it like 83 or

something like that? And the problem is this. Imagine I show up at your doorstep and I

give you a package, the package is

just this black box, it’s just horribly present. It’s a black box which

has a function on one bit. There’s one of

those four functions on one bit, do you

remember what those are? I said I would ask you

about them. Set zero, set one, identity, indication. Exactly. So one of

those four functions, I don’t tell you which one

is inside this black box. There’s a wire going in and

a wire going out so you can send in values see

where it goes out, but you can actually look

inside the black box, okay? So how many queries on a classical computer

would it take to figure out which function is inside

the black box? Two, exactly. You send in zero,

see what comes out, you send in one,

see what comes out. So that will uniquely

identify which function it is. Now, how many queries

do you think it takes on a quantum computer. You’re wrong, it’s two. I say this to illustrate

an important point, which is quantum computers, they don’t really compute

with all value simultaneously. At the end of

the day, you collapse your Qbit to a single bit

of information, and a single bit of

information is not enough to uniquely identify one of

four functions, right? You need two bits at least So this actually takes two queries

on a quantum computer. Well I’m not too

exciting so far. Now, what if instead of not wanting to know

which function it is, we just want to know

whether the function is constant or variable. The constant functions are, constant zero, constant one, they’re always mapped to

0, always mapped to one. The variable functions

our identity and negation. So how many queries would this take on a classical computer?>>Two.>>Two. You put in zero, if you get zero you

don’t know whether it’s identity or constant zero. If you get one, you don’t

know whether it’s bit flip or constant one, symmetrically with

one, so it always takes two queries on

a classical computer. Even though there

are two categories, so really we only

need a single bit of information to tell us

which category it’s in. But how many queries do you think it takes

on a quantum computer? I kind of burned you last time

so maybe you’re a bit shy.>>I’m going for a one. One, you are correct. We can do this in a single query

on a quantum computer. We can tell whether

its constants or variable. This like undeniably outperforms a classical computer and

we’re going to learn how. Okay, we do with the magic

of superposition. But first we have to define which each of

those four functions look like on a quantum computer. We have an instant

obvious problem with the constant functions. Can anyone tell me what it is?>>Not reversible.>>They’re not reversible, how are we going to write these non-reversible functions

on a reversible computer? This is actually a really common problem in quantum computation. You really often

have to deal with non-reversible functions if you have to write them in

an irreversible way, and the hack we do is this. So originally we

had this, right. We add an input and an output, a single wire going through. And we just imagine

that you put in the value and you

get the function applied to that value, right? But the hack that you always

do on quantum computers is you add an

additional output Qbit. So you actually have two Qbits. We have to rewire our black box. So you have your input

Qbit, which is unchanged, and then the value of

the function on the input Qbit is written to

the output Qbit. Does everyone kind of get this. I think this the thing

that people have the most trouble with,

this is necessity. The reason we have to do this, is so we can write

non-reversible functions in a reversible way. And the way you do that is to have a separate input

and output qubit. So when you see

larger quantum computations, instead of having all the bits go in and have transformations applied to them and

then being measured. You usually have

a separate set of output bits, so the input bits go in, they have their value sort of

written to the output bits, and you measure the output bits. This is a very standard way

of doing quantum computation. So does anyone have

any trouble with this? This is a very difficult

concept. So, yes?>>I didn’t get it.>>Okay. So, do you understand

this model basically, this is what we have now, okay? So we need to rewire it so there are two wires

going through the box now. And one of those wires

we call the input wire, one of those wires we

call the output wire. We assume the output wires just initialize to zero,right?

It’s always zero. Now our input wire is what we

actually give our input in. Like it’d be like zero or

one or whatever value you want to give

input to the function. So, it goes to the box,

it’s just unchanged. We don’t touch the value

of the input wire, but we calculate

the function in here, on this input and then we write its value to

the output wire, okay?>>Black box?>>Yes, we are

rewiring the black box. We have to rewire

the black box in order for the black box

to really work. So the black box I gave

you has to be rewired. Yes.>>Did you use the first input, which is the output of zero?>>Did I use the first input?>>Yeah, because one of them

was kind of identity, right? You put the X out, and

then it was the F or X.>>One of them was

X and the other was>>You need the X out.>>Say we only have this, right? This is

the old way of doing it. We can’t have a non-reversible

function in here, right? For it to be on

the quantum field.>>No, that I get, right?>>Okay, yes.>>Because when that thing

is on the right side, you have two going

in, two going out.>>Yes, two going in,

two going out, yes.>>I get why two going out.>>Yes.>>I don’t get why we have

that zero is also going in, It doesn’t seem that

you’re actually using it to produce any of the others.>>You’re correct,

it’s just we need.>>Symmetry?>>Not really symmetry, it’s just like how we would

write the quantum circuit, we would need

two qubits in general. So, you’re correct that this algorithm value

isn’t really used.>>Is it like we

don’t care a pen off?>>No, we do want it to

be zero because the way that we write

the circuit assumes that this value coming in

is always zero. Yes.>>Why is it ingoing

output wire called output.>>What? Yeah. So, this is

kind of weird that the output of the input

is called input. But, we basically only really

look at this value here, is the basic idea. This is like the real output. The input will

always be unchanged.>>Question. So if I have multis two black

boxes in series, the upper input which

you have labeled Alvap.>>That’s smart,

that’s a good one.>>And the second stage

would be the F of X output of the first stage?>>Okay, so you’re

saying if you had these in series

rather than sort of in parallel to what we’re doing

is that what you’resaying?>>Yeah I want to

do two operations one and then another one. And the black box is

doing some operation.>>The black box is

doing some operation. You can have as many

operations as you want in here inside

this black box basically.>>True, but I’m trying to conceptually

understand whether I would take the F of X is

the output upper right. And that will be the input.>>The input, the next one.>>Absolutely and in fact I said that this black-box

assumes this value is zero, this isn’t maybe throw

in a bit much of you, but actually we can break

that assumption and send it some other value which maybe will get us more information which is in fact

what we’ll be doing. So, the working of black box assumes that the

output input is zero, but we can break

that assumption and be tricky.>>My way of

thinking was I didn’t have any other value

for the first stage, but for subsequent inputs

I do have one. So I could use it if I want?>>Yeah you could, yeah and you might get some interesting

values which actually well. Okay I swear, this is the most difficult part conceptually of

this entire presentation. So if anyone has any trouble

with it please let me know. Ask any questions you can spend as longer time on

this as we want. Yes>>As we go ahead, is there some additional clarifications

because I didn’t get it.>>Okay. Well we’ll

go over all each of the four functions in this way,

so maybe that will help. So, for example, constant

zero, here’s how it would look. X goes in, X goes

out it’s unchanged. Now, the output is always

going to be zero, right? That’s just what

the constant zero does. So we always want this value in the upper right to be zero. If we assume zero goes in, this is our circuit diagram, neither of the two wires make

any modifications, right? It’s a straight wire. Does that sort of makes sense? We will see the next slide, what about for constant one? We want one to go

out here, right? This is our function

output value. And we assume zero

is the input here. All we do is we do

a bit flip right here, and that gets us

the semantics we want. Is anyone having any trouble

with this so far? I swear this is

the most difficult part. So if you get this

you’re golden. Yeah.>>So these labels

output, input, would you call them something like computations and its spare?>>Sure yeah, you could. You can call it the

compute and the spare fit. Yeah, that also

works.They might reduce some confusion about there being an open output and input output.>>Why is it called output?>>Why is it called output? We call this the upper

qubit because it’s just the place that we write

the output of the function. But we could call

it like compute and spare or something like

that, like he suggested. Like this would be

the spare sort of bit that we write the function number 2. Yes>>We need this to do

a reversible computation, right why is this?>>Reversible?>>Can we compare

the reversibility of this likewise the right

one reversible one?>>Absolutely, okay. So let’s consider this one

right here, right? We have our black box with a single wire and say we want to do

the bit flip operator. So, that would just be. Sorry not with

bit flip operator, a bit flip operator

is reversible. So we want to do

the constant zero operator. We always want to

map this to zero. So you need some operation right here, that would

map this to zero. But it’ll be the matrix 1100 but this is not a valid operator

in a quantum computer, because it’s not reversible. So, does that kinda makes sense? It’s just we can’t construct

a device which does this. It’s just not permitted

by physical reality. All this math and

stuff I’m showing you, it’s not like special it’s just, we found that it corresponds to the semantics and workings

of a quantum system, and so it’s a nice way to

reason about it basically. Okay. Of course if we want to write constant

zero here with their two inputs are the two wire model it

would just be blank, right? Or if we want to do this is constant one always maps to one we saw that this

has an X gate here. And this is reversible, right? Okay. So we managed to write a non-reversible function

in a reversible way. If you’ve got

this congratulations, this is the trickiest part. It took me awhile to

figure out why we needed to do this staring at the textbook. Does anyone have

any confusion here? Okay. So remember constants

zero is just blank. Constant one has

a single X gate. Yes.>>There’s a point

you always end up with a four by four reversible matrix by doing this in black box?>>Yes. Black box

is always a four by four reversible

matrix applied to a product state, you’re correct. Although we will be not going into the math in that way

we’ll just be using the state machine to look at it, but the math is very easy

for you to do it yourself. Okay. So let’s look at

identity this is a bit more complicated this is

the CNOT gate, okay? Where this is the control,

and this is the target. So we’ll end up with, so input again is unchanged. We want output we

assume it zero we want to end up with

a value X, right? So if zero is sent in here, then this is the control bit, so the target bit is

just left unchanged, right? So zero comes out. If one is here, one is sent in, and the control bits

one so we flip thright? Is bit, and we end up with one. Does this make sense?

This is kind of tricky it is a big step up

in complexity of our circuit, but everyone’s fine with this? Wow okay. Can anyone guess

how will do negation?>>You can hardset

the control bit to one.>>How can we hardset

control bit to one?>>Two controlled NOTS. They’re.>>Not two controlled NOTS, we just have an X gate there. So, up to here it’s

equivalent to identity, right? And then we just flip the output bit

and then we got NOT X. So, those are

the four circuit values. Okay. Everyone’s good so far? Everyone knows how we

write our four functions? Are you ready to

see how we solve it on a quantum

computer? We use this. So, we’re going to

break the assumption that this value goes into

the black-box as zero. We put, first, we initialize both in putting up

a qubits to zero. We bit flip them so

now they’re both one. We put them through the

Hadamard gate to put them into equal superposition then we

send them into the black-box. One of those four

circuits is applied. Then we do the post-processing, we send them through

the Hadamard gate again and we measure them.

This is measurement. And I claim, and I will

show it to you that if the black-box function

is constant the system will be in state

one-one after measurement. Like this will have value

one, this will have value one. We’re using input as the most

significant bit by the way. And if the black-box function is variable and the system will be in state zero-one

after measurements. So this will be zero,

this will be one. And we will know whether

the function is constant or variable in a single query. Pretty nifty, right? I’m going

to show you how it’s done. First the preprocessing. Remember, we start

with zero then we’d been flipped both in

the Hadamard gate both. So we start here, bit flip

takes us up to here, Hadamard gate down here. So this is the value that

is sent into the black-box. Just remember it’s in the bottom right

on the unit circle. This is the value

right before we send it through one of

those four circuits. Okay? Now, let’s look

at how we do constant-0. So constant-0 remember,

it’s just blank on both and the post-processing

is a single Hadamard gate. So since no gates are

applied they stay in this bottom right value, and since the Hadamard gate is applied as part of

the post-processing, we flipped back up here. When we measure this,

this is one-one. Remember I said

the value would be one-one if it were

a constant function. So we’re one for one, okay? Seem okay so far? All right. Let’s add a bit flip because we’re going to

go over constant-one now. So this is the other

constant function. Now remember, if

we do a bit flip in this state we flip across

the unit circle over here, and the Hadamard gate then takes us down to here,

zero and negative one. When we measure it

we again get one-one. Okay? So we’re two for two. Not bad, right? Okay. Things

get a bit more complicated. Does anyone have any trouble

with this so far? And then, yes?>>I just didn’t get like

why it turns out to one-one?>>Why it works out to one-one?>>Yes.>>That’s a good question.

Okay. So we’re up here, right? If we measure this

then what value do we get? This is just one. Remember, this is

the value of the one bit. So if you measure

one, we get one. Yes. Now down here, if we measure this we also get one because negative one

squared is one. So is 100% probability

of collapsing to one. And so, we can say

this is one-one. This is like

the most significant bit and this is the least

significant bit. So we end up with one-one. Does that answer your question?>>Yeah.>>Okay. Great. All right. Let’s go on to something more

complicated, which is CNOT. This is going to get a bit weird but this is how we

do identity remember? The input bit is

the control bit, the output bit is

the target bit. And don’t panic, I’m going to show you why

this is on the next slide. But the action of

CNOT is to take our input qubit up to here. That’s the green line. This

is weird for two reasons. One is that the CNOT is supposed to leave

the control bit unchanged. Right? But here this is

the only thing that control bit, like the qubit it’s

the only thing that’s changed. And, this sort of

action is a bit odd, but don’t worry I’m going

to show you the math, the reason why this

works on the next slide. But just for now, so we flip from here up to here, and then when we do

the Hadamard gate to post-process we

end up in state zero. So zero-one, pretty neat. Okay, here’s how the math works. We’re applying the CNOT gate to the state one over root two, negative one over root two, and one over a two, negative one

over root two, right? When we tensor these together, we get this ridiculous matrix

which I’m going to factor out one-half,

just to make it readable. So, we have the matrix one, or a spectra is at 1-1-1,1. Right? Now, we remember this familiar matrix

from the CNOT slide. When we apply this matrix

to this vector we get this. Right? We flip

the bottom two rows. Now, when we factor this, remember the products

that we can factor it into

the individual state, we get this tensor product. If you ignore everything

in the middle and just compare our start values

to our end values, this is the output or

least significant bit. This is unchanged. Right? This is

still one 1/2 -1/2. The input bit which

started out as 1/2 -1/2 ends up as

1/ 2 1 over root two. This is just the action

of the gate. So this is kind

of a limitation of our visualizer that

we can’t really show the state transition

but I hope I’ve convinced you that this arrow

is in fact what happens. Does anyone have

any questions about this? Okay so we’re three

for three right. I said the measure value

would be zero-one, if it were a

variable function and indeed it is as I said. So for three-three.Three

for three. Let’s go over the very last one

which is negation. It’s a CNOT and then a bit flip. Right? Let’s see how that works. Again we have this arrow. Taking us up to here and the bit flip takes us

across the unit circle and we do the Hadamard post-processing to

get us down to here. When we measure these,

we get zero-one. Four for four, huh? Single query, outperformed classical computation,

pretty nuts, right? Pretty nuts. Okay, so we did it. We now, we have outperformed

classical computing. Classical computing

is in the dust. It’s done, it’s dead. So we might think like, yeah I see how the math works

and what’s the intuition? I’m going to tell

you the intuition. The intuition is the difference within the categories was

a single negation gate. So if we go back to here, so we have constant

zero and constant one. The only difference

between them is a single negation gate. When you apply negation gate

in a superposed state, it doesn’t really

have any effect. Right? So we kind of neutralize the effect

of the negation gate. So we neutralize

the difference within the categories and

then we magnify the difference between

the categories which is that the variable functions

have a CNOT and the constant

functions do not. So we magnify the effect of the CNOT and minimize

the effect of the negation. And that’s a

powerful thing about quantum computing which

is that you can change the action of

various logic gates by putting yourself in superposition in different sorts

of states and stuff. So that’s pretty

neat. And this problem you may say like,

“Okay well yeah. Great. Whatever.”

It’s really contrived. When do I ever do

this in real life? That’s a good

question and it was contrived back when

it was announced, I think was 1993, but

then a generalized version of this function was found which it takes n bits as

input, not a single bit. And the n bits either all

map to the same value, sorry, like that’s two to

the n possible values, they all map to the same value or they equally

map to zero or one. They’re constant or

balanced it’s called. And so it’s kind of just

generalized version of this. It turns out we can still

solve that on a single query. Exponential speedup, huh? Exponential speedup. A single query versus on a classical computer you

have to try all two to the n values before you know whether it is constant

or variable. Pretty nuts. Okay? Then there’s a variant of that problem building everyone’s kinda like

building on top of each other, it’s called Simon’s

periodicity problem. It’s again you have

like a black box and you’re trying to figure

out some properties of the function and

then once that came around Shor he looked at

this and he’s like, “Oh! We can use this to

factor large integers.” And so he came up with

Shores algorithm and that’s when the whole field

really caught fire. So I hope I’ve

convinced you that well this individual problem is kind of contrived

and not that useful, it’s the base, like

the foundation of some very interesting

computational properties. Did that make sense? Anyone have any questions? You’re all like

convinced that we just crushed a classical

computer right here? Yes?>>On the Microsoft site there’s an article where

the girl was saying, with quantum computers

you can take programs that take billions of years to run and run them in

a week. Is this… [Croostalk].>>This could be

that. I mean yeah. We have an exponential speedup. If you have like, I don’t know. What it would take something

like a billion years to run? Like if you have

an 80 bit function, like to the power of 80 versus

like a single query that’s probably a billion years

versus a week something like that. So.>>A question. So I

understand speedup but this is the speedup in answering

this question from the output coming

to get the input. Right? Whether the function

was a constant function or.>>Yes.>>Right? But in what context is

that question unimportant?>>Great question. Why do we care about

this sort of thing? So for example in

Shor’s algorithm you can construct a question like does this integer have a certain factor in

structure basically? And you can tell a property

like whether it has that property or not basically

which will allow you to, and if it does have

that property you can factor it pretty much. It’s very very hand-waverly explaining how

Shor’s algorithm works. So you can construct

a lot of problems in terms of does this function have

a certain property or not, which you can find

efficiently on a quantum computer. I hope, Yes?>>Do you mean

this decision helps?>>Mainly decision problems. Although, as we know from

theoretical computer science, decision problems can be

usually be turned into like generally

finding the answer to problems and vice versa. So, yeah. Okay, pretty good so far. To recap the whole presentation, we learned how to model

classical computation with basic linear algebra,

we learned about qbits, superposition, and

the Hadamard gate, and finally we learned about

the Deutsch Oracle problem, where quantum outperforms

classical, pretty nifty? Okay, now the bonus topics. With all the tools we have these will be a breeze for you. You’ll never have to read

some pop science articles on quantum entanglement

and like try and muddle through there

a horrible metaphor. You’ll actually know

the math, all right? You’ll know the math,

that is incredible. And we’ll go on quantum

teleportation, which is super, super nifty like

it is mind-blowing. Okay, quantum entanglement. You asked a great question, a very impressing question

earlier which is, “Can we always factor the product state

into the qbit state?” When we cannot do that, that means that

the qbits are entangled. For example this state, if we have qbits in this state

which is one over, two, 001 over root two, if we try and

factor this, we can. So let’s try and factor this. If we can factor it, we should be able to write it as a tensor product of

two matrices, right? Where A times C is

one over root two, A times D is zero, B times C is zero, and B times D is

one over root two. So we have this set

of equations right? Now, A times D equals zero that means A or D has to equal zero. If A equals zero then AC will be equal

zero and it doesn’t, so A cannot equal zero. If D equals zero then BD would

equal zero but it doesn’t, so D cannot equal zero. So the only solution is there is no solution. We

cannot factor this. This is an percent

unfactorable state. And what this means is we

cannot separate these qbits. They have no individual value, their value only make sense together, they’re

called entangled. And the way we might

think of this is that if we measure this state, it has a 50 percent chance

of collapsing to zero, zero and 50 percent chance

of collapsing to one,one, so the qbits are

coordinating, right? Does anyone have

any confusion with this sort of mathematical

representation? Okay, let’s talk

about what it means. Well, let’s not talk

about what it means yet, you might be like, “Well, Andrew I can sling

any old value into the vector how do you

actually entangled qbits?” It’s really simple. If we have two qbits, we just put one qbit through the Hadamard gate to

put in superposition, and then that qbit is

the control bit in C naught. Two gates, that’s all we need. Here’s how it works

mathematically. We started with zero zero, we put the most significant bit

in superposition, right? And then here’s our familiar

matrix, seen our matrix. If we apply it to

the product state, we get this. This is the state from

the previous slide. So really simple

to entangle qbits. Okay? What does this mean? I mean they seem

to be coordinating, or like communicating,

or something in some way, these two qbits. And if you measure one qbit, it collapses the other

in coordinated state. Now the weird thing, here’s how we’re going do

really weird stuff here, okay? This happens across

huge distances. China just this year, managed to do this between Earth and a satellite in space. They entangled qbits, put

one half on the satellite, it was launched into space. When they measure them,

they’re the same value. It happens across

huge distances. It happens faster than

light, it is instantaneous. A 2013 experiment

entangled qbits, moved them very far apart, synchronizing with

an atomic clock, they measured them

very close together. So close together and time

that it would have taken like 10,000 times longer

to travel between them. So they aren’t communicating

with any sort of radiation anything

like that, okay? They are instantaneous,

it’s faster than light. And you might be like “Well, it’s pretty obvious

what’s going on here. When the qbits were entangled, they just decided ahead of time what they’re

gonna do, right?” Well I got to

explain everything, but that’s called

hidden variable theory, this is hidden variable theory. It’s the same reason that

when a qbits in superposition, it isn’t secretly zero, or secretly one, it’s

both, it’s the same thing. Hidden variable

theory, we’re not going to over the proof

why it doesn’t work, but basically here’s

this guy named John Bell, and he showed that if hidden

variable theory were true, it had some really

weird implications, and therefore it’s unattainable. This is just the state, this

is how the universe works. They coordinate

faster than light, they just do and that’s nice. And you might be like, “Well, I’ve been told

my entire life there’s a universal speed limit,

the speed of light, right? Like what’s up with that? We can’t just chuck it all out.” And this is in fact a big source of consternation to Einstein, the idea that

locality wasn’t true, and then it was discovered that there’s a really

important qualifier. You can have faster-than-light

coordination, but you cannot have

faster-than-light communication, so information cannot be

communicated. So think about it. If I entangle two qbits,

I give you one, we go to opposite ends of the universe, if

I collapse mine, all I know is that

you collapse yours, and when you collapse yours,

you will see the same thing. That there’s no information that can be communicated

there really. So, faster than

light coordination is okay, faster than like light

communication, not okay. Yes?>>Coordination does not

involve communication?>>It does in a way, but communication here is a technical term

which means like, I have a bit of information

that I can transfer to you, pretty much. So I use the term

coordination to try and give a name to something

which is not that, but still involves

like some kind of coordination I guess. Like I said, there is

a limitation of our language, all we can do is look at

the math and see what it does, and our language it was

not developed for this. Anything I try and tell you is fundamentally a lie,

except for the math.>>I have a question.>>Yes.>>So let’s say I have

two entangled qbits.>>Yes.>>And I measure one

and I know its value. Does that mean

that the other one is could potentially

still not be measured, but when it is measured it

will have the same value?>>Right, when you measure one it instantly

collapses the other.>>I’m sorry, that was

my question earlier.>>Yeah, good question. I said that’s

a simplification again of language but you can

think of it that way. Yes, sorry you had a question.>>So there’s no way to tell that something has been

collapsed or not then.>>Excellent question. If you could tell whether something’s

been collapsed or not, you could measure one and

use that as synchronization, faster than light

synchronization, right? Yeah you can’t. The process of telling whether something is in superposition or not

would just collapse it.>>It seems like you will

be able to tell through some of the sort of

quantum computation, like you do some computation

on that, they was collapsed, they would only be

this state and if it wasn’t it would sometimes

do this, sometimes do that.>>You would think so, but

in fact it is not the case.>>I believe you I was

just creating imaginations, is there any intuational ways

about the case?>>Is there intu can I say intu?>>Shut up and do the math?>>Shut up and calculate, that’s a good like a way out. I’m not sure I can’t

say it intuitively, I can say that if you do put a pencil and paper

it, try it yourself, try and come with some sequence of

operations you can do on the other qbit

which would reveal it as having being collapsed

or not then maybe but, yes.>>Doesn’t this coordination

communication conversation that we’re having

violate causality or it doesn’t?>>Yes, this is

the critical thing, it does not violate causality. If we could communicate then

it would violate causality, but since we coordinated

does not violate causality.>>But instead

what you said was, if you measure

the other one is going to be that as well, right?>>Yes.>>The act of measurement

is in your control, right?>>Yes.>>So how can that happen

on the other side of the qbit if you don’t have

communication because that’s.>>Well let’s define

what communication is. Communication is I have a bit, either zero or one and I’m able to send it

to you in someway.>>Somehow yeah.>>Yes.>>The state that

is not collapsed, be communicated to

the other state, this is what I’m saying.>>Yeah I mean this

is a language problem. Qbits are like communicating but we can’t get information

through them basically. You might be able to say that. I use that term coordinating to try and avoid this problem. Other times in literature you’ll just see

the word correlated. Which tries to avoid

that whole problem.>>Coordination, it state

the word here when you are using it, it has an action

that you have performed.>>Yes, you control when you measure in qubits

it collapses the other. But there’s no way

you can change causality in

that other qubits frame. Basically, there’s no way

you can get information from your frame into that frame which would affect

their causality. All we can know is, we have generated the same random numbers

basically, yeah.>>It’s kind of like

pre-coordination so these are.>>I want to avoid that,

pre-coordination is the qubits decided ahead of

time which is not the case.>>Until you measure.>>Yeah.>>Or until these.>>At the time they measure they decide whether they’re going to zero or one and they somehow communicate that coordinate, correlate, whatever,

to the other qubits and it goes in the same. Yes.>>So, if you cannot communicate what’s the practical

application of quantum?>>Great question.

We’re going to get into quantum teleportation

on the very next slide. First, I want to tell

a funny story about this. So, you may have heard the phrase spooky

action at a distance. This is Einstein coin that

he was referring to this. So, Einstein,

Podolsky and Rosen are three physicists who actually came up with the idea

of quantum entanglement. They call it the EPR paradox, there like the workings of quantum mechanics

result in this. This is obviously

absurd therefore, quantum mechanics is garbage, was the basic argument. But then the experiments came

out and they’re like nope, this is how it works, the universe is in fact absurd, locality is broken

and so it’s kind of funny that a deep

pair of paradox is originally designed to

discredit quantum mechanics, it turned out to be the actual way that the universe works, I think it’s

a great little story. Okay. Any other questions

about entanglement, yes.>>Let’s say the same

problem, the qubits.>>Yes.>>If we say that this has a certain probability collapsing to zero

collapsing to one, and then we observe that

it collapses to one.>>Yes.>>How can we justify that

our presumption that it had a probability of collapsing

to zero was valid?>>Excellent question. The answer is used a whole bunch

of times and you see that you get a 50 percent

distribution of values.>>Exactly they won’t be

occurring at the same time.>>Experimentally, we know that they occur

at the same time. With the 2013 experiment. It entangled qubits took

them far apart it used.>>No, I mean the same qubits.>>Yes.>>It happened at time X.>>Yes.>>And now you take

another pair of qubits and this is another pair of qubits but not

necessarily the same ones.>>Yes.>>So, until it

happened at that time, that space or whatever, you can’t really tell that this was happening

with probability.>>One half.>>Yes.>>You’re questioning, okay so, they could have

decided ahead of time for example maybe or.>>Yeah, or probably

the language of probability itself is not active.>>It works. Probability

works I mean, it’s just the amplitude

squared gives you the classical

probability of it collapsing on

zero or one I guess. I’m not a 100 percent sure

what you’re driving at, so.>>So, The question is once

observed then we rationalize.>>Once observed then

we rationalize, yes. And then if we do the experiment a whole bunch of times we see that it’s about

a 50 percent chance of them both being

zero or both being one. Which in fact, I will

show that to you live on a quantum computer

that we do that, okay. All right, let’s move on teleportation This is

the actual use which you asked about and you’ve probably read about

quantum teleportation again in pop science articles. Needless to say, their

explanation was complete trash, made no sense at all,

but now it will make sense to you, okay? It’s the process by which we take

an arbitrary qubit state, and transfer it across space

and time somewhere else. So, you use entangled

qubits as a sort of bridge to send a qubit

from one place to another. And here’s a very

important thing it’s called the

no-cloning theorem. You can transfer qubit states so you can cut and paste them, but you cannot copy them, you cannot copy and paste a qubit state,

you cannot clone it. This is called the

no-cloning theorem. It’s actually pretty simple

to prove you just show that any off-such operation would not be reversible or

its own inverse, but we’re not going

to go do that. And, here’s an

important thing, the teleportation despite using a faster than light phenomenon

of entanglement, is not itself the whole protocol is not itself faster than light for communication because you actually must exchange

two classical bits. So, if I’m teleporting

my qubit to you in addition, to us having

an entangled qubit pair, I also have to send you

two bits of information and we’ll show why that

is in the next slide. So, everyone kind of

conceptually grasp the purpose of

quantum teleportation? Okay. So, here’s what

the circuit looks like. We’re not going to go

over the math, there are appendices to

this slide deck which you can see

after the class to go over the math

but it gets a bit complicated so we’re

not going to do it. So, we have the qubit

that we want to teleport here we call it T

and its value is phi, is just this generic qubit value

can be any value. And then, we have these two qubits A and B which are both

initialized to zero. Now, you will recall this

is the entanglement circuit. So these two qubits are

entangled, all right? Now after they’re entangled, we’ll say we have Alice and Bob. Alice wants to send her

entangled qubit to Bob. So, Alice has these two qubits, Bob has this qubit. And these two qubits

are entangled. So, the qubits are like these two qubits

are separated right after being

entangled, basically. Now, Alice then entangles her qubit she wants to teleport with

the other two qubits. So it’s a three qubit

entangled system. If you were to write out the product state you

wouldn’t be able to factor it into three qubits. Then she puts this qubit

through the hadamard gate. Finally, Alice measures

both qubits in her possession, and this results in

two classical bits. These are the two bits that

Alice has to send to Bob, and the measurement result of this bit determines whether Bob has to run his qubit through

an X or bit flip gate. And the measurement result of this qubit to controls whether

Bob has to run this qubit through a new type

of gate which we haven’t seen before

is called the phase flip gate or Z and this is

what the matrix looks like. And basically, once Bob has applied those two gates

or neither gate, if both of these end up been zero Bob doesn’t have

to apply anything, he’ll end up somewhat magically with Alice’s qubit value

she wants to teleport. Pretty nifty. And you might

be like while we already exchanging a qubit here

why do we even care like we’re obviously just

giving a qubit to Bob, can’t Alice just give

her a qubit right there? So, what you can do is you can pre-entangle a whole bunch of qubits a few billion

qubits or something. And then you ship them by mail

they’re called EPR halves. You ship them by mail or

something so Alice and Bob have a big repository of

these entangled qubits, and then anytime Alice

wants to send to a qubit to Bob she can just use up

one of the EPR pairs. And at that point, that EPR pair has been collapsed can no longer be used so

it’s non-renewable resource. But Alice can just send as many qubits as she

wants over to Bob. Okay? Now, you might be saying, “Well I don’t really get this.” The math is in the appendix if you really want to go see it. It gets pretty complicated, but I think I did

an okay job of explaining it. Okay, you might be like “Okay.” Oh by the way, I forgot to

say, really important thing. You may have heard

that we can simulate quantum computers on

a classical computer but it takes exponential

slowdown or exponential memory. This is the reason,

if two qubits become entangled you have to keep their full

product state around. So, if N qubit with

become entangled you have a vector of size two to the N you have

to keep in memory. And that is why, it takes exponential memory to simulate a quantum computer on

a classical computer. Pretty nifty, okay. So maybe you’re like, “Okay this is all pretty interesting, further

learning goals.” You can learn the

Deutsch-Jozsa algorithm that’s the one with N bits

that I talked about, and also Simon’s periodicity

problem which is another, I figured out some property

about this function. We’re not going to talk about

the complexity stuff but anyway you can also learn Shor’s algorithm,

Grover’s algorithm, Quantum cryptographic

key exchange, that one’s actually

pretty simple I recommend looking at that. You can learn how

they’re actually implemented in physical terms, if you care about that. An important thing quantum

error correction since these systems are so small

like a spare cosmic gray could just come out of

nowhere and just wreck your entire computation you need very very stringent

error Correction Schemes. So, I think

theoretically it takes five physical qubits for a single logical qubit like

we’ve been operating that. In practice, is looking

more like we’ll need one or two hundred to get a qubit of 100 percent probability like we’ve been

using pretty much. So that’s something

to keep in mind. When we see Google’s

coming out with a 30 qubit computer that maybe doesn’t mean

as much as we’d hope. We’ve made only guys like two or three really

high-quality qubits. And also quantum programming

language design which I will go over

because I’ll show you a Q sharp example but anyway,

recommended textbooks. This one is

my absolute favorite, has the same title, has the name of the talk, Quantum Computing for

Computer Scientists. This algorithm is by

our friend David Mermin, the shut up and calculate guy. It is a meat grinder of a textbook but I started

out with this one. It was horrifying,

it was just like, but it skips a lot

of steps basically. It’s more symbolic manipulation. You won’t see as many

vectors and matrices. I like to write

out the vectors and matrices to see what’s

going on which gets really unwieldy when

you’re writing out like a 64 by 64 vector or matrix. But I like to have

both of these. So, I’ll use this to fill

in the gaps with this. This has more interesting sides,

stuff like that. This is also in the MS library. There’s another one called Quantum Computing

Gentle Interaction, also in the MS library. I’ve heard mixed reviews or semi decent reviews of it. I

haven’t looked at it myself. There is also Mix of

Quantum Development kit. They have the docs. They’re actually

pretty nice thing called the Quantum Computing Simulator

and Q Sharp as we’ll see. Now, I said I would

end the talk on some skepticism which

there’s an article, came out I think was Quantum Magazine pretty

prominent recently, interview with

a mathematician who believes that physically realizable quantum computers cannot exist. His basic argument simplifying

is that the amount of noise in the system grows exponentially with

the number of qubits. So we cannot get a really

large qubit system because our computation will

just keep collapsing in the middle of it and it’s just like

an exponential term. And so, I’ll be very

sad if this happened. I’d feel like the universe

is against me. It’d be really,

it’d be very sad if we could not realize

the benefits of Quantum Computing,

like cosmetically sad. But anyway, you can’t argue with the universe and yeah you can read that article

for some skepticism. I think his name is Gil Kali,

is the mathematician. There’s some appendices but I’m going to do some demos now. Okay, the first demo is just the Doge Oracle

problem in Q sharp. So Q sharp is based on F-Sharp and we have this function

I’ve written, IsBlackBoxConstant. You’ve taken a black box

and they tell you whether it’s constant. Oh, gosh, sorry.

Here, of course. Okay. We have our function

IsBlackBoxConstant where it takes in

a black box and it just returns the Bool. Is

it constant or not? And it just uses

this same protocol we went over. It allocates two qubits, calls one input one

output, clears them, sets them both to zero,

does the preprocessing, flips them, puts them

through the Hadamard gate. Then it sends them

into the black box. Afterward, it again

put some through the Hadamard gate

and then it measures both of them and again if

the input results is one, then it’s constant

otherwise its variable. Okay? We have our black boxes defined here. So, ConstantZero. Again, remember it’s nothing. For ConstantOne we

flip the output bit. For Identity we run

a CNOT gate with input control up it is target and Negation reducing

our next, okay? And we just have these, like IsZeroConstantZero I call. Is BlackBoxConstant

with ConstantZero? And then we have

our classical driver. Any quantum computation

will have a sort of classical computer to

tell it what to do, and so I ask for each of those four,

well, what’s going on? And we can run it and it

runs on a simulator and we see the output,

IsConstantZero constant? True. ConstantOne constant? True. Identity constant? False. Negation constant? False. So there you go. Yeah we wrote the Doge article, ran it on a real

quantum simulator, you saw that it worked out. Okay, the final demo of the day and then I’ll

let you get out of here is here we go. This is called the IBM

quantum experience. There is a real like world quantum computer

that IBM has built. It only has five qubits but

they just let you online just drag gates onto this quantum circuit diagram and run it on a real

quantum computer. So I thought it’d be pretty

nifty if we demonstrated entanglement live for

you on stage. Let’s see. So, if you remember

the first thing we do is we drag a Hadamard gate onto one debt and then we use

the control not, oh no, okay. So, the way that quantum computers are

constructed you can only usually put CNOT between certain debts basically

it’s just kind of, otherwise it’s just

mechanically impossible to see. Can we do that? Nope, okay. How about, success. Okay, we did it. This is the CNOT gate. You can see varying

representations of it. It’s like the opass. And I say we’ll run it on a quantum computer, oh

right, measurement gates. I forgot. We need to add the two measurement

gates obviously. So we’re measuring both these qubits

after entangling them. And what we expect is to

see them predominantly been 0-0 and 1-1 right?

Well, let’s test it. We’ll call it that and we can save the result from cache but I want to do

it live for you guys, so I’m going to run

a new execution. And you can imagine right

now deep at IBM Research Lab nestled within

a dilution refrigerator operating at slightly

above absolute zero, we have real qubits being entangled and

measured thousands of times for our entertainment.

That’s pretty cool.>>It is.>>That’s pretty cool. Okay, let’s see if it’s, oh here we go, we

got the results. And executions

it’s pending, okay. So it might take

a couple minutes. We’re going to see now. Does anyone have

any questions while we’re waiting for this? Yes.>>I don’t know what question. You said this experiment where this sentiment tangled qubit

to space and the satellite?>>Yes.>>Are we good at storing

like qubits for a long time? I’m really surprised

they were able to do that. I thought

they kind of…>>Yeah, yeah, that

was actually a lot. They will manage to send

the entangled qubit up file laser but, yes.>>Okay.>>I don’t think

we’re that good at storing qubits for awhile. I think they’re

fairly short-lived.>>[inaudible]>>Yeah, they actually, this Chinese

satellite experiment, they teleported

a qubit up there. So they sent one EPR half up

by a laser and then they use that EPR half to teleport the qubit up there. Pretty cool.>>That’s awesome.>>Yeah.>>So we can send

entangled qubits by laser?>>You can send entangled

qubits by laser, yes.>>Okay, that’s even cool.>>Yeah. Let’s see,

it’s still not. Okay, that’s fine. Anyway, yes.>>You mentioned that there’s this new article by the mathematician that says

the noise has grown faster.>>Yes.>>What is the whole purpose of a topological quantum

computer resist that.>>Of course. Any corner computer will

have issues with noise. The topological quantum computer is supposed to be better than its IBM counterparts in terms of noise but it’ll

still grow exponentially. Like it can still

be better but it still runs into

exponential barrier. And so the next couple of years are really sort of

make or break for quantum computing because

we’ll now have the ability to create computers which run into this exponential term if

it exists, if it exists. And so we will see with

the next couple of years whether quantum computing is

really possible or not. It’s nervous and it makes

me nervous but yeah, because we’ll run into this limit probably

like this year. If Google does not manage to demonstrate

quantum supremacy it’ll be a bit scary

I guess but yeah. Let’s see, we don’t have, I’m

just going to refresh this.>>Question.>>Yes.>>Do we know what Google uses Quantum theorem

for, like what?>>What they use it for?>>Yeah.>>I don’t believe we do.

I think they just have…>>Is it experimental mostly?>>Actually no. They haven’t announced

what they use it for. My manager is actually

playing around with the D-Wave simulator to…>>The Canadian company.

Is it the Canadian company?>>D-Wave is Canadian company. Yeah, everyone out there is like really scammy

and not really quantum but everyone

kind of believes that they’re quantum but

it’s a different paradigm. It’s like optimization basically but it uses quantum computing. They have a simulator

you can use. My manager has been using it to kind of play around with

finding routes in a network. It has general applications like that. Well, this

is taking a lot.>>The data is publicly

available somewhere?>>Yeah, it’s in the invitation and I think it’ll

probably be posted on their resonant website

or posted online.>>So that application is like a requesters type

of application?>>Yeah, yeah, it’s like… It’s optimized. You’re able to express the network graph

in terms that like an optimization result

would be like the least energy path

in terms of like the least cost path

through the graph sort of. That’s different than

the way the [inaudible].>>Open Shortest Path.>>Come on, why isn’t it going? Pending. I’ll be

really sad if this doesn’t finish in time. Oh well.>>So on D-Wave, how are presentations

centered you could do classically faster than

when they were doing. So, they’ve improved in that or?>>I don’t know actually I

haven’t looked into that. They’re probably about

comparable I would say. Because given that

it’s just like optimization and especially

with the explosion of machine learning there’s been a lot of development in

making optimization better. Optimization is like you

have a surface and you’re trying to find the highest point

or the lowest point. So there’s been a lot of

research that goes into that. We’ll just run it

from cache and okay. Here we go, okay. So here’s

the results from cache. Unfortunately our real execution

didn’t finish yet but. So we see that indeed they entangled some different

qubit than ours but we end up with 0-0 and 1-1 almost exclusively but then

there are some in the middle because of

the error rate, right? So this is on

a real quantum computer. We have some error rate where it doesn’t exactly

work according to our model all the time

but pretty cool, these are entangled and they’re measured and we have that. That’s the

experimental data right there that entanglement

is a real thing. Yeah. Okay, that concludes

the presentation. Thank you very much. I hope you all feel as though you

followed the whole thing, no real confusion and feel that you could

keep on learning. This isn’t like

mad genius science. This is very accessible science. So, thank you very much.

He's so young, yet so adult at explaining and reasoning. Wow.

Are the presentation slides available?

@5:36 C programmer!!!!!

Thanks a lot!

All those "popular science" explanations that try to oversimplify are in fact just confusing even more.

doesn;t hadamard gate break the quantum coherence, and quantum computer ability to perform all operations in superposition state? I am mainly thinking of using it in the chain of perrforming multiple operations.

Very good presentation. Thanks!

quantum will never beat classical computing on all calculations, there's all kinds of physical systems we could leverage to calculating niche problems. I just dont get the hype. If you had a stack of i9's the size of a quantum computer cooled with liquid nitrogen, it would kick quantum arse. No?

Excellent video.

My Millennial colleagues really need to stop their poor habit of asking/saying "Right?" There's some use for this word when you're teaching something, but if you're in the midst of explaining one part of a larger puzzle, asking "Right" doesn't exactly help considering you can't always understand one part of the puzzle until you learn more parts of the puzzle — if that makes sense. Which is ironic, because of all things he's trying to teach Quantum Theory and its applications in Computer Science. It shouldn't be taught classically, using traditional logic at every step to qualify what's true (1) or false (0), when you DON'T KNOW THE ANSWER YET. That's literally the "black box." If you're asking "right" after explaining something that is not readily apparent using traditional logic — you should expect that the answer in the individual's mind will be "yes? no? I don't know." Which is ironic, because you shouldn't be teaching them to always apply logic to a science that has a lot of illogic in it — yet as a system of illogical subsystems, the outcome with those taken as a whole becomes logical… Assbackwards approach to teaching this, my friend. Teach them the outcome and work backwards if you expect them to 1) put together the puzzle pieces and 2) expect to understand

howthat puzzle was solved and how those puzzle pieces being such as they are, solved the larger puzzle… It's called reverse engineering. Better to teach Quantum Theory using reverse engineering, because scientists are still trying to figure out how the hell it works. Because it's still a THEORY and is actively being explored, with many unsolved paradoxes that seemingly disprove the theory's premises entirely — yet the outcomes say otherwise. So don't expect a layman to comprehend until more concepts are introduced to them. It must be explained to students, constantly, that westillcan't explain all of this perfectly because it's not a settled science (though no science is truly settled), and thus they need to roll with it sometimes. That should always be a given. If not, we will not get anywhere in terms of accelerating our scientific discovery..Wow!!! Microsoft has a Research Division? Who knew? I knew that they had a kick-ass marketing division that is without rival. And their legal department is absolutely stellar. (Or should I say quasi-legal dept?). But honestly, I thought that the only research that they did was how to steal intellectual property. This is news to me.

1:06:39 If I measure one of the entangled qubits, can someone else know when I measured it, causing their qubit to collapse? Or do they not know WHEN I measured it. If they can know, then FTL communication would be possible. You could measure qubits in short and long intervals which could be interpreted as 0's and 1's, which would enable the transfer of data.

This is excellent! This is exactly what I was looking for to gain a basic understanding.

I feel like this whole thing could have been condensed to "a quantum computer is a unitary matrix" and "the input/output is a unit vector"

With a re-turning lightsignal you can stabilize the qubit and confirm the message

Finally a real explanation of Quantum computing. Popular stupid analogies of flipping coins don't work. I am not a computer scientists and this video finally helped me understand what QC really are

I don't understand the claim that the quantum computer outperformed the classical computer because it only took 'one query', because you've added another input and output. Isn't that 'equivalent' in some sense as the cost of a second query?

It was hard to follow for me but my interest in this has grown due to this. I did run through this multiple times before it started making sense. I am still not 100% there but getting there. QC is really cool. I love it. Nature is so weird and wonderful. This was a great video. Thanks!

For anyone else stumbling upon this, here's the slides

https://www.microsoft.com/en-us/research/uploads/prod/2018/05/40655.compressed.pdf

How are the qbits coordinating when they have 50-50% chance of collapsing to 00 or 11 ? 59:56

The shit you end up on after youtube autoplay

I'm 16 and I think I know what I want to do know….

nice talk, but he should stick to the computing part and leave the physics to the xperts (especially around 1hr in +- a couple of minutes) … What he calls "coordination" and claims to have no term yet due to language limitations is actually called "causality"… And Bell's theorem does not do away with locality but with local realism! Huge difference! I could go on here, but I dont want to bring in negativity to a topic and effort worth applauding.

I suppose it's a good thing, physicists don't watch 90mins videos with "for computer scientists" in the title ^^ otherwise the comment section probably would look somewhat different^^

Would have been nice to be able to see the slides the whole time

2 Questions:

1. How do we interpret the probabilities if we allow complex numbers? For example, if the spin of particle is in a superposition represented by (√2/2) + (√2/2)i, what will we expect to see when we make a measurement?

2. How does this model deal with more than 2 q-bits? Would an n-qubit system be represented by a vector of length n for each q-bit, or of length 2^n for each possible binary string of length n?

Did Google ever achieve quantum supremacy or did Huawei do it instead?

In reference to the confusion in 43:14 regarding naming confusion. Just wondering, is this confusion typical because traditionally, as you mentioned earlier, in a classical computer, you change the variable. Hence the variable wire changes from "input" to "output". However, in the quantum world, the variable stays in place while you change the program. Hence, the wire, which represents a variable instead of a function, is always called the output wire or the input wire. I wonder if it is this shift in perspective that causes the confusion?

This is simply pure fucking gold! Thanks!

he’s hot. would love to be in superposition with this dude.

This is exactly what i wanted . Thank you so much

İ want quantum girls 😍😌

I'd like to see things like human choice shown as a Qbit in a superposition (Do/Do Not) until the physical action occurs which is the collapsed stated. I think this kind of thinking is going to revolutionize our way of thinking let alone our way of computing.

43:24 I think the output input thing could be more easily understood by C programmers, since we have the concept of returning through parameters.

1:10:07 The guy is questioning whether or not superposition actually exists. Is the probabilities due to the fact that we have imprecise tools that cannot observe the particles, or are the particles actually in multiple states in the same time? Copenhagen interpretation says that particles truly are in multiple positions at the same time, and alternative theories like pilot wave theory says that there are things that exist, that we cannot precisely measure. (I don't know if the math behind pilot wave theory has been fully worked out yet)

9:55 "…only use operations that are their own inverses"

He is wrong there, the phase shift gate S being a counterexample.

So teleportation scrolls were real

Ok… if I have 2 qubits and I entangle the qubits they can be in a state of either entangled or not 1 or 0. If I take the qubits and I separate them I now have 2 qubits and they are apart. I use a robot to push a button if the qubit is not entangled any more. If I wanted the robot to push the button I would measure the one qubit and the other one would collapse making the button get pushed. How is not a transfer of information.

Problem with computer scientists, they like to disregard physics lol

One of the most amazing explanation on Quantum Computing. 😃😃

How long does that drink last?

I think it would help in the Black Box problem to draw the CNOT gate as having 2 inputs and 2 outputs so the fact that it changes the input makes more sense.

nice tutorial, thanks a lot.

What if I use two input bits in a classical computer, one is always zero as in QC, other one as 1:

Const 1 -> 11

Const 0 -> 00

Identity -> 10

Negation -> 01

Then use XOR gate on the output I will get 0 for constant functions and 1 for variable functions in one query. And since QC was allowed to use 2 qbits in the problem, I think it is fair to give CC that much if we are comparing them.Where is the speed up we are talking about ?

33:00 i'll be back to watch this later

1:06:45 So does this mean that I physically separate two entangled qubits, run some operation on one (so that its probability of returning 0 or 1 changes) and then if I collapse the one qubit the second qubits' probability will get updated "somehow"?

Actually As I understand quantum computing is just a different concept of laying/extracting bits using schrödingers state function?? With a bit of advancement and time I think we can reflect and implement those Qbits principles onto the current classic computing?

Any slack Chanel for course?

Polarization could also be a classical phenomenon once you say ‘photons’ it becomes a quantum phenomenon:)

Great video but don’t you think opening parallel gates to other worlds is a bit much just to play minesweeper 10,000x slower than my Commodore 64?

This is supposed to be for scientists, but it's the video from which I learned the most of Q.C. out of them all. All other videos are just barely understandable analogies. And I'm not a scientis, nor a programmer.

Dude should drink his beer from a glass instead of a can. Low class.

The whole discussion on the deutsch oracle (36:00) would be much clearer if he finished the arrows and adapted his termology: how must we interpret a system where ‘output’ goes in and ‘input’ comes out?

At only 32 minutes in, things are already SO much CLEARER! Thank you for making this!

Your ability to make predictions is increased by exponential levels when you have Quantum Computing Technology.

"Does any one have any questions about this?

0.13 seconds laterGood!"This was actually awesome! Thanks a lot.

The observation that all metaphors ring wrong for describing quantum algorithms bothered me for a while as well (3:40) however shutup and calculate is bothering in its own way 🙂

good vid, thanks. maybe some animation in slides would help

well, but two people can coordinate, like that they start a spaceship to meet in the middle faster than light

hey I saw a Sun jacket. This guy must be a employee of Sun.

@38:54 The teacher himself didn't understand it clearly! It's obvious!

25:27 is world-shattering. So quantum physics is not just, naively, "all possibilities are realized", it's "all collectively reversible possibilities are realized"?

So for clarification, the constraints of the Deutsch oracle problem allow there to be usage of multiple bits? It's not required that there is just a single bit used for a classical single bit operation as per the constraints of the problem?

Hi I have a question. For the 4 operations, the preprocessing was done, with the assumption that both starts with both values as 0. However when we were solving for variable, X, the preprocessing was applied from the starting point of 0. But X is not 0, right? Shouldn't the preprocessing have started from somewhere else?

Hope to find out what he means by neutralising the difference within the categories, and magnifying the difference between them. What are the categories he is referring to? How can I tell it is neutralised, how can I tell it is magnified?

When you have n qbits that are being represented with a single vector through an n-fold tensor product of the product states, there are probabilities for the system to collapse with a 1 at one of the 2^n numbers in the vector. How does this n-qbit system collapse? Can all qbits be measured at once, are they required to be measured all at once? And what does the 1 in the product state represent? With a single qbit, there are probabilities for collapsing to 1 and collapsing to 0. What do the probabilities correspond to with a larger product state of multiple qbits?

Watching this 15 months after upload. Anyone know if Google has reached "quantum supremacy" i.e. do we know if the resulting noise makes the quantum computer unusable?

Can someone tell me why the dirac vector 10 was equivalent to 2 around 12:30

55:13 “…Exponential speed up, huh?! Exponential speed up.”

At 1:00:00, using entanglement for communication is possible in one case that I can think of. If I take a Q-bit, which is entangled to my friend's Q-bit. imagine me traveling to some far place. I tell my friend that if the Q-bit collapses to 1, then perform task A. And if it collapses to 0, then perform task B. And I would know which task he performed because of the Q-bit that I have. This is communication even though I don't send information implicitly…what do u guys think…?

richard spencer cuts the bug-oisie popsci garbage and hatefacts you with quantum identity

Quantum Supremacy – still as far in the future as ever. What the last year has shown is that the scaling problem is far larger than anyone had anticipated, and by implication, perhaps the foundation expectations of quantum computing may be flawed – if not impossible.

Great intro to quantum programming, but the tangent at the end gives false information. Bell's inequality proved that there can be no hidden variable theory only under the assumption that the universe is local. The later discovery of quantum entanglement showed that Bell's inequality actually was proof that all theories must be non-local. Hidden variable theories are NOT disproved by Bell's inequality, they merely fell out of popularity after the initial misinterpretation of Bell's inequality. Bohmian mechanics is a perfect example of a hidden variable theory that is consistent with all known quantum mechanical experiments thus far.

Bell's inequality proves that there aren't hidden binary variables but it still doesn't prove there is any "teleportation" or "spooky action at a distance", you just collapse the wave and measure the same state both sides 100% of the time. Nothing was teleported, we just can't explain this action with binary variables which is quite normal because we are measuring quantum particles not tennis balls.

There is no way to entangle q-bits if they weren't created from the same particle before. The fact that there aren't binary hidden variables doesn't mean they are being teleported faster than the speed of light. You need to entangle the particles before. No magic happening just quantum mechanics

Honestly the usage of the word "teleportation" should be banned from QM. Let's keep this term for Star Trek. There is NO INFORMATION TELEPORTED, Alice and Bob have random results, they need to communicate via normal channel about the operation they performed on the q-bit to have the same sequence of bits, this is not clear in this presentation. No need of mystification of quantum physics with Teleportation, flying saucers, time travel, flying fairies and unicorns

In the Teleportation slide where the output is psi after the operator X or Z is applied there is a very important piece of information missing. Bob needs to know what operator is valid to have the correct sequence. Thus there is NO TELEPORTATION

0 & 1, meaning the symbolism used representing female and male principle. How dare you! The outer "glow" surrounding the earth is been as if a lockdown surrounding the earth. Fools. 1619-2019 🙂 Yeah. Live with the knowledge that your mathematical equations have always been about minimizing what is universally available to us all. Good luck in your endeavors. Your time is short! 🙂

@18:24, the use of negative numbers, meaning minimizing the value of the whole. Fkrs.

Quantum weirdness. Yeah. You said it.

Clue: How we manipulate them….

If I write a SQL query that does the filter before the join, I can get a tremendous speedup in processing. Isn't the pre-processing you do for Deutsch-Jozsa the same sort of thing? How is this considered a fundemental accelleration of processing?

Holy sh*t.. The audience is not buying his weasel words – they are obviously not afraid to ask the most obvious question. If I have an "entangled coin" and split it, and separate the two halves by great distances.. Why is it so amazing that measuring one half reveals "tails"? Wow!

faster than the speed of lightthe other half is "heads"? Seriously? How much money are they scamming for this snake oil? LolThanks for the vid. A lot of good info here.

If anyone wants more detail on exactly how the teleportation process works, check out this other vid:

https://www.youtube.com/watch?v=3HiYm9SB-xU

A tree that falls in the forest with nobody listening, still makes a sound.

Pretty nifty.

1:05:54 If it's not collapse, measurement will make it collapse. If it's already collapsed, measurement will make known the already collapsed state.

Communication ~= transport the qbit

Coordination ~= collapse at both end

21:10

Raises handyeah i'll be back after i take like a million pre-req courses….i barely understand heaviside step functions and am a psych major lololol

A REALLY helpful lecture!

Hi. Could you explain?

45:58

We have BB, which realises identity function. But also we have "No-cloning theorem". Is it posible to construct that BB in physical world?

Supremacy achieved. Kinda.

At 40:23, the real confusion is labelling an Input as Output which makes no sense. I can see that it's related to the Output' in the same way that Input is related to Input', but someone really needs to think of a better way to name these things so it's not so confusing.

Spoiler: google demonstrated quantum supremacy in 2019

Thanks for the video!

Great Video! I have looked at various articles and videos online which described pieces (generally confusing) of the quantum computing puzzle. This brought it all together and I now feel I have a solid basis to go further.

1:11:56 if Alice has to measure A and T then send the results of those measurements to B so that bob can collapse the system forcing teleportation, why couldn't Alice just collapse the system from her end?

As far as I know the decoherence can be initiated from either alice's or bob's particle. Why Should bob be the one to collapse the wave function if Alice has everything needed to measure and collapse the system to enable teleportation?

Any videos or links about more stuff like this, please? The video is extremely simple made and clear. Very well done, thanks for that!

This presentation was pretty nifty!

At last there is someone who can tell us what really can be done, the Hello World! Thanks

Google had managed to demonstrate quantum supremacy, good news for you! 1:24:45

This is the best explantation / introduction of QC I've seen, and indeed very well targeted at computer scientists. Thanks for that.