You don’t know how Quantum Computers work!

#dont #Quantum #Computers #work

Ever since I first heard about quantum computing, there was something that bugged me about it. The story goes like this: All operational computers today are classical computers. They store and operate on information represented as 1s and 0s (bits) to solve intensive, mathematical problems.

Quantum computers, which are being developed in labs right now, are fundamentally different. They take advantage of quantum mechanics to do multiple calculations at once. This is done by putting quantum bits into superpositions so they can be 1 and 0 at the same time.

But you have to be careful with superpositions, because as soon as you read them, they collapse to either a 1 or 0, with a known probability. If all that was a little too fast, feel free to check out Building the Bits and Qubits, as it explains all of this more clearly.

Don’t worry, I’ll wait here. Done? Good! Now we’re on the same page. Here’s my problem: if you put a qubit in a superposition to do many computations at the same time, wouldn’t you only obtain one of those many calculations when you measure your answer?

You can’t get many answers at once, since reading the answer to a quantum computation would destroy most of the information your qubits are storing! How can quantum computers even be practical if this happens? The problem is that this story doesn’t completely explain what quantum computers actually do.

Why don’t we just take a look? To understand what’s happening here, let’s actually build a quantum algorithm. Qubits can be visually represented as Bloch spheres. 1, 0, and everything in-between. Today, we won’t be needing all of these qubit states, so let’s simplify this representation to a slice of this sphere.

Let’s call it the Bloch circle. And just a little aside for those of you following the math, the Bloch circle illustrates all possible qubit states where the probability amplitudes have no imaginary component. And don’t worry if none of that made sense.

This is just so those who already know the math can follow along. Now let’s begin. Say that I hand over to you this quantum circuit. It takes in two qubits, and spits out two qubits. Let’s call these x and y.

Qubit x always passes right through this circuit unaffected, so if it was a 1, it comes out as a 1, and if it was a 0, it comes out as a 0. Now, here’s where you come in.

I’m not gonna tell you what this circuit does to qubit y. I will only tell you that it will do one of 4 possible things. Case A: it does absolutely nothing to it, just like qubit x.

Case B: it flips it, so if it was a 1, it comes out a 0, and if it was a 0, it comes out a 1. Case C: it flips it like before, but only if qubit x is a 1. If instead qubit x is a 0, it does nothing to it.

Case D: it flips it only if qubit x is a 0. If instead it’s a 1, it does nothing to it. So to review: In case A, never flip y. In case B, always flip y.

In case C, only flip y if x is a 1. In case D, only flip y if x is a 0. In cases C and D, whether qubit y flips or not depends on qubit x’s value, so let’s call these the needy cases.

“Umm, qubit x, sorry to bother you… What should I do to qubit y?” This is not true for cases This is not true for cases A and B, so let’s call them the laid-back cases.

They’re the cases where the circuit goes: “Yeah, I don’ really care what you say qubit x, imma jus’ go do my own thing.” By the way, remember this exact terminology. It’s important! …naw I’m kidding, these names are completely arbitrary!

So, with that in mind, here is the circuit I’m giving to you. By toying around with it, can you figure out if it’s a laid-back case, or a needy case? Oh and by the way, I rigged the circuit to self-destruct if you try to open it. So all you can do is pass

Qubits through it to see what happens. And, it also self destructs after you use it once. So you only have one chance. Good luck! Okay, that was a little unfair. Let me show you how to do it. What would happen if we pass in both qubits x and y as 0s?

In case A, we would get two unaffected 0s as expected. In case B, nothing would happen to qubit x, and qubit y would flip vertically to a 1. In case C, qubit y would only flip if qubit x is a 1. Qubit x is not a 1, so it’s unaffected.

In case D, qubit y would only flip if qubit x is a 0. Qubit x IS a 0, so it does flip. So, the result will only ever be 00, or 01. If you actually did the experiment, and got

01, that means that qubit y would have flipped, and you would know that this circuit is either case B or case D. But which is it? Would y have flipped because it always flips, or would

The circuit have been listening for instructions from qubit x, and it happened to say to flip qubit y? Would something else have happened if x was different? We could then then try passing in x as a 1 instead to see what happ… Whoops, the circuit gets destroyed after a single use, remember?

