What can quantum computers do?

should I go? Excellent? Thank you. So today we wanted to tackle an incredibly complex subject, which is a quantum computers. We've talked a little bit about quantum computers in previous podcasts, but we haven't really dedicated a full episode to it, and part of that is because it scares us. Yeah, and you'll probably see why as soon as we get further into the discussion today. Yeah. The the the potential for quantum computers is phenomenal. Yes, it potentially could be

a true breakthrough in computing for certain applications. But the actually describing what a quantum computer does and how it works is a pretty herculean task for for the layman. And this is where Chris and I both say, neither of us are quantum physicists. We are not experts in quantum mechanics by any stretch of the imagination. Although I do know that they used to work on VW midsize sedans in the eighties. It wasn't mid sized sedans, it

was quantum size sedans. Yeah, because it doesn't work on the classical system. Um, we're gonna get into that. Actually. See, to really understand how a quantum computer works, you have to know a little bit about quantum mechanics. And this is a crazy kind of world for those of us who are accustomed to things working on the classical level. So for to kind of ease into this. For me, physics was an easy class in general. I was able

to grasp the concepts of physics pretty quickly. And the reason I uh I give to that is because I am a fairly observant person, and physics really was just a way of explaining why the things I see work the way they work. Yeah, I I didn't split off on that vector very easily myself. Um, you know, I think I think my interests in high school when I took physics were not where they where they would have

been now, maybe I should go back through it. Well, physics though, ultimately, I mean once you get past the equations and the formulas, once you get past that, that barrier, that mathematical barrier that exists for some of us. I mean, I know there are math whizz is out there that they they see mathematics as a beautiful expression of the universe, which is phenomenal to me. It's just that doesn't come naturally to me. However, the concepts behind it made perfect

sense to me because it described the world I live in. Right, So so I'm like, well, of course, you know, the deceleration from gravity makes sense because of this. I mean I I can observe that and and draw conclusions from and in fact, that's where physics comes from. It are these observations of the universe, trying to make uh, explanations for those observations, and predictions based on those observations, and testing that out over time to make sure that they

are relevant and and accurate. Right, I mean, that's that was the basis of that science. Well, right, I mean it's easy for you to you know, shove a book off the table and watch it hit the floor and be able to explain that because that's something that you can see, but quantum mechanics is not something that you can see exactly. Quantum mechanics deals with elements that are on the atomic or subatomic scale, So we're talking about things that are so tiny that it is very difficult

to observe them in any classical sense. You can, you can observe some quantum effects using a classical system, but there are complications that will get into in a second. But on the quantum level, things behave in a really weird, funky way. And we don't fully understand all of the the aspects of quantum mechanics. And when I say we, I'm talking about super yeah, super smart people who make it their livelihood to study and try to understand quantum mechanics.

We know bits and pieces. We don't know if there is an overall system that everything fits neatly into place. We we hope there is, so that we can explain everything, but we can't know that yet. We just don't have. You know, it's kind of like you've been given, uh, five or six little tiny, tiny pieces of a puzzle and you can't really be sure that they're all belonging to the same picture. And you're trying to put the picture together just based on those little tiny pieces, right right, Well,

and the analogy holds for classical computers. It's hard to think of computers as being classical, but in this sense classical computers versus quantum computers because um, when you talk about the computers that we use every day, laptops, desktops, other kinds of computers, we're talking about things that are fairly standard. Now. I mean, we use materials like, uh, silicon and mercury and lead and glass and all sorts of other things that we are pretty familiar with. We

know how the properties work. Now we have the semiconductors and transistors. You know, these things are are pretty common. I mean can basically you know, computer science as far as the hardware and software goes. And this also does apply to programming. We'll get into that in a few minutes. But um, you know, the the things are fairly standard to the point where you know, the layman is pretty

familiar with the guts of a computer. But quantum computers use materials that we don't use in classical computers at all. And not only that, but in a system that is really complex to the sense in the sense that you have to you have to isolate the computing elements from the overall system, because if you don't, the computer breaks down. Um. But to understand that, we need to talk about some

of the the features of the quantum mechanics world. One of those is the wave particle duality concept, which is that certain elements, certain things behave as both a wave and a particle. And the classic experiment to demonstrate this

