Wisconsin Public Television University Place Wednesday Nite at the Lab  Marty Lichtman A Historical Introduction to the Quantum Computer    cc >> Tom Zinnen: Welcome, everybody, to Wednesday Nite at the Lab. I'm Tom Zinnen. I work here at the UW Biotechnology Center, and I also work for UW Extension Cooperative Extension. On behalf of those folks and the Science Alliance and Wisconsin Public Television and Wisconsin Alumni Association, thanks again for coming to Wednesday Nite at the Lab. We do this every Wednesday night, 50 times a year. Tonight I'm delighted to be able to introduce to you Marty Lichtman. He's with the Department of Physics here at UW Madison. He'll be talking about "A Historical Introduction to Quantum Computing." He holds a SBC, which I think is like a BSC, only it's from Brown University. >> A little more... >> What's that? >> A little more highfalutin. 

>> Highfalutin, excuse me. [LAUGHTER] From Brown University in Providence, the one in Rhode Island. And he's got a master of aeronautics and astronautics from Stanford University, and he's currently a PhD grad student here at UW Madison. His previous adventures include growing up in Manhattan. The one in Kansas? >> Yes, Kansas, New York. >> Kansas, New York, okay. [LAUGHTER] Because she's from Kansas only she was from Lawrence. Co-founding a surgical robotics company and working in the aerospace industry on hybrid rockets. Marty is also a short track speed skater and is the current Wisconsin state champion in his age division. What is your age division? Never mind. 

>> Not going to answer that one!  >> It's not every day that we get to have a topic that baffled Einstein. [LAUGHTER] So I'm really looking forward to seeing how Marty handles the whole issue of quantum things, especially quantum computing. Please join me in welcoming Marty to Wednesday Nite at the Lab. [APPLAUSE] >> Marty Lichtman: Hi. Thank you for coming on this lovely day. You chose to be here. So as Tom said, I'm going to talk to you about quantum computing which is a wonderful magical device, the quantum computer, and as I'll explain it can do pretty much everything. It slices, it dices, it factors numbers in polynomial time. And I'm going to walk you through this in what I call a sort of historical introduction because I think that that's a good way to talk about what we mean by the quantum computer is by comparing it to what is a regular computer. So first of all, I'm going to start out by giving an example of why you might want a faster, better computer when your current computer can already run Halo 3 or whatever it is perfectly well. 

And then I'm going to go back in time and I'm going to explain, I'm going to break down a quantum computer into quantum and computing. I'm going to start with the computer part, and I'm going to explain what exactly we mean by a computer. And then I'm going to explain why a quantum computer is better, and then I'm going to explain how the quantum computer works. We'll get there. And don't worry I will let you know everything you need to know about quantum mechanics right from the very beginning, and then I'm going to talk a little bit about the current research that's going on including in my lab, as Tom said I'm a graduate student. I'm in my second year here in the physics department. And I'll also mention a little bit about other research that's going on and what the current state of the art is in terms of where we're at with actually building a quantum computer and research that's going on in my group and other groups here at UW. So I figured we're in the genetics building so I'll give you an example from genetics. Now my lovely wife is there in the fourth row, and she's a biologist and so I've learned two things. One, that biologists are complicated, but the other is that I've learned from her that biology is very complicated. 

This may be a review for some of you, especially if you've been to others of these talks, but you know that everything about you is coded on 23 pairs of chromosomes. Of course, that's just the nature part, of course there's the nurture. A lot also goes into who you are as you grow up. But all of the information that's passed down from your parents is on 23 pairs of chromosomes. And on those chromosomes you have sequences of adenine, cytosine, thymine, guanine, ACTG, repeated over and over again in different patterns. 3.2 billion of those. Those 3.2 billion base pairs, they code for 23,000 different possible proteins that are in the human genome. All of that boils down to a very, very compact package. In each cell you only have 3.3 picograms of actual genetic information in there. And if you look at that in terms of data, what would it take to store that on a computer? It's about 800 megabytes which is a bunch but it's not really that much in terms of today's computers. 

800 megabytes, you could fit that on a compact disk. But things start to get interesting if you look at the field of bioinformatics. Bioinformatics is what I like to think of it as data mining in order to cure diseases. And what data mining is, is something typically a company like Google or another advertising company would collect a lot of information about you and everyone else all around the world who uses their websites and they would try and filter that down to figure out what do you want to buy. So it's taking a lot of data and figuring out stuff from it. So what the people in bioinformatics are doing is they're collecting a lot of information about your DNA and also a lot of your life experiences, what you've been exposed to, in order to figure out what causes diseases. What part of it is caused by your genes, what part of it is caused by environmental factors. And they can go farther than that in order to try and deduce what drugs are more effective on people with certain genes because not all drugs work equally well on all people, and they're trying to sort out why. And beyond that they can actually, in the future, possibly create custom drugs for certain people based on their genetic makeup so that those drugs will be more effective. Now, well I just want to mention that those 3.2 billion base pairs that you have in you, that's a big number but it's not huge, but when you start multiplying that by seven billion people on the Earth and doing all the cross-correlations between it, that starts to become a very large number and this starts to become a rather difficult problem. 

