Quantum Computing for Computer Scientists

Welcome to Quantum Computing for Computer Scientists. Happy Valentines Day. We will learn about the most romantic topic of all: Quantum Computing. This is a talk aimed at Computer Scientists. We won't go over much, if any, physics during this talk. We will not opt ​​for the double slit experiment or the uncertainty principle. We're not learning about any of that. We're going to cover the

computing

model that everyone will find, I think quite intuitive, is a state machine. And we'll run a

quantum

algorithm on it, show that it outperforms a classical

computing

model, and then finish with some demonstrations, including a program running in Q-sharp, Microsoft's

quantum

language.

This is the gate model of quantum computing. It's a lot like the classical computing model where you have bits, you send them through logic gates, and you apply transformations to them. There is another computing model called quantum annealing model that uses D-Wave, if you've heard of it. That's a little different from what we'll see 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 you all have your reasons for being here, but here are three reasons I can think of if you need a little more convincing as to why you should learn Quantum Computing.

The first is that quantum supremacy is expected this year, this very year. Quantum supremacy means that we have a real problem running on a real quantum

computer

that, in real time, runs faster than the same problem on a classical

computer

. So, Google has announced that it believes it will do so this year. If they do, it's a really big thing. Then, it could be in your future. Who knows? Within five or ten years we could all be running some really complicated problems on quantum computers. So we have a lot of big companies, Microsoft, Google, Intel, IBM, they're all investing billions of dollars in quantum computer developments.

There are many really interesting applications. This is the algorithm that everyone has heard of: Shor's algorithm. When this article came out, it set the world on fire. People were saying, "Wow, quantum computers could have a real economic impact." We could factor RSA and undermine our global financial system, which is pretty cool. Here's one that I think programmers will appreciate: we can search an unordered list by square root N times. So, think that for an unordered list, you have to check each element. That's ON. You can get a good speedup, just square root n queries on a quantum computer, which is quite, quite clever and generally useful.

And this is the one that, in my opinion, probably has the greatest chance of changing the world. Sorry, programmers scroll and search probably not too much. That is, we could have an exponential acceleration in the simulation of quantum mechanical systems. So things like drug design, if you simulate the interaction of biological molecules, things like that, could greatly accelerate a lot of our biological research, and everyone talks about nitrogen fixation for this. That's part of Microsoft's main selling point. But this is the one that really motivated me, the one below, which I think by talking to a couple of you before the presentation, we can motivate you as well.

It's intellectually interesting and it's interesting because it's outside of my intuition. I think all of us, at this point in our careers, can basically look at any digital or mechanical system and have a rough idea of ​​how it works, right? But if you look at a quantum computer, how can a quantum computer outperform classical computing? It does not make any sense. As if there was no way I could even begin 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 getting a little philosophical.

But our language, our informal language that we use, developed in a very classical world. It's simply not equipped to deal with the quantum world, and that's why any popular science article you've read about quantum phenomena doesn't ring true. All the metaphors don't really make sense because we're trying to express them in this language that takes place in the classical world. We need to learn a new language, which is the language of mathematics, and the only thing that will really allow us to understand quantum mechanics is to learn it mathematically. All the metaphors and analogies will lead you astray.

There's a famous quote here from a physicist named David Mermin which is "Shut up and calculate," regarding quantum mechanics. So some graduate students, maybe they sit back in his chair and say, “Oh, what does all this mean?” Shut up and calculate. Just trust the math. Mathematics is the only thing that won't lead you astray. Well, here's how this presentation will break down. First, we will learn to represent computation using super basic linear algebra, matrices, vectors, and matrix multiplication. We will then generalize that to learn about Qubits, superposition, and quantum logic gates. And finally, we'll use all those tools we've developed to go over the simplest problem where a quantum computer outperforms a classical computer.

This is called the Deutsche Oracle problem. I mean, there are many problems, but this is the simplest. And finally, it will almost be remiss to let you leave here without learning about quantum entanglement and teleportation just because with the tools that we will develop, they are very easy to understand. So, I'll have additional tracks and then we'll have some demos. Alright, let's get to it. You will become very familiar with these two vectors. This is how we represent a 0 and a 1, the two values ​​of a bit in classical terms. So the top one is just 1 over 0, and the bottom one is just 0 over 1.