And, we still don’t know if the circuit was a laid-back or a needy case. In fact, if you just pass 1s and 0s into this circuit, you would always need to use it at least twice to get an answer. But we can’t do that, because I’m a mean person

And made it explode after 1 use. Let’s try thinking of something else. Now, the problem we had before is that we didn’t know if qubit y flipped, because it always flips, or it only did that because qubit x was a 0.

We didn’t know if it would flip if x was a 1. So, let’s see what would happen if we put qubit x into a superposition, so that it’s a 1 and a 0 at the same time.

That makes sense. With that, we can see what would happen when qubit x is a 1 AND when qubit x is a 0 at the same time. To do that let’s use the Hadamard gate. The Hadamard gate is useful because it can take qubits into and out of super positions. Let’s use

It to take a qubit 0, and turn it into a qubit right. Qubit right, is half-way 0 and half-way 1. Or as many like to say, it’s 0 and 1 at the same time. If you’re doing the math, qubit right represents this quantum state.

That should do it. We’re testing both scenarios at once. Let’s see what would happen. In case A, nothing ever happens to either qubit, so they are unaffected. In case B, qubit y flips no matter what qubit x is. So it flips.

In case C, qubit y flips only if qubit x is a 1. But it’s both a 1 AND a 0. So does it flip? Does it both flip and not flip at the same time? Something interesting happens

Here. Qubit y goes into a superposition, but it isn’t tied back to its own opposing state. It’s tied back to the state of qubit x. In other words, qubits x and y come out in an entangled state. They can no longer be considered separate from each other. Now,

Measuring either of these qubits will cause both to collapse to 1 or 0. In this particular case, they will always collapse to the same value. Here’s the reasoning: If we found that qubit y flipped, it would because qubit x was a 1, since that is the only scenario

In which qubit y WILL flip in case C. Similarily, if we found that qubit y didn’t flip, it would be because qubit x was a 0, since that is the only case in which qubit y will NOT flip. In case D, qubit y flips only if qubit x is a 0.

Again, qubit x is kind of both 1 and 0 at the same time. In this case, the qubits come out entangled again, but they will always collapse to opposing values. If qubit y flips,

It was only because qubit x was a 0. If qubit y doesn’t flip, it was only because qubit x was a 1. At first, it looks like we may have solved the problem. The qubits come out entangled

In only the needy cases, and not the laid-back cases. So all we need to do now is check whether or not the qubits are entangled, and we have our answer! So what would happen if we tried it?

What would happen if we put in qubit right for x, and qubit 0 for y. Say we find that qubit y came out flipped. We would know that we don’t have case A, because it never flips

In that case. And let’s say qubit x comes out a 1. Wait, was that because it was entangled and became a 1 when we measured qubit y (as in case C), or was it because it randomly collapsed to a 1 from an entirely separate superposition (as a possible case B).

Like last time, we don’t know if we have a laid-back case or a needy case, because there is simply no way to check if two individual qubits are entangled or not. This is the problem I was talking about earlier. Sure, you can do multiple calculations at the same time

By putting qubits into superpositions. There is information about two separate calculations in these qubits, but you lose that information when you read them. Well it turns out, there is a very clever way of getting around this…

Okay, enough stalling! This is the solution. Set x to qubit right, and set y to qubit left, both in superpositions. If you’re doing the math, qubit left represents this quantum state. In case A, nothing happens. In case B, y always flips. But flipping qubit

Left top to bottom just results in qubit left again, so oddly, nothing happens. In case C, the strangest thing occurs. The classical description of the circuit says that qubit x never changes. But, somehow, the circuit actually flips qubit x left to right, even though nothing is really supposed to happen to it!

The same thing happens in case D. As for how this happens, hold that thought for just a sec. We’re really close to solving the problem. Now, one last obstacle remains. As a reminder, we are trying to figure out whether the circuit

Is laid-back or needy. In the laid-back cases, qubit x faces right. In the needy cases qubit x faces left. But we can’t measure this qubit yet, because superpositions collapse randomly to a 1 or 0. All we need to do, is pass it through the Hadamard gate once more.

Now, qubit x only comes out as a 0 when the circuit is laid-back, and only comes out as a 1 when the circuit is needy. Problem solved. So let’s do that. Qubit x comes out as a 1. Therefore, we know that this circuit