It's still within the realm of what we can do today on normal computers but it's getting towards the limit. And where we go even beyond that limit is when we want to look at, well, what exactly do those genes do when they code for proteins. So the chemicals that a protein is composed of is not the end of the story because what most of the functionality of a protein is is in its shape. So DNA will, through the cellular mechanisms, form a string of chemicals that is a protein and then very quickly, in about 10 microseconds, all of those molecules will fold up into some complicated shape. And most of what the protein does is defined by that shape because it can either be a receptor for other chemicals or it can transport them to somewhere else, and it's not at all obvious how you go from the DNA sequence to the actual shape of the protein. So we try and do this on a computer using computer simulation, and the problem is those 10 microseconds of folding in nature, it takes 30 years to simulate on your average Intel desktop computer. 30 years. So they try and get around this, for example, with parallel computing there's a really cool project called Folding@home. It's a project out of Stanford University where you can download a program onto your own computer and whenever you're not using your own computer, the idle cycles will be used to help them calculate the folding of these proteins. And so this is a massive project that's managed to simulate about a dozen of these proteins and how they fold. 

So parallel computing is not going to get you there. You need something else. And that is the quantum computer. But let's go back in time for a little bit. Let's go back to this picture. So I have a question for the audience. Does anyone think they know what this is a picture of? Guesses? >> A graduating class? >> A graduating class? No, not quite. So this is actually a picture of what I would consider to be the first computer. And I will explain why. But in order to get there, we need to go back a little further even. 

To Halley's comet. So Edmond Halley, in 1682, he saw later what would become known as his comet. This inspired in him a love of astronomy, and he was quite a good scholar. And he, by the year 1705, he had figure out that what he had seen in 1682 was the same comet that had been seen every 75 or 76 years going all the way back to the year 240 BC. And actually up there I have written 467 BC, since then we've found records of even another sighting that was probably the same comet. And in order to sort of prove his theory, to be like, you know, obviously this is the same thing and I'll show you why, he needed to predict when it was going to come back. He needed to say what year is this comet going to come back, and then when it showed up people would believe him and say yes, comets are periodic, it all makes sense. And he tried to do this in a method that we would call analytically. And analytically means you come up with one equation that describes how the orbit of the comet goes around the solar system. And we know from Kepler's laws that all of the planetary bodies are supposed to go in nice beautiful ellipses. 

The problem is they don't because it would only go in an ellipse if the only other body in the solar system was the sun. And Halley realized this. He realized that the problem, the reason that he couldn't come up with one equation to fit to all the data for all of these comet sightings, 75 or 76 years at a time throughout history, was because the large planets, Jupiter and Saturn, were perturbing the orbit of the comet. But nevertheless, he couldn't figure out what to do about it because he was stuck in this motive: I need one beautiful equation to sort this out. And he was never able to predict the comet to any better than it's every 75 or 76 years. So the actual prediction was left to a French astronomer by the name of Alexis Claude Clairaut, and what Clairaut did was something very clever. He decided he was going to do a method that we would call numerically. So he said, okay, we know at a certain time exactly where the comet was because we had these sightings, and we also know very reliably where all of the planets were. And at that time they had Newtons laws, and so they know what the gravitational pull on that comet is from the sun and all of the large planets. And they could calculate, okay, at that given time we know where the planets are, we know how much they're pulling on the comet so we know its acceleration. 

So in a short amount of time later, say maybe a week or even just a day, they could predict very accurately where it would be. And then they do it again based on the new position of the comet and the new position of all the planets, which were fairly reliable because they're much larger than the comet, they could do it again. They could calculate based on those positions. What is the gravitational pull on the comet, what is it acceleration, and tomorrow where will it be? And they do this over and over and over again and they had to iterate this forward one day at a time for 75 or 76 years in order to figure out when is the comet going to come back around again to perihelion, which is the point of closest approach to the sun. And what they had found was that it was going to come back in the year 1859, which was interesting because it's actually closer to 77 years, and when it turned out that they were right and they had predicted the return of the comet to an accuracy of less than one month, that was a triumph for what we would call the numeric method. So what this picture is, the only man in the picture in the back, Professor Edward Charles Pickering, was the director of the Harvard College Observatory. And what he saw was the industrial revolution going on in which you took human beings and you put them on an assembly line and each person was responsible for one small job. They'd take something, screw it in, pass it to the next person. And he decided to apply the same thing to numeric calculations where you would have a team of people each doing one small job. They would take a number from the person before them, do something easy to it, multiplication, division, probably not even division, addition, subtraction, pass it to the next person. 

