There are some problems for which it’s very hard to find the answer, but very easy to check the answer if someone gives it to you. At least, we think there are such problems; whether or not they really exist is the famous P vs NP problem, and actually proving it will win you a million dollars. This kind of question falls under the rubric of “computational complexity theory,” which formalizes how hard it is to computationally attack a well-posed problem. Scott Aaronson is one of the world’s leading thinkers in computational complexity, especially the wrinkles that enter once we consider quantum computers as well as classical ones. We talk about how we quantify complexity, and how that relates to ideas as disparate as creativity, knowledge vs. proof, and what all this has to do with black holes and quantum gravity.
Support Mindscape on Patreon.
Scott Aaronson received his Ph.D. in computer science from the University of California, Berkeley. He is currently the David J. Bruton Jr. Centennial Professor of Computer Science at the University of Texas at Austin, and director of the Quantum Information Center there. He specializes in quantum computing and computational complexity theory, but has written on topics from free will to the nature of consciousness. Among his awards are the Tomassoni-Chisesi Prize in Physics (Italy) and the Alan T. Waterman Award from the National Science Foundation. His blog Shtetl-Optimized is known both for its humor and as the most reliable source of information on news in quantum computing. He is the author of Quantum Computing Since Democritus.
- Web site
- Shtetl-Optimized blog
- University of Texas web page
- Google Scholar publications
- Wikipedia
- Amazon.com author page
- Talk at TEDxCaltech
[accordion clicktoclose=”true”][accordion-item tag=”p” state=closed title=”Click to Show Episode Transcript”]Click above to close.
0:00:01 Sean Carroll: Hello, everyone. Welcome to the Mindscape Podcast. I’m your host, Sean Carroll. Here is a question of interest: How hard is it to solve a problem? That seems like a very important question, right? Especially, when we’re faced with all sorts of very difficult problems, socially, biologically, planetarilly, and so forth, but it’s also a very hard question to answer in itself, right? What do you mean, how hard it is? What kind of problems are you talking about? Happily, computer scientists have a very specific field of problems, a specific kind of problems, and they care a lot about how hard they are to solve. There is a whole field of endeavor called theoretical computer science. You can be a world-leading theoretical computer scientist and never actually program a computer, although today’s guest is not in that category.
0:00:48 SC: One of the things that theoretical computer scientists worry about is, if you have a certain kind of problem, like sorting a list into alphabetical order, how many steps does your computer program have to take to solve that problem and how do the number of steps depend on the size of the list? This is the problem known as computational complexity, and today’s guest, Scott Aaronson, is one of the world’s experts in this field. In fact, I feel bad even about saying this. Scott is a computer scientist at the University of Texas at Austin who is not only one of the world’s experts in theoretical computer science and computational complexity, but seems to be the world’s expert in many different fields. So today, we’re going to dive into things like P versus NP. This is a famous problem about whether or not a problem that is easy to check the solution for is also easy to solve. Almost no one thinks it’s true, yet it turns out to be really, really hard to show it.
0:01:44 SC: We’re going to go into quantum complexity theory, which then gets you into the question of, if you built a quantum computer, would it be able to speed up hard problems that we know about, like factoring large numbers. As Scott will tell us, many of the claims you may have heard about the potential for quantum computers speeding things up tend to be a little bit exaggerated. There really are speed-ups available, but maybe not as many as you’ve heard about.
0:02:09 SC: And on the on other hand, we’ve had a real difficulty improving any of these results. There’s a long list of things that we believe are true and haven’t yet proven. It’s a very fruitful area to go in for a young person who really wants to make a mark on a new and emerging field. But also, once you get into quantum mechanics, you’re going to become interested in things like quantum gravity, right? Who could possibly avoid that? So with Scott, I talked about black holes and the holographic principle and complementarity and how we’ve somehow gotten quantum information into the game of trying to understand the fundamental makeup of the universe. Scott is a long-term friend of mine, a collaborator on fun papers, and everyone’s favorite go-to guy when you talk about these issues, and if you listen to this podcast, you will find out why.
0:02:56 SC: If you don’t know, let me remind you that, here, during our lockdown, as long as it’s still going on, I’m doing a set of weekly videos called The Biggest Ideas in the Universe. Right now, we’re about 10 videos in and we’re in the middle of a pretty intense couple of weeks trying to understand quantum field theory, Feynman diagrams, stuff like that. There’s no mathematical background presumed, but you have to be willing to go along with me on some pretty heady ideas. So check those out, they’re on YouTube. Just go to YouTube and search for my name or Biggest Ideas in the Universe. We’re going to be getting to some even bigger ideas, the ideas just getting bigger and bigger, that’s what we’re going to do. So we haven’t done gravity or quantum gravity yet, but believe me, we will get there before too long. I hope you’re enjoying them, I hope that everyone is staying healthy and sane and safe during this weird situation we’re in. And let’s go.
[music]
0:04:00 SC: Scott Aaronson, welcome to the Mindscape Podcast.
0:04:01 Scott Aaronson: Thanks, it’s great to be here.
0:04:03 SC: You know, I recently became an external professor at the Santa Fe Institute and for… Their focus is complexity studies. And I remember back in the ’90s, this used to be a huge thing, defining what a complex system actually was, and it took me a while to catch on that people like you have a way of using the word complexity that doesn’t have anything to do with any of the complex systems that they’re talking about. So what do you mean when you talk about complexity?
0:04:32 SA: Yeah. It’s an overloaded term, right? The definition of complexity is complex. [chuckle] It’s one of these self-describing words, like shorts are short, okay. But in theoretical computer science, what people mean by complexity, let’s say, by computational complexity is the resources that are needed to solve some problem, and specifically, what we care about is the scaling of the resources. So the most common resources that you might worry about are how much time does your program take and how much memory does it use. Time and space, those are pretty fundamental.
0:05:18 SA: You could worry about other things, also, like how many random bits do you need, how many parallel processors do you need, do you need a quantum computer, what’s the physical substrate of your computer, how many qubits, how many classical bits. But we’re not so interested in just giving answers like, “Oh, I can solve problems of size 1000 using 30K of RAM, let’s say, and solve problems of size 2000 using 50K,” because that’s kind of like, “Okay, great, but tomorrow someone might have a slightly better idea and then it’ll just cut that number by a factor of 10,” or, I mean, these numbers are… They’re not fundamental features of the universe or of math. They depend enormously on details of what machine you’re using. Of course, the faster computer will be able to do the same thing but faster and so forth.
0:06:22 SA: What we really care about is how are the resources like time or memory growing as you go to larger and larger problem sizes. So for example, if I ask you to tell me whether a number is prime or composite, then we could say the input size is just the length of the number, how many digits it takes to write it down. And what we really like is to have an algorithm to solve that kind of problem that we’d use resources, the time and memory, that grow only like the size of the problem raised to some fixed power. Okay? So the number of digits cubed or something, that’s actually state-of-the-art algorithms for primality testing. That’s about how much time they do use. Okay.
0:07:12 SC: Okay.
0:07:12 SA: What we don’t want is an algorithm that uses resources that grow exponentially with the size of the problem. And the reason… I have this whole mini-lecture about explaining exponential growth, but I feel like in the age of coronavirus, that might not even be necessary. And now, maybe if there is one good thing to come out of this, maybe people now understand it, that an…
0:07:37 SC: Better understanding of exponentials, sure.
0:07:38 SA: Yeah, exactly. That an exponential… Well, by the time you’re at problems of size 1000 or 1000-digit numbers that you’d already be talking longer than the age of the universe to solve it, even if you had every atom in the observable universe working on your problem in parallel.
0:07:58 SC: So if something is exponentially hard, then we say it’s really, really hard. And if it’s only polynomially hard, then we say it’s easy.
0:08:04 SA: Exactly. Yeah. So in practice, this tends to be the dividing line that we focus on, is your problem solvable by some algorithm that has only polynomial scaling or does every possible algorithm require exponential scaling. Now, there are intermediate possibilities, there are functions that grow faster than polynomial and slower than exponential, there are… And, of course, even among polynomials, if it grew the problem size to the 1000 power, well, that’s technically polynomial but that’s not very good.
0:08:47 SA: But in practice, usually, if you can solve your problem by some method with exponentials… Oh, sorry, by some algorithm with polynomial scaling, then usually if you put enough effort into it, if you care enough, that problem size to the 100 can become problem size to the 10, can become problem size to the 3 or to the 4. Whereas if every algorithm you can find has exponential scaling then you’re just… That’s kind of saying that you don’t know anything better than some brute force approach that involves just trying every possible answer from some astronomically large space of possibilities. If you’ve got a polynomial algorithm… Yeah.
0:09:33 SC: So it seems to me that a lot of the bread and butter of a working complexity theorist in your sense and the theoretical computer science sense is the best existing algorithm takes end bits and solves the problem in N to the 2.4 power steps, but I can find an algorithm that does it in N to the 2.3 power steps, so now I’m the winner.
0:09:55 SA: Yeah. That is certainly a game that people play, or even to improve N to the 2.4 to N to the 2.4 divided by a log of N, or something like that. That’s a little bit looked down upon, just shaving logs off.
0:10:11 SC: Okay.
0:10:11 SA: But yeah. So basically, we want to know for various important problems, by important problems like, let’s say, multiplying numbers, multiplying matrices, telling whether a number is prime, deciding the truth or falsehood of a sentence in mathematical logic or a scheduling… Scheduling airline flights, not that anyone is doing that right now. But figuring out how a protein will fold that might fight the coronavirus or something where the size of the input would be the number of bases, the number of amino acids in the protein.
0:11:06 SA: So these are all the sorts of problems that people might care about and you want to know what is the inherent difficulty of each one, so in a way that does not depend on the details of are you using a Mac or a PC, but that really just ultimately depends on what are the laws of physics that underlie your computer. And so on the one hand, that means finding the fastest algorithm that you can. But on the other hand, that also means trying to rule out that you can do any better than some limit. So trying to prove that some algorithm is the best one. Now, that is a lot harder. It’s a lot harder to prove a negative than to prove that nothing can solve some problem than to just find a way to solve it. But often, what we can do is that we can at least pass the blame to someone else.
0:12:04 SC: What does that mean?
0:12:06 SA: In the following sense that… So let’s say that the best algorithm is N to the 2.4, and let’s say that you work on it and work on it for months and months and you just cannot get it down to N to the 2.3. Okay. So you could just give up, admit that you’re just not very good. But sometimes, what you can do is you can say, “Well, I can prove a theorem that says, if you could improve that to N to the 2.3 then here are a thousand other problems where you could also improve over the best that anyone knows.” So it’s kind of, “It’s not my fault that I’m stuck at N to the 2.4 and I can prove that.” There is a more fundamental difficulty here.
0:12:51 SC: So in other words, we have this set of problems that are computer-friendly, we can state them precisely. It’s not like autonomous driving where we’re not quite sure what we’re doing. There’s a set of input bits and what we’re discovering, what you’re discovering, is that there is structure in the space of how hard these problems are.
0:13:11 SA: Yes.
0:13:13 SC: And you’re trying to figure out which problems fit into different classes. So you become sort of a… Oh, what’s the word? Not botanist, but someone who divides things into species and things like that.
0:13:27 SA: A taxonomist or something.
0:13:28 SC: Yes, that’s what you are. Yeah.
0:13:31 SA: Yeah, yeah. And I would say that like any other kind of taxonomy, what you’re really after are sort of like the general laws, the general principles. No one goes into particle physics probably because they just want to classify every type of meson or every type of baryon. But what you hope is that by classifying things, you will notice patterns and then you will notice a deeper structure there.
0:14:01 SC: Yeah. I don’t want to zoom over this too quickly because it’s something that to me is on the one hand, both perfectly obvious in retrospect, but also really profound, the idea that the kinds of questions we ask come along with a different set of difficulties when it comes to trying to solve them.
0:14:20 SA: Yeah, yeah. Absolutely. Look, the theory of computation as we understand it today, you could say it really started with Alan Turing in the 1930s, writing down a mathematical definition of what we mean by a computer. He had this concept of a Turing machine. But if you don’t know what a Turing machine is, that’s fine, because your iPhone or your Android or your desktop PC, these are all equivalent to Turing machines. And…
0:15:00 SC: In the sense that they’re just sufficiently powerful computers to do the kinds of questions we ask.
0:15:04 SA: Exactly, in the specific sense that they can all emulate one another. Merely some are faster, some are slower, some will run out of memory a little sooner than others will. But in principle and the limit where you give them enough time and enough memory, they can all compute the same set of functions. And so then, mathematicians, logicians spent decades just understanding the boundary between what is computable and what is not computable. One of Turing’s great discoveries along with the invention of the Turing machine was the discovery that not everything is computable. There are problems where you can just prove that there is no algorithm to solve them in any amount of time.
0:15:50 SC: So that’s the infinite complexity limit. You can literally never… There’s no number of steps that’s guaranteed to give you an answer.
0:15:58 SA: Precisely, precisely. Yes.
0:16:00 SC: What’s a question that falls into that category?
0:16:04 SA: So the most famous example is, I give you a computer program. Now the question is, does this program ever stop running? Okay, the famous halting problem. And that may sound like a boring question for debugging some code. But that question actually encodes a large fraction of all of mathematics.
0:16:26 SC: Yeah.
0:16:27 SA: Because we could write a program that just will enumerate over all the zeros of the Riemann zeta function and will halt only if there is one that is not on the critical line. Now that is a program where to determine whether that program halts or runs forever is equivalent to solving the Riemann hypothesis. And you could do the same for many, many of the great unsolved problems of math. So that’s a really profound question. Maybe it shouldn’t shock us too much that there is no general algorithm to solve it to sort of… Yeah, math does depend on creativity. Who would have thought? Which doesn’t mean, by the way, that human mathematicians could never be beaten by machines. It just means that if they are, then the machines won’t be perfect either.
0:17:24 SC: Yeah. This is a big, big difficult set of ideas.
0:17:29 SA: It is, it is.
0:17:30 SC: When you say… Well, we talk about the halting problem, I guess I have many questions here.
0:17:35 SA: Yeah.
0:17:36 SC: But you used the word creativity. What does that mean? Can we [0:17:42] ____ that?
0:17:43 SA: Okay. It is much easier to say what creativity is not. If something can be done by a completely mechanical algorithm that we completely understand, then maybe we would say that there is no creativity there. So like a multiplying of two integers, for example. You might choose to do it in a creative way, but it doesn’t require creativity. And then…
0:18:14 SC: But now we’re skating into Penrosean waters, where he’s going to say that there’s something…
0:18:19 SA: Excuse me? Sorry.
0:18:20 SC: We’re skating into Penrosean waters where Roger Penrose is going to say, “There’s something about the human brain that can’t be a computer because we are creative and they’re not.”
0:18:29 SA: Yeah. Well, I don’t agree with him. To get to where Penrose goes, you have to take this further step of… And furthermore, I am in some sense a perfect mathematician. I can just say that formal systems are consistent.
0:18:47 SC: By, I, you mean Roger Penrose, not you.
0:18:49 SA: And when I make a statement like that or maybe when I make it ex cathedra or something like wearing my official hat, then I am never mistaken.
0:19:00 SC: So I think we need to slow down and unpack that a little bit.
0:19:05 SA: Okay, okay.
0:19:07 SC: Why don’t you tell us in your words what Penrose is trying to say.
0:19:11 SA: Yeah. So he famously gave an argument, which was really an updating of an earlier argument due to Lucas, that said that human creativity can never be even simulated by a machine. And the argument, well, we could actually make the argument in terms of the halting problem, as he sometimes does. And there are certain algorithmic problems that we know just cannot be solved by a computer using any amount of resources, but then he would say, “But in these cases, humans can just see the truth or falsehood of the relevant statement, maybe even by introducing new axioms, if needed.” It’s that second part that I have problems with, because… Yeah.
0:20:14 SC: Well, I mean, I get what… I’m totally on your side here, but I get why he would say that, because I have in my mind a vision of staring at a computer screen with a simple algorithm with a loop in it and going, “Oh, yeah, that’s not going to terminate,” or, “Oh, yeah, that is.” And so, why can’t I put… Somehow, if you prove that I can’t do that by a computer then it sounds like you’re proving that humans are better.
0:20:45 SA: Right. Well, I think the main issue is that when we talk about algorithms in theoretical computer science, we’re typically talking about algorithms that always have to be correct. I mean, you can relax that, but even then, you’ll have some specific condition, like correct at least 99% of the time on inputs that are chosen from this distribution or something like that. You have a formal criterion of whether your algorithm succeeds or fails, and humans are not like that. When we try to do science, try to do math, there is no a priori guarantee that we have to succeed. Andrew Wiles, when he started working on Fermat’s Last Theorem, he had no guarantee of success, right?
0:21:35 SC: Yeah.
0:21:36 SA: I mean, yeah, we can look back and we can count the… By confirmation bias, we can count the successes only, but there are lots of other big math problems that no one has solved and for which we don’t even know whether they are solvable. And so if you… As soon as you grant a machine the same liberty that it can try to learn from experience, it can make mistakes sometimes, it can sometimes just give up and say, “I don’t know,” then there is no longer anything that math or logic can say against the machine doing just as well as a human does, or better than a human does. And if you want to say that the computer is somehow not as good, I think you’re forced at some point to retreat to internal criteria. Like you could say, “Well, the computer is just saying that it understands why a set theory is consistent, but I just really, really feel its consistency.”
0:22:40 SC: Yeah, okay.
0:22:42 SA: And, right, but at that point, I think you might as… Why even talk about something as abstruse as set theory? You might as well just say, “But, you know, when I taste the strawberry, I really taste the strawberry.”
[chuckle]
0:22:53 SC: Oh, there are people who say that.
0:22:54 SA: Yeah, the full quality of strawberry-ness, right, and the machine could only be programmed to pretend that. And then it just reduces to the usual debate that everyone always goes in circles with and doesn’t get anywhere.
0:23:09 SC: But this is very good, because I think… So, the point is that when we are able to prove these theorems about what computers can’t do, it’s because we’re sort of restricting our notion of computer to something very, very specific that it would be easy to jump out of, right, if you give computers some randomness, some fallibility, some give-up-ability, then there is no reason to think they can’t be just as good as us, and vice versa.
0:23:31 SA: Well, it’s not so much that we’re restricting the computer as we’re restricting what counts as success. I mean, we’re saying that, “You really have to guarantee me that you will get the right answer, you will halt then return the right answer on all the inputs of this type,” for example.
0:23:50 SC: Yeah, got it.
0:23:50 SA: And, yeah, as soon as you’re allowed to be heuristic, well, then a lot many more possibilities open up. But, yeah, this is a whole fascinating discussion that you can have just about computability. But where I was… Where I wanted to go was that when people started building actual computers in the ’50s and ’60s, they realized that, well, most of what they really wanted to do was computable in Turing’s sense, but computable could mean computable but taking an amount of time that grows like 2 to the 2 to the 2 to the 2 to the N, where N is the size of the input. And then if N is more than 1…
0:24:36 SC: If N is 2, you’re screwed…
0:24:37 SA: You’re completely hosed. So, I think it was the actual digital computer revolution that made people realize that, often, the much more important question than just is something computable at all, is is it efficiently computable? Is it computable in a way that avoids a brute force checking of astronomically many possibilities?
0:25:04 SC: And so this is where we get into polynomial versus exponential.
0:25:08 SA: Exactly, exactly, yeah. And I think that is maybe the main insight that Turing and von Neumann were kind of missing. Well, maybe they sort of understood it, but I guess they had a lot of other stuff on their plates, also.
[chuckle]
0:25:27 SC: It was an exciting time back then.
0:25:28 SA: Yeah, it was. It was, it was. Yeah, yup, yup.
0:25:30 SC: They were not under lockdown so they could really think about these things. Okay. So give us more of a lay of the land kind of explanation for what these computability classes are. There are things that take exponentially long, things that take polynomially long. What else do we got?
0:25:46 SA: Yeah. Yes, okay, so… Okay. So you could say, the most basic thing you could do is just try to classify problems by how much time they take, how much memory they take, so what can be done with a polynomial amount of time? This is a class that we call P for polynomial. You know, physicists have much better names for things.
0:26:12 SC: But also don’t…
0:26:13 SA: You know, big bang, black hole. But yeah.
0:26:15 SC: To the audience, they should not get sanguine because that’s the only label that’s going to even make sense in what’s to come. At least seems to make sense.
0:26:24 SA: Look, there’s everything you can do with a polynomial amount of space or memory, that’s called PSPACE. That’s pretty intuitive, isn’t it?
0:26:33 SC: Okay.
0:26:33 SA: And that’s a potentially larger class because you could use the same memory over and over, but for an exponential amount of time. So you could say polynomial time is contained in polynomial space, which is contained in exponential time. And the reason polynomial space is contained in exponential time is that, well, if I have, let’s say, N bits of memory, then my computer can pass through at most 2 to the N power possible states before either it halts or else it gets into an infinite loop, an infinite recurrence. So you can relate time and space to each other in that way. Now, already here, we encounter some of the most enormous open problems in mathematics. For example, is polynomial time equal to polynomial space? No one knows. We expect that the answer is no, but no one has proven that.
0:27:39 SC: Sorry. Let’s not let that go by too quickly.
0:27:42 SA: Okay, alright.
0:27:43 SC: You said before it’s contained in, but you didn’t mean that it’s properly… We’re not sure whether it’s the same size or smaller.
0:27:49 SA: That’s right, exactly, exactly. Everything you can do in polynomial time, you can also do in polynomial memory. And that’s because each… At least if I have like a serial computer, each time step is accessing at most one memory location. So after T time, I can access at most T memory, but we don’t know whether everything you can do in polynomial memory can also be done in polynomial time. We would expect, no, because that would… If the answer were yes, that would mean that, for example, there was just some super duper algorithm to play chess perfectly or Go or any other game. Not merely as well as, let’s say, AlphaGo plays it, but to play it perfectly.
0:28:43 SC: You gotta fill in the details there. You mean because we could just give it enough memory?
0:28:48 SA: Well, because it is known that you could perfectly play any of these games like two-player games of perfect information using a small amount of memory because all you need to do is evaluate what’s called the game tree. The game tree is the thing that says, is there a move I can make such that for every move that the opponent makes there is a move I can make and so on, such that I win. And that’s a tree where you can basically just traverse that tree. It’s an exponentially large tree, but you can reuse the same memory over and over. So playing games, that’s a problem you can do in small memory. Now, if P were equal to PSPACE, that would mean that perfectly playing all these games would also be a problem that you could solve in a small amount of time.
0:29:36 SC: Yeah, okay.
0:29:37 SA: Okay. And that would be amazing. And then is PSPACE equal to exponential time? So everything that you can do in exponential time, can you also do it with small memory? Again, no one knows. We expect that the answer is no. No one has proven it. Again, I don’t want to give the impression that we’re complete ignoramuses. As one example, we do know that exponential time is bigger than polynomial time, okay. That we know.
0:30:13 SC: Okay.
0:30:13 SA: Okay. So we can prove that when you’ve got more time, then you can solve more problems that you couldn’t solve with less time. Likewise, when you’ve got more memory, you can solve more problems that you couldn’t solve with less memory. But when you’re comparing different resources like time against space, then it becomes very hard.
0:30:34 SC: So just to translate that, you’re saying that we know there are problems that cannot be solved in polynomial time but can be solved in exponential time and likewise for space.
0:30:44 SA: Precisely, yes. And even more fine grained than that, we know that there are problems that can be solved in N to the 2.4 time that cannot be solved in N to the 2.3 time, for example.
0:30:56 SC: It is an interesting feature of this field that… I’m not going to give you a hard time for not having proven anything yet, that’s okay. Everything yet.
0:31:04 SA: I have proven something, just not the things that we most want. Yeah.
0:31:10 SC: But there is this thing that comes up over and over again where here’s something we haven’t proven yet, but every person has the same opinion about what the answer is eventually going to be because it would lead to this very, very strange thing if it turned out not to be true. How reliable is that sort of quasi-argument in your mind?
0:31:34 SA: Well, I think that we need to be prepared for the possibility of surprises. I would say that there already have been surprises. There have been cases where people thought that two complexity classes were different that then turned out to be the same. I would say that none of those were nearly as surprising as, let’s say, P equals PSPACE would be.
0:31:57 SC: Would be, right.
0:32:00 SA: But there were things that… I mean, look, if there were no surprises, then you could say, well…
0:32:09 SC: Why bother?
0:32:09 SA: Why even do it. So yes, there have been surprises, but I think that the right way to think about it is that even though this is pure math, the way that we approach it has some elements of empirical science also. Physicists don’t prove that there’s no superluminal signalling, they don’t prove that quantum mechanics is correct. These are taken as very well-supported assumptions relative to our present state of knowledge, let’s say. And then much more fine grained things than that, like that there’s a CPT symmetry and that there… And on and on.
0:32:54 SA: And you could have sort of a hierarchy of surprising-ness if you could send… If, let’s say, the OPERA experiment had been correct and you could really send the neutrinos faster than light, well, then that is at the top of the hierarchy of surprising-ness. And there are many other things that could happen in physics that are not quite as surprising as that, a new particle at the LHC but still, you would take it. It would still… And it would still overturn something that had been previously believed. So I think that…
0:33:38 SC: It’s amazing to me how many people bring up that those damn superluminal neutrinos as something that is in everyone’s head as something you guys almost believed that for a while.
0:33:51 SA: Well, no. Look, the physicists I know, none of them thought it was very likely that it was correct.
0:33:57 SC: We have priors, we’re good Bayesians. So that’s the point, also in that…
0:34:00 SA: Exactly, exactly. And I would say it’s exactly the same with us. We are just trying to be Bayesians and have priors on things. And yeah, I would… You can say if two complexity classes, let’s say, if they have been enormously studied for 60 years and, again and again, people did things that if they had turned out slightly differently then these two classes would have been equal and yet every single time it just miraculously avoids whatever theorem they prove, just miraculously avoids the thing that would make those classes equal. Then you start to suspect that, well, maybe there is a deep reason why they’re different.
0:34:47 SC: Do you begin to anthropomorphize your complexity classes as you learn more and more about them? Do you say like, they don’t want this to happen?
0:34:54 SA: Oh, absolutely. Oh, absolutely. Yeah. No. This is the thing. Each one has a personality. They’re like comic book superheroes. Each one has a different set of powers. And sometimes, some are just clearly better, more powerful than others. Other times, you get two classes with just bizarrely incomparable powers. And so then you try to compare them to each other but it’s just kind of asking… I don’t know. It’s like one of these internet memes of who would win in a fight, Godzilla or Batman, or something. I know. Sorry, just they’re from different universes.
0:35:43 SC: Exactly. But…
0:35:45 SA: But yeah. But the sort of less obvious, maybe slightly less obvious thing you can do but it turns out to be of absolutely central importance is you define complexity classes in terms of what is provable, okay, or what has a short proof. And this is what we need to do, I would say, the next most famous complexity class along with P, which is called NP. Okay, now, NP doesn’t stand for not polynomial…
0:36:20 SC: See?
0:36:21 SA: Okay, it stands for non-deterministic polynomial. But don’t worry about what that means. Yeah. I can say what it means in plain language. A problem is in NP if whenever the answer to it is, yes, meaning like, yes, there is a solution, then someone can show you the solution and you could check the solution using a polynomial-time algorithm. So let me give an example, like a jigsaw puzzle, okay, especially if there is no picture on the jigsaw puzzle, it could be… It could take quite a while to do one.
0:37:02 SC: Yeah.
0:37:03 SA: But once it’s done and you’ve made some neat square, well, then you can… Anyone who doesn’t believe that you did it, you just show them that you did it. Similarly, finding the prime factors of a gigantic number, this is a… Well, for better or worse, most of the encryption that we use on the internet is based on the belief that this problem is hard, this and a few closely related problems, that finding the prime factors of a gigantic number is a hard problem. But if you did find the factors then, well, you might not want to multiply them, but your computer could very easily multiply them and check that those factors were the correct ones.
0:37:51 SA: Likewise, with a Sudoku puzzle. Likewise with optimization problems. It might be hard to prove that you’ve found the best solution. But if you just want to convince… Let’s say, you’re a consultant. You want to convince your client that you’ve found a solution that will only cost them this much money, well, you just show them your solution. So these are all examples of NP problems. And the way things fit together is that P is contained in NP, which is contained in PSPACE. And… Yeah.
0:38:25 SC: By the way, I just want to make it clear so everyone knows…
0:38:28 SA: Yeah, absolutely. Absolutely.
0:38:30 SC: The picture that we have, there is this big space of problems and we draw some kind of Venn diagram of these complexity classes. But they don’t need to be nested. Two complexity classes can have some intersection but some non-intersection also. And a third one might intersect with some of them but not others. Is that fair or…
0:38:54 SA: Absolutely…
0:38:54 SC: They don’t all live right inside each other.
0:38:56 SA: All of these things happen, yes.
0:38:57 SC: Okay.
0:39:00 SA: So some of them do fit in a linear order, as I was saying before, but probably not well, some of them do fit that way, like P is contained in NP is contained in PSPACE is contained in X, meaning exponential time. And we believe that each one is strictly more powerful than the last, but all we know so far is that X is larger than P, okay. So, yeah, which means that either P is different from NP, or NP is different from PSPACE, or PSPACE is different from X, at least one of those three has to be true. We think all three of them, but we only know that at least one is true.
0:39:41 SC: And you mentioned…
0:39:42 SA: Now, the most… Yeah.
0:39:44 SC: You mentioned about factoring that you believe it’s hard, but you didn’t say that we know it’s hard.
0:39:51 SA: That’s right, that’s right. So now we can go in and now… In fact, we don’t know that any NP problem is hard. This has been the situation for the last half century that we, famously, we cannot prove that P is not equal to NP. Okay, that is a… Yeah.
0:40:15 SC: So NP… Sorry, sorry. NP problems are those that we can easily check the answers to…
0:40:20 SA: Exactly, exactly.
0:40:21 SC: And you’re saying that we believe there are problems that are hard to solve but easy to check, but we can’t prove it yet.
0:40:27 SA: Exactly.
0:40:28 SC: We cannot prove it yet.
0:40:29 SA: Exactly, exactly. That if you’ve heard… Yeah, if listeners have heard of the famous P versus NP question, that is that question. And now, factoring is an NP problem, but factoring, we think, is a very special problem. Okay. So it could be that someone just discovers a fast algorithm for factoring and then that would break most of the security of electronic commerce, but it wouldn’t necessarily mean that P would equal NP, ’cause maybe they just solved that one special problem. Now, the surprising part, the big surprise to people in the early 1970s was that most of the hard problems in NP are not like that. Most of them have an amazing property of universality, a property that we call NP-completeness. And what NP-completeness means is that you show that your one specific problem has the property that if anyone could solve it in polynomial time, then P would equal NP, then you could solve every NP problem in polynomial thought.
0:41:43 SC: So this goes back to the thing that you’ve mentioned before where you just relate the hardness of problems to each other even though you don’t…
0:41:48 SA: Exactly.
0:41:49 SC: You might not know what the hardness of any of them are, but you can say that they’re equally hard.
0:41:54 SA: You know it’s all the same, yeah. So, this is exactly what I was talking about before, about you may start out as a taxonomist but ultimately you want to discover something deeper, right? And what you discover is that there is this huge class of easy problems, the P problems, then there is this huge metropolis of hardness, these NP-complete problems, which includes just literally thousands of the problems that engineers and scientists would care about, airline scheduling, traveling salesperson problem, just about any kind of combinatorial optimization problem that you could imagine involving a whole bunch of variables, a whole bunch of constraints, problems like that will be NP-complete, unless they have good reasons not to be.
0:43:00 SC: Is this one of those ones where packing luggage into your trunk is one of them?
0:43:04 SA: Yup, fitting luggage into the trunk of your car, that might be one that many people have experience with. There is a beautiful paper from a decade ago that proved that Super Mario is NP-complete.
0:43:17 SC: Yes, yes.
0:43:18 SA: You have to create these crazy levels with these weird patterns of these koopas that you stomp on that encodes a logic problem, but you can do that. So basically, you get… Yeah.
0:43:33 SC: But the luggage in your trunk is a good reminder because even though we say NP-complete means super duper hard, people have put luggage in their trunk. What we mean is that…
0:43:42 SA: They have.
0:43:43 SC: As their trunks have… If you imagine large and larger trunks and more and more luggage, it just becomes very unwieldy very quickly.
0:43:51 SA: That’s right, that’s right. What it means is that if I wanted to, I could give you a very, very hard time figuring out how to fit some luggage into your trunk. I could even, in principle, I could design some millions of boxes of different dimensions that would have the property that you can fit these boxes into your trunk and have it closed if and only if there is a proof of the Riemann hypothesis of it [0:44:21] ____ a certain length, okay, or, for example, that in order to fit them in your trunk, you would have to break some cryptographic code. I could also do that.
0:44:31 SC: But if someone showed you a way to put them in your trunk, you would be easily enough to be able to say, “Yup, yup, that worked.” It was easy to check.
0:44:37 SA: Yup, exactly, exactly. Yeah. So there’s these NP-complete problems, and sort of a priori it didn’t have to be that way, but this is a substantive discovery that most of these hard NP problems are actually all equivalent to one another, in the sense that a fast algorithm for any one of them implies a fast algorithm for all the rest. And then there are a few outliers. Factoring is one of the weird ones, okay, that might be somewhere in between P and NP-complete in some no-man’s land.
0:45:13 SC: Besides the anthropomorphization and the personalities, does thinking about this stuff tend to turn you into a mathematical Platonist, thinking that there really is a mathematical reality out there because of all the structures that you wouldn’t have imagined existing before finding it?
0:45:30 SA: Yeah, I feel like probably every mathematician, while they’re actually doing their work, is in practice a Platonist. They might claim later that they’re not one, but to do math is a push back against something that can tell you that you were wrong. It’s not just a thing that you were making up. It is a thing that has constraints that are external to you. And in that way, it is like empirical science. It’s not…
0:46:05 SC: Well, yeah. You’ve made that point before. You’ve made that point before and I think it’s really interesting, because I think you’ve made the point in comments on my blog that this kind of discovery… I will mention in the introduction that you are a world-famous blogger and stuff like that but…
0:46:20 SA: Oh, very kind.
0:46:21 SC: That the kinds of things we learn about the real world by these purely mathematical discoveries are, at least, rubbing shoulders with the kinds of things we learn about the real world by doing empirical science. The universe could have been expanding or contracting, and we had to go out and look at it to find out which way it was. But it’s really, really hard to put boxes into your trunk in the most efficient way, and you want to say that one of those is comparable to the other in terms of important insights about the universe.
0:46:57 SA: Yeah. It’s funny because I am often in conversations with my many, many physicist friends where we are ribbing each other and they will point out that, oh, I’m just a Platonist in some abstract la-la land while they are dealing with the real world. And then if these are theoretical physicists, I can reply that I’ve actually… I’m an author on more experimental papers than they are.
0:47:28 SC: Safe bet, yup.
0:47:30 SA: But yeah. Yeah. But look, even in physics, you are a theoretical physicist and a cosmologist. You are not on a typical day out at the observatory peering through a lens.
0:47:47 SC: Certainly not.
0:47:48 SA: You are thinking. You are thinking hard about things that we already know and trying to deduce the consequences of those things, or trying to build models that explain something. And that’s also what we do in math and in theoretical computer science.
0:48:04 SC: Yeah. No, I’m on your side. I just want to give you a chance to put it into your words.
0:48:07 SA: Yeah. Yeah, yeah. Yeah, yeah. Sure. But, no, I have described my position as not so much a Platonist but an anti-anti-Platonist. Because, look, Plato wrote all kinds of really weird trippy stuff, and I don’t want to give him a blank check that I agree with whatever he said. I haven’t even read enough of Plato to know if I agree with everything he said. And it sounds quasi-mystical and weird to be talking about this world of perfect triangles and perfect squares or whatever. I don’t know if it has a metaphysical existence. But I will say this, that if we ever encounter an extraterrestrial civilization and we are able to communicate with them, I think that they will agree with us about the Pythagorean theorem. I think that they will have discovered much of the same math as we have discovered. Because I think that it is not just an arbitrary cultural creation. It has cultural aspects, but it is constrained by the… Well, by logic, by truth.
0:49:26 SC: Well, yeah. Okay. Let me push back a little bit on that in my role as a devil’s advocate on the podcast…
0:49:32 SA: Yeah.
0:49:34 SC: The Pythagorean theorem is true in Euclidean geometry. So it’s a conditional statement that says, “If you accept the following set of axioms, then you prove the Pythagorean theorem.” And every statement in math is like that. If the axioms are true then the conclusions follow. But so one could say we will never learn anything exclusively about the actual world that way because we don’t know what axioms are true.
0:50:02 SA: Yeah. Okay. So there are really two questions. One is which we could call the easy question, if we can agree on the same axioms with the aliens, will we agree about the consequences of those axioms? And I hope most people would agree that the answer is yes, we’ll agree about what are the laws of logic or what are the rules of inference that we can use to validly draw conclusions from axioms. But then there is a broader question, maybe a harder question, will we and the aliens have thought of the same axioms or will we have thought o, f about similar mathematical objects such as Euclidean space, the space where the Pythagorean theorem holds, or such as the positive integers. And I think… Okay, so there certainly are some mathematical objects that we have invented that probably the aliens will not have invented. Chess could be an example of such an object…
0:51:12 SC: That would be weird.
0:51:13 SA: Maybe a particular cryptographic codes that we happen to use, like AES. I doubt the aliens will have that. But I’d be willing to wager a lot that the aliens will have a concept of integers, that they will have a concept of Euclidean space, and even more than that, they will have a concept of complex numbers and things of that kind. There are certain things that are just really, really fundamental to the mathematical universe where even if you started out in a different direction, you would eventually have to reinvent those concepts because they’re so ubiquitous.
0:51:50 SC: If I were really being the devil’s advocate, I would say that maybe the reason why certain sets of axioms seem so natural to us is because, not of math, but because of physics, of the particular way that the physical world around us has arranged itself to make certain things more natural for us to describe it.
0:52:08 SA: Yeah. Well, okay. Well, then it becomes an even more interesting question. Let’s say, okay, I was imagining talking to aliens who live in the same universe as we do…
0:52:18 SC: Self-limited.
0:52:18 SA: Even though they had a completely separate evolutionary history. But now we could also imagine some aliens in some parallel universe with completely different laws of physics. Maybe it’s not even quantum mechanics, maybe they don’t even have space-time, even approximately, I don’t know, maybe they’re all just sitting on top of each other or something. But, one thing that we can say is that we can imagine many ways that the laws of physics could have been different, but where we would have invented much the same math in order to think about it. So, I mean, we… And in fact, it has happened again and again in the history of math and physics that mathematicians have invented a certain concept, well in advance of that concept being needed by physics, right?
0:53:15 SC: Sure, true.
0:53:16 SA: They had their own reasons for inventing it that were not in any direct way motivated by physics, but then they just turned out to be very handy when physics had reached a certain point. And I think if you look at examples like that, you could say, maybe that is just because these concepts are so fundamental, that sort of any laws of physics, if you go deep enough into them, you want to understand them deeply enough, you might be tempted to re-invent those concepts.
0:53:49 SC: I think this is…
0:53:50 SA: Like, for example, concepts of symmetry groups would be an example.
0:53:54 SC: Yeah. I think that this is a rabbit hole we could profitably dig even deeper, but I do want to switch topics onto your opinion of what I’ve heard on the internet, which is that once we build quantum computers, all of these hard problems will become suddenly easy.
[laughter]
0:54:11 SA: Ah, okay, yeah. So this actually feeds beautifully into the discussion that we were having earlier about could there be different classes of problems with different incomparable powers. Now, a perfect example of that is provided by quantum computers. Okay, so a… Once we ask what is efficiently computable, what is computable in polynomial time, you might worry that the answer to that might depend somewhat on physics. And actually, apparently it was asking that question that led David Deutsch to the idea of quantum computing in the first place, in the early 1980s. So…
0:55:02 SC: So the way that it could potentially depend on physics is because what it means to do a computation depends on what kind of physical things you’re pushing around.
0:55:11 SA: Yeah. Precisely, precisely. Now, Turing’s definition of computability in the 1930s had this amazing invariance to the details of physics. It just… It doesn’t care whether the universe is classical or quantum or how many spatial dimensions there are. You just get the same notion of computability, okay. But once we ask about efficient computability, polynomial-time computability, well, then it’s still very, very insensitive to a lot of the details of physics, and that’s why we like this notion, that it gives you a nice elegant theory that doesn’t depend on your specific model of computer, but the really cool thing that emerged in the ’80s and ’90s is that, well, changing the laws of physics from classical to quantum, that does seem to be enough to enlarge what is computable in polynomial time. Okay, once again, this shouldn’t surprise you at this point, no one has proven that…
[laughter]
0:56:18 SC: Right.
0:56:18 SA: Okay. But, we think so. Okay. So, the way to say this in complexity language is that there is a class of all the problems that are solvable in polynomial time using a quantum computer, which we could get into exactly what that means, but it’s a computer that could have not just bits in its memory but quantum bits, what we call qubits, bits that can be in superposition states and that can even be entangled with each other. And so the key property here is that if I have, let’s say, 1000 qubits, 1000 quantum bits, then just to describe their state, I need a list of 2 to the 1000 complex numbers. I need a quantum mechanical amplitude for every possible configuration of all of these bits. So we’re talking about enormously larger objects here. And so that, at least, opens up the potential that we could compute more things in polynomial time. It will take work to see whether that potential is realized, but we can define a class of problems that is called a BQP, bounded-error quantum polynomial time. This was defined in ’93 by Umesh Vazirani, who was my adviser at Berkeley, and his student then, Ethan Bernstein.
0:57:47 SA: And they basically just defined it as a quantum mechanical generalization of P. So it’s like, what you can do in polynomial time with a quantum computer. The B for bounded error, that’s just saying that, well, the computer doesn’t always have to output a right answer. It just, for every input, you should have, let’s say, at least a 90% chance of getting the right answer. And…
0:58:15 SC: Yeah, because deep within that, there’s quantum…
0:58:17 SA: And we’re happy with that, because if you don’t like 90%, well, then just repeat the computation a whole bunch of times and take the majority vote among the answers.
0:58:28 SC: Yeah.
0:58:28 SA: Right. So that’s BQP. Now, it’s pretty easy to show that BQP contains classical P, or in other words, a quantum computer can always efficiently simulate a classical computer.
0:58:45 SC: That makes sense.
0:58:45 SA: Right. The way I like to describe that is, you could use a space shuttle to taxi around the parking lot, you know what I mean? It wouldn’t be very smart, it wouldn’t be very useful, but you could do it. The interesting question is, is BQP larger than P? Are there things that you could solve in polynomial time with a quantum computer but you can’t solve in polynomial time with a classical computer or that would even take exponential time for a classical computer?
0:59:14 SC: Right.
0:59:14 SA: Okay. So, and we don’t know the answer. I mean, when Richard Feynman talked about this in the early ’80s, he suggested the problem, well, what about the problem of simulating quantum mechanics, itself? And that is one of our best candidates to this day for what a quantum computer will be useful for, if and when we can really make it practical, but maybe some people would like a less autological example of what a quantum computer could do, or sort of an example that is not itself about quantum mechanics. So that came via a now super-famous discovery in 1994, and this was when Peter Shor discovered Shor’s algorithm for factoring, okay. So what Shor discovered was that the problem of factoring huge numbers, the one that we talked about before, the one that most modern encryption is based upon, and that’s an NP problem but it’s kind of special. We don’t know whether it’s NP or not. Shor showed that the factoring problem is in BQP. Okay. So he showed that if you could build a quantum computer then you could factor an n-digit number using a number of elementary operations that only scales like N squared, roughly.
1:00:42 SC: Right. Whereas, classically?
1:00:43 SA: Okay. And so this means that… Excuse me?
1:00:47 SC: Whereas, the classical belief?
1:00:49 SA: The best known classical algorithm takes time that grows, like, exponentially and roughly the cube root of N.
1:00:57 SC: Okay.
1:01:00 SA: Okay. It’s something fancy, called the number field that uses the algebraic curve…
1:01:01 SC: But we count that as exponential, even though it’s the exponential [1:01:04] ____…
1:01:05 SA: Yeah, we’ll count that as exponential. And I am sure that the NSA cares enormously about the exact free factors in that exponential and so forth. But, yeah, we’ll count that as exponential.
1:01:18 SC: But we don’t… Yeah.
1:01:21 SA: Yeah. So…
1:01:22 SC: But we don’t know that there isn’t a better one, classically, that’s the issue?
1:01:26 SA: That’s right, that we absolutely do not know that. And in fact, we don’t know… It could be, for all we know today, that P equals BQP. In other words, maybe everything that a quantum computer can efficiently solve could also be efficiently solved by a classical computer, right? So what Shor showed, again, it’s just relating our different domains of ignorance. If you wanted a general way to simulate quantum mechanics with a classical computer, then you would also have to invent a fast classical algorithm for factoring.
1:02:07 SC: Yeah. And it is true, I think we do know that there are problems for which there is a quantum algorithm that is provably faster than any classical algorithm but not in an entirely different complexity class, is that right?
1:02:23 SA: Yeah, right. So, this is… Okay, good, good. Now, we’re getting to something that is when I teach my undergraduate class, this is always one of the more subtle points, but I’m glad you’re asking about it. There is a thing called the black box model, okay, where it’s sort of a different game, a different domain where you just ask the question, suppose that I have a black box that just evaluates some function for free, and now, maybe it’s a sub-routine where I don’t know its inner workings, for example, okay, and now I just ask, “How many questions do I need to ask to this black box in order to learn something that I want?”
1:03:07 SA: So as an example, I love playing a game, playing the game with my seven-year-old daughter where she shall think of a number from 1 to 100, and then I say, “Is it bigger or smaller than 50? Is it bigger or smaller than 75?” So, yeah, and with seven questions, you can find the number, right? So, she would then be a black box, and we could say that the query complexity of this problem is seven queries. But now, you could ask, and people have asked, “Well, what changes if I could somehow ask my daughter many questions in quantum superposition and get back a superposition of answers, and then apply… “
1:03:52 SC: If anyone can do it, Scott, I think that it’s going to be you. [chuckle]
1:03:56 SA: What? Well…
1:03:56 SC: If anyone can do it, I think you’re the best bet.
1:04:00 SA: Okay, alright, alright. Anyway. In this model of query complexity, here, we really do have proven advantages of quantum computers over classical ones. And some of these advantages are exponential, some of them are even more than exponential, by the way. There are problems involving end bits of input where it takes square root of… About square root of N queries to solve them classically, and they can be solved with only one query with a quantum computer, okay, literally, one. That’s, by the way, a paper that my colleague Andris Ambainis and I wrote five years ago. And we also proved that that gap is the largest possible one, between classical and quantum.
1:04:45 SC: Oh, okay, good, yeah…
1:04:46 SA: But just plugging my own research…
1:04:50 SC: Yeah, that’s why we’re here.
1:04:52 SA: Okay. But, yeah, yeah. But, so in the setting of query complexity, we do know how to prove that quantum computers are strictly better than classical ones for some problem. But now, you could say, in the real world, so query complexity is like a very, very useful playground for figuring out what might be true, like if you can’t even get a separation in query complexity then probably you have no chance to get a separation in the real world, between one type of computer and another type. But ultimately, you do want an advantage of quantum computers that will persist even in the real world where you don’t have these magic boxes for answering questions, right? So, I often explain it to physicists by saying, “Query complexity is our perturbation theory.” It is the street light to look for your keys under, where you can actually answer the questions, but, okay.
1:05:58 SA: So in this “real world,” they’re… What we know is that P is contained in BQP, meaning everything a classical computer can do so can a quantum computer. We also know that BQP is contained in PSPACE, which means anything that you can do in polynomial time with a quantum computer, you can also do in polynomial space with a classical computer, okay. So that means several things, that means that in terms of running time in the real world, quantum computers could, at most, give you an exponential advantage over classical ones. So they’re not going to solve the halting problem. They’re not going to solve anything that is literally uncomputable for a classical computer, but they could solve certain things up to exponentially faster.
1:06:51 SC: Okay.
1:06:51 SA: Okay. And it also means that we have a very good excuse for why we cannot prove today that quantum computers are better than classical computers in the real world. And the reason is, if you wanted to prove that P is not equal to BQP, well, then you would also have to prove that P is not equal to PSPACE, that’s a famous unsolved problem that’s like as big a problem as P versus NP.
1:07:18 SC: Yep, except you’ll make less money for solving it.
1:07:22 SA: Yeah, well, yeah, right, right. It happens not to have a million dollar prize, but you know what I say about the… By the way, so there were these… For people who don’t know, there are these $7 million Clay challenge problems. The first one is P versus NP, and then there is the Riemann hypothesis, there is the Poincare conjecture, which was solved by Perelman, although he refused the prize, I wouldn’t have done that but, okay.
1:07:51 SC: I wouldn’t have done that.
1:07:53 SA: Yeah, yeah. And there are four other problems. I like to say that P versus NP is just clearly the most important of the seven, right.
[laughter]
1:08:03 SA: And I have several reasons for that. One of them is that, well, if P… If you could prove that P were equal to NP and, furthermore, your algorithm was actually efficient in practice, so not like N to the 1000 but, let’s say, N squared or something like that, well, then, yeah, you could not only collect a million dollars for solving that problem but you could also solve the other six problems.
[laughter]
1:08:27 SA: Because you would just program your computer to say, “Is there a proof of, at most, a million characters written in some formal language that a computer can check?” And because a computer can easily check the proof, that means that if it’s there then if P equals NP, the computer can also easily find the proof. But not only that, forget about these measly million dollars. If P equals NP, you could start by stealing $200 billion-worth of Bitcoin.
[laughter]
1:09:00 SA: And I guess, then decide what to do next in your quest for world domination. Okay, but it’s… Yeah.
1:09:05 SC: But I think this is important because it really is driving home the reason why when mathematicians say things like, even though we haven’t proven that P is different from NP, we’re all sure it’s not true because NP is this collection of problems, some of which seem so hard that if you showed that they were really easy, you’d be axiomatizing all sorts of things that we think are just preposterously difficult.
1:09:32 SA: Exactly. So, yeah, some people they may have an intuition that, well, when I run across NP-complete problems in my application domain, which might be some machine learning, some AI optimization, oh, they tend not to be so hard. I just run some heuristic algorithm and it does perfectly well. So what makes you so sure that P is different from NP? And, you know, my response tends to be, “Well, why haven’t you made billions of dollars from mining Bitcoin?” You could say, since 2008 that’s been the easiest answer, right? I mean, you… I mean, yes, if you only try to solve easy instances of your problem then they will be easy.
[laughter]
1:10:19 SA: But the point of a problem being NP-complete is that you can encode these enormities into it, like finding a proof of the Riemann hypothesis, like mining billions of dollars of Bitcoin, and so forth, anything for which an answer could be easily checked. Or another example would be compress Wikipedia into the best, the smallest file you can where it could then be easily decompressed. Okay, that’s another example of an NP problem, where in order to solve that problem, it is, at least, a plausible speculation that the computer would have to understand human knowledge in a very, very deep way, and solve a lot of the problems of artificial intelligence. But, again, if P equals NP, you would just type with a few key strokes, you would do that.
1:11:18 SC: And likewise, this is why our intuition tells us that even quantum computers are not going to be able to solve NP-complete problems [1:11:23] ____.
1:11:25 SA: Exactly, yes, good. So now, we come to a wonderful example of two complexity classes, two models of computation that we really do think are incomparable, and those are… Or that as far as we know are incomparable, and those are NP and BQP, okay, so the easily checkable problems and the problems that are easily solvable by a quantum computer. Now, in some sense, the biggest mistake that popular writers make when they write about quantum computers, and this has been true for 25 years by now, okay, is that they conflate NP with BQP, right?
1:12:12 SC: Yeah.
1:12:12 SA: They write as if a quantum computer would just be a magical machine for solving NP problems. They say, “Well, look, a quantum computer just has to try each possible answer in a different parallel universe, a different branch of the wave function.” And in some sense, it is actually true that a quantum computer can do that, that’s not even a hard thing to do, to program your quantum computer to create a superposition over every possible answer. The hard part is reading out the answer that you want. Okay?
[laughter]
1:12:47 SA: So, if I just, you know, you know this, Sean, but for the benefit of our listeners. If I just create an equal superposition over every possible answer to some super hard problem, like all possible keys for breaking a cryptographic code, let’s say. And then I just measure it, not having done anything else, the rules of quantum mechanics tell me that what I will see will just be a random key, a random answer.
1:13:19 SC: Yeah.
1:13:19 SA: Well, if I just wanted a random key, I could’ve picked one myself with a lot less trouble. I didn’t need to build a quantum computer for that. Then that makes it sound like that maybe quantum computers are not really useful for anything at all if all they can do is pick random answers. But no, it is a little more than that that they can do, and the reason why they can do more is that the quantum rules of probability are different from the classical rules of probability. So in quantum mechanics each possible configuration that your system could be in gets assigned this number called an amplitude, which is very closely related to the probability that you see the system in that configuration when you look at it, but it’s not a probability. So unlike probabilities, amplitudes can be negative. They can even be complex numbers.
1:14:22 SA: And in some sense, the central trick in quantum computing, the trick behind every single quantum algorithm is this, that you are trying to choreograph a pattern of interference of these amplitudes, where for each wrong answer, what you would like is for the amplitude of that wrong answer to be a sum of many contributions, potentially, but some of those contributions should have positive amplitude, and some should have negative amplitude, or they should point in every which way in the complex plane. And so they mostly just cancel each other out. Whereas for the right answer, the answer that you do want to see, you would like all of the contributions to its amplitude to be pointing the same way. Or mostly the same way. So you would like constructive interference…
1:15:17 SC: It’s like a resonance.
1:15:19 SA: Yeah, exactly, for the amplitude of the right answer. If you can arrange that, then when you measure, the right answer will be seen with high probability, and of course if it’s not seen, you can just try again until it is. But you’re trying to exploit interference to boost the probability of seeing the right answer to way, way more than it would have been with any similarly efficient classical algorithm.
1:15:44 SC: Yeah.
1:15:44 SA: Now, the tricky parts here are that you’ve gotta do all of this despite not knowing yourself which answer is the right one in advance. If you knew that, then there would be no point. So you need to arrange this interference pattern where you know for some mathematical reason that it’s going to concentrate the amplitude on the right answer, even though you don’t know yet which one that is. And you’ve gotta do it fast. You’ve gotta do it much faster than just a classical brute force method could have found that same answer, or else the quantum computer is not winning. So it is a really bizarre hammer that nature gives us for extending computation beyond what Turing knew about. And it is a happy miracle that we can occasionally find some nails for that hammer to hit.
1:16:41 SA: Okay. Yeah. Factoring was a very famous example of such a nail. But now it is very important for people to understand that you design his fast quantum algorithm for factoring. Peter Shor really had to exploit some very special structure in the factoring problem, stuff that comes from group theory, from number theory, from the Fourier transform. It’s just a beautiful set of ideas that goes into it. But it is not something as simple as just I try every possible divisor in a different parallel universe. If it were that simple, you wouldn’t have needed Peter Shor to think of it. And as far as we know, it is not something that extends, generalizes to the NP-complete problem.
1:17:33 SA: I said before that factoring is not believed to be NP-complete. It has a lot of very, very special structure. Just one simple example is if I gave you some boxes to fit into your trunk, a priori they might not fit at all, or there might be only one way to fit them, or there might be 1000 ways to fit them. You don’t know. But if I give you some huge composite number, than no matter how hard it is to factor, you know in advance that it has one and only one prime factorization. Because you could prove that 300 BC. So factoring is special in a whole bunch of ways, and its specialness on the one hand is what makes it so useful for cryptography. You use the structure of factoring to do all the beautiful things that enable modern cryptography, but the other side of the coin is that that structure is what Shor was able to exploit in order to choreograph this interference pattern with a quantum computer that reveals the factors of your number.
1:18:46 SC: But this does sound a little deflationary in the sense that… I’m sure you’ll correct this. But it sounds like factoring, we lucked into it in the sense that it is a hard problem, but one that quantum computers are very good at. Typical exponentially hard problems will still be exponentially hard on a quantum computer. Is that a safe thing to say?
1:19:08 SA: That is what we think. That is what we think. And by the way this is something that I’ve been trying to… It is not controversial, by the way, within the field, and I’ve been trying to explain it to people for 15 or 20 years. It used to be the tagline of my blog because I found myself just explaining the same thing to journalists week after week after week. No, we do not expect that quantum computers will just exponentially speed up everything. It depends on the structure of your problem. Because this is often not what people want to hear, but I feel like we should be telling the truth. Yeah, now…
1:19:49 SC: Like this podcast will do it. Now that you’re on Mindscape, I think that everyone will be educated and you don’t have to explain anymore.
1:19:54 SA: That’s right, that’s right. Yeah, yeah, yeah, no, well, I love having a forum that is so devoted to the truth, as I know that you are.
1:20:06 SC: There you go.
1:20:09 SA: But now, I should say that even for NP-complete problems, we don’t expect an exponential speed up from a quantum computer. Once again, we can’t prove that, which is no great surprise, we can’t even prove that P is different from NP. If we can’t even prove that classical computers can’t solve these problems quickly, far less can we prove that quantum computers can’t do it. But what we generally think is that quantum computers would give you more modest speed-ups for these problems. Okay, so after Shor’s algorithm, maybe the second most famous quantum algorithm is called Grover’s algorithm. It was discovered just shortly afterward. Grover, by the way, was like… Worked down the hall from Peter Shor then at Bell Labs. So, these ideas were in the air then and I actually started in the field doing a summer internship with Grover.
1:21:10 SA: But what he discovered was that there is a quantum algorithm that can search a list of N possibilities in only about the square root of N steps, okay, where classically, if I just told you, “Here are N boxes and inside one of them is a golden nugget,” well, you’re going to… On average, you’re going to have to open about N over 2 of the boxes until you find that nugget. I have just sort of… By fiat, I have ruled out any other structure that you get to exploit here, right?
1:21:46 SC: Yeah.
1:21:47 SA: But what Grover showed is that if I can ask about every box in quantum superposition and then take my superposition of answers, do some quantum mechanical transformation to it, what we call a unitary transformation, then ask another question, and so on, and so on, then there is a way to get all, or almost all, of the amplitude onto the right answer, that is onto the box with the golden nugget in it, by asking only about square root of N question.
1:22:21 SC: Right.
1:22:22 SA: Okay. So what this means is that, for example, if you had some combinatorial search problem, say an NP-complete problem, if previously it would have taken you, let’s say, 2 to the 100 steps to solve with your classical computer, well, by layering Grover’s algorithm on top of what you were doing classically, typically, you would be able to solve it in about 2 to the 50 steps with a quantum computer. Okay. And that’s something…
1:22:49 SC: Yeah.
1:22:49 SA: That will expand the frontier of these sizes of problems that you can handle, and I think that absolutely would have applications in a world with fully scalable and useful quantum computers. It’s just it’s not the exponential speed-up that you get from factoring.
1:23:06 SC: And for anyone out there who knows a little bit of quantum mechanics, studying and understanding Grover’s algorithm is way easier than Shor’s algorithm. It’s actually pretty straightforward.
1:23:17 SA: That is true. That is… Yeah, that is true. And actually, the reason for that is that Shor’s algorithm, two-thirds of it is just classical number theory that’s got nothing to do with quantum mechanics. Right. It’s just getting it into the form where you can then do something quantum, right?
1:23:31 SC: Yeah, and who wants to learn that?
1:23:36 SA: Grover’s… So, when I… So I do teach all of these things in an undergraduate course for which the only prerequisites are linear algebra and some classical programming or like, let’s say, a semester of classical algorithms. I teach all the quantum mechanics that we need for the class, and we do Shor’s and Grover’s algorithm. But, typically, yeah, Shor’s algorithm would be three lectures. Grover’s algorithm would be one lecture.
1:24:05 SC: And we should also plug your book on this podcast.
1:24:08 SA: Oh, yeah. Yeah, yeah. I do have a book. It’s called Quantum Computing Since Democritus. Yeah, it was published seven years ago. It is not a popular book, it is also not a text book, it is in some intermediate complexity class.
1:24:26 SC: Superposition, yes.
1:24:26 SA: In between, I don’t know exactly what it is. But when I wrote the prospectus for the publisher, I told him, well, kind of like whatever audience is buying Penrose’s books, I’m hoping that they would also buy this book.
1:24:41 SC: Some subset thereof, yes.
1:24:44 SA: Yeah, yeah, yeah, yeah. Yeah. That’s right. Yeah.
1:24:45 SC: So, okay, obviously, there’s a large terrain of questions about the reality of quantum computing and things like that, but that’s for lesser minds, we have other fish to fry. I would like to start talking to you about the nature of space and time and stuff like that. So it’s, again, maybe a little bit of a surprise that people… Famous physicists, like John Preskill and Lenny Susskind, who grew up doing particle physics and quantum field theory and cosmology, have taken to quantum computing and quantum information in such a strong way. Why do you think that this set of ideas that started by how can we improve the speed at which a computer can answer a certain kind of question suddenly seems to be everywhere in discussions of the nature of spacetime itself?
1:25:36 SA: Yeah, well, okay. So I have several thoughts. The first one is, you’re the one asking me about the nature of space and time.
[laughter]
1:25:43 SA: But, okay. But, yeah. But, no, my second thought was the specific people you mentioned, John Preskill, Eddie Farhi, we could add Ray Laflamme, by the way, these were all people who started out in high energy physics but then very early, so back in the mid-90s, kind of switched to quantum computing and quantum information basically after Shor’s algorithm came along. And I know all of them. So I’ve talked to them about what some of their reasons were. And I think mostly just it was something that was new and exciting and where the knowledge that they had was relevant. It was not the only thing that was relevant. Computer science and information also was, but these were people who knew quantum mechanics really, really well, and high energy physics. It is one of the great pursuits of the human species. But if I’m advising a student on what they should specialize in, and they don’t really, really have their heart set on doing high energy physics, well, there is an immense amount of brain power that is being expended on not a huge set of questions on a very narrow… Let’s say a very tall and narrow tower of knowledge.
1:27:26 SA: And there was an unbelievable success over the course of the 20th century in building up that tower. And now that we’re in this world where the LHC has found the Higgs boson, it hasn’t found anything else, one could ask the question of should we just continue trying to add a millimeter to this tower in the way that we knew or should we go down to the land and look for what else is being built somewhere else?
1:28:03 SA: These are hard… There’s no one right answer to these questions. There’s an answer for each individual to make for themselves. But I think it is… Quantum computing, especially in the ’90s, was a field that was just full of low-hanging fruit and I think really fundamental questions. I think that to someone like Preskill, it was clear that this is not just a technological question. This is not just an engineering design problem of build this quantum computer. This is a fundamental question of, does… Is nature going to allow this at all? Can a scalable quantum computer be built? Or is this so ridiculous that we should just suppose that there is something about quantum mechanics that we have not yet understood that is going to prohibit getting an exponential computational speed-up in this way?
1:29:04 SC: Yeah. I think I understand your point. In fact, I think you’re being diplomatic about it. As amazing as high energy physics is, and I’m a big fan myself, it’s a mature field that has slowed down a little bit, the rate of progress. But I’m asking less about people who have switched from high energy into quantum computers versus people who… The thing they want to understand is still why black holes evaporate in a certain way. And they’ve decided that ideas from quantum information theory are relevant to that somehow.
1:29:39 SA: Yes. Well, that is a newer thing that has happened, and that’s actually right where I was headed next. Because in the ’90s, people went into quantum computing. I went into it in the ’90s, and did not expect that it was going to say anything about string theory, about black holes, about spacetime. Maybe even then, I secretly hoped it would, but I had no basis for that hope.
1:30:14 SA: And I would say that within the last eight or nine years, something really amazing has happened, which is that the things really have circled back and the people who talk about quantum gravity these days, about the black hole information problem, and about the AdS/CFT, about holographic spacetime, at least the ones who I talk to, they are talking about it largely in a language of qubits and qugates, quantum circuits acting on those qubits, and entanglement and the entanglement structure of the quantum states that you get, and even complexity. The complexity of doing various tasks to these qubits.
1:31:15 SA: And this has been an amazing development for me because I’m like, well, now I can actually talk to you about this stuff. This is a language that I can parse at least half of what you’re saying now. And if you look at the list of talks of the Strings Conference in recent years, it is quite remarkable to an outsider like me how much of it is not explicitly about strings at all, but is about sort of ideas that are just as much quantum information.
1:31:57 SA: So if I had to speculate… The way that this happened is a long story. But you could say in some sense, it goes back to Hawking in the ’70s and Bekenstein. The story goes back to the black hole information problem that said there is this fundamental conceptual problem about black holes. And this problem is information theoretic in character in some sense. The problem is, explain how information can come out of a black hole as it needs to do in order for the evolution of a black hole to be unitary, to be fully compatible with quantum mechanics as we understand it. And it was thinking about matters like those, that people in the ’70s and ’80s were led to the realization that a black hole has an entropy. Not only does it have an entropy, but it has the largest entropy of any object in the universe of a similar size. You could say a black hole is the highest density hard disk that is allowed by the laws of physics. Specifically, it stores about 10 to the 69 bits or rather 10 to the 69 qubits per square meter of surface area of its event horizon. Roughly one…
1:33:35 SC: Certainly, they’re in their highest entropy state. So it’s not a very useful hard disk.
1:33:40 SA: That’s right. That’s right. So it’s… Well, it’s not… It’s really not great for retrieving the bits. That’s the other problem with it. You’d have to wait for these bits to fizzle out and Hawking radiation, which might take 10 to the 70th years or something like that, and then they’d be in some completely scrambled form. So it’s not a very useful hard disk. But even just purely in… By the lights of information theory or computer science, black holes are interesting. Black holes are an extreme object. And so these were realizations that people started to have in the ’70s and ’80s.
1:34:28 SA: I would say it was not really connected yet to computer science. It was certainly something that enormously intrigued me, even in 2002, 2003, I talked to Raphael Busso at that time. I talked to Juan Maldacena, and Maldacena was joking with me about it a couple of years ago. I go, “Yeah, you were this crazy kid who was saying that complexity was somehow going to be relevant for quantum gravity, and I was trying to be polite to you.” So, yeah. But I would say that what really made it click, what really made this connection happen in a deep way, a lot of it started in 2012, which is when there was this now famous paper, the AMPS paper, Almheiri, Marolf, Polchinski and Sully, that they’d pointed out this thing called the firewall paradox. And this was… Well, it’s a long story, this firewall paradox. Okay.
1:35:41 SC: That was a punchline of it.
1:35:42 SA: But basically, you can… If you’re worried about how information can come out of a black hole, you’re led from there to the idea that, well, the information, it couldn’t have gotten out from the singularity. So really, what you would like for it to have happened is that instead of just fizzling off from the on or very near the event horizon. And in fact, if you’re an observer outside of a black hole, well, you never even see anything fall into the black hole in the first place. You just see it get slower and slower and pancaked over the event horizon and scrambled there.
1:36:21 SA: And so an observer who’s outside of a black hole ought to have a description of what’s going on, where all the bits of information that are dropped into the black hole are just sort of pancaked on its horizon, scrambled on the event horizon, and then come off from there. And yet, an observer who falls into the black hole has to have a completely different picture of the same physics. For them, they have to see that the information really has fallen in and that there is an interior of the black hole, in the middle of which is a singularity.
1:36:56 SA: And so then these two completely different sounding descriptions have to be somehow dual to each other. They have to be two different ways of describing the same thing. So then that leads, in the ’90s, to this idea of the holographic principle, that you can have different physical theories with different numbers of spatial dimensions, but that are somehow… Somehow one is just an encoding of the other one. So you can encode everything that happens in a given region of space by some hologram that lives on the boundary of that region. And then people were, I wouldn’t say like 100% satisfied by all of this, but they thought they had the broad outlines of a solution to the black hole information problem. And then basically in 2012, this AMPS paper came along and it broke everything again.
1:37:55 SC: Just to fill in long term…
1:37:58 SA: It said that if you write down certain postulates that seem like they should be clearly true, like an observer who is falling into a black hole notices nothing special as they cross the event horizon, and black holes from the outside observer’s perspective, they quickly scramble information and a few other postulates, then you could write down an experiment that, in principle, some observer who was outside of a black hole could do. So here’s how the experiment would work. Let’s say you’re Alice. So you dropped some stuff into a black hole. You keep track of its exact quantum state with some super-duper powerful quantum computer. And now, you wait for the black hole to mostly but not completely evaporate. Okay, you know, for a black hole, the mass of a star, this might take 10 to the 67 years, we assume that you have a really long grant, okay, you collect all of the photons of Hawking radiation that come out of the black hole, you route them all into your quantum computer for analysis, then you do a certain measurement on those photons that proves that they were not in a completely thermal state.
1:39:25 SA: In other words… And one can argue that once the black hole has more than 50% evaporated then something special happens where you can actually detect very subtle correlations in the Hawking radiation that shows that they actually do encode the information that fell in to create the black hole. Okay. So you get out… Excuse me?
1:39:48 SC: Yeah, so just to be clear about this, the phrase, not completely in a thermal state, in this sentence that you just said means that it’s not completely random, that there is some information encoded there that is related to what fell in.
1:40:03 SA: Yes, precisely, precisely. You detect some correlation with the stuff that fell in. And again, this is something that, in principle, you can do after the black hole has more than halfway evaporated. Okay.
1:40:18 SC: Yeah, okay.
1:40:18 SA: And then having done that, you then immediately jump into the black hole and you see what’s on the other side. And now, for reasons of quantum field theory that I don’t… Well, I’m A, not expert on and, B, not sure if we have time to go into, but because of the correlations that you saw outside of the black hole, you now… You either see a complete breakdown of the rules of quantum mechanics as you cross the event horizon, or else, if you want quantum mechanics to still work, then you have to see a wall of ultra high energy photons that are so high energy that you just disintegrate as soon as you hit the event horizon. This is what is called the famous firewall. Okay, and now, to be clear… Yeah.
1:41:15 SC: And, of course, no one has actually ever fallen into a black hole, but this is one of the times where physicists have a strong belief, that we have no empirical justification for, namely that nothing special happens when you cross a black hole’s event horizon.
1:41:28 SA: That’s right, that’s right. And in some sense, you could take the position that just, what happens in a black hole stays in a black hole. It could be any… It could be that like in that movie Interstellar that you meet your long-lost relative, or something, right. And just like beliefs about the afterlife, this would have no consequences that, at least, we could publish journal papers about here on Earth, because everything is just inside the black hole. But physicists, I think, very understandably, have high aspirations. They would like to describe even regions of the universe from which we can never receive a signal. And, at least, classical general relativity has… Paints this very nice picture where you sail right past the event horizon and nothing very special seems to happen.
1:42:26 SA: Now, to be clear, you do die after you jump into a black hole, but you’re only supposed to die when you hit the singularity. You’re not supposed to… So, you’re supposed to have another second or whatever after you’ve crossed the event horizon, you’re not supposed to die right at the event horizon. But this firewall paper was saying, “Well, from these assumptions, it appears that you would,” and this was not just some completely formal question about, say, the structure of the state space. What I liked about it is what they said here, very explicitly, “Here is the experiment that would lead to the problem,” and, okay, fine, it’s not an experiment that maybe we could ever practically carry out within the lifetime of the universe but, nevertheless, here is the experiment and if you claim to understand this then you have to be able to say what happens if someone did that experiment. Right?
1:43:31 SA: And this was… I would say that this was really the watershed thing that brought quantum information ideas into quantum gravity in a really deep way. And in particular, a year later, my friends Daniel Harlow and Patrick Hayden wrote an amazing paper about the firewall paradox where they said, “Well, it might be true that if you do this crazy experiment and then try to jump into a black hole to see what happened, that you would experience a firewall.” But how hard would it be to do that experiment? And they gave evidence that to actually do the quantum computation on the Hawking radiation that would detect those correlations, so detect that it’s not in completely a thermal state, would require a quantum computation that would use a number of steps that is exponential in the size of the black hole, meaning in the number of qubits of the black hole.
1:44:39 SA: So in other words, we’d be talking about a problem that would take your quantum computer not a mere 10 to the 67 years to solve, that is by our new standard, that’s going to be easy, 10 to the 67 years is an easy problem. But this would be a hard problem, meaning, one that takes 2 to the 10 to the 67 years to solve, okay, or something like that, yeah.
1:45:04 SC: So it’s really… It’s a very nice example because it takes us back to the realization post-Turing that the question is not just the distinction between solvable and unsolvable but how long it takes to solve things. And so once you appreciate that you might have some really strong beliefs in something, but if those beliefs could, in principle, be violated but only by things that would take way, way, way longer than the age of the universe to happen, maybe you’re not bothered so much. And that’s exactly what complexity theory is all about.
1:45:36 SA: Exactly. Now, now, this is, you know, this is somewhat controversial. Some people said, “Well, who cares if the computation takes this huge amount of time, that’s merely a practical issue.” But as Harlow and Hayden pointed out, one thing that it means is that you could not have made a dent in this computation before the black hole would have long ago evaporated anyway.
1:46:01 SC: Yeah.
1:46:02 SA: Right? [chuckle] Which means that then there’s nothing to jump into, which means that maybe then there’s no paradox. And yeah, you could think about, “Well, what if you did it for a really, really tiny black hole for which this exponential scaling wouldn’t matter.” But for a really, really tiny black hole, we didn’t really expect classical general relativity and quantum field theory to work well anyway. So I think it is plausible that that sort of the… I think… Okay, well, let me put it this way. If someone said it’s okay for there to be a contradiction in the laws of physics as long as it takes exponential time to discover it, I would not agree with that. I would say that sounds like nonsense. But that’s not what Harlow and Hayden were saying. They were saying something more subtle, that there are contradictions in the effective theories that we normally work…
1:47:01 SC: The approximate theory.
1:47:02 SA: But that we know have to ultimately be superseded by a quantum theory of gravity. And it might be that some of these problems with effective field theories, you would find them not by going to an enormously high energy or to an enormously tiny distance, but by going to a regime of extreme computational complexity. But if it would take an exponential computation to uncover the breakdown of effective field theory, then we do have a reason for trusting our effective field theory in “normal situations.”
1:47:43 SC: Yeah, and I don’t think… Sadly we don’t have time to go into the details, but I think that since then, since that watershed moment, there’s really been this wonderful importing of all sorts of ideas from quantum information and just theoretical computer science. I know, even I’ve written papers involving things like quantum circuits and tensor networks and stuff like that. And it’s really, really invigorated a mature field, I know.
1:48:06 SA: Yeah, yeah, yeah. No, it’s right. Lenny Susskind became a prophet of this movement, as he’s often a prophet for whatever he believes in at the given moment. [laughter] But I would say he became far more gung ho than I am about complexity as the future of physics. I was the one saying, “Slow down. I wouldn’t go that far.”
1:48:34 SC: You’d make a terrible prophet.
1:48:35 SA: But the connection has gone a lot further now, like in this AdS/CFT correspondence, where you literally use circuit complexity as the thing that is holographically dual to some geometric quantity, like the volume of a wormhole. That might be because… Lenny thinks that it’s because circuit complexity really does have fundamental importance in physics, just like entropy or energy. I’m not willing to go as far as he does there, but I say that nevertheless, it is the best placeholder that anyone can come up with for whatever quantity really is dual to these volumes of wormholes and things like that.
1:49:24 SC: It is great stuff. It’s right there on the cutting edge. And I think we’re going to have to end because the other topics I wanted to talk about include words like free will and consciousness and I can’t imagine that we would get anything interesting said in less than an hour each. So we’ll save that for a future episode.
1:49:42 SA: Great.
1:49:43 SC: And let people absorb the complexity and quantum-ness of what we already talked about.
1:49:49 SA: Awesome. If you invite me for a podcast about free will, I will choose to participate.
[laughter]
1:49:57 SC: So you say.
1:49:58 SA: Alright.
1:49:58 SC: It’s the universe that gets to decide. Alright, Scott Aaronson, thanks so much for being on the Mindscape Podcast.
1:50:03 SA: Alright, thanks so much, Sean. A pleasure as always.
[music][/accordion-item][/accordion]
Pingback: Shtetl-Optimized » Blog Archive » The US might die, but P and PSPACE are forever
The lecture notes are superb, for which well done!
Always interesting! I definitely want to hear the podcast where you guys talk about free will and consciousness. That should be really interesting.
This was one of my all time favorite Mindscape podcasts. The content was superlative. I particularly enjoyed the interaction between Sean and Scott. Sean is a great interviewer backed up with knowledge. He knew when to let Scott run and when to reel him in 🙂 I’m looking forward to the future “free will” podcast
All of these podcasts are amazing, but this one kicks goals. Sean, bring this guy back.