is called the double slit experiment. Now, this is an experiment where you have a thin sheet of material and in that thin sheet of material you cut two vertical slits that are close together, all right, and then behind the thin sheet of material you've got a a wall, essentially a target. You start to fire particles at this sheet of material it has these two slits, and detect

where they hit on the on the target. Now, if you were to shine light at this at this double slitted material, you would observe on the other side, uh, some some little bands of light where the lights passing through the slits, and the bands would have little dark sections between them or within them even which would show where the waves of light are interfering with one another. All right, So so you see the interference pattern from light, And that's because light behaves, at least in part like

a wave. It can also behave as a particle, but we'll get into that. So that's the wave behavior of of light. You see that those inference patterns um. Now let's say instead of light, you're firing electrons at these double slits. Now, presumably you've got something on that wall

that's going to detect where the electron hits. After as an individual shot of an electron going through those double slits, you'll just see that it appears on one specific spot, all right, So you're like, oh, well, here's where the electron landed. Uh. After you've done repeated shots of electrons through those double slits over and over and over again.

The interesting thing is when you look at the accumulation of those spots, they're going to fall within that same sort of uh pattern as the light did when the

wave forms were interfering with one another. So you're gonna see those dark bands appear, showing that somehow the electron is behaving both as a particle in a wave, meaning that every time you fire an electron at that double slit of material, the electron is somehow passing through each of those slits, because it's only if there's an interference that those bands are going to appear. Otherwise you wouldn't expect to see the bands, like the dark bands within

the collision area. You wouldn't expect to see those appear at all. Otherwise it would just be a continuous line within wherever the double slits would allow the electron to hit. That means that somehow the electron is in two places at one time, and it's only you know, it's doing that while it's moving through, but by the time it hits, when you look at it, it's clear that it's it had to be in one space because there's only one impact point per electron. Now, this is insane to someone

who's looking at this on the classical level. How how can something be in two places at the same time and yet ultimately be in one place at the end of it. That would be a good time to pause the podcast and take some headache reliever medicine. Yeah, because it's gonna get weirder from here on out, all right. So, there were people who had been there's some people who had some problems with this idea of of the wave

particle duality. Of this this idea of not just that something can behave as both wave and a particle, but that it could somehow be in two places at one time. Einstein had some issues with this um and created some

thought experiments. But there's an UH and and and then there were There's a related concept, at least related within quantum mechanics called entanglement, which is this is also pretty complex, but the ideas essentially is that let's say you've got a particle and it has a certain number of states it can exist in. In other words, there's some sort of feature or behavior this particle can have or not have,

and that that one way of describing this particle. Now we'll go with electrons and say that this electron could have one of two different spins, so it could be spinning up or it could be spinning down. Now UH. Within quantum mechanics, another, yet another UH concept is called superposition. Superposition describes a system's ability to to occupy multiple states at one time, like there's no way to determine until you measure it which state it's in, So therefore it's

in all of those states at the same time. And the best part is if you observe this, you will affect what's actually happening. Yes, it it goes through decoherence. It decoheres, which means that the quantum state collapses and it becomes a classic system, not a quantum system, at least to the observer, which means that, so you have this electron that could be either spinning up or spinning down.

From a quantum level, we would say it's doing both at the same time, which is because it's a Superposition's a superposition right Mathematically, if we were to describe the system, we would have to say it's doing both because we cannot determine at this time which one it is um and it behaves as if it's doing both in multiple experiments. So entanglement means that you could have another particle interact with that first one, and then its behavior is dependent

there or their behaviors are dependent upon each other. So in the classic sense of the electron spinning up, you might have a second electron that you introduce into this system, and it's always going to spin down if the other one spinning up, and vice versa. Now again, if you haven't measured it yet, you cannot be certain which what electrons are doing what So both electrons are acting in superposition. They're both spinning up and down. There, that's what they're doing.

They're spinning up and down. And it's only when you measure one that you determine that that the system collapses and you see, all right, it's spinning up. Well, by knowing that that spent that electron is spinning up, you then know the other electron, which has entangled with the first one, is spinning down and you don't have to mess with it. You're want to measure it. If you do measure it, you realize it's spinning down. So you've

already determined the measurement by measuring the first one. Uh. Now this Einstein also had a big problem with because entanglement is uh there are certain types of entanglement that are have non locality. So locality is talking about how