You can also write them between those weird angle brackets. This is called Dirac vector notation. So you have a zero there. That means this is the value of that vector. If you're having trouble remembering this, think of it as an array indexed from 0, so there is a 1 at index 0, which means it's a zero. There is a 1 in the first index, that means it is a 1. Okay, is everyone okay with this? You will be very familiar with this by the end of the presentation. Let's go over matrix multiplication very quickly. So the way to think about matrix multiplication, just to review it.

Most of you will have gone over this in your Linear Algebra courses on the first day or two. So if we have a matrix multiplied by a vector, you take this horizontal row, then you flip it over and multiply it pointwise with these vector values. So, a times x, b times y, and that's how you get the one above. And you do the same in the bottom row. C times x, d times y, and you get two vectors. The same thing happens with the 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. We won't really do much of that. And there is a very special matrix called the Identity Matrix that has zeros everywhere except ones along the main diagonal, and anything multiplied by the Identity Matrix is ​​itself. It's like multiplying by 1. In fact, you usually refer to the Identity Matrix with the symbol 1. Now, fortunately, for simplicity, many of the matrices we'll use look a lot like this one. They're mostly 0's with just a few 1's, and you might notice that it's a good rule of thumb that relative to the identity matrix, this matrix has the middle two rows reversed, okay?

And that is actually the action it has on everything that multiplies. Then, flip the middle two rows. It's a good rule of thumb to remember how matrix multiplication works. Does anyone have a problem with this? Because you really need to know this in order to move forward. You have to know it. Good, excellent. In reality, the operations are. I would like to make this a quiz. Can anyone tell me what are the four operations on one bit? There are four of them. A little. A little. AND, OR, exclusive-or. That's about two bits. No identity. Identity no.

Set to 0, set to 1. Set 0, set 1. Here we go. Good. Yes. So, we have identity, only f of x is equal to x. The negation fx is equal to not x. Constant-0, is always set to 0. Constant-1, is always set to 1. You can see with a diagram what it looks like, okay? And we can write them as arrays. So identity is just the Identity Matrix. Remember this is our zero symbol. The identity multiplied by 0 is 0. The identity multiplied by 1 is 1. Here is the negation. You change it from 0 to 1 and from 1 to 0. Same for constant-0, constant-1. So, I hope I've convinced you that we can represent very simple functions at least, with matrices multiplied by our vectors 0 and 1, okay?

And remember these four functions because I will ask you about them later. They will rise again. So, let's talk about Reversible Computing. Reversible computing is kind of a buzzword. If you've read the popular science fiction book Accelerando, it talks about Reversible Computing, and it basically means that if I tell you the operation I did and the result of that operation, you can always know the input of that operation, if the operation is reversible. So, intuitively, operations that simply mix bits, such as permuting them, are reversible. But operations that erase bits and then overwrite them are not reversible.

And on our previous slide, identity and negation are reversible because I say the output is one and I put it through the door of negation. That means the input was zero. You can always say that. But if I say the output was 1 and subject it to the constant-1 operation, you can't tell what the input was. It is not reversible. Delete information. And the good thing about Quantum Computing, as you may remember, is that one of the computers only uses reversible operations. Those are the only ones we care about. So the only operation we really care about on this slide is really negation.

As well as identity but it is the same as doing nothing. Another fun fact about chronic computers is that they actually only use operations that are their own inverses. Therefore, not only are they reversible, but if you apply them twice you will get the same input value. And let's get into it a little bit, this is like getting into popular science, but whatever. There is something called the Von Neumann Vander limit, which is the smallest amount of energy that physicists have calculated is necessary for the simplest possible calculation, and which is not reversible. And reversible computing could eventually lead us to go beyond that limit, being more efficient than that theoretical limit.