One tiny job. And he hired these teams of all women, and their job description was computer because that's what they did, they did computations. And these small computations built up to the large calculations that he needed in order to calculate these astronomical tables. So really, in every way that counts, this is the first computer. Now, of course, people started using machines in order to automate the tasks that previously humans had been doing in factories and you can do the same thing with numbers. And the first person to realize that was Charles Babbage, who, in 1822 he proposed to the Royal Astronomical Society that he wanted to build a machine to do this. He never actually completed the machine but his designs were shown to be completely valid, for example, by this reconstruction which is at the Science Museum in London. And this machine actually bears an amazing amount of resemblance to the computers that we have today in that it had an input/output system, it was instruction-based, it had a separate memory for the program and for the data, and, more importantly, it was programmable. You could change what it was capable of doing and what calculation it was going to do. One fun thing to note is that the Countess Ada Lovelace, who is the daughter of the poet Lord Byron, she's actually considered the world's first computer programmer because she wrote algorithms for this machine that didn't even work. 

But her algorithms were perfectly valid. And she was honored in the year 1960, one of the first computer languages was named after her, Ada, and it was only three years after Fortran, which was the first computer language. So of course eventually mechanical computers were made functional. And people outside the field of astronomy began to realize wait a minute this is sort of a useful method that we can use for other stuff, in particular for military uses. And this is a German example which sort of speaks to that. Well, the US had its own hand in that and upped the ante a little bit where, during World War II, the US Army commissioned ENIAC, the Electronic Numerical Integrator and Computer. And this was designed at the University of Pennsylvania by John Mauchly and Presper Eckert, and it was not actually, they funded it for the purpose of calculating artillery ballistics, which is to say that if you've got a large gun and you know how much wind there is and how far away the person you're trying to shoot is, you want to have a look up table that tells you what angle do I point my gun at and how much charge do I put in it in order to hit that person. And it's actually, when you take into account the wind, it's a fairly complicated problem. So they wanted a computer to turn out all these numbers for all their various guns that they could distribute to the army. And it was not actually completed until 1946, by which time, of course, the war was over. 

However, the programmable nature of ENIAC made it really useful. It was actually operated until 1955 because it could be applied to all sorts of different problems. And a nine-year life span is actually pretty good if you think about how long your last PC probably lasted. Now, all these computers basically the same thing as your modern computer they've just gotten faster and faster according to what's called Moore's Law which says that every 18 months computers get twice as fast and twice as small and twice as cheap. But they can do all the same calculations. Now, we call this being Turing complete. Being Turing complete means that all these computers are equivalent to a thought experiment by Alan Turing. He came up with in 1936 which is a really boiled down version of the computer. And it only has a couple of elements. I'm going to use the mouse so that this will show up on the video here, but we have here a tape and that tape has some data on it. 

Ones and zeros in a row. And then we've got a head, and the head can move back and forth. And it can only read the data that's next to it. And the head has what we call a state. It could be just a sequence of numbers. And then there's some instructions, and the instructions tell this machine what to do. And the instructions are only based on what is the state of the head and what is the adjacent data. And what the instructions can be things like change the state of the head, write a different piece of data to the tape next to it or move the head. And that's it. And using those basic elements, you actually can do all of the calculations that any modern computer is capable of. 

This was formalized by Alonzo Church in the Church-Turing thesis, which basically says that anything that is computable is computable by a Turing machine. And at the heart of the Church-Turing thesis, this is the idea that the hardware doesn't matter, that the human computer, the Babbage difference engine, ENIAC, your Intel Core 2 Duo, that they are all basically equivalent and some might be faster than others. Now, in the last 25 years or so physicists have thrown their hats into the computer science arena, and we've decided that that is not the entire story, that the hardware does, in fact, matter. Enter the quantum computer. And I'm not going to, in what follows, dispute the completeness of what is computable by a Turing machine. A quantum computer can compute essentially the same things, however, there are certain reasonable sized problems which would take a supercomputer the size of the Earth longer than the lifetime of the universe to calculate that is reasonably sized quantum computer could do in your lifetime. Now, a computer is not much good to you if it can't give you the answers before you're dead. So I consider this a fundamental difference in capability. That quantum computers for certain problems are so much faster that it makes possible in this universe problems that a regular computer could not do. The history of the quantum computer, like many things in physics, goes back to Richard Feynman. 