close these things are to one another. If you have a system that where you've got entangled particles that are non local, it means that it doesn't matter how far apart those two particles are, they're going to behave this way, so that if you measure one, you know the other one. This in theory gives us the ability to communicate over

huge distances. Um, if we're able to manipulate this in such a way so that uh, the information, like you know, the information that exists in another location, no matter how far away it is, Like even if it's on the other side of the universe, you instantly know the state of that particle. That means that you the information has traveled faster than the speed of light. That's the problem Einstein had, because nothing travels faster than the speed of light,

except possibly information. So if I've got a system here on Earth, and there's another system across the universe, perhaps set to a Beatles tune, uh felt that one coming. I can, I can, and and my system is entangled with that system. By by observing and measuring my system, I now know the state of the other system across the universe without having to be there to measure it.

And and this is again kind of crazy for anyone who's thinking up from a classical point of view, because it's that's just not the way stuff appears to work to us on the macro level. Now, I wish I had remembered my pain reliever medication. I do, However, I hope to avoid any imperial entanglements. Nice, thank you, thank you made the Kessel running twelve post sex. It's fast

enough for you, old man. Um. So yeah, so quantum computers rely on this idea on on multiple ideas, superpositions and entanglement in particular, and uh and just another aside. I know we've done a lot of prep works here in the sides, but it's it is really important to kind of get that that information about quantum mechanics across um. You may have heard of a thought experiment called Schrodinger's cat, and Chris actually alluded to it earlier in the podcast.

Schrodinger's Cat was and uh, well, Schroedinger was using this as a thought experiment to kind of show the absurdity of the quantum world compared to the classical world um. And it wasn't necessarily to ever state that such an experiment is should be carried out, but rather just that it shows how how how insane to us this world is. Troanjer's thought experiment is this. You've got a steel box.

You put a cat in the steel box. The steel box also has a Geiger counter which has some nuclear material, some radioactive material in it. That's undergoing radioactive decay um and within an hour and atom of this material within the Geiger counter may or may not decay into another element. All right, so you've got you've got uh this this uh, this uncertainty here. You don't know whether or not that

adam is going to decay within an hour. The guy your counter is hooked up to a system where if it detects that an adom has decayed, it will break some glass and some acid will be released into the box, which will kill the cat. You seal the box and you wait an hour, so you don't know if the atom has decayed within that hour. Now, based upon the the traditional interpretation of quantum mechanics and this idea of superposition, you would say that the cat before you open the

box to observe it, is both alive and dead. It has to exist in both states at the same time. And only by opening the box and observing it will this quantum state collapse. It'll decohere and you will see definitively whether the cat is alive or dead. Now, there are a lot of philosophical objections to this. Not not I mean, it's all thought experiment anyway, right, It's not like people are actually gonna do this, but philosophical in the sense of, wait a minute, So from the cat's perspective,

it's going to know whether or not it was dead. Well, if it's dead, it doesn't know anything. If it's alive, then it knows it didn't die. So the point being that how can you say it is both alive or dead because it's going to have no memory of such a being in such a state. Others have said that. Another objection is that, well, we talk about measuring a system, and that's what causes it to collapse. Some people would argue that it that opening up the box isn't necessary

for that system to be measured. The Geiger counter inside the system is already a measuring device and is measuring part of that system, and just by measuring part of the system, it deco hears and becomes a classical system, so that the cat, the cat's life or death is not It's never a superposition thing in the first place.

But this is one of those thought experiments that is meant to kind of make people think about this and try and figure out, all, right, well, how do we resolve this problem of our description of how the universe works and we don't have all the answers yet. There are a lot of different interpretations two quantum mechanics, and they some of them are fairly contradictory to one another. And you've got adherence to multiple different approaches and we

don't have the full solution yet. This finally brings us to quantum computers. So here's another crazy thing about innovation. Sometimes we find out that something really cool happens when we do a certain action and we don't really know the mechanism behind it, but we go ahead and build stuff anyway. Yeah, a lot of sometimes great things happen because of this. Sometimes bombs happen because of this. But quantum computers almost fits into that realm because we don't have,

like I said, a full understanding of quantum mechanics. But the idea behind the quantum computer is that you create some sort of system that uses sub atomic particles that have a particular feature, Like I was talking with the electron spin. That could be an example. It's not the only one, but it is an example of this. And you know that because of superposition, the electrons spin is