Currently, processors need millions of times more energy than the Von Neumann Vander limit but, you know, in 5,000 years, who knows? Pretty clever. Alright. This is something you probably didn't go over in linear algebra, but don't worry, it's still pretty simple. It is called the tensor product. So if you have the tensor product of two vectors, it's like you take the second vector and tile it for each element of the first vector. So, X0 gets its own copy and X1 gets its own copy. And then you multiply it to eventually get X0, Y0, X0, Y1, etcetera. It may be easier to see this with real numbers.

Here we have one times three, one times four, two times three and two times four to get this. This is what it looks like with three vectors. You get this as a giant array. Don't worry too much about that. And I would like to point out that if we use R0 and one values, we will end up with a vector that has a one in only one position. Well. Does anyone have any real problems with this concept? If I gave you two vectors you could probably calculate the tensor product. It's not at all difficult. Alright. But, the animated endpoint leads to how do we represent multiple classical bits?

And we represent them by their tensor product. So 00 remember we have 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 times 0, 0, 1 times 1, 1. One times 0, 0. Good. And 11 is the state of this product and, similar to a single bit, you can think of it as an index into this vector array. So this is 0. There is a one at the zero position. This is one. There is a value with the first position that comes from zero and this is two values ​​of the second position, three values ​​of the third position.

This is the only time I will strain three pieces together, fortunately, because they form humus. They grow exponentially in size but this is what it works for. So four is 100 and 01234 is where the bit is. Well. Yes. So we call this product status. We can always factor it into its individual states and the state of the n-bit product is a vector of size two to the power n. Here we see a kind of whisper about the power of quantum computing in this exponential term, but if we hold that thought, we will come back to it. So, we are going to learn a very important, very fundamental operationfor reversible computing and quantum computing it is called CNOT or conditional non-computing.

It operates with a couple of bits. You designate one bit, the control bit, and the other bit is the destination bit. So the control bit, if one, inverts the target bit. If it is zero, it leaves the destination bit alone and the control bit is always left alone. So if we have the most significant bit of a 2-bit system as a control, the least significant bit is the target, then 00, since this is the most significant bit, is the target bit, and it just goes to 00, 01 goes to 01. Now, 10, since the control bit is one, is assigned to 11 because it inverts the other bit, and 11, since it is inverted again, the target bit goes to 10.

And this array, you can actually write it, you see what there is. kind of a correspondence here we have Flipping the bottom two rows, which is the identity matrix, and this thing that I state and that I will show in the next two slides, will change the states of our product according to the semantics of CNOT. So does everyone understand the semantics here? We have a control bit and a destination bit, control bit one, we invert the other bit. Fairly good? Now, this is a lot of math, but don't panic, we'll go through it step by step.

If we apply the CNOT gate to 10, remember this is the control bit, so we're going to invert the other bits, so we expect it to go to 11. Now, let's expand this step by step. . So, 10 corresponds to this tensor product. This is the matrix from the previous slide and we are applying it to the state of our product. Remember, you're just going to flip the bottom two rows to get to this product state, which when we factor it, it actually gives us 11. Now, let's do it with 11, same thing, we have our familiar matrix, multiply by We get to this product state, which we factor by 10.

So I hope I've convinced you at this point that we can use matrices to represent more interesting logical operations than just inverting a bit. Has anyone finally done it? Is that factorization always possible or practical for larger vectors? It's practical, yes. It's not always possible, something we'll get into when we get into quantum entanglement, basically, but it's a good question. So is this okay for everyone? Doesn't anyone get lost in the gigantic equations here? Well. So we're going to go from 10, or sorry, 00. So the control bit 0 means we're going to leave the other bit alone, right?

And we see that this is indeed what we do and the same with 01. Good. So everyone, well, maybe you're familiar with how classical computers are like real CPUs, they're all built on some kind of NAND gate, like everything is fundamentally built on NAND and CNOT is some kind of analog NAND for reversible computing. . It's like a really basic thing that you use to build bigger, more complicated logical statements. So I'm sure that if I gave you a task, like building some more complicated logic formula with CNOT, you could probably do it at this point, you just have to put them all together and it eventually comes out.