Richard Feynman, in a talk titled Simulating Physics With Computers, he proposed this quandary that was really disturbing him, that it had been proven that in order to simulate a physical system with all of the full laws of quantum mechanics that on a regular computer the number of bits that it would require, or the amount of information storage that it takes to simulate that system, is exponentially larger than the number of particles in the system itself. So even if you were storing information at the atomic or even subatomic level, you still would need a computer that was massively larger than the system you're trying to simulate. And he said now wait a minute, nature can do it. If you want to know what happens in a physical system like shaking up this glass of the water, all nature needs is the particles that are in this bottle in order to figure it out. So he said there must be some mode of logic that we're missing. And what he proposed was to use the actual physical transformations from one state to another as his logical elements. And he had a really interesting thought because he was a theoretical physicist that like many theoretical physicists has a lot of problems with the idea of quantum mechanics because it's weird. And he suggested that if we are able to build this thing, first of all it will be wonderfully useful to physicists because we'll be able to figure out what will go on in a lot of situations, simulate a lot of physical systems. But also, by looking at how the actual device works once we've built it, it might actually teach us something about quantum mechanics. The next step in the evolution of the quantum computer was in three years later. 

David Deutsch figured out that actually the quantum computer that Feynman had proposed would be useful for more than just simulating physical systems, that it actually was the universal computer in the sense of the Turing machine. And he called this a quantum Turing machine but that it was capable of solving all the same problems that a Turing machine would be able to solve. Now, this didn't really go anywhere. It was interesting to physicists and maybe some computer scientists. But it was still sort of a little bit of a nerdy fascination. If we could build this thing, wouldn't that be cool. Until, in 1994, Peter Shor came up with Shor's algorithm. And what Shor's algorithm does is it takes large composite numbers and it factors them into their prime factors. Now this also just seems like a kind of esoteric thing that why is that interesting? Well, the reason that it's interesting is because all Internet security, all Internet commerce, the security of all financial transactions, is based on the notion that factoring numbers into their prime factors is difficult. So this was a shocker because all the sudden people said wait a minute, if we can build one of these things, that changes everything. 

And all the sudden there was funding for it because every government wanted one. So this was sort of when really things started ramping up with people really wanting to build a quantum computer. Now, I'm going to pause for a minute to explain how the quantum computer works, and in order to do that I need to teach you a little quantum mechanics. So, the most famous example in quantum mechanics, I think, is Schrodinger's cat. Most of you have probably heard of this but what the details of the setup are, this is a thought experiment by Edwin Schrodinger, and he was a man who did not like cats. I actually had a discussion with the chair of our department in which he told me that they had looked into hiring Schrodinger but they couldn't because of moral issues. [LAUGHTER] Not sure exactly what the details of that were. But the way that Schrodinger's cat experiment works is you take a small amount of radioactive material, not enough that it can actually hurt anyone, not enough to hurt you, not even enough to hurt the cat, but what radioactive material does is it emits particles at completely random intervals. That's what makes it radioactive, the emitting of particles. So you take that and you put it in the box. 

And then also in the box you put a Geiger counter, and the Geiger counter sets off a click every time it sees an emitted particle. And you hook up the Geiger counter to a mechanical hammer and underneath the hammer you put a capsule of poisoned cyanide gas and you put that all in the box and you put a cat in the box and you close it up. So what's going to happen? After a certain amount of time, there is some probability that the radioactive chunk has emitted a particle. The Geiger counter clicks, the hammer smashed, the capsule broke, and the cat is dead. But there's also some probability that it didn't because the emitting of particles from this radioactive material is at completely random intervals and no particle has been emitted yet and the cat is still alive. So the box is closed so how do we know which one it is? Well, the quantum mechanical answer is that it is both. It is in the state of being both alive and dead. It's what we call a quantum superposition. Now, Schrodinger actually proposed this in order to demonstrate, not how much sense quantum mechanics makes, but how little sense it makes. He brought this up as an example to say that well this is absurd, you can't talk about a cat being both alive and dead at the same time. 

And the problems here is that quantum mechanics does not work very well with large systems because there's too much going on. There's no way you can possibly isolate this. The walls of the box are always going to transmit vibrations even if you seal it perfectly with a vacuum around it. Unless the wall, it's a double wall with both walls being perfectly at absolute zero, there will both be radiation emitted between the walls of the box so there's no way to do it. So we can't actually seal it up perfectly. It does raise a lot of philosophical questions about what state does the cat think it's in. But that's better left for discussing over a beer at the terrace. But what I do want to stress is that for small systems, ones that we can isolate very well, we actually do see behavior like this where as far as all the experiments are concerned, a small particle can be in multiple states at the same time. And I'm going to give you an example of that. So this is possibly the most famous experiment in quantum mechanics which is the Stern-Gerlach experiment. 