all every every type of spin that it can be. Well, if you translate this into the classical computer system, which relies on bits. And if you've listened to our Logic Gates episode, we talked a lot about this. There are two states a bit can be in orffe yeah, or one or zero. Yes, exactly, because you said on or off, I was going to confuse everybody. Yes, or true or false. That would be the other way of looking at it, right.

It can't be both true and false, right, right, So yeah, an individual bit is either going to be true or false, one or zero, on or off in a classical classical computer. Now, quantum computers use something called cubits. They're also great for measuring an arc. Actually, cub i t. The cub it in a quantum bit is a qub it, which is a little orange guy who hops up and down pyramids.

Uh no, wait, that's cue Bert. So cube bit is a is is the fundamental element of information within a quantum computer system, and unlike a regular classical computer bit, a cubit is able to be a zero or a one, or any value of zero or one or all of them, or all of the values of zero or one. Yeah, that's not confusing. It exists in superposition, and so if you have two cubits together, then you've got all the different combinations of zero and one that two bits would have.

H three cubits, you've got all the different combinations of zero and one that three bits would have. So exponentially it becomes a more powerful computer for certain computing problems. Haircut two. Yeah. So you you keep on adding more and more cubits, You've just created an incredibly powerful theoretical computer. And there have been some some advances in creating computers that use cubit technology. Uh, although we still have a lot of ground to cover in order to really make

one that is um, that is practical. Yes, as a matter of fact, you listed some of those I believe that I I might have there. Well, there is a list in the article how quantum computers work on the website.

Kevin Vonsa and I both worked on this article, and it's yeah, it's there have been several the first being back in where am I t researchers and Lost Alamos researchers were able to create a single cube it across three nuclear spins in a molecule of or in in molecules, I should say, of a liquid solution of of alanine, which is an amino acid. Yeah, this is what I was talking about before. We're not using the traditional materials, the silicon and metals that we use to manipulate information

in a classical computer. This this kind of computer is going to require a brand new style of physical architecture. Yes, And remember when I mentioned about superposition and entanglement and decoherents.

That's the reason why you have to be able to isolate the actual computing element from the system it's end, because if it comes into contact with the system, it's and you you have that problem of decoherens and quantum collapse, or you have a problem of entanglement where the system is getting entangled with the actual environment it's in and it's no longer able to do what you needed to do. Uh. These are real problems and it's it's there's no easy

way to describe the solution to it. And there are a lot of different approaches that that scientists are are taking to try and create quantum computers, including a creating quantum computers that operate at a temperature close to absolute zero, yes, which is very very cold absolute zero by the way, In case you do not know that is the point

where you have no molecular movement whatsoever. Uh, And even deep space usually be is a few uh kelvin over absolute zero because it's it's not easy to create a system where every single molecule in that system is is completely motionless. Yeah, that's that's one of the troubles here is that this is not something that's easy to achieve, no or cheap. It's really expensive that too. So what

kind of problems could a quantum computer solve. Let's say that we've created a quantum computer and it exists with these cubits that can have any sort of value of zero, one, or all of those values all at the same time. What would you use that for? Well, you wouldn't use it to play doom. No. One of the advantages of quantum computers is that the superposition of the cubits would theoretically, assuming that you know, we get to the point where we can have a fully operational um. Yes, uh, fully

operational quantum computer. You you could theoretically. Now we talked about parallel processors before, we're talking infinite parallelism um, which means that you could crunch a massive amount of data and no time flat The thing is. You're right, you could use it for something like do but that would be like trying to cut open a grape with a chainsaw. Oh, you might as well just use a regular computer, because it's not gonna do that. It's not gonna it's not

good for doing um, simple computing problems. It's not gonna do those any faster than a classical computer. Not really. It's it's meant for doing very specific types of computer problems. For example, factoring large prime numbers, which is the basis of a lot of cryptography out there. Not all cryptography, but a lot of it. So when you encrypt files, uh, one of the methods of encryption involves taking a large prime number. And when I say large, I'm talking hundreds

of digits long. All right. You take this incredibly long prime number. Then you take another prime number of approximately the same number of digits, but a different one. So you've got two different, really really really large prime numbers. You multiply the two together. You get a product. Yes, you give that product to someone else. If they have one of those two large prime numbers, they've got the key to figuring out the other large prime number. And

