Daniel and Kelly’s Extraordinary UniverseWhat's so exciting about quantum computing? (featuring Scott Aaronson)
Daniel and Kelly chat with Dr. Scott Aaronson about quantum computing, and try to bust through the most common misconceptions.
Hey, everyone, Daniel here. You know you hear the word quantum a lot, like a lot a lot, mostly in places where it makes no sense. I see it on advertisements for pest control companies or financial firms or laser tattoo joints. Okay, lasers actually are kind of quantum, so maybe that one works. But the point is that the word is so ubiquitous that it's come to mean very little. But it does have meaning. It evokes something modern and mysterious, because in the last one hundred years, physics has discovered that the world is very mysterious and operates under very different rules than the ones we are used to the world that we experience, the one that Aristotle and Copernicus and Galleo and Newton and even Einstein we're trying to understand is something of an illusion. When we peel back that layer of reality and see what's happening underneath, we discover that the rules of the microscopic universe are very different, almost alien to our intuition. And so of course people wondered, almost immediately, hey, what can I do with this? Can I take advantage of that to make my video games faster or hack into my school computer and change my grades because hey, what else is fundamental physics?
Good form? All right?
But jokes aside, quantum computing is something you hear a lot about these days. There's a lot of information and plenty of misinformation out there. Is it just another marketing ploy like quantum wasps appers or is it like the first computing revolution which completely transformed our society, our economy, and our daily lives. So today on the podcast, we're excited to be talking to Professor Scott Arenson, one of the world's top experts in quantum computing and a renowned communicator who can help us answer the question should we be excited about quantum computing? Welcome to Daniel and Kelly's Extraordinary Universe.
Hello, I'm Kelly Waiter Smith, and I sort of think I understand how quantum computing works, but I'm never really sure.
Hi.
I'm Daniel. I'm a particle physicist, and I simultaneously understand and don't understand quantum computing.
That's very appropriate. I think I think I understand it enough to get that joke, which makes me feel pretty good.
Oh, you're pretty clever.
So what is your favorite product that has been pitched as being quantum that makes you laugh.
I once sat next to somebody on airplane who told me she was a quantum messuse. I was really wondering about how that worked, and I asked her a bunch of questions and I didn't reveal my expertise, but I didn't learn anything about quantum mechanics, and that conversation just something about.
People, you know, yeah, yep.
It was it like maybe she's giving you a massage, maybe she's not, and you don't know until you pay. That's the thing that reveals if it happened or not.
No, it was more like spooky action at a distance, because she massages you without actually touching you. She like waves her hands nearby, and that somehow, through quantum mechanics influences your muscles and joints and whatever. So she was charging a lot of money. Also, people were paying her big bucks for this effect.
I would be so grumpy if I paid for a massage like that, like you really got to get into my muscles if I'm paying you. But anyway, okay, well that's amazing. I once heard it was a quantum self help talk, and the whole time I just couldn't, could not understand how quantum, like how thinking about it from a quantum way was helpful at all, And it just left me completely baffled.
I think people just latching onto the idea that the world is fundamentally different from the world we thought it was, that it works in a different way, it follows different rules, and that feels a little bit like magic. You can sort of grab onto that and smear your business with a little bit of that sparkly quantum physics stuff, And this feels like maybe you can do something which seemed impossible.
When I think quantum is particularly likely to get used in that way because it's confusing. I mean, maybe it's not confusing to the people who study it, but for like lay people, it just sounds so unclear. And I think that you can feel like you understand it and yeah, but definitely feel like using the word quantum makes you sound smart and then you just run with it. And so I'm excited to see what our audience thinks quantum computing is all about, because I until I married Zach, who likes giving me literally three hour lectures on car rides about what quantum computing is. Well, I'm driving and can't escape. I didn't feel like I knew. So let's see what does the you know, what does the general public, in particular our audience think quantum computing is.
So I reached out to our listeners and I asked them what's different about it quantum computer. Here's what listeners had to say.
Quantum computers do multiple calculations at once, and each time you add a bit it goes up by exponential numbers faster.
But especially they do not overheat.
I don't know anything about quantum computers.
You can actually get an answer faster because you can determine the probabilities rather than brute forcing it.
Quantum computer works with superpositions instead of ones and zeros. That gives it advantages for some calculations, but makes it worse for other calculations.
But quantum computer is like having five hundred and eighty thousand people all typing one word of the book, all at the same time, but in order.
A quantum computer is different because you'll never show with it to turn it on and off again or off and on again.
A quantum particle can be in.
A superposition on off or on and off at the same time.
A quantum computer can use three bits I think spin up, spin down, and I think something in between.
A quantum computer runs on quantum mechanics, which makes it capable of calculating the probabilities in a situation where randomness is involved.
Does a quantum computer not use binary code zeros and ones so there can be more options, which.
Makes it more powerful.
Possibly quantum computers use q bits that are super cooled and have many many states rather than the binary transistor logic that only has off and on.
Quantum computing is all about probabilities.
With a quantum computer, you can't tell if it's on or off until you hope the box it came in.
A quantum computer uses quantum fluctuation for its processor and explores every possible answer instantaneously.
How this is useful for our computation is still beyond my understanding.
Computer uses quantum technology to search all the random variables that possibly happen and come up a handurd solution.
I think quantum computers process really small numbers. Do they do computations on extremely tiny numbers? I'm not sure what is different about a quantum computer that.
Makes use of superposition of states to give nearly infinite possibilities.
The size of the processor or the flip flops. So now we're down on a quantum level versus the smallest transistors we have at this moment.
Other them its fast are really about nothing.
What's different about a quantum computer. I don't really know much about how quantum computers work, but there's something fundamentally different about how the bits, essentially we're being.
On or off.
And that's not something I know the details of.
I'm not surprised that our audience had detailed and insightful responses to this question.
That is awesome, But you know.
You and I decided this is a complicated question, and well, I'm sure Daniel could have explained it on his own. We thought, you know, it might be a good idea to bring in Scott Aronson, who's an expert on quantum computing, has been working on it for a really long time, and so we're bringing you a conversation that's a collaboration between Daniel and Scott Aronson. So, Daniel, where do we start?
So I think the place to start with understanding quantum computers is first with the word computer, Like what do we mean when we say computer? And this isn't just like philosophical rabbit hole. I think it's important to think about what a can is, what a computer does, not just the kinds of computers that we have, but other kinds of computers, what possible computers there are, because then we can compare the different kinds of computers, we can understand what they have in common and what they don't have in common. Because computers are not just something that sits on your desk or the thing inside your phone that makes it go. A computer basically is something that computes. It's something that gives you an answer to a question, you know, and that can be something very simple, like you can have a baseball and you throw the baseball. That gives you the answer to what happens when you throw a baseball, and that can be kind of a complicated calculation. You know, you have to take into account gravity and air resistance and the spin of the Earth and all this kind of stuff, and the baseball does that for you. It computes the answer to that question. And that's not a very exciting computer because that's basically all it can do other than let you play baseball. That one just answers one question. In general, we're interested in computers that can do lots of different kinds of calculations, and one kind of computer is you. You know, back in the middle of last century, what they called a computer was a person like at NASA who sat at a table doing calculations pencil and paper to figure out how are we going to shoot this rocket and what angle do we need to go at, because that was the best way to do those calculations. And humans pretty good at doing lots of different calculations. So a computer can include the thing on your desk, the thing in your phone, a baseball, even a person, right, and all these computers, some of them are good at different kinds of calculations, Like the ball is excellent at calculating where the ball is going to go, but terrible at everything else. A human is pretty good at some kinds of things and not that great at other kinds of things. Like a human is really good at doing things like spotting a tiger in the grass. Your brain is really efficient at noticing things that look like predators, not so great at other things like adding up all the numbers between one and a trillion. I mean, maybe you can find some mathematical shortcut, but if you have to actually add them up, it would take you a long time. It's not the kind of thing your brain is efficient at now. The kind of computer where, of course are interested in. It's not baseballs or tigers. It's the kind that are programmable, the kind that can basically do any kind of calculation. And this is something that's kind of incredible that we can even do. We have a question we want answer, it's some calculation we want done, and we build a computer which is like a machine, build a physical objects that we can manipulate in a way to do our calculation. That's the amazing thing about programmable computers that when you build it, you don't have to know what kind of calculations you want it to do. You can build it in such a way that it can do almost any kind of calculation. That's sort of amazing. We're taking a real world problem and then we're building a device that can calculate the answer as long as we can represent that real world problem somehow in the language of that computer. So these are deep issues and fascinating questions. To help us understand what is computing and how quantum computing is different from regular normal computing, we talk to Professor Scott Arenson. He he's a professor of theoretical computer science at the University of Texas at Austin. He's worked with open AI on the theoretical foundations of AI safety. He writes a wonderful blog about quantum computing called stettl Optimized, and he's maybe most famously the author of quantum computing since democratis. And he's a lot of fun to talk to. So we're very glad to have Scott on the show. And our first question for Scott, who's a professor of theoretical computer science, is what is theoretical computer science anyway?
So it's a field that's usually considered to have started with Alan Touring in the nineteen thirties, who came up with a theoretical model of what a computer could be, which was called the touring machine.
So when Scott is talking about a touring machine, he's not talking about any kind of computer anybody's ever actually built. This is like the computer science equivalent of a thought experiment, right, It's a thought computer. It's something Alan Turing came up with. It's the simplest kind of computer he could imagine, and it's a computer that, again you would never build. But it's very simple. Imagine a computer that has a tape on which there are written numbers zeros and ones, for example, and you can read the tape. It can move the tape forwards and backwards. They can also write to the tape, so you can do all the basic stuff that we think computers can do. Right. It can read in information, it can do a calculation and decide what it's going to do next. It can write onto the tape, so it can modify that. It can store information. And Turing did something really cool, which is that he showed that a Turing machine is very simple, basic kind of thought. Computer can do any kind of calculation that any computer could do. So if it was doable on a computer, you could do it on a Turing machine. That doesn't mean a Turing machine is the best way to do it or the right way to do it, but because the Turning machine is so simple, it let you think about the kind of things computers could do.
Well.
You could say, if you can do it on a Turing computer, then you could do it on any computer. And it's easier to prove theorems and think about stuff on a Touring computer. And again, a Turing machine doesn't lend me you to thinking about the kinds of computer that we've been building. It can explore the kind of things any computer can do.
When Touring used the word computer in the nineteen thirties, you know, that was what it meant people, usually women, who were hired to do computation. And he came up with his model of the Touring machine by trying to idealize what such a person would be doing. You know that they'd be reading symbols on a piece of paper, maybe you know, crossing them off, replacing them with new symbols, you know, moving back and forth on the paper. They would always be doing so according to some rule that they knew or had been taught. There is nothing in the concept that is tied to you know, it has to be built out of transistors that are etched onto wafers of silicon.
Right.
That happens to be the way that we do it now because it worked so spectacularly. Well, okay, but you know a computer could in principle be made out of billiard balls, right, It could be made out of jets of water.
Right.
You know, these would maybe not be very reliable.
Methods, and also doesn't have to be programmable and infinitely powerful. Right, anytime I build an experiment, I'm building a computer.
Until very recently, you know, there was use in analog computers, right, and people just building analog systems to simulate some physical process. You know, at some point digital computing became so good that it eliminated the use cases for that.
So it's great that the kind of digital computers we've been building can basically solve any problem. I mean, there are cobbyists to that, there are things turn computers can't do. But the crucial thing for understanding quantum computing and computing more generally is that some problems are hard, and some problems are easy. Some problems you can do quickly, and some problems you can do very very slowly. And different kind of computers are going to be good at different kinds of things, so the same with it. Like you as a person, you are a computer. You are fast or slow at particular problems. Our style of computers, what we call classical digital computers. These are good at some kinds of things and slow at other kinds of things. It's a feature of the kind of computers we've long developed, which, of course you know isn't the only way to do it. That's where we're going. But the origins of the digital computer that we've been using go all the way back to the middle of last century with John von Neuman.
John von Neuman, who built some of the first digital computers, was you know, directly inspired by tourings insights, in particular the idea that you didn't want to build a different machine for each possible function. You wanted to build one universal machine and then have it simulate any other machine by.
Giving it an appropriate program.
This is, you know, an idea that today is so obvious that, you know, it's hard to convince my students that it was ever non obvious. So today what we do in theoretical computer science is often about trying to understand what problems can be solved efficiently.
All right, And so when Scott talks about computers being efficient, he's thinking about whether they're good at this kind of problem? Can they do it quickly? As a problem gets bigger and bigger, do they become unbearably slow at solving it? Like you can add up the numbers between one and five pretty quickly, you can add up the number between one and one hundred, little less quickly. If it gets to one in a trillion, it's hopeless, right, And so for digital computers there are some problems that can be solved in principle but would take a very very long time, and the kind of computer we've been building. An example of that problem is checking to see if a number is prime. Like you can tell that eleven is prime because you can't think of any two numbers that multiply themselves together to give you eleven because it is prime. If I give you an arbitrary number seven, four hundred and seventeen, how do you know whether it's prime. Well, a computer can do this by, for example, checking all the numbers that go into it. That's just brute forcing it. There are some more clever algorithms we'll hear about later, but essentially it's very slow at checking prime numbers. So computers can do a lot of things, and the way we've usually built computers are good at some things and slow at other things. So we ask Scott, who thinks about this a lot, what kind of things our normal computers are good at and our normal computers are bad at?
Sure?
So simulating physics, you know, which you mentioned, is a great example of you know, something that computers have been used for since the very beginning, right and in some sense, you know, the entire program of physics since Galileo and Newton has been to you know, understand nature. Well. It off that we can put the initial conditions into a computer and just have a computer tell us what is going to happen.
Simulating a differential equation, you know.
In order to model fluids or gravitational dynamics, celestial mechanics. These are our famous examples of things that you know, comput uters.
Are very good at. There are issues here, you know, that have to do with discritization.
Nature is traditionally modeled in physics as using a continuum of numbers, and computers in the touring sense can only deal with discrete quantities with bits with ones and zeros. So we need some way to deal with that, right, Typically we take continuous quantities and we truncate them, we represent them only to a finite precision, and then you know, we have to understand how.
Much error that's going to cause and so forth.
But you know, in terms of what computers can do efficiently, you know, I think the classic examples that you know, we would teach in computer science are going to be things like, Okay, you know all of the arithmetic operations that we learn in school, right, adding to integers, you know, multiplying, dividing given Also, you know the thing that Google Maps does for us, right, find the shortest route between two given cities, you know, or between two addresses in the distance between each address and the immediately neighboring ones.
Right, it's finding the shortest path in a graph.
Okay. Now, there are a bunch of things that turn out to have clever efficient algorithms, even though it is sort of totally not obvious a priori that they would. For example, I give you a bunch of students, you know, I tell you who is willing to be roommates with whom? Okay, and now I ask you pair off as many willing roommates as you can. Right. This is called the maximum matching problem. Find you know, maximum number of pairs of people who are willing to room with each other A priori. That seems like that might require an exponential search, right, It might require considering an astronomical number of possibilities.
But it was discovered in the nineteen sixties that it doesn't.
There is an efficient way to solve that, That is, there's a way to solve it that scales only like the cube of the number of potential roommates something like that, rather than exponentially.
Another great example would be linear.
Programming, right, one of the most important problems in industrial you know, operations research, things like that, where you're given a bunch of linear constraints on some variables like this one plus this one can be at most ten, this one minus this one has to be at least eight, and so forth, and you're looking for a solution that satisfies all of those linear constraints. Okay, that also has an efficient solution primality. Right, I give you five thousand digit number, and I ask you is it prime or composite?
Right?
Well, you know you can try some simple things.
You know, if it ends in an even number, or a zero or a five, right, then it's composite. But you know you can check if three, if seven, if eleven, go into it, right, But more generally, right, this is a famous problem in math. It's even extremely important in cryptoc Modern cryptography sort of uses gigantic prime numbers as one of its central ingredients.
Okay, Now it turns out that there is.
An efficient algorithm that tells you whether a huge number is prime or composite.
Okay, it was discovered in the nineteen seventies.
There are probabilistic methods, and in two thousand and two even a deterministic method was discovered.
Okay, you're very very non obvious.
Now, Crucially, these methods only tell you if the number is prime or composite. If it's composite, they don't tell you what the prime factors.
Are, all right. So those are some great examples of what classical computers are pretty good at. What kind of things are they slow at? Again, a great example is prime factors. And this is really important because it turns out that it's useful to a lot of people that computers are slow at this. Like, if you know that computers can't crack this puzzle quickly, you can use it as a way to protect your information. The whole field of cryptography, of building codes and protecting information relies on some things being easy and some things being hard for computers to do.
The belief that finding the prime factors is hard is actually also central to modern cryptography. So modern cryptography, you have to be able to generate huge prime numbers quickly multiply them together quickly, which we know how to do all of that. That's how we generate the cryptographic keys called the public keys, that people can use to send us encrypted messages. But then the way that it works is that in order to decrypt the message, we.
Think, you need to know the prime factors.
If anyone had a fast way to find the prime factors of a gigantic composite number, most of the cryptography that protects the Internet would be broken.
Okay, so it is crucial that.
You know, after half a century of effort, at least the best publicly known methods for factoring numbers.
You know.
Of course, if the NSA you know knew something better, then you know, I would have no reason to know that. But the best publicly known methods you know use an amount of time that scales exponentially with the number of digits, or more precisely, exponentially with the cube root of the number of digits.
So when Scott talks about scaling with the number of digits, what he's talking about is how long it will take the computer to solve the puzzle, depending on the length of the password. Problems that get much harder very quickly when you add digits to your password. Those are good for cryptography because it makes it easy to make the problem impossible even if computers get faster. Like if computers suddenly tomorrow get twice as faster next year they're five times as fast. You don't want people to be able to crack your passwords. The good thing about the prime number puzzle is you can just add a couple more digits to our keys to our passwords, and now the puzzle is impossible. Again, this problem is easy to make much harder because it gets exponentially harder as it gets bigger. So it's easy to keep making the problem harder faster than computers are getting better at the problem. That's the key to these exponential problems. And there are a bunch of problems like this that are very hard to solve for our classical digital computers.
So factoring is a famous example of a problem that might be exponentially hard for all we know. Okay, but there's maybe an even more famous class of problems that are believed to be exponentially hard. And this includes, like most of the problems in combinatorial search and optimization that people care about in practice, and so examples would be, I give you the distances between every city and every other. I ask you to find the shortest path that visits every city. That's the famous traveling salesman problem traveling salesperson.
Call it today.
Or I give you the mess of a bunch of suitcases. I asked, can they all fit in the trunk of your car? That's a problem with which many of us have experience.
The answer is always yes, you have to try.
Arranging them in a different way. Or you know, I give you a jigsaw puzzle, you know, can you solve it? To make it hard, let's imagine a jigsaw puzzle with no picture on it, okay, or a sudoku.
The answer is always you can solve. It's just a question of how many curse words are going to be the.
Answer yes, yes, And if it's thousands of pieces, then are we talking about more curse words than there are atoms in the observable universe.
So we've reminded ourselves what it digital computer can do. Some things it can do really well and very quickly, and other things it does more slowly, and as a problem to bigger, becomes unbearably slow. But the topic of today's episode, of course, is other kinds of computers. What if you decided to build a computer using something other than zeros and ones. Remember, computer is just some arrangement of a physical system that lets you do a calculation. Doesn't have to be based on like bits that flip between zero and one and half precise values. What if you found something in the universe that operated differently, that wasn't so crisp, right, that operated under a different set of rules that you could then exploit to do different kinds of calculations, or to have some calculations be faster or slower. That would be awesome because it would complement our current computer system.
Right.
We already know that this is possible in principle. You know my example of a baseball that can do a very precise calculation that includes all sorts of effect wind resistance and the tug of Jupiter and all sorts of stuff that would be very laborious for a traditional computer to do. It can do it very very quickly, in like the time you throw a baseball. But the question, and of course, is can you make a programmable computer not a specialized one off thing like a baseball, A programmable computer that is good at the kinds of problems that classical computers are slow at. And that's where quantum mechanics comes in, because quantum mechanics does operate under different rules, and we can exploit those rules to build a different kind of computer. The crucial things to understand about quantum mechanics in just a few minutes are that rather than having to have definitive states like this bit is zero or this bit is one, quantum bits from what we call cubits, can be in a superposition of states. A superposition just means it has a chance to be in more than one state, So rather than being a zero or a one, it can be like, well, this one has a thirty percent chance of being a zero and a seventy percent chance of being a one. That one over there has a ninety percent chance of being a zero and a ten percent chance of being a one. So a superposition just means two things laid on top of each other doesn't have to be zero or one. It can be some probability of zero or one. And the fact that it can maintain these superpositions lets it do something that classical bits can't do, which is interfere If you've heard of the double slit experiment, this is like a beam of photons that go through two slits, and maybe the photons come from one slit, and maybe the photons go through another slit, and the possibility that they've gone through both slits interferes with each other, creating this interference pattern on the final screen. And it's the fact that the photons can be in a superposition of those states, that they can be maybe through slit one and maybe through slit two. Those possibilities are the things doing the interfering. So that interference is very important part of what quantum systems can do and what classical systems cannot do because the classical system like if you throw a base ball through a double slit experiment, it either went through the left one or through the right one. There's no superposition and there's no interference. Now these are quantum systems that can do this weird thing of having multiple possibilities at the same time. But then when quantum systems interact with classical systems, when you ask the quantum system, hey, what is the value of this bit? Because eventually you want to know the answer from your computer, right you have to make a measurement, you have to do something, you interact with it. That's when the universe picks one of the options. So there's a spread of possible outcomes for any quantum interaction. There's a superposition that describes the various possibilities, and measurement is the thing that collapses it that makes the universe pick one of those outcomes. So this is the way the universe works in the microscopic scale, which is weird and amazing and very different from our experience and the macroscopic scale, and it opens the door to doing different kinds of computation. Remember a computer, it's just a physical system we've arranged to calculate something we're interested in. We take advantage of the way that physical system works to represent some kind of calculation and hope that that computer that we've built is good at that kind of calculation. And because quantum computers work with these very different rules, it means they can do different kinds of calculation, and they can do different calculations quickly, and they have different strengths and weaknesses than classical computers. So here's Scott telling us more about that.
Let's now imagine a computer that operates by these principles of quantum mechanics, we'll call it a quantum computer, so.
A classical computer.
Typically, for simplicity, we like to imagine it as having a state that's built up out of bits out of you know, zeros are ones, right, and if there's one thousand bits, then there's two to one thousand power possible configurations of that computer's memory, okay. But now with a quantum computer, there's going to be vastly more configurations than that, okay, because if I have even one quantum bit or you know, what we call a cube bit, right, then it can have some amplitude for being zero and some amplitude for being one at the same time. So it can be in what we call a superposition of the zero state and the one state, you know, at.
Least before we look at it.
Once we make a measurement, then we'll force it to snap to either zero or one, and then it will probabilistically collapse to one or the other.
But before we look it can be in this superposition state. And now if I have let's.
Say three cubits, okay, then it's not enough to give amplitudes for each cubit separately from the others. Right, The rules of quantum mechanics are unequivocal. I have to give an amplitude that the three bits are zero zero zero. I have to give an amplitude that there are zero zero one. I have to give an amplitude that they're zero one zero, you know, and so on, so I have to give eight amplitudes.
So it's sort of more information dense because the amount of information grows exponentially. But why does that allow us to do different kinds of computation? Why does that allow us to solve different kinds of problems efficiently than classical computers.
Yes, I mean, of course that's the point, and that's where this is ultimately headed. But we have to be very careful about it, because if you take these three cubits and you measure.
Them, don't see those eight numbers.
Now, the cubits collapse and you just see three bits each, you know, with some probability. Right now, if I have one thousand cubits, right, then that's two to the thousand power amplitudes to keep track of their state, right, which is, you know, more than you could write down in the whole observable universe. Okay, so there seems to be that this exponentiality, you know, beneath the surface. And this is certainly a problem if you wanted to simulate quantum mechanics on a conventional computer. Okay. And actually chemists and physicists have known that for generations, right. They're like, once they started trying to apply the Schrodinger equation to you know, calculate the behavior of even quite simple molecules, right, they have to write down a wave function that has like more and more dimensions, you know, the more electrons you add, right, and this you very quickly get the problems that would tax you know, the fastest supercomputers of today. You know, let alone of the nineteen fifties when they started doing this, right, And so you know, chemists and physicists invented all sorts of hacks and approximation methods for dealing with these exponentially large wave functions. Okay, But it was not until the early eighties that a few physicists like Feineman and Deutsch, you know, started saying, well, if nature is giving us this computational lemon, you know, it is making it so hard for us to simulate atomic physics on computers.
Then why don't we make lemonade? That is, you know, why don't we build.
A computer that itself would exploit quantum mechanical principles, you know what they called a quantum computer.
And then what would that be good for?
Well, if nothing else, it would be good for simulating quantum mechanics itself, right, And that was sort of the original application that they had in mind, And forty years later, I think that that's still, honestly, you know, the most important application economic that we know. A bet that's the truth of the matter, right.
Anyone who is.
Trying to design better batteries or better solar cells, or high temperature superconductors, or better chemical reactions for making fertilizer or better drugs that you know buind a receptor in a certain way, right, they're basically dealing with a many body quantum mechanics problem. And these problems can be incredibly hard for classical computers for reasons that you know, ultimately come from the exponentiality of the wave function, right, and a quantum computer could potentially help with any of that.
Scott is pointing out a really crucial feature of quantum systems. Not only do they have these cubits that can be in superposition, but the cubits can be entangled with each other, which means the value in one bit can be linked to the value in another bit, and that's what makes them much more information dense than classical computers. It's like, instead of having three independent axes where you can just pick a number along the access, you have three pieces of information. You semble those into a three dimensional space, so now you have a three D volume of information. So they're capable of storing information much more densely because of these connections between the bits, which creates this information space, and this makes it very hard for classical computers to simulate a quantum system. It takes a lot of normal bits, classical zero one bits to calculate what a quantum system will do or what a cbe bit will do. So the first thing that quantum computers could be good for is to just describe quantum systems. It's kind of a natural application. You know, the quantum computer follows similar rules to the quantum system, and so it's natural to describe it in that way, the same way like the baseball follows the rules of the baseball. So it's a good way to calculate what a baseball will do. But of course we wonder, like, is that all quantum computers can do simulate some nerdy quantum experiment or are quantum computers also good at doing other things? Here's Scott telling us all about it.
That was the original promise.
But you know, as long as that was sort of the only promise, I think, you know, this remained very much a niche interest of some weird physicists pursuing this idea.
And you know, the eighties, the early nineties.
Now, the big discovery that put quantum computing on the map for you know, most of the rest of the world was that a quantum computer can sometimes also help to get exponential speed ups, even for problems that have nothing to do with quantum mechanics, at least for a few very specific such problems.
Can we predict these kinds of problems in advance?
Welcome to what my colleagues and I have been trying to do for the last thirty years.
Yeah, I mean, for the whole history of this field.
We are trying to figure out what is the border between what is efficiently solvable by a quantum computer and what isn't and we know a lot about it, but you know, there is.
A great deal that we still don't know.
The big discovery that sort of started quantum computing as a field, I would say, you know, as opposed to just an idea, came in nineteen ninety four, Okay, and that was when Peter Shore, who was a mathematician then at Belle Ebs, discovered that there is a fast quantum algorithm for factoring numbers.
Okay, So he discovered that the factoring.
Problem, the problem of factoring a huge composite number into primes, and some various closely related problems of central importance in modern cryptography are all solvable on a quantum computer using a number of steps that grows like the size of the number. You know that you're trying to factor squared maybe, but not exponentially with the size.
Of the number.
So this is a big deal because, as you're saying, you know, we can use billiard balls to calculate how billiard balls move, and we can use quantum systems to simulate quantum systems. But now we're using a quotum system to describe something that's fundamentally not quantum. So it gives us a clue that like, maybe we can open up a whole new category of problems.
It is totally not obvious a priori that a quantum computer should help you for factoring numbers.
You know, what does that have to do with quantum mechanics?
Right? And of course this problem is hugely important because, for better or worse, we base the whole security of the modern Internet on the belief that factoring is hard. Okay, What Sure was saying is that if and when someone builds a large quantum computer, a scalable quantum computer with you know, thousands or millions of cubits, then that is no longer true. Okay, then you can break all of the encryption that we use to protect the Internet.
So a bunch of things happened, you know after that.
You know, one was people you know kind of like with the story of Rumpelstiltskin, Right, It's like, if you can spin this much straw into gold, and then why not more? And people said, well, maybe all of the exponential, really hard problems that we're you know, dealing with, maybe quantum computers can solve all of them.
Is there any way to intuitively understand the idea here? Like what it is about quantum computing that makes this problem easier to do.
I teach a whole undergrad course where you know, at the end of it, I hope that people will have the intuition for these things.
Right.
But like, if there were a one sentence way to say the intuition, then you wouldn't have needed Shore and Grover to discover these things, right, you know, it could have been obvious from the beginning.
Right. But let me say this, right, so, you know.
What almost every popular article about quantum computing wants to say is something that sounds really appealing and is totally wrong. Okay. In fact, Zach Kelly's husband and I made a whole cartoon about exactly this eight years ago.
So throw cold water on some clickbait for us. What's wrong about quantum computing descriptions?
What almost every popular writer has wanted to say is that a quantum computer just tries every possible solution in parallel. You know, it tries each one in a different parallel universe, or you know, all of them in superposition or whatever, and then somehow magically the best one gets picked. Right. If that were how it worked, then quantum computers would solve, not only factoring, but also np complete problems. Right, they would break not only the cryptosystems that currently protect the Internet, but they would break all other possible cryptosystems you know that are based on hard problems. Okay, but that is not what we believe that quantum computers can do, right. We believe that they're more limited than that. So the question is why are they more limited? Okay?
And it all has to do with the restrictions of measurement.
Right.
It's true that with a quantum computer you can create an equal superposition over all the possible solutions to your hard problem. That's even an easy thing to do if you have a quantum computer, right, like create a superposition or each of these two to the thousand and power possible solutions has some amplitude. You know, that's just like very simple, it's done, Okay. The trouble is for a computer to be useful, at some point you have to look at it. You have to measure, you have to get an output. You know, you have to read something out. Okay. And if you took an equal superposition over all the answers and you just measured it, not having done anything else, then the rules of quantum mechanics are very clear on what you're going to see. It's a completely random answer. And if you had just wanted a completely random answer, then you could have just flipped a coin a bunch of times, or just you know, use a random number generator that's inside your classical computer. Right, You didn't need to spend all these billions of dollars to build.
A quantum computer.
Right, So the only hope of getting an advantage from a quantum computer is to exploit the way that these amplitudes, you know, being complex numbers, work differently from conventional probabilities. Okay, And the central thing that amplitudes can do that probabilities cannot do is that they can interfere with each other. They can cancel each other out. And so with a quantum computer in particular, the idea with every algorithm for a quantum computer is that you are trying to choreograph things in such a way that for each wrong answer, because each answer that you don't want to see, some contributions to its amplitude are positive and others are negative, so they're canceling each other out.
Whereas for the.
Right answer, the answer you do one you want all the contributions to its amplitude to reinforce each other, okay, to add up constructively. If you can arrange that, then when you look, you're going to see the right answer with a large probability.
That's the name of the game.
Now. The hard part is you have to do all of that even though you yourself don't know in advance which answer is the right one.
You know, if you already knew, what would be the point?
Right, And you have to do all of this faster than even the cleverest classical algorithm could do the same thing.
Otherwise what would be the point?
Okay, so nature is giving us this really really bizarre hammer and a priori.
It's not obvious whether.
There's any nails that that hammer can hit, you know, other than just the obvious one of simulating quantum physics itself, right, And it really it took more than a decade for people to discover those nails and factoring the problem that Peter Shore designed his algorithm for. That was the first big example, and some people hope that that would be followed by a flood of other examples, and you know, unfortunately, you know, thirty years later, factoring remains one of our pre eminent examples.
So I have a crazy question for you. You're telling me that quantum computers work by maintaining all of these different amplitudes and the superpositions, but that we don't have access to all the superpositions because we have to take the measurement. So we have to play clever games with interference so that we can use this system to do something useful. But we don't have access to the superpositions because of the measurement, only because we are classical objects and classical interactions with quantum systems collapse the measurement. What if we were tiny, we were microscopic, we were quantum, could then we use quantum systems in a way that didn't collapse all their wave functions and access all of those amplitudes.
So I hate to break it to you, us being microscopic wouldn't help. Right, You can be as tiny as you like, But if you interact with a quantum system in a way that carries away the information about you know, which branch of the superposition we're we in, then that has exactly the same effect of collapsing the state. Right, So it's not our physical bigness that's the issue. It's that, you know, sort of we want an answer in our universe, right, what we can say, You know, there are people who are very gung ho about the interpretation of quantum mechanics, where they would say, collapse is not real, right, collapse is just a figment of our limited perspective. Right. Really, what's going on is it's just the Schrodinger equation all the way. And so they would say that whenever you know, you measure a quantum computer that's in a superposition, Actually the whole universe then splits into all these different branches, and each branch is equally real.
We have an experience of one of them where.
We perceive some answer. So a many worlder, that's what these people are called, right, a Mani worlder would say that there is some branch of the universal wave function in which you do get the right answer right, in which you try all the possible answers in superposition. You know, they would say, well, there's some branch where you get lucky and you measure the right answer, right. And they love, you know, all sorts of crazy thought experiments, like you know, quantum suicide, right, Like why not.
Use a quantum random number?
Generator to pick a lottery ticket and then just decide to kill yourself if it doesn't end up being winning, and then in all the branches of the wave function where you still.
Exist, you know you'll have won the lottery.
Now, I do not recommend that any listeners try that, Okay. I don't think there's any principle of reason that says, you know, you get to condition on being in a branch of the wave function where you're alive.
Yeah, it sounds like a cool premise for a streaming show, but not a way to live your life.
That is the one thing that I can say in the direction of what you were hoping for, and it's not very useful, I'm afraid.
All right.
So you're sort of famous for, you know, throwing cold water on mis explanations of quantum computing and maybe even overhype. Let me flip that around and ask you what is the most under hyped aspect of quantum computing. What is the thing that you're most excited about that would make you like, take your family money and invest it in somebody's quantum startup if you heard them doing it, if I had that.
Kind of risk tolerance.
There are so many things that I knew about when they were small, that I should have been investing in. And you know, clearly it's probably for the best that I became a professor and not an investor. I mean, one thing I think that a lot of people don't realize is that, you know, we are just within the last year the experimentalists have gotten very very close to the degree of control, you know, over cubits that would be needed to build a scalable quantum computer with with what we call quantum error correction, which is the technology that would ultimately allow you to sort of keep your cubits isolated, keep them from being prematurely measured by their environment, and you know, do an arbitrarily long quantum come computation with them. Right, So people have been talking about these ideas for thirty years now, and you know, so some people you may have gotten fatigue with quantum computing. What we've known since the mid nineteen nineties is that if you can control two pairs of cubits well enough, like if you can get the error the noise in a two cubit interaction to be sufficiently small, then there are these very very clever quantum error correcting codes that can get you the rest of the way that can encode like a single logical cubit across an entangled state of tens or hundreds of physical cubits, you know, in such a way that you can survive and recover from, you know, an error on any one of.
The physical cubits.
And you know, these codes have the effect of pushing your effective error rate down closer and closer to zero. Right, but only after you've passed this critical point at which the error correction becomes a net win, which it starts making things better rather than making them worse. It's almost as if like you have to pass the critical mass for a nuclear reaction. Right, if you're halfway there, you don't get half the reaction, right, you know, you need to pass criticality, okay, And so that's sort of been the engineering goal of the people who, unlike me, have labs and not just blackboards, right, who are actually trying to build these devices. You know, that's been their goal for thirty years, and I think you know, many people might not realize just how close they are. So basically, you know, the estimate is that you want to be able to, you know, apply a two cubit gait, that is, you know, do a desired operation on two cubits with about ninety nine point nine nine percent accuracy, about four nines of accuracy, and that ought to be enough to get this quantum error correction, you know, self sustaining reaction started. And when I joined the field, which was in the late nineteen nineties, such as a few years after shores and grovers algorithms had been discovered, right, it would have been amazing if you could do like a two cubit gate with fifty percent accuracy, right, Like that would have been a nature paper, okay. But then at some point the fifty percent became ninety percent, and then that became ninety five ninety nine percent, and within the last year we've seen like ninety nine point nine percent accuracy, okay, in several different groups. You know, the neutral atoms grew Querra and Boston, the trapped ions which like Quantinuum in Colorado does superconducting cubits, which at Google and IBM are doing. So you know, so a bunch of different approaches are you know, being pursued simultaneously, but you know, several of them are getting up to this, like ninety nine point nine percent accuracy, and it looks like just one more nine and you should be at the point where you know this self sustaining reaction works. So I think that's the central case for optimism right now. For just looking at the hour raid as a function of year, it looks like either you get there in the next decade or else something surprising.
Happens, you know that explains why you didn't get there.
That's one aspect of the story that maybe is not so well appreciated.
All right, So that was our interview with Scott in conversation about quantum computing. I think the answer to the question should you be excited about quantum computing is yes. This potentially represents a whole new era of computing computers that are good at solving different kinds of problems than our traditional computers and opens our minds to the way computation can be done. Maybe there are other kinds of computers, not just classical or quantum computers, but other kind of things. Ways we can take advantage of the universe to do the calculations that we want to do. Thanks Scott very much for joining us, and thank you to everybody for listening. Tune in next time.
Daniel and Kelly's Extraordinary Universe is produced by iHeartRadio. We would love to hear from you, We really would.
We want to know what questions you have about this Extraordinary Universe.
We want to know your thoughts on recent shows, suggestions for future shows. If you contact us, we will get back to you.
We really mean it. We answer every message. Email us at Questions at Danielankelly dot.
Org, or you can find us on social media. We have accounts on x, Instagram, Blue Sky and on all of those platforms. You can find us at d and Kuniverse.
Don't be shy write to us