Is either case C or case D. But no matter what, it was a needy case. This is called Deutsch’s algorithm. It depends on the fact that qubit y is specifically facing left. This mechanism results in the ability for qubit x to flip left-to-right. If qubit y was facing right instead of left,

Nothing ever happens to qubit x. It’s a lot like how multiplying a number by 1 keeps you where you are, but multiplying by -1 flips your sign. Likewise, qubit y facing right keeps qubit x where it is, but qubit y facing left flips qubit x left-to-right.

But why is this? Left and right are both half-way 0 and half-way 1. Why should something so drastically different happen under each case? Well, left and right do each collapse to 1 or 0 with the same probability. But mathematically, they are as different from each other as 0

Is different from 1. Qubit right is half-0-half-1 in-phase, and qubit left is half-0-half-1 out-of-phase. They are, in a sense, “opposites”. For those following the math, [0,1] and [left,right] each form an orthonormal basis. So, while the in-phase state has no effect on qubit x, the out-of-phase state has the ability to flip it.

And if this still doesn’t make much sense, which it probably shouldn’t, just remember, as Richard Feynman once said: “If you think you understand quantum mechanics, you don’t understand quantum mechanics.” After all, the mathematics we are dealing with here involves transformations through 4-dimensional vector spaces, so it’s a little

Tricky to come up with good analogies. This terminology zoo and this flipping piece of card are honestly all I got. And if any of you can, please research quantum computing, go through the math, and find a

Better way to explain this. It really bugs me when I get the math but I can’t explain the essence of it. What kind of channel is this? Frame of Matrix Algebra? Quantum Mechanics… you have defeated me. Moving on… Since we’ve solved our problem, here’s what the individual circuits actually

Look like on the inside, made out of elementary quantum gates. And here are their classical analogs. So, what have we learned from all of this? That there is no hope in understanding quantum weirdness? I don’t know the answer to that question, but that isn’t the point of this

Video. The point is that the answers extracted from quantum computations contain no more information than the answers extracted from classical computations. With classical bits, running the circuit once, only ever narrowed our answer down to 2 possible cases. Using

A quantum algorithm did not change this, but it WAS able to use quantum mechanics to cleverly twist the question we were asking to result in information that we found more useful. Now, you may be wondering one more important question. What was the point of this?

If I already built this quantum circuit, I obviously knew that I gave you a needy case. Why did I keep that fact secret and make you figure it out? When would finding out something that was already knowable in the first place be practical? Well, this is precisely what a quantum computer does best.

Take this example. I mentioned in the last video how quantum computers can break current computational security techniques. Today’s internet security depends on the fact that is very hard to factor a large number which is a product of two primes. It’s not so

Bad with a small 2-factor number like 15, but it’s practically impossible for a classical computer to factor large ones. If someone can factor this giant number, the security fails. How does a quantum computer break this? It turns out that it’s possible to create

A quantum circuit which implements some modular arithmetic with this giant number. It’s a lot like the circuit I gave you. If we pass in superpositions to it, we are able to obtain a result, which we can then use in some classical arithmetic to quickly find the giant number’s

Prime factors. Classical security has been broken. This is known as Shor’s algorithm. It’s been done as a proof of concept, but it shouldn’t actually be a real threat anytime soon, because the physical implementation of quantum computers is very difficult, and

Is currently being researched. But it does put pressure on humanity to develop more robust security techniques. Maybe quantum security techniques? In each example, we had a problem with an answer that was computable, and was already a property of the very quantum circuit that was already built. We do not need quantum

Computers to solve these problems in principle. They just enable us to solve some problems, such as these, in less time. There’s another, more optimistic one called Grover’s algorithm, which finds the location of an item in an unordered list. Classically, because this list is randomly organized, you

Would need to check each item, one by one, until you found the answer. Grover’s algorithm allows us to find it much faster. If we had, say around 10 000 items, instead of performing up to 10 000 queries, you would only need a measly 100. This opens up numerous possibilities in database theory.

There are more quantum algorithms, but I think we’ve already learned the essentials today. Quantum computers cannot do anything that classical computers can’t already do in principle. Quantum computers cannot give you multiple answers to the multiple computations

It may be doing at once. What they can do, is twist the questions we can ask it, to aim the answer down to something more relevant. Quantum computing is hard, which may be part of the reason it’s still being researched.

But be on the look out for computationally intensive software being partly running on quantum processors. They may be just around the corner. KABOOM! 😀