then you can use that to encrypt information. But if they do not have the key, if they do not have one of those two large prime numbers, they have to figure out, all right, what two prime numbers were

multiplied to create this product. And when you're talking about a number that large, breaking that down, breaking that encryption can take years or centuries with a classical computer, because the classical computer what's going to do is it's going to start finding the factors for that particular product, and then it has to determine which ones are prime numbers and which ones arn't. So I might start with, all right, is it divisible why two? Yes? So is the other

number a prime number? No? Alright? Is it divisible by three? Yes? All right? Is the other number of prime number? No? All right? Is a divisible wy four? Weight? That doesn't matter because four is not a prime number. So I mean no, no, it would have to figure That's what the classical computer would have to do. It goes bit by bit by bit. Now I was just imagining the computer argument. No are you idiots? I thought I had it, and then it turns out four is not a prime number.

Oh sorry, I see these things in my I see this in my head. Yeah, anyway. Yeah, so yeah, has to go through the entire series. Right, And and if you're talking about parallel program or parallel computing, Uh, if you have a computer that has a multi core processor, well, each core of that processor may be able to work on a part of a problem similar to this and

thus solve it in less time. But when we're talking about these large prime numbers in this encryption technique, even a multi core processor would take centuries to solve it. It's not it's not fast enough to really reduce that time to a practical limit. Yeah, a lot of our our computers today use quad core processes, and that's great for doing all kinds of everyday stuff, but working on a problem of that magnitude just doesn't and it would take a well, it's still gonna take a long time.

We're gonna get to I'm sure eight and sixteen core processors, but still, and even if you create a grid computing network where you have uh, you are you are leveraging the processing power of multiple computers, each computer with multiple processors, Even then it's taking it's gonna take ages to solve this problem. But using a quantum computer with enough cubits

where where it has enough cubits for all the different inputs. UM. It can then run this sort of problem where since all the cupids are are in superposition uh and it can run all all the different potential solutions in parallel and come back with a solution in seconds where it might take centuries for a classical computer system. UH. There are a few problems with this, the first being that UM as soon as you observe the system, you have broken down that it decoheres and you and it becomes

a classical computer. So you just turned your quantum computer into a classical computer and this is not reversible. Oops. Also the other problem being that the solutions that a quantum computer represents are given in terms of probability, not

in terms of certainty. So in other words, you're going to receive a series of solutions and you'll essentially know which one it has the most probability of being the correct solution, but it may take multiple calculations to UH two make that probability feel like that like that's the answer you want to go with UM And and even so, there's still some problems that a quantum computer just may or may not be good at solving and there's added

complexity here. If you remember back to our logic Gates episode just a few weeks ago, we were talking about certain how how logic can classical computers flows in a certain direction, and there are some logical operations that cannot be reversed. Here here's here's part of the problem. In quantum computers, all operations have to be reversed. I mean they have to be reversible. So some of the logical operations used in classical computing just don't operate the same

way with quantum logic. And in addition to this, the superposition of the cubits also requires a different style of programming. You have to be able to write programs in a completely different way quantum algorithms using quantum algorithms, and that means again you can't play doom on it. So which is still is a huge bummer to be big doom

fans well know that. But if you if you back off of this, we're looking at the big picture here and not you know, the quantum picture quantum computers since since they use such a different way of computing and it's a different physical architecture, it's a different intellectual architecture and programming. That means you have to completely reinvent the way you compute, and it's not an inexpensive way to

re engineer the computer either. So although people are building quantum computers, it is unlikely that we're going to see them on our desktops and our laptops. It's not even It may even be years before we see one that is truly capable of of doing the things that we suspect quantum computers are capable of doing. Um and and the kinds of problems that quantum computers can tackle are generally called b q P problems, which stands for bounded

error quantum polynomial time problems. Yeah uh, and so they that's those are the ones that those are the type of problems that quantum computers we think would be ideal for solving. But of course not all problems fall into that category. There's another kind of problem that may or may not be at all connected to b q P problems called MP complete problems. And I'm not gonna get into too much detail here because we're gonna have to really dive into complex computer science in order to explain it.