I note that it is not actually universal. Not all logic functions can be performed with the CNOT gate. You need something called a Toffoli Gate, but we won't look at it in this presentation. And we've learned everything we need to know about how to use linear algebra to represent classical computing, and now we can move on to quantum computing. So, to summarize, we learned that we can represent classical bits in vector form: 10 for 0 and 01 for 1. We can represent operations on bits by multiplications of their bit vectors. We know that quantum computers only use reversible operations and in fact the operations are their own inverses and multi-bit states, we write is the tensor product of our single-bit states.

Finally, I learned about CNOT, which is a fundamental gateway in reversible computing and quantum computing. So is everyone following us so far? This is pretty simple, right? And it's not that bad. Well. Let's take the leap, qbits. And I'll surprise you: we've actually learned to use qbits all along. Cbits are just special cases of qbits. And we represent the qbit in general by a two-element vector a, b where a and b are complex numbers. Don't worry. We will only use real numbers for this presentation. We'll keep it simple. Using only real numbers. And we have the restriction 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 that you will become very familiar with. It's one over root two, one over root two. Can anyone tell me what one over the root of two squared is? Half. Half exactly. half plus half is one. So this is a qbit. What about the half and root of three divided by two? How much is half squared? Quarter. So, one quarter plus three quarters is one. Here's something interesting.

In fact, we can now use negative numbers 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 the same as this first array, but one of the values ​​is negative. Good looking. Not bad so far, right? Okay, but you could say that this is like saying that a qbit has a value that is neither zero nor one, but zero and one at the same time. This is called overlap. Everyone has probably heard that Schrödinger's cat is dead and alive. It's like a popular science the way this concept is articulated.

And the interesting thing about a qbit being in superposition is that it means that we can, I really want to qualify this kind of calculation with the values ​​of zero and one at the same time, which again is kind of a whisper of something quantum. acceleration power. Well? Now, how this works is that 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 calculation to get the final result. We send it through the measuring gate, see what the result is.

So how probability works is that if you have a value (a, b), it collapses to zero with probability a squared and one with probability b squared. So if we look at our familiar qbit from the previous slide, one over root two, one over root two, has half the chance of collapsing to zero and half the chance of collapsing to one. It's like flipping a coin. Now, if we simply measure our classical qbit, our classical cbits (1,0) have a 100 percent chance of collapsing to zero, and (0, 1) have a 100 percent chance of collapsing to one. So, it's kind of an article put that way.

And I found it helpful to give people a kind of physical intuition about what we're doing, what a bit or a qbit is. If you've heard of polarization, you've probably bought stylish sunglasses, it says they are polarized. So polarization is actually a kind of quantum phenomenon. You can polarize this way or this way, and your glasses will only polarize a certain way, so basically just let polarized light pass through this way. It turns out that qbits, you can think of this, yes, a photon polarized this way is a zero, and a photon polarized this way is a one.

The overlap means it's actually like both, right? So you could actually go through both gradients. And then if you measure it, and one way to measure it is to just shoot it through a grate and see if it passes, then you can collapse it to zero or one. So, that's our intuition that attributes this to a physical concept. Of course, nowadays, we find that photons actually produce very, very poor qbits, they tend to collapse easily. So we didn't use them, but maybe you can think about that. Does anyone really have any confusion here about how this probability of measurement process collapse works?

Good, excellent. We will learn about multiple qbits. The same goes for various cbits. We represent them by the tensor product. Why is he doing that? Okay, wait, laser pointer. Well, here we go. No, that's not it. Well. So if we have two qbits and we multiply them, the sum of squares identity actually holds. And so, if we consider our perfectly balanced 50 percent coin flip qbit. And we tension with another qbit by flipping a coin, we get these four vectors with one half in each column, and the half squared is, of course, a quarter. So a quarter plus a quarter plus a quarter plus a quarter is one.