And the way this experiment works is you have a furnace which has a bit of silver in it. And the silver heats up and those atoms get very hot and they start bouncing around and they want to fly out of the box but there's only one small hole so they all have to fly out in the same direction. So you end up with a beam of silver atoms. And then we're going to shoot those silver atoms through a magnetic field that we've set up here by having opposing north and south poles. Now, silver is, I believe, element number 47, anyway it's definitely an odd number, and that's important because you have one unpaired electron. And the one unpaired electron means that these atoms will have some magnetic moment, they'll act like tiny little bar magnets. Now, if classical physics had its way, what would happen when we shoot these tiny bar magnets through, and they're all randomly oriented because they're super hot in that furnace, so they're bouncing around every which way, they have no predefined disposition to be in a certain direction. Well, some of them would be aligned with the magnetic field. Their north poles would be facing the south pole and they'd be attracted to it. And they would be bent down. 

But some of them would be a little bit to the side and they might go down but not quite as much. There's no force to the left or right because the magnetic field gradient is only vertical. So they would go down but not quite as much. And some of them would be perfectly perpendicular to the magnetic field, and they would just go straight. There'd be no force on them at all. And some of them would go up a little bit and some of them would go up a lot. And you'd get sort of a smear and you see that here. The classical prediction is just a smear of atoms. But that's not what they saw. They saw two distinct dots. 

The atoms went either up or down and they did so by exactly the same amounts. There was no in between. And this was completely shocking to the physics community at the time. This ran counter to all of the current physics thought at the time. And it was really the beginning of the quantum era. It really convinced a lot of people that quantum mechanics was valid. Because there's no other way to explain it unless the, what we call the spin of the electron, which is what gives it its magnetic moment, is quantized. It can be aligned with the field, it can be aligned against it and there are no other choices. What's interesting about this is that where you put your magnetic field matters. It was our choice, our conscious choice, to align the magnetic field vertically. 

We could have put it side ways, which I'll talk about in a minute. But we aligned it vertically. And that was essentially a measurement. The applying of the magnetic field to these atoms is a measurement which forces them to choose one state or the other, but before that time they were in a quantum superposition of being up and down. And that is a really useful notion. In classical computers, your information is stored in bits. Zeros and ones. And a bit can be either a zero or a one. And when you want to store more information, if it's an essay or a picture, you build this up out of little zeros and ones. And you put it all together you have some code, ASCII code gives you the alphabet. 

That's how you store all of your data. In a quantum computer, we use what we call a quantum bit, or a qubit for short, and a qubit, because it is a manifested as a quantum system, it can be in a quantum superposition of two states at the same time. So, for example, in the Stern-Gerlach example we can have either spin up or spin down. Well, we'll say that spin down counts as being in the zero state. And spin up counts as being in the one state. And what this funny notation here, this is called Dirac notation. It's really useful for doing a lot of calculations in quantum mechanics. You don't need to worry about any of what that means right now except that everything from this bar to this greater than sign with the zero in between, that means being in the zero state. These numbers before them, the alpha and the beta, those tell you the probability of finding that system in that state. And those are complex numbers which means that they have both an amplitude and a phase. 

And their squares, it's actually their squares that tell you the probability. And their squares need to sum to one because, of course, the probability of finding this system in some state is 100%. The probability that those atoms went either up or down is 100% because they have to go one way or the other. So they're in either the up or down state, they're in either zero or one, but not until you actually measure them. Before then, they can be in a mixture of the two. They can be in a pure state if we set them up that way. But we can set them up to be in a quantum superposition. And I'm going to explain how you can do that. First I'm going to show you a picture that explains a little more graphically about the qubit or the two level system which are equivalent. So this is the block sphere, and at the top I have the zero state at the north pole there. 

At the bottom I have the one state at the south pole. And this sphere shows you that all of the surface of this sphere are valid places for the value of your qubit to be. Because you have that alpha and beta, they're both complex numbers. They need to sum to one. So that gives you one equation which tells you that it has to be on the surface of that sphere. The length of this vector has to be one. That puts it on the surface of this sphere. And also we disregard any overall phase between alpha and beta because there's no way to measure that and it doesn't really matter. And anyway the end result is that you can picture the value of that qubit as being somewhere on this sphere. So it can be zero, it can be one, or it can be somewhere in between. 

And a 50/50 chance would be somewhere on that equator. So how are we going to set this up? Well, let's think about what would happen if we took the Stern-Gerlach experiment and we block the beam that went down. So we only let through atoms that were spin up. I'm going to represent that as this entire box here. The up arrow means that this is a filter for spin up silver atoms. So we send in a beam of randomly oriented atoms and the only ones that make it through this are spin up. So 50% of them will make it through. Well, what happens if we put another one after? Completely what you think. It's totally predictable. All the atoms that make it through the first one are spin ups, and when we filter for spin up again, they will all take the upper path and they will all make it through the second apparatus. 