But um, but in general, there some people have proposed that quantum computers could possibly solve NP complete problems. And there are other people who completely disagree and say, no, MP complete problems fall outside the realm of what a quantum computer could could attack. I'll just give you an example of an MP complete problem. And again this is just an example, not a This isn't like the end all be all, Okay, it's uh. This is called this

is an MP hard problem. Uh, the traveling salesman problem. Mhmm. Have you heard about this one. I've had a problem with some traveling salesman before. Well, this is a little bit different than that, the so that you've heard about that. I guess everybody read about that in the paper. You know you eventually you're gonna if you listen hard enough.

I just don't tamper with my ankle bracelet, and everything's okay. Now, Really I should say that the this is an MP hard problem, uh, not necessarily an MP complete problem, because I want to say that before we have all our math mathematicians right in, but I wanna you know, again, this is one of those things where we know a lot, but we don't know all the intricacies, all the connections between these types of math problems to be able to say definitively what is and is not solvable by a

quantum computer. But it's a The traveling salesman problem is a sort of an optimization problem. Right. So we say that you are a traveling salesman. You have a list of cities that you need to visit on your route to to make sales. And it's your job to try and determine the fastest or the shortest route to take where you don't uh retrace your steps at all among the those cities. And then every time you add another city to that list, you have just made the problem

much more complex. And it's determining, all right, well, there are in number of possible routes for me to take, and only one of them is going to result in the shortest distance between two spaces. But then you add another city, all right, well, now it's in plus one, in plus two, and in in plus three. And that's the sort of problem that could maybe be solved by a quantum computer. It's it's hard to determine. I mean, it's again whether or not it falls into that realm of

b QP. But that's sort of the that's an example of a problem that may not be solvable by quantum computers. We've seen quantum computers actually tackle problems like Pseudoku puzzles. So there are some, uh of these sort of parallel problems that we know quantum computers could tackle. We just

don't know the full extent of it. It's complicated, man. Well, it is interesting to think that they have they have been able to build some quantum computers, even to the point where they're they're operating on a que bite which is eight que bits um. You know, I'm I'm fascinated

by this, but it is pretty amazing stuff. I mean, it's it's really not simple even for maybe even probably because I am so immersed in the world of classical computing, you know, I've done programming and some of the immersed in the classical world period. Yeah, yeah, and I think of it's hard for me to imagine something existing in

more than one state at the same time. So, um, here, I I was gonna say, in doing my story, say and doing my research, I read an article called an Introduction to Quantum Computing for non Physicists by Eleanor Reefal and wolf GETG. Pollock. Um I beg to differ with the non physicist part, but it still was it still was a good read, and they broke down a lot of things, but they really got into it, and I would uh suggest that if you're really interested in reading that.

In addition to the article on how stuff works dot com, how quantum computers work, and we have other interesting quantum articles on the site, the big one being the one that the one that's a favorite of our general manager is quantum suicide. Yeah. Yeah, I don't know how many times has Connell mentioned quantum suicide. I don't know, but it's well, it's a favorite of a lot of our fans too. It's indicative, it's indicative of a deeper psychological issue,

I think. And that concludes this final episode text stuff. I don't know this, Connell, so listen, hey conal uh So, anyway, guys, that wraps up our discussion of quantum computers and again the applications for this maybe a complete revolution of how we do cryptography. For example, because if quantum computers are capable of breaking down those those um those large factor numbers, then clearly that would no longer be a safe way

to encrypt information. And again, it's not the only way to encrypt information, but it would just mean that we'd have to move away from that and adopt something else that quantum computers might not be so good at doing um calling missnomials polynomial nice and on that theorem. We are going to conclude this episode. If you guys want us to tackle a subject, maybe something that's you know, less fuzzy and scary and spooky, or Einstein would call it spooky. He called it spooky action. That was the

whole entanglement thing. Um. Einstein was pretty awesome. Yeah, If you guys want us to tackle a similar subject, or there's just something totally different you think that we should talk about, let us know. Drop us an email. Our address is text stuff at how stuff Works dot com, or let us know on Facebook or Twitter that handle there is Text Stuff h s W. Chris and I will talk to you again really soon. Be sure to check out our new video podcast, Stuff from the Future.

Join How Stuff Work staff as we explore the most promising and perplexing possibilities of tomorrow. The House Stuff Works iPhone app has arrived. Download it today on iTunes. Brought to you by the reinvented two thousand twelve camera it's ready. Are you