This maintains ownership. And the way to read this is that when these two qbits are measured, it has a quarter chance of collapsing into (0, 0), (0, 1), (1, 0) and (1,1). This is kind of the probability that when you measure it, you'll find a one there and a zero everywhere else. So we might find that there is a one-quarter chance of finding one in this position and all zeros elsewhere. Does that make sense for multiple qbits? Good, excellent. You are just moving forward and there is no problem. It should be very easy. Yeah? I have a question. Absolutely. So there will only be one left in the vector?

Yes. Couldn't there be two? It couldn't be two because that would actually violate our constraint that a squared plus b squared equals one. Okay. But yeah, after the measurement there will only be one, one here in this vector of four, which we can then factor into two bits. Well. Yeah? Do you also find the collapse for that longer vector? Yes, yes. So if you measure these two qbits at once, you can think of this product state vector as collapsing. And that's simply the probability of finding a one here and a zero anywhere else. It will be useful in the future when we can't factor the state of the product, but that's anyway.

Well. How about operations on qbits? We have these qbits, how do we actually manipulate them? The same thing we do with classic bits. And all the matrix operators we have learned also work with qbits. So, for example, denial. If we have our qbit that has a 25 percent chance of collapsing to zero, a 75 percent chance of collapsing to one, if we run it through the bit flipping operator, it now has a 75 percent chance of collapsing. to zero and a 25 percent chance of collapsing into one. So we can manipulate these probabilities, actually called amplitudes, with gates. And you can think of doors, they correspond to a device that

scientists

have created that is like manipulating the qbits with a gentle touch.

Not enough to collapse them, but enough to change their state. Very good. And there are also a couple of important matrix operators, which we haven't learned yet because they really only make sense in the quantum context. Okay, everything is fine. We're ok. Then the most important is the Hadamard gate. And what it does is it takes a zero qbit or one bit and it takes it to the coin flip state where it's exactly in equal superposition. The matrix looks like this. It's one over root two in every entry, except for a negative in the lower 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, minus one over two. Good looking. So, that's how we get to the overlap. We use the Hadamard device, which

scientists

have developed, and we can get a lot of use out of it. So, question 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 top of a larger provision. I don't know exactly why, but it's 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 be assigned the same value and it wouldn't be reversible. So, we need this negative sign. If right. Well. Question. Yes? Overlay review, what exactly does that mean? Overlay, yes. So superposition means that a qbit is in both zero and one states at the same time. Okay. And I want to make something very clear here. This doesn't mean that the qbit is secretly zero or secretly one, and we don't know. It means that it is actually in both at the same time, this is simply quantum weirdness.

This is exactly 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, it looks like we have different values ​​but they conceptually represent the same thing. Correct. So this comes down to the distinction between the quantum and classical world. That is, from the classical perspective, these two qbits are the same. Both have a 50 percent chance of collapsing to zero or one.

But, if we stay within the quantum realm, this sign information is preserved as long as we do not measure it, and it can affect our calculations. So it's a 50-50 chance, but do you have a feeling it used to be one? Do you have the feelingWe know they occur at the same time. With the 2013 experiment, she entangled the qubits and separated them a lot. 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 in that moment, that space or whatever, you can't really say that this was happening with probability. Half. Yes. You're wondering, okay, they could have decided beforehand, for example, maybe or. Yes, or probably the probability language itself is not active. It works. Probability works, I mean, it's just that the amplitude squared gives you the classic probability of it collapsing to zero or one, I guess. I'm not 100 percent sure what you mean, so. So, once we have observed the question, we rationalize. Once observed then we rationalize, yes. And then if we do the experiment many times, we see that there is about a 50 percent chance that both are zero or both are one.

In fact, I'll show you live on a quantum computer that we do that, okay. Alright, let's move on to teleportation. This is the actual use you asked about and you've probably read about quantum teleportation again in popular science articles. Needless to say, his explanation was complete rubbish, it didn't make any sense, but now it will make sense to you, okay? It is the process by which we take an arbitrary qubit state and transfer it through space and time to another location. So, entangled qubits are used as a kind of bridge to send a qubit from one place to another.