Then what happens if we turn the second one upside down? If we filter for spin up and then we put a spin down filter after that, all of them are blocked. It makes sense because they all are spin up. If we then measure which direction is the spin, none of them will have spin down, none of them get through. It makes sense, right? Starts getting interesting when we ask, what happens if we turn the apparatus on its side? Because remember, there were only two choices for which way the atoms would go when we put it through that initial experiment. They either went up or down. They had no preference left or right. There was no information about it because the only choices were up or down. Well, what ends up happening is all the spin up atoms that go through, because they are exactly halfway between being spin left and spin right, if we turn this apparatus on its side and filter for spin left, 50% of them will take the left path. And they will make it through. Now, we say that the atoms at this point were in a quantum superposition of being spin left and spin right because they had absolutely no information about whether or not it's left or right. 

Despite the fact they were completely randomly oriented here, we forced them to all be spin up by measuring them using this vertical magnetic field and taking only the ones that are spin up. It's what we call a quantum superposition. The up state is a quantum superposition of being in the state's left and right. It gets even more interesting if we put three of them in a row because remember when we filtered for spin up and then we filtered for spin down, nothing got through. But if I stick a third one in between the two, all the sudden I get atoms through which kind of makes no sense at all because at this point they were all spin ups. So when I check if they're spin down, none of them should be spin down. But they are because measuring them in the left/right basis is completely perpendicular to the up/down basis, and they lose all information about the fact that they were ever spin up. When we force the atoms to be spin left here by only letting through the half of them that are spin left, they don't care that they were up before. They're not left and a little bit up. There's no such thing as left and a little bit up because there are only two choices. 

There's no such thing as right and a little bit up. There are only two choices, and it depends on what direction I measured in. But in this case, at this point, they're either left or right, and there's no other information that can be carried along with them. So then when they're all left and I measure whether or not they're spin down, well, spin left is a quantum superposition of the up and down states and now I get half of them coming through this one. So half through here, half through here, and half through there, an eighth of the atoms that made it through initially actually make it out even though if I took away this middle one, none of them would make it through. So that's how you can create a quantum superposition using a real physical system. And we use that. We say that that physical system in a quantum superposition is equivalent to a logical state of being a superposition of a zero and a one at the same time. Well, how is that useful? Let's say I was a hacker and I was trying to break into your email account. Now if I just had a regular computer, I would have to try the passwords one after another after another one at a time, and it would take me a very long time. 

But if I have a quantum computer I could create a quantum superposition of all of the possible passwords and put them through whatever checking algorithm for the password there is all at the same time. Now I'm skipping over a little bit of detail because obviously if we could do everything all in one step then quantum computers would not only be exponentially faster, they could do any algorithm in one step. The difficulty comes in in actually reading out whether or not you found the correct answer, which I will save for another day because it's complicated how the algorithms actually work. If you'd like to talk about that a little bit after the talk, we can talk about that. But I want to give you an example going back to Shor's algorithm exactly how this would work. So here I have two large numbers, six-digit numbers, that I have happen to know that those are prime numbers because I looked them up on a list of prime numbers. Now, if you were to multiply those two together you'd get another big number. But it's still pretty easy to do. You punch that in your calculator, it gives you the answer, it's not a hard problem. That is equivalent to the way that a computer checks whether or not you have the correct password. 

The numbers that you put in needs to multiply with another secret number and give you the correct number. Now, doing the reverse problem, if I were to give you this huge number, 10 billion, 967 million-something, and I asked you what two numbers multiply together to give me that number, I think that would take you a very long time to figure out. And that is a very hard problem, and it's traditionally always been difficult. No one knows how to do it quickly on a classical computer. However, it's not hard if you can try all the possibilities at the same time. This is where the quantum superposition comes in. If we create a quantum superposition of all of the possible numbers that are less than this and it's actually easier than that. You only have to do the numbers less than the square root of that in order to find the factors because one will be less than the square root and one will be more than the square root. Then you try all of those numbers at the same time and you get the answer. So this gives what we call an exponential speed up, and what we mean by an exponential speed up is that on a classical computer doing this algorithm would take a number of steps that is exponential in the number of bits in your passwords. 

