Quantum Computing for Computer Scientists

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

Channel: Microsoft Research

Views: 276,116

Rating: 4.9061756 out of 5

Keywords: microsoft research

Id: F_Riqjdh2oM

Length: 88min 22sec (5302 seconds)

Published: Mon May 14 2018

Reddit Comments

[u/Nathanfenner]

Here are the slides [pdf] since the video seems to do a bad job of actually showing them.

[u/curious_s]

watched the whole thing, fascinating...

​

my head hurts.

[u/Darksonn]

That's a pretty decent talk.