And here is something very important: it is called the non-cloning theorem. You can transfer qubit states so you can cut and paste them, but you can't copy them, you can't copy and paste a qubit state, you can't clone it. This is called the no-cloning theorem. It's actually quite easy to show that any operation outside of this type would be neither reversible nor inverse, but we're not going to do that. And here is an important thing: teleportation, despite using a faster-than-light entanglement phenomenon, is not in itself the entire protocol, it is not in itself faster than light for communication because you actually have to exchange two classic bits.

So if I teleport my qubit to you in addition to the fact that we have a pair of entangled qubits, I also have to send you two bits of information and we'll show you why on the next slide. So does everyone conceptually understand the purpose of quantum teleportation? Well. So, this is what the circuit looks like. We're not going to go over the math, there are appendices in this slideshow that you can look at after class to go over the math, but it gets a little complicated, so we won't do it. So we have the qubit that we want to teleport here, we call it T and its value is phi, but this generic qubit value can be any value.

And then we have these two qubits A and B, both initialized to zero. Now you will remember that this is the entanglement circuit. So these two qubits are entangled, okay? Now that they're tangled, we'll say we have Alice and Bob. Alice wants to send the entangled qubit to Bob. So, Alice has these two qubits, Bob has this qubit. And these two qubits are entangled. So qubits are like these two qubits separate right after they get entangled, basically. Now, Alice entangles her qubit that she wants to teleport with the other two qubits. So it's an entangled system of three qubits.

If you were to write the state of the product, you couldn't decompose it into three qubits. Then pass this qubit through the Hadamard gate. Finally, Alice measures both qubits that she possesses 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-inverting gate. And the measurement result of this qubit controls whether Bob has to run this qubit through a new type of gate that we haven't seen before is called a phase reversal or Z gate and this is what the array looks like.

And basically, once Bob has applied those two gates or neither, if they both end up being zero, Bob doesn't have to apply anything, he'll sort of magically end up with the value of Alice's qubit that she wants to teleport. Pretty clever. And you might say that while we're already exchanging a qubit here, why do we care that we're obviously just giving Bob a qubit? Can't Alice just give him a qubit right there? So what you can do is pre-entangle a bunch of qubits, a few billion qubits or something like that. And then you mail them and they're called EPR halves.

You send them by mail or something so that Alice and Bob have a big repository of these entangled qubits, and then whenever Alice wants to send a qubit to Bob, she can use one of the EPR pairs. And at that point, that collapsed EPR pair can no longer be used, making it a non-renewable resource. But Alice can send as many qubits as she wants to Bob. Well? Now, you might be saying, "Well, I don't really understand this." The math is in the appendix if you really want to see it. It gets pretty complicated, but I think I did a good job of explaining it.

Okay, you might say, “Okay.” Oh, by the way, I forgot to say something really important. You may have heard that we can simulate quantum computers on a classical computer, but it requires exponential slowdown or exponential memory. This is why, if two qubits become entangled, their full product state needs to be maintained. So if N qubit gets entangled, you have a vector of size two to the power of N that you have to keep in memory. And that's why exponential memory is needed to simulate a quantum computer on a classical computer. Pretty clever, alright. So you might think, "Okay, this is all pretty interesting, additional learning objectives." You can learn the Deutsch-Jozsa algorithm, which is the one with N bits that I talked about, and also the Simon periodicity problem, which is another one;

I discovered some properties of this function. We're not going to talk about the complexity, but anyway you can also learn Shor's algorithm, Grover's algorithm, quantum cryptographic key exchange, that one is actually quite simple. I recommend watching it. You can learn how they are actually implemented in physical terms, if that matters to you. One important thing is quantum error correction, since these systems are as small as a spare cosmic gray that could come out of nowhere and ruin the entire calculation, very, very strict error correction schemes are needed. So I think in theory you need five physical qubits for a single logical qubit as we've been operating it.

In practice, it looks more like we'll need a hundred or two hundred to get a qubit with 100 percent probability, as we've been practically using. That's something to keep in mind. When we see Google launch a 30-qubit computer, that may not mean as much as we expected. We've only created types like two or three very high quality qubits. And also quantum programming language design, which I'll go over because I'll show you an example from Q Sharp, but anyway, recommended textbooks. This is my absolute favorite, it has the same title, it has the name of the talk, Quantum Computing for Computer Scientists.