So N here would be the number of bits in your password. And so A to the N, where A could be any number, like two, would be how long it would take. And that base A it could change depending on the details of your algorithm. But, for example, if you had a hundred bits in your password, two to the 100 is over 10 to the 30. So one with 30 zeros after it. A huge number. However, on a quantum computer, Shor's algorithm can do this in what we call polynomial time, which means that the N is in the base and the A is in the exponent, which is quite different. If you look at instead of two to the 100, 100 to the two, that's just 10 to the fourth, that's 10,000, which in comparison to 10 to the 30 is tiny, and as N gets bigger and bigger, these numbers diverge explosively. So what is the current state of the art in terms of numbers that have been factored by a quantum computer? Well, they have successfully factored the number 15 into three and five. So three times five is 15, and there are groups that are working on factoring the number 21. 

Does anyone know what the prime factors of 21 are? What two numbers multiply together to give me 21? [INAUDIBLE] Seven and three. Very good. [LAUGHTER] So you are all as smart as the world's most powerful quantum computer. Congratulations. [LAUGHTER] Another aspect of how powerful quantum computers can be is how densely they can store information. So how the amount of information storage builds as you add more qubits, more quantum bits, to your system. It doesn't just go linearly. It's not like one qubit gives you one more unit of information. Because the system of states, represented again by this funny Dirac notation here, this is a state, this is a state, and this is a state, we have all the possible permutations of those individual qubits, and if you wanted to, I could store a number in the amplitude of each state so the probability of a qubit being in each state and making an analogy between that and bits. So for example, for three qubits I have eight possible states. 

And so by turning on and off the probability that that qubit is in a certain state, I can treat those as bits and effectively I have two to the N bits of storage for every qubit, and I'm subtracting one off of there because all of these amplitudes do need to, their squares need to sum to one so that means that you can't have them all be zero which takes away one possibility. So how much is that? Well, in my lab over in Chamberlin Hall, we are working on building a 64-bit quantum computer. So if I had two to the 64 bits of storage, that's equivalent to 4.6 million terabytes. And my laptop has a one-half terabyte hard drive which actually is pretty large but it's nothing compared to this. So it would be the equivalent of over nine million MacBooks Pro. So how do you like them apples? [LAUGHTER] All right, so now remember when I went through all of the different ways that you can make a classical computer, in the same way there are a lot of different ways that you can make a quantum computer. The quantum Turing machine is a theoretical model the same way that the classical Turing machine is. And there are a lot of different ways that we can instantiate it. So we really only need two things. We need a system that's very small in order so that it behaves quantum mechanically so that the effects of quantum mechanics are obvious and we can use these quantum superpositions. 

And we also need to be able to isolate it from the rest of the world so it's not like the cat in the box where the quantum state decoheres because there's too much interference with the outside world. And we would like to be able to control it also. So a number of ways that you can do that. First of all, a single photon is a wonderful quantum entity because it's pretty much as small as you can get. A massless particle, you can't get any smaller than that. And that was actually the original way that Richard Feynman proposed to build a quantum computer was to use the polarization states of individual photons. The problem with doing it that way, there has been some success with that method but you can't do logic between multiple qubits that way because photons don't interact with each other, you need some sort of mediator like an atom. There are groups that have used nuclear magnetic resonance which is the exact same technology that you have in an MRI that you would get scanned by except in this case they're going to scan a little vial of some molecules and what they can do is they can detect the state of individual, for example, hydrogen atoms in a long molecule. And they'll say that each hydrogen atom represents a qubit, and its state tells you whether or not that qubit is a zero or a one. Now, here at the University of Wisconsin, Professor Robert McDermott is working on a method called Josephson junctions which they use a superconducting charged island. 

It's a very tiny device they have in a giant refrigerator and they get it very cold, and the charge that is going around a small circuit is actually quantized, and that can only have certain levels, and they use that to represent their qubits. Another method also being worked on here at the University of Wisconsin by Mark Eriksson is called the quantum dot. And the quantum dot is another solid state technique, just like Josephson junctions, where they have a small circuit that actually traps a single electron at one point. And the advantages of these techniques is that they use the same manufacturing process that we use to make all of our microchips today. They use lithography and silicon, and they can basically draw these circuits. So this a good avenue to go towards because once they get this working, they will be able to scale it up very easily because we already have the technology to make large circuits this way. But the current leader in terms of number of qubits, which is 14 by the way, the largest quantum computer that has been built they've successfully entangled 14 qubits, are the ion trappers. And that's actually a group in Innsbruck that holds that record right now. And what that means is that you have an ion which is just a charged particle. It's missing one electron so it has some overall positive charge. 

And you can manipulate it easily. All you have to do is charge up two plates and you can apply and electric field and you can move that ion around. So you can trap them very easily and you can manipulate them very easily. Also, they have a large electric field themselves because they are charged. And so that can affect other ions that are nearby. And that's how they do the communication between qubits and have logic work between multiple qubits. The problem with this method is that you can't turn that interaction on or off. The ions always have whatever charge that they have and it's difficult to control it. So my group, my adviser, Professor Mark Saffman, he's an atomic physicist, which means that traditionally he studies the interaction between light and atoms, and we are applying the methods of atomic physics in order to try and build a quantum computer. We are not the only ones. 