This algorithm is from our friend David Mermin, the guy who shuts up and calculates. It's a meat grinder textbook, but I started with this one. It was horrible, it was like that, but it basically skipped a lot of steps. It is a more symbolic manipulation. You won't see as many vectors and matrices. I like to write the vectors and matrices to see what happens, which gets really unwieldy when you write as a 64 by 64 vector or matrix. But I like to have both. So I'm going to use this to fill in the gaps with this. This has more interesting sides and things like that.

This is also in the MS library. There is another one called Quantum Computing Gentle Interaction, also in the MS library. I've heard mixed to semi-decent reviews about it. I haven't looked at it myself. There is also a mix of quantum development kit. They have the documents. They're actually a pretty good thing called Quantum Computing Simulator and Q Sharp, as we'll see. Now, I said I would end the talk with some skepticism because there is an article that I think came out recently in Quantum magazine, quite prominent, an interview with a mathematician who believes that physically realizable quantum computers cannot exist.

His basic simplifying argument is that the amount of noise in the system grows exponentially with the number of qubits. So we can't get a really big qubit system because our calculation will keep collapsing in the middle and it's like an exponential term. And so, I will be very sad if this happens. I would feel like the universe is against me. It would be really very sad if we could not realize the benefits of Quantum Computing, something aesthetically sad. But anyway, you can't argue with the universe and yes, you can read that article for some skepticism. I think his name is Gil Kali, he is the mathematician.

There are some appendices but now I'm going to do some demonstrations. Well, the first proof is just the Doge Oracle problem in Q sharp. So Q sharp is based on F-Sharp and we have this function that I wrote, IsBlackBoxConstant. You have taken a black box and they tell you if it is constant. Oh my god, I'm sorry. Here, of course. Well. We have our IsBlackBoxConstant function where it takes a black box and simply returns the Bool. Is it constant or not? And it just uses the same protocol that we went over. It assigns two qubits, calls an input and an output, clears them, sets them to zero, does preprocessing, flips them, and passes them through the Hadamard gate.

Then he sends them to the black box. Then you pass something through the Hadamard gate again and then measure them both and again if the input result is one then it is constant else it is variable. Well? We have our black boxes defined here. So, ConstantZero. Again, remember it's nothing. For ConstantOne we invert the output bit. For Identity we run a CNOT gate with input control up is the target and Negation reduces the next one, okay? And we just have these, like IsZeroConstantZero that I call. Is BlackBoxConstant compatible with ConstantZero? And then we have our classic controller.

Any quantum computing will have some sort of classical computer telling it what to do, so I ask for each of those four, well, what's going on? And we can run it and it runs in a simulator and we see the result, is IsConstantZero constant? TRUE. ConstantA constant? TRUE. Constant identity? FAKE. Negation constant? FAKE. There you go. Yes, we wrote the Doge paper, ran it on a real quantum simulator and you saw that it worked. Okay, final demo of the day and then I'll let you out of here, here we go. This is called the IBM quantum experience.

There is a real-world quantum computer that IBM has built. It only has five qubits, but they allow you online to simply drag gates onto this quantum circuit diagram and run it on a real quantum computer. So I thought it would be really clever if we demonstrated the entanglement live on stage. We'll see. So if you remember, the first thing we do is drag a Hadamard gate to a debt and then we use the control no, oh no, okay. So the way quantum computers are built you can usually only put CNOT between certain debts, basically it's something like that, otherwise it's mechanically impossible to see.

We can do that? Not well. How about it, success? Well, we did it. This is the CNOT gate. You can see different representations of it. It's like the opass. And I say we'll run it on a quantum computer, of course, measurement gates. I forgot. Obviously we need to add the two measurement gates. So we are measuring both qubits after entanglement. And what we expect is to see them predominantly 0-0 and 1-1, right? Well, let's try it. We'll call it that and we can save the cache result, but I want to do it live for you guys, so I'll run a new run.

And you can imagine that right now, deep in the IBM Research Laboratory, inside a dilution refrigerator operating slightly above absolute zero, we have real qubits entangled and measured thousands of times for our entertainment. That is very beautiful. It is. That's great. Okay, let's see if it's, oh here we go, we have the results. And the executions are pending, okay. So it may take a couple of minutes. Let's see now. Does anyone have any questions while we wait for this? Yes. I don't know what question. Did you say this experiment where this feeling entangled the qubit with space and satellite?

Yes. Are we good at storing similar qubits for a long time? I'm really surprised they were able to do that. I thought that in a way... Yeah, yeah, actually that was a lot. They will manage to send the entangled qubit file laser, but yeah. Okay. I don't think we'll be that good at storing qubits for a while. I think they last quite a whilebit. Yes, actually, this Chinese satellite experiment, they teleported a qubit there. So they sent an EPR half through a laser and then used that EPR half to teleport the qubit there. Very cool. That's amazing.

Yes. So we can send laser entangled qubits? You can send laser entangled qubits, yes. Okay, that's even cool. Yes. Let's see, it's not yet. OK it's good. Anyway, yes. You mentioned that there is a new paper by the mathematician that says that the noise has grown faster. Yes. What is the purpose of a topological quantum computer? resist that. Of course. Any corner computer will have problems with noise. The topological quantum computer is supposed to be better than its IBM counterparts in terms of noise, but it will still grow exponentially. It can still be better, but it still runs into an exponential barrier.

And so the next few years will be really decisive for quantum computing because we will now have the ability to create computers that reach this exponential term, if it exists, if it exists. And so we will see in the coming years whether quantum computing is really possible or not. It's nervous and it makes me nervous, but yeah, because we'll probably hit this limit like this year. If Google fails to prove quantum supremacy, I guess it will be a little scary, but yeah. Let's see, we don't have, I'm just going to update this. Question. Yes. Do we know what Google uses the quantum theorem for, and for what?

What do they use it for? Yes. I don't think we will. I think they just have... Is it mainly experimental? Not really. They haven't announced what they use it for. In fact, my boss is playing with the D-Wave simulator for... The Canadian company. Is the company Canadian? D-Wave is a Canadian company. Yes, they are all really scammers and not really quantum, but they all think they are quantum, but it is a different paradigm. It's basically like an optimization, but it uses quantum computing. They have a simulator that you can use. My manager has been using it to play route finding on a network.

It has general applications like that. Well, this is taking a lot. Is the data publicly available anywhere? Yes, it's on the invitation and I think it will probably be posted on your resonant website or online. So that application is like a requester type application? Yeah, yeah, it's like... It's optimized. You can express the network graph in terms of what, as a result of an optimization, it would be like the path of least energy in terms of the least cost path through the graph. That's different from the way . Open the shortest route. Come on, why doesn't it work?

Earring. I will be very sad if this doesn't end in time. Oh good. So in D-Wave, how do you focus presentations? You could classically do them faster than when they did it. So have they gotten better at that or? I don't know, I haven't really looked into it. They're probably comparable, I'd say. Because since it's like optimization and especially with the explosion of machine learning, a lot of progress has been made to improve optimization. Optimization is like you have a surface and you are trying to find the highest point or the lowest point. So there's been a lot of research on that.

We'll just run it from the cache and that's fine. Here we go, okay. Here are the cache results. Unfortunately our real execution is not over yet. So we see that they did indeed entangle some different qubits than ours, but we end up with 0-0 and 1-1 almost exclusively, but then there are some in between because of the error rate, right? This is on a real quantum computer. We have a certain error rate where it doesn't work exactly according to our model all the time, but it's pretty good, these are intertwined and measured and we have it.

That's the experimental data that entanglement is a real thing. Yes. Well, that concludes the presentation. Thank you so much. I hope everyone feels like they've followed the entire process, that there's no real confusion, and that they feel like they can keep learning. This is not some crazy cool science. This is a very accessible science. So thank you very much.