There are other groups working on it. But what we do is we, our atom of choice is the cesium atom. And what is interesting about cesium is it's one of the alkali atoms which means it's on the far left-hand side of the periodic table. And all of the atoms in that column share something in common which is that they have one lonely valence electron. All of the other inner shells are completely filled. They're happy, there are no more electrons that can be put in there. So if you shoot a laser beam at this cesium atom, chances are it's only going to affect that outer electron. And we can take that electron and we can bump it up to a higher state without actually knocking it off the atom. So we can change the state that the cesium atom is in. So as a result, what we can do is we can manipulate one electron, but we only have to hold on to an entire atom, which is a lot easier than holding on to a single electron. 

And so that puts us in a pretty good situation. And the way that we trap these cesium atoms is in something called a magneto-optical trap. And what a magneto-optical trap does is you would have your cesium atom right in the center there and there's a laser beam coming in from each side, all six directions, each of these arrows represents a laser beam pointing in at that atom. So if the atom moves in one direction, it sees a laser beam coming at it, and if it moves  another direction, it sees a laser beam coming at it, and which ever direction it goes, it's slowed down by those laser beams pointing at it. So we can cool this atom tremendously, and we can get it down to micro-Kelvin temperatures, which is wonderfully cold. And actually the coldest things in the world, Bose-Einstein condensates, have been made using magneto-optical traps like this along with some other techniques. But we can get it colder than anything in the universe while our set up is still at room temperature, and we don't need a huge fridge in order to do it. So that's really convenient. And what we are planning on doing then is we're going to make an array, an eight-by-eight array of 64 of these magneto-optical traps, and we're going to trap 64 cesium atoms and we're going to have a lot of lasers pointing at this thing that it needs to be very precisely controlled in order so that we address the correct atom and that we can change the states the way that we want and we can turn on the interaction between these atoms by changing what state they're in. And this here is a picture of my lab and it's very messy. 

But I like to think this is somewhat of a visual analogy between this and ENIAC, which is also this huge room filled with boxes and wires. What you're seeing here is these are optical tables covered with a bunch of mirrors and lasers and beam splitters, all basically preparing the correct frequencies to point at our tiny little array of atom traps. And then we have computers in order to turn the lasers on and off at the correct time in order to manipulate the atoms in the way that we want. And if everything goes according to plan, we will have a 64-bit quantum computer. And for reference, there is a study that I read that showed that the largest supercomputer in the world currently is equivalent to a 40-qubit quantum computer for a certain problem. Now, unfortunately that would be 40 perfect qubits. So a physical qubit might not exactly behave the way you want because it has some temperature, other atoms sometimes come into your trap and knock your atoms out. Problems happen so we have to have error correction. And error correction means you need redundancy. So we actually need more physical qubits than we will have logical qubits and depending on how on the fidelity of our gates and our state preparation, that ratio may be as bad as five to one. 

So we may end up with something like 12, 13, 14 qubits. But if our system turns out that we do it better than that and we isolate it better and there's lower noise, we may get more than that. So that would be very exciting and so we're hoping to build a 64-qubit quantum computer. If we work quickly enough, it may be the largest supercomputer in the world, although being the smallest. Now this is not my last slide, this is my second to last slide. I would like to thank my adviser, Professor Mark Saffman, and our funding agencies and everyone who works in my lab. So I'm still learning a tremendous amount about this subject. I think it's very exciting. My last slide is I'd like to give you a little more information if you are curious to look up. I thought it was better to leave you with some other directions to go if you want to know more. 

And a few things to look at. The page about all of the quantum computing research going on at the University of Madison, QC.physics.wisc.edu, and if your smartphone is capable, you actually can zoom in on these things and take a picture and it will take you right there. But if it's not, don't worry, just Google it. If you want a really in depth treatment of quantum mechanics, the go-to book is by Nielsen and Chuang. I actually met Ike Chuang last month. He's a really cool guy. This was at a conference. He had answers to every single question that anyone asked even if it was not his talk. And his book is wonderful. I recommend that. 

This link will take you to the Amazon page. That's a fairly long book, but if you want really the reference for quantum computing, that's what to look at. And this last link is to the original paper by Richard Feynman, actually it's a transcript of a talk by Richard Feynman. And if you want to find it, just Google Simulating Physics with Computers by Richard Feynman. And that's a really interesting read because everything that he's ever written or said was just explained really beautifully. So that is what I will leave you with. Thank you very much. [APPLAUSE]