#83 - Scott Aaronson

Hey, how's it going? This is Greg Cannon, and you're listening to Y Combinators podcast. Today's episode is with Scott Aronson. Scott's the David J.

Bruten Centennial Professor of Computer Science at the University of Texas Austin. He's also the Director of their Quantum Information Center. And before Scott taught at UT, he taught Electrical Engineering and CS at MIT. And if you've checked out our other episodes about quantum and want to learn more, I'd recommend checking out Scott's book, which is called Quantum Computing Since Democritus.

He's also been blogging for over 10 years, and you can find all those posts at scottaronson.com slash blog. All right, here we go. Today we have Scott Aronson, a UT Professor CS, and also a blogger at Shtetl Optimized. And on the top of your blog, you have something that says, if you take just one piece of information away from this blog, quantum computers would not solve hard search problems instantaneously by simply trying all the possible solutions at once.

Why not? Good question. Go ask. So I've been researching quantum computing, working in this area for about 20 years.

I've been blogging about it for 15 years, I guess. Yeah. And the single most common misconception, right, which you find repeated in almost every popular article about this subject that is written. It says, well, a classical computer is made of bits.

And so it can just try each possible solution one by one. But a quantum computer is made of qubits, which can be 0 and 1 at the same time. And this means that if you have 100 qubits that the quantum computer can explore two to the 100th power state simultaneously, and then it can just try all the possible answers at once. Well, that is gesturing towards something in the vicinity of the truth, but it's also very seriously misleading, right?

And it leads people to think that quantum computers would have capabilities that actually we don't think that they would have, right? And this is not even controversial within this field, right? We all know this, but it's very hard to get the message out. I've been trying.

So here's the situation, right? The central thing that quantum mechanics says about the world is that to each possible state of a physical system, each possible way that it could be when you measure it, you have to assign a number called an amplitude. And amplitudes are related to probabilities, right? The larger amplitude means you're more likely to see that outcome.

But amplitudes are different from probabilities. Unlike a probability, an amplitude can be negative. In fact, it can even be a complex number. And so all the sort of magic of quantum mechanics, anything you've ever heard about the weirdness of the quantum world, the spookiness, it all boils down in the end to the way that these amplitudes work differently from probabilities.

In particular, probabilities can only sort of add up positively. The more ways that something could happen, that just keeps increasing the probability that it happens. But amplitudes can, as we say, interfere destructively and cancel each other out. So if a photon could reach a certain point, for example, in one way with a positive amplitude, and in another way with a negative amplitude, those two things can cancel so that you never see the photon there at all, as in the famous double slit experiment.

If you won't take this on my authority, you can take it on Richard Feynman's, right? He used to say that everything in quantum mechanics boils down to these minus signs. So a quantum computer is just a device that could maintain a state that is, as we say, a superposition with some amplitude for every possible configuration of the bits. So indeed, if you had a computer with 100 quantum bits, qubits, as we call them, that is two to the 100th power amplitudes that are needed to maintain that computer state.

And it's actually very easy to create, as we say, an equal superposition over all the possible states, which you can think of as every possible key for a cryptographic code, every possible solution to your optimization problem. So that's what the popular articles are trying to talk about. All of that is true. The problem is, well, for a computer to be useful, at some point you've got to look at the thing, right?

At some point you've got to measure and get an answer out. And the rules of quantum mechanics are very specific about how these amplitudes turn into ordinary probabilities that you see something. And the rule is the probability of some outcome is just the squared absolute value of its amplitude. That's the rule.

It sounds a little technical, but that's one of the most basic rules of the universe. It's probably a word. If you sound on paper, it would be. Yeah, that's right.

But in particular, one thing that means is that if I just created an equal superposition over all possible answers to some problem, and then I measure it, not having done anything else, then all I'm going to see will be a random answer. Now, if all I wanted was a random answer, I could have just flipped a coin a few times, saved billions of dollars building this device. So the entire hope of getting a speed advantage from a quantum computer is to exploit the way that amplitudes work differently. It's to try to choreograph a pattern of interference where for each wrong answer to your computational problem, like some of the paths leading there have positive amplitudes, some have negative amplitude, so they cancel each other out.

Whereas for the right answer, you want all the contributions to it to reinforce each other. The tricky part is you've got to figure out how to do that despite not knowing in advance which answer is the right one. Right, in addition to the error correction. That's right.

Oh, yeah, yeah, yeah, all of that too. Those are all the engineering difficulties. Now, I'm talking about even if you had a perfect quantum computer, it's still not obvious how to get a speed advantage from it, because you've got to choreograph this interference pattern. It's like nature gives you this really bizarre hammer.

And it was not until the 1990s that people really started figuring out what nails you could hit with this hammer. Well, this is a question I had for you. So quantum computers seem to be in this technology category, rather than the science category. So we did a podcast with Rana Adakari from LIGO.

And that is squarely put in the science category. How did quantum computers end up in this business use case category? That's a super interesting question, right? Because, yeah, indeed, often when magazines and newspapers are writing about quantum computing, they put a technology recorder on it.

And then they want to know about, well, how is this going to impact the finance industry in the next five years? And they will let's just see if the universe, let's prove that the universe has this capability at all. How about we do that? It's important understanding.

It's not there. That's right. So I think that part of what makes it exciting is that this is fundamental science. I mean, in the sense that we're overthrowing any of the known laws of physics, in fact, all we're doing is we're taking completely seriously quantum mechanics as it was written down in 1926.

It hasn't changed at all since that time. But what we're doing, what we're trying to do, is to test it in an entirely new regime, right? Where really, it has never been tested in this regime of, let's say, universal quantum computation or quantum error correction. The math seems very unequivocal that it's going to be done, but this is really building something that has never been built before.

And there are skeptics. I talk to them a lot. They come on my blog often, who say, this will never work. This is so absurd that you could build this quantum computer, that there has to be some new law of physics that will prevent it.

But there seem to be equal amounts of crackpot scientists to come on your blog and figure out the PNP problem. No, I get every kind of an original thinker on my blog. But that's one of the joys and pitfalls of blogging, I guess. But in particular, there are people, including very serious and well-known computers, scientists, and physicists, who say, well, look, if not a new law of physics, it must be that we just don't understand quantum mechanics well enough, that the error is going to inherently kill you.

You will not be able to scale this. And maybe you can build a small quantum computer, but nature will prevent you from scaling it up. And in the 90s, that actually seemed like a pretty plausible view, even to many of the experts in this field. What changed everything for most of us in the 90s was the discovery of quantum error correction and quantum tolerance, the upshot of which was if you want to build a scalable quantum computer, you don't need to get perfect qubits that are perfectly isolated from their environment, which, of course, would be a physical absurdity.

You merely need to get them ridiculously well isolated from their environment, and way better than we can do. But in the minds of most experts, it reduced it to nearly a staggeringly hard engineering problem. What I like to say is that if it turned out that there's some deep reason why this could never be done, and if the attempt to build quantum computers were to lead instead to the discovery of that new impossibility principle, well, then that's awesome. That's like Nobel Prizes for whoever discovers it.

And that's, compared to that, the idea that you can build a quantum computer is the more boring possibility. That's the more conservative option. As I said, we're testing quantum mechanics and this new regime, and we want to know the truth, whatever it is. So I think that there is fundamental science here.

And to me, that's really why I got into this. For me, the number one application of a quantum computer is not breaking cryptographic codes. It's not optimization problems. It's not simulating quantum physics.

It's just proving the skeptics wrong. Just to get out. What happened in your childhood? A lot happened, but we don't have to go into that.

But it is sort of seeing whether nature actually has this computational ability beneath the surface. Now, of course, what made a lot of the world interested in it is that it actually could have some applications. Maybe the most important application that we know about, it's just giving us this new way to simulate nature, simulate physics and chemistry, and maybe discover new drugs, discover new materials. I mean, that's the application that Richard Feynman and others had in mind when they first proposed the idea of quantum computing in the 1980s.

But before we started recording, you were talking about what you've been working on for the past year, which is potentially relevant, because many of these drug-finding applications might need, say, a million qubits. We might already be able to start getting some of these with some hundreds of qubits. People are going to try. But we're not even at 50 yet.

That's right. Not 50 that we have good enough control over, certainly. Right. So what was the application that you're working on?

OK. So I have no idea that I've been working on for the past four months or so. And there's been independent work by others pursuing related ideas. But as far as I can say, maybe the first application of quantum computing that people could actually be able to realize with like near-term devices, with 50 or 60 or 70 qubits.

And this application is to generate cryptographically secure random bits. So for example, if you have these proof-of-state cryptocurrencies, you need a huge public source of random bits to sort of run this lottery to decide who is allowed to add a new block to the blockchain. For all sorts of other cryptographic applications, you need public random bits. Of course, decide which precincts to audit an election, for example.

Of course, for cryptography, you also need secret random bits. Now for secret random bits, you would need to own the quantum computer yourself. You wouldn't want to download them over the internet. So now there are many websites already that will give you public randomness.

There's one called random.work, where you can just get random bits to order. Allegedly random. Yeah, right. Yes.

Allegedly random. Thank you. NIST runs something called the randomness beacon, where every minute they release 512 new random bits to the world, which are partly generated using quantum mechanical processes. So now you could say if you believe quantum mechanics, that would you should, it's very easy to get random bits.

Randomness is going to baked into quantum mechanics, famously. You could just keep measuring some photons, measure the polarization, the outcomes will be random, or just get some radioactive material from Kim Jong or whatever. Just put a Geiger counter. The Ks will be random.

But if you were to get these random bits from the internet, then the question is, how do you know how they were generated? How do you know that the hardware wasn't back to word by someone? In fact, NIST did have a standard for pseudo random bits, which we learned a few years ago because of this note in documents was back-dored by most likely by the NSA, right? So there is a big issue.

How can you trust randomness? How can you prove to someone that bits were actually generated randomly? It seems almost like a philosophical impossibility. So how does yours work on that?

So there are ways to do this with quantum mechanics. Over the past 10 years, people discovered that one way to do it is using the bell inequality, which means if you had two entangled particles that were far away, and you measured them, and you see that they have a certain type of correlation that could not have been produced classically. This is kind of the famous bell inequality. It's the thing that disproves Einstein, that there's no sort of secret local hidden variables that control what's going on, that sort of quantum entanglement is a real thing in the universe.

But for many decades, people said, well, this is a conceptually breakthrough that Bell made. Of course, it's completely useless. Of course, you don't actually need to create these correlations between far away particles. But what people realized a decade ago was actually the fact that you've created those correlation also means that there has to be some randomness in the bits that are produced.

Because the only way to create those correlations without using true randomness would be using communication. But if we put the things far enough away that a signal could not have gotten from one to the other, even traveling at a speed of light, then we can have some kind of assurance that there is randomness there. But now the one thing is you've got to believe that these devices were really separated far enough, which again, if it's over the internet, how would you know? So the new realization is that you can get guaranteed randomness with a single device, at least under some cryptographic assumptions.

As long as that single device is able to do quantum computations that are sort of hard to simulate with a classical computer. So basically what you would do, imagine that Google, let's say, has some 70 qubit quantum computer, as indeed they are working to build right now, just visited their lab a month ago. They're working on it. I don't know when it's going to be ready.

But then you could, with your classical computer, could submit challenges to the quantum computer that basically say, just run this quantum circuit, which is pretty random looking, pretty messy arbitrary quantum circuit. But just run this quantum circuit, and then it will lead to some probability distribution over output strings, in this case, strings of 70 bits. And so that just gives me a sample from this distribution. And I'll just keep sending it challenges of that kind, one after another.

And each time, the man that had sent me back the sample from this distribution in a very short time, like let's say, half a second. And then I take these samples. And now if Google did the right thing, then these samples have lots of randomness in them. But the more interesting part is that under cryptographic assumption, if I can check that these samples were actually correlated with the distributions that are supposed to be.

So in other words, one shows up 10% of the time. Well, yeah. So all the outcomes are pretty unlikely, because they're all on the order of 2 to the minus 70 probability of occurring, but not exactly. Some of them are twice 2 to the minus 70.

Some are half 2 to the minus 70. And so I can check that the heavier outcomes are more likely to occur. I can do some statistical test to check whether Google is plausibly sampling from this distribution. And then what we can do is we can mathematically prove, if you'll assume that some problem is hard for a quantum computer that looks like it should be hard, then it would follow that even with a quantum computer, the only way that Google could be quickly generating samples that pass this test is to generate them truly randomly.

There's no secretly deterministic way to do it without them spending a huge amount of computational power more than we believe that they have. And so when you were testing this out, or did you test it out with tons of computers? It has not been tested out with real quantum computers yet. I mean, the apparatus that I use is a pen, paper.

And I did use a maple a little bit to do some numerical optimization. So yeah, I have a sexy thing. I'm a theoretical computer scientist. But Google is hoping to move forward and test this out and actually demonstrate it once they have the device.

I mean, of course, it could also be simulated with a classical computer, one could code something up. But one thing that's exciting about this is that it looks like pretty much as soon as you have a 6-0 or 70-cubit quantum computer that can sample any distributions that are hard to sample with a classical computer, you can pretty much get this application. So it's sort of designed for near-term quantum computers. And in fact, even if you had many more qubits, we couldn't really make use of them for this application.

Because the verification, if I have n qubits, is going to take 2 to the n time with my classical computer, which means that with 1,000 qubits, it might be working fine, and yet we can never verify it. Man, what other projects did you clear from the cache on your sabbatical? Well, not many. So I was on sabbatical in Tel Aviv for a year.

I came with a long list of old papers that needed to be written up. And I wrote up almost none of them. And instead, I just started new projects. And put the old ones even further onto the back burner, which is often the way it goes, unfortunately.

But actually, I did write a paper this year about a new procedure for measuring quantum states, which is called shadow tomography. I had a more boring name for it. And then a physicist. I appreciate it.

Yeah, it came up. Physicists are much better than computer scientists at naming things. So it's called shadow tomography. And what it is, so measuring in quantum mechanics is an inherently destructive process.

Famously, it collapses the wave function. It collapses your state. And you only get one chance. So the problem that shadow tomography is trying to solve is let's say I have a small number of copies of a quantum state.

But I want to know the behavior of that quantum state on a large number of measurements. So a much, much larger number of different measurements than the number of copies that I have, maybe even an exponentially greater number. Let's say for simplicity that each measurement has just two possible outcomes. Yes or no?

And I want to know for each measurement, what is approximately the probability that it would return yes applied to the state? So of course, if I have enough copies, I could just measure each copy with a different measurement. But I don't have enough copies. And again, if I have enough copies, I could just fully learn my state, measure each copy and then eventually, by collecting enough statistics, I could write down in my classical computer a full description of the quantum state.

But I don't have enough copies for that either. Where are these assumptions coming from? You don't have enough copies? Oh, well, I'm telling you that because this makes the question interesting.

I mean, if we do have enough copies, then we do one of those simpler things. But I'm asking what happens if we have... So maybe it's very expensive with your hardware to create new copies of the state. So what shadowed demography is, is it's a way to sort of take these states and manipulate them very, very carefully so that you can keep reusing them over and over.

And where are they? Without destroying them. Without destroying them, damaging them only slightly each time. And where are the answers to each of these yes or no questions, which again, there could be exponentially more of than there are copies of the state.

How does the partial destruction work? Well, OK, so it has to do with the way that measurement works in quantum mechanics, right? Is that if you measure your state in the wrong basis, then the state is destroyed. So for example, if I have a state that is...

If I have an electron that's very spread out in position, and I ask it what's its position, then I now force it to make up its mind. It's localized now to one place, and then that destroys all the other information that was in that superposition over positions. On the other hand, if I ask that electron for its momentum, well, then its momentum might have been much more determinate. And if I ask a question, where given knowledge of the state, and someone could have almost perfectly projected the answer to that question, then the state only needs to be damaged slightly by the measurement.

OK, I mean, we know that nodal measurements are destructive. You know, if I read a book, and I see where's the written in it, my friend can read the book, too. So that's a non-destructive measurement. But even in the quantum realm, if I'm careful to measure a state in a basis where it's already been localized, then that's not going to damage it by very much.

So now the challenge, of course, is now I have these copies, and I say, I don't know in which basis they are localized. But I can do something. And this measurement procedure that I designed takes a very long time to carry out. So I'm not promising you that it's fast.

But it makes very, very careful reuse of these same states over and over again. So this had various implications. It's all various theoretical questions that I cared about. By the way, I had conjectured that this was not possible.

And so this is the way that research often happens for me. I tried to rule it out. I was unable to rule it out. And eventually I figured out why.

So was it just brute-forced pen and paper? Or did you have a conversation and sparked it? Well, I mean, I had taught a mini course in Barbados a few years ago, where I raised this as a question. Yeah, I don't see how to do this.

Maybe it's not possible. And then I just thought about it more. And of course, I was building on earlier work that others had done. So it's like, you never start completely from scratch.

You know the tools that were used to solve related problems. But anyway, but then this year, we've carried it further. So I have joint work with Guy Rothblum from the Weitzman Institute. And what happened was I gave a talk about this work.

And he said, this idea of measuring a quantum state very gently and not damaging it. This sounds a lot like what I work on. He's a guy who's a classical computer scientist who works in a field called differential privacy. So some people may have heard of this.

This is actually used, I think. And some, I don't know if Facebook uses it, but some websites use this. It's a way that you can do data mining for a database of a whole bunch of users' sensitive data. It could be their medical records, it could be all their personal data.

But you can do it in a way that mathematically guarantees in some sense that you're not going to be revealing too much information about any individual user. In a sense, if any individual user were to drop out of the database or change their data, then that would have only a very small probabilistic effect on the outputs of this algorithm. And the way that you achieve differential privacy was often things like I may ask like how many of these users have colon cancer or something. But that'll add some random noise to the result.

And so then adding the random noise, the data is still perfectly good for doing medical statistics. But now it's like, even if I knew everyone else's data, I still can't determine whether a particular person has colon cancer or not. So he said, you know, and actually you do the same kinds of things to get gentle measurements of quantum states. So Guy said, there seems to be a connection here.

And he said, come on. It's like you can relate anything to anything else. That's probably just an analogy. But then we sat down and in fact, there is a connection.

There's a precise mathematical connection between these two problems. You can prove it. It goes in both directions. And then we were actually able to use it to take work that's been done in differential privacy by people who don't know anything about quantum mechanics, just purely classical CS and use it to get better procedures for shadow demography.

That's really cool. Is that online? Is that OK? It's another thing on my stack.

It's like another stack all the way. Well, you know, we will try to write it up this summer. All right, cool. So moving to one of the more poorly named CS problems that we talked about at email, the P versus NP problem.

I heard you describe this because it can sound really complicated. But I heard you describe it once as, for every efficiently, checkable problem is it efficiently solved. Yeah. I thought that was a good way to describe it.

I mean, that's just the standard way to say what this problem means, right? But why does it matter? I guess it's quite a question. I think it's a strong contender for the most important unsolved problem in math, you know, of this century.

So NP stands for a non-deterministic polynomial time. As I said, not as good as naming things. Terrible, yeah. But it's all the problems where if I told you the answer, you could check it efficiently.

What we mean by efficiently in computer sciences, like buying algorithm that uses a number of steps that scales at most like the size of the problem raised as some fixed power. We call that a polynomial time algorithm. That's kind of our rough and ready. It doesn't always correspond in practice to efficient, but it's a pretty.

Yeah, exactly. It's ballpark. And it's like, if we can't even answer this, then we're not going to answer the more refined questions either. So NP is all the problems that are efficiently solvable.

They actually have an algorithm that will find the answer in many steps. So a good example of an NP problem would be factoring. I give you an enormous number. I ask, what are its prime factors?

That problem happens to underlie much of modern cryptography. A good example of a problem in NP, if I just give you a number and I ask you whether it's prime or not, but not to find the factors, then that actually has a fast algorithm. It was only proven to be in P 16 years ago, that a big breakthrough. So that's an illustration of how it could be very, very non-obvious to figure out which problems have these efficient algorithms and which don't.

And so in particular, I think as soon as anyone, as soon as a late person understands the P versus NP question, I think most of them would say, well, of course, there's not going to be an efficient way to solve every problem. It's a different checkable way. Why are you even asking that? I mean, a jigsaw puzzle.

Obviously, it's a lot easier to look at a jigsaw puzzle that your friend did and say, oh, good job. It's like you finished it. And to actually do it yourself. Same with a Sudoku puzzle, same with breaking a cryptographic code, same with solving some optimization problem, like optimizing an airline schedule that may involve solving some satisfying some enormous number of constraints, or as many of them as you can when they conflict with each other.

But it's not proven not to be possible. That's right. That's right. No one has ruled out that a fast algorithm could exist.

Essentially, it's very, very hard to prove a negative. Occasionally, we can do it. But it tends to be much harder. And if something is possible, you just have to show how to do it.

But to prove that something is not possible, you have to, in some sense, understand the space of all the possible ways that it could have been done, and give some general argument why none of them could work. So sometimes we can do that. We've made no progress. But we're a long, long way from being able to prove things like peanut equal to NP.

I like to say that if we were physicists, we would have just declared peanut equal to NP to be a law of nature. We would have just been done with it. Yeah, fine, I'm not a bit clear. That's right.

It's like the second law of thermodynamics. We could have given ourselves Nobel prizes for our discovery of the law. And later, if it turns out that, oh, actually, P equals NP, there is a fast way to solve all these problems. Well, then we could just give ourselves more Nobel prizes for those over-thrown.

But there's one thing you learn in an interdisciplinary subject, like quantum computing, is there differences in terminology and culture between fields, right? What the physicists call law, we call a conjecture. Right. Yeah.

It's increasingly hard to draw the lines in between the two as well. Yeah. C.S. math, physics.

Oh, yeah. Well, no, I make fun of my brothers and sisters in physics all the time, only because I love them, of course. But in fact, large parts of physics and C.S. have been coming together in the last decades.

Partly, statistical physics made this very, very deep connection between spin glasses and condensed matter physics and combinatorial optimization problems. And you can understand what many algorithms are doing using physical analogies. And then, of course, quantum computing was this enormous intersection where suddenly these fields were just thrust together. And they had to quickly learn each other's terminology and frame the reference.

And that's a good part of what I've been doing. It's just helping to translate. And I give colloquia in physics departments where they just want to know, what are P and NP? What are the basics of undergraduate level computer science?

But what's cool is that I can talk to string theorists, let's say. And they know this staggering tower of knowledge that I don't know, that I'm only at the lowest foothills of. And yet, suddenly, they too need to know about computer science. So they want to know what they want to talk about.

So we did a podcast with Leonard Suss. And that's not out yet. He's the perfect example of someone who has been pushing this intersection, maybe even more aggressively than I've been. Every time I talk to him, I'm like slow down, many.

Computer science is not quite the future of all of physics. He's like, absolutely is. We didn't even get that far. But I do have a question related to his work.

So he talks about this holographic principle. How does that relate to the firewall paradox? I couldn't quite grasp it too together. This is a big discussion.

OK, the holographic principle is this general phenomenon, where often you write down a physical theory in some number of dimensions, involving, let's say, a three-dimensional space. And then it turns out to be doable, in some sense, to a completely different looking physical theory, which is defined on the boundary of that space. So I can even in a different number, one fewer dimensions. And the first theory, the one that's in the bulk, as they say, in the interior, involves gravity.

So it's a quantum theory of gravity, where it could have things like black holes that form and evaporate. Whereas the theory that's on the boundary is a pretty ordinary quantum field theory, meaning it has no gravity. It has a flat spacetime. So these two theories look totally different.

And what do you even mean in saying that they're the same thing? Right. It's like literally the same information. It's very confusing.

Well, you mean that there's a one-to-one mapping between states of the first theory and states of the second theory. And this mapping is non-local. I could have a little particle here inside of the bulk. And yet, in the boundary theory, that would correspond to some enormous smeared out thing.

The mapping between the bulk theory and the boundary theory, in recent years, people realized that it is literally an example of one of these quantum error correcting codes that I told you about before. Same things that one would need in building a quantum computer. It is the whole point of an error correcting code is that you take a local one bit and smear it out. You represent it with a large number of bits.

And so this is also what happens in a hologram, hence the name, holographic principle. So there's this smeared out representation of everything that's happening in the interior, which is represented on the boundary. And this is the most precise definition that the string theorists are able to give, of what they mean by quantum gravity. They say, well, what we really mean by quantum gravity is you define this theory on the boundary, which they more or less know how to do.

And then somehow there's this thing in the bulk that's still a little bit of action. So again, the different cultures are different states. They don't even have a rigorous independent definition of this bulk theory. But what they can do is in various special cases, they can calculate things in the bulk theory, and then they can calculate the same thing in the boundary theory.

And in every single case where they can do the calculation in both places, they get the same answer. This is what leads them to say. Good enough for them. How does that relate to the firewall?

So the firewall paradox is this sort of like a modern refinement of Stephen Hawking's original black hole information paradox from the 1970s. Like Hawking radiation. So shortly after he discovered Hawking radiation, in 1975, Hawking wrote a paper that posed the information paradox or puzzle of black holes, which is basically just the question, how does information ever get out of a black hole? Why does it have to get out?

Well, if we believe that quantum mechanics describes everything in the universe, quantum mechanics accept possibly when a measurement is made. If you believe in the many worlds theory, then even a measurement is just another ordinary thing, which is you split into multiple branches. But let's leave that aside. Any isolated physical system is supposed to evolve in a completely reversible way.

It may be very hard to reverse in practice. It's a lot easier to scramble an egg than to unscramble it. But in the video of physics since the 19th century, that's merely because our universe started in a very special state with a very low entropy. My friend Sean Carroll likes to say that every time you cook an egg, you're doing an experiment in cosmologists.

You're proving that the Big Bang was in a special state. But in principle, everything is supposed to be reversible. So in particular, if I drop an encyclopedia into a black hole, then the information, what was written on the pages, cannot be deleted from the universe. It has to still be there.

So the question is, where does it go? You could say maybe when it hits the singularity, it goes into some other bubble universe. I think people thought about that for a while. But a popular point of view nowadays is that ultimately the information does come out.

It comes out in the Hawking radiation, which were for a black hole that was the mass of our sun. It would take a mere 10 to the 67 years for this to happen. Maybe, eventually, you have a long enough grant. You could wait and see this.

Eventually it would come out. Of course, it's in a very scrambled form. If I burn a book, physics tells us that the information is still there and the smoke and ash. It's not very accessible anymore.

In principle, it's still there. And so the idea is that a black hole is just another example of this. But there's a big puzzle, because the information, if you were a floating next to the encyclopedia, you would just see it right past the event horizon of the black hole all the way down into the singularity. And it doesn't seem like it's ever coming out.

How does it get into the Hawking radiation to go to come out? And so this was such an acute puzzle that it forced people like Lani Saskin and Gerard and Hooft in the 1990s to this view called black hole complementarity, which basically says that there are two different ways to look at the same situation for an observer who's outside the black hole or for an observer who is jumping into it with the encyclopedia. And the idea is from the point of view of the first observer, the information, if you never even makes it past the event horizon. It just sort of gets pancaked.

Right. It's like a flying windshield. Yeah. I mean, first of all, just because of relativistic time dilation, you're never going to see anything fall into the black hole.

It'll just get slower and slower as it nears it. You'll never actually see anything go in. And so the idea is from the outside observer's point of view, you could treat the interior of the black hole as not even existing at all. Or it's just like some weird and different and scrambled way to rewrite what is happening on the event horizon of the black hole.

So this is another example of one of these holographic dualities, where there's two different ways to look at the same physical situation. There's the interior point of view. And then there's the point of view where it's all on the event horizon. And so then there are all sorts of puzzles about reconciling these two different points of view.

As you could imagine, the firewall paradox was a particular technical puzzle about how to reconcile these two different points of view. If we had another 20 minutes, I could get into it. But it might take too long. People actually do.

The other thing they do is that they use this bulk boundary correspondence as a laboratory. So they say, we have a space time where we have a boundary, where we can calculate what's going on. And now that's inside of the bulk of that space time, let's form a black hole. And now let's try to answer all these enormous conceptual questions about what is going on inside of a black hole by translating them into questions about what is happening in the boundary theory.

Now meaning the boundary of space time, not the boundary of the black hole. But that's proven very difficult. Because in some sense, what physics, what the theory wants is to just answer questions about what is observable by some hypothetical observer who is far away from all the action, who can just send in some particles that also hit each other and stuff, and then some other particles come out. So this is a point of view that physicists like to take a lot of the right, all of existence.

It's like a giant particle collider. He just sends some things into each other. You look at the debris that comes out on the other end. But if you're asking, what is the experience of someone who jumps into a black hole, then that is inherently not that kind of a question.

It's not a question about the observer at infinity. It's a question about someone who is very much in the action. Like Alice Sensbob into black holes. Exactly.

And these boundary pictures don't seem very good yet at addressing that kind of question. OK, so let's head on to another unanswered question. Yeah, sure. Sure.

So you've got a bunch of AI-related questions from the internet. And it seems that people want you to opine about AGI. So let's go with one of them. Yeah, sure.

So Anag asks, how can we channel AI growth but not weaponize it? So in a sense, like, how do we, it seems like there is something AGI happens? What do you think? I mean, I think that there will be many social issues that we'll have to deal with with AI, or already are having to deal with.

Even long before we reach the arrow in, AI is near the level of human intelligence. I mean, we're obviously going to have to worry about self-driving cars and all the benefits, and also the disruption and issues that those are going to bring AI for data mining and all of the implications that it has for privacy. Or a deep net denies your loan application. But then no human can explain why your application was turned down.

So those are things that lots of people are thinking about. And the good thing is that we can try things out in the real world. I think we don't normally think of ethics and morality as experimental sciences. But very often, people have moral intuitions about something that are really bad until they have been checked by experience.

And so we're going to have to sort of, and we'll have the opportunity to refine our ethical intuitions about all these issues by seeing the ways that AI actually gets deployed. And I don't think I'm going to shock the world. I hope that we'll find ways to use it for good and not for evil. But I have many friends, especially here in the Bay Area, where I see every time I come to visit here, who are very, very interested in what happens after that, when AI actually reaches the level of human intelligence or exceeds it.

And clearly, whenever that happens, then we are living in a completely different kind of world. And I think of the woolly mammoths, once the hominids start making their spears and their bows and arrows, life is not the same anymore. And so a lot of my friends in this community are very interested in the question, how can we ensure that once an AI gets created, or beyond human level, that it shares our values? It doesn't just say, OK, my goal was to make paper clips.

So I'm going to destroy the whole Earth, because that's more raw material for paper clips. And I said, well, I should know the humans created me. I should revere them as my great, although slightly dimly that answers their side. I should let them stay in a nice utopia or something, even while I go off and prove P is not equal to N-Pit.

You're going to do whatever interests make. So my point of view is that if civilization survives for long enough, eventually we're going to have to deal with these kinds of questions. I see no reason to believe that the human brain, which is the product of all these weird evolutionary pressures, including the width of the birth canal, and how much food was available in the ancestral environment, and all this stuff, there's no reason to believe that we are near the limits of intelligence that are allowed by the laws of physics. And so eventually, sure, it could be possible to produce beings that are much more intelligent than we are.

And we have to eventually worry about that. I have to confess that personally, when I think about the future of civilization, the next 20 years, the next 50 years, I tend to worry less about superintelligence than I do about super stupidity. I tend to worry about killing ourselves off or by catastrophic climate change, by nuclear war, or just the world, regressing into fascism, just giving up on liberal democracy. And of course, we've seen many distressing songs all over the world that there is this kind of backsliding right now.

And so I like to say that I hope that my biggest hope is that civilization should only last long enough that being destroyed by super intelligent robots becomes our biggest. Right. Let that be our worst problem. Right, of course.

It's a silly mental game where it assumes we've learned nothing along the way. And it's just like how to do that. Well, I mean, I wouldn't go that far. I mean, I think it's good to have some people thinking about these things, right?

Just like there should be people thinking about how could we prevent a catastrophic asteroid impact? Or how could we prevent a bioterror? And they'll probably discover various interesting things along the way that we'll have implications for the world of today. I mean, that usually happens when people let their minds roam freely over the far future.

So I'm happy to have people think about this. I just think that let's as practice for solving the problem of AI alignment. Let's see if we can solve global warming first. Yeah, let's see how that goes.

Yeah, see how it goes. All right, let's do another Twitter question. So Michael Berg asks, is anyone keeping track of the smallest and such that Busy Beaver N is independent of ZF set theory? Yeah, he mentions, I recall there was some activity after the 2016 article.

I assume that was on your blog. I guess it was. And I'm wondering if 1919 states is still the record. So let me back up and explain what he's talking about.

So the Busy Beaver numbers are one of my favorite sequences of numbers, since I was a teenager. The nth Busy Beaver number, you can think of it as the largest finite number of things that could be done by any computer program that is n bits long. So we rule out programs that just go into an infinite loop. But we say as long as your program has to eventually halt, then what is the most number of things that it could do before halting this program is say n bits long.

And it's run on a blank input. So of course, this could depend on the programming language a bit. But let's just take the original programming language, touring machines. And so then the nth Busy Beaver number is defined as the largest number of steps that can be taken by any touring machine with n states, as defined by Alan Turing in 1936 before it halts.

And the amazing thing about this function is that it increases more rapidly than any function that could be calculated by any computer program. This is provable. So it is a ridiculously quickly growling function. So the first four values of the Busy Beaver function are known, right?

They're like 1, 6, 21, and 100 and something. The fifth one is already not known, but it's at least 47 million. And then the sixth one already, you would need a stack of exponentials to start to express it. So if you're ever in a contest to name the bigger number, you just say Busy Beaver of 100, if your opponent does not know about computability theory, you will destroy them.

OK, but now another fascinating thing about this Busy Beaver sequence, besides the fact that it grows so rapidly, OK, well, in some sense, in a certain sense, it encodes all of mathematics. For example, if I wanted to know, is the Riemann hypothesis true, right? Well, there's some touring machine with some number of states that tests the Riemann hypothesis, right, that halts only if it finds a counter example to it. And then if I knew Busy Beaver for that number of states, then I would just have to run that machine for that number of states, see if it halts, that would answer the Riemann hypothesis, right?

So sometimes it's no surprise that this function grows uncomputably rapidly, because it has so much, so many secrets of the universe encoded into it, right? And furthermore, one can prove that the axioms of set theory can only determine finitely many values of this function. OK, so sometimes beyond a certain point, the standard rules of mathematics cannot even prove what are the values of this function. It has some values, because every touring machine either halts or it doesn't halt.

And yet, in some sense, we could never know them, right? So a few years ago, I had a master student, when I was then at MIT named Adam Yudidia, and I gave him as a thesis project to try to determine, well, what is a concrete bound on the number of states where this Busy Beaver function just goes off the cliff on the nobility, right? We may not be able to determine exactly where it happens. But at least we could say, does it happen at most 10,000 states, or most 100,000 states?

So what he did is that he designed a touring machine with about 8,000 states that does something that's equivalent to just trying out all the possible theorems of set theory, one after the other, and halting if it ever finds a contradiction. Now, what does that mean? Well, it means because of Gertel's incompleteness theorem, means that a set theory can never prove that this machine runs forever. If set theory is consistent, then the machine does run forever.

But if set theory were able to prove that, then set theory would be proving its own consistency. That is a no-no. That's exactly what Gertel's second incompleteness theorem says it can't do without being inconsistent. I think I got it.

Yeah, yeah, yeah. It's kind of like the way to remember it is anyone who brags all about themselves probably has nothing to brag about. If your theory is bragging about its own consistency, it means it's inconsistent. And a theory could believe it's inconsistent while being consistent.

That's possible. But not the other one. So I can't believe it's consistent. So he designed an 8,000 state machine.

This was a lot of software engineering. You had to compile down the touring machine, keep very careful control over the number of states. And so then he and I wrote a paper about this. I put it up on my blog.

And then what's cool is that a lot of hobbyists were able to look at this, say, maybe they can improve on it. In particular, there's a guy named Stefan O'Rier. And he got it down to a less than 2,000 state machine. And I believe that most recently, he's gotten it down to under 800 states.

In any case, he hasn't written a paper about it, but all of his code is available on GitHub. If anyone wants to look at it, even try to improve over what he did. I suspect that there may even be a machine with 10 states that would already exceed the ability of set theory to know what it does. Why do you suspect that?

Well, I don't know. I mean, already with five states, there were machines whose behavior seems to hinge on some weird number theory. No one has yet understood this. And we know how rapidly this busy beaver function grows.

I mean, the truth is that we don't know. But it's somewhere between 5 and 800 or so. This thing goes off the cliff. Cool.

Yeah. I actually do have a question about your blog. So from what I can tell, you're basically inactive on social media. Yeah.

Well, I do not have a Twitter account. That's not an accident. OK. Yeah, that's what I figured.

Despite that or in spite of that, you've been blogging for 10, 15 years. Since 2005. And I guess blogged on some other blogs before that. OK.

But I mean, blogs used to be considered social media. I mean, yeah, I feel like a dinosaur. Like back in my day, we just had blogs. And we really liked it.

I mean, I feel like so. So my friend Sarah Constantine had a post. I thought a very insightful post about this recently, where she was making the point that blogs are, I think, very much in keeping with the sort of original promise of the internet. The original idea that it was going to be a space where people would discuss things, where they could spell out an argument by composing some paragraphs of text that would set out what they think and why, put their take responsibility for what they said, put their name to it.

Other people would then respond to it, give counter arguments. It would all stay there. You could search for it. You could find it.

You could link to it. It's very much a continuation of the culture of the USNET in the 80s and 90s. And since then, we seem to have moved away from that toward a model of communication on the internet. That's a lot more like what offline communication used to be.

I've described Twitter as the world's biggest high school. I mean, which doesn't mean it's all bad. In fact, I have wonderful friends who use Twitter to do very worthy and great things. I like to tell them that they're sort of like, they bear the same relationship to Twitter as the 10 Righteous Men, Boredess Autumn and Demorra.

But unfortunately, it is not a medium that I think is designed for spelling out an argument or for explaining carefully where you're coming from. It is almost designed for ganging up with people, for forming these kind of outrage mobs, which indeed, we see that it is susceptible to these repeated outrage explosions. And I'm not blaming one political side. I think we could find plenty of examples on both ends of the political spectrum of Twitter being used for I think it was really nasty purposes.

And I mean, a tumblr and Instagram. It's not always nastiness, right? But they're just sort of, you know, they're designed for kind of sharing a photo. People click like on it.

It's a lot of kind of social signaling. It's a lot of building up one's popularity, one's presence, and not sort of discourse. They're not really designed for carefully clarifying, well, what is it that we really disagree with? Where are we coming from?

And that is really what interests me. That is what, I don't always succeed. But that's kind of what I try to do in my blog. I think the problem comes when we try to have that kind of conversation on the blog, like a really careful conversation where anyone is welcome to contribute, but they have to play by the ground rules, right?

Of sort of have some empathy, understand where other people are coming from. And then if people come into that from the culture of outrage models, they just say, let's just look for the most inflammatory sentence ripped out of context. We can just put all over Twitter to say, look at these weathering idiots, right? Then it really becomes scary.

And it becomes much harder to have that kind of discourse where you're really trying to understand the other side. So have you been, yeah, because you've been the victim of this before, right? Like, yeah, for a better point. I mean, I mean, a lot of people who try to do this.

I'm sure, yeah. In fact, a lot of people have had a much worse than I have. Yeah, absolutely. And is that like, were you on Twitter at one point?

And these, okay. No, it was just never really tempted me. I mean, if I have something to say, I, you know, I mean, sometimes I just put like little updates on the ends of my blog post that are kind of like tweets. But yeah.

Yeah, okay. Do you have a favorite post? Oh. So I had these posts critiquing information, so sorry, Integrated Information Theory, which is a proposed theory of consciousness by people like Julia Toononi.

And I was explaining why I don't think this theory of consciousness works, why it's all of the problem it's supposed to solve. But what was great about this post is that, you know, the, all the experts, you know, Toononi himself got involved in the discussion. David Chalmers, the philosopher of consciousness got involved in the comments section. And so we kind of had this, you know, kind of Plato's Academy thing going, right?

You know, like, you know, just in my blog comment section, I feel like we were actually able to make progress on major issue, right? You know, that's not all right. I mean, sometimes I write a post that just, you know, so stupid joke or procrastination. But sometimes, you know, when I, you know, have something that I want to get out there, it's nice to have a forum.

Yeah, that's great. Yeah. All right. So you suggested this question, so I might as well ask you advice for young people.

So you kind of are all across the world, like, you know, you're potentially licensing ideas to companies, but you're within academia, and you're also, you know, kind of a CS science communicator. So you're across many realms. What is your advice for nerds in general, or yeah, people who want careers in science? Well, first of all, you know, if you are currently in high school, you know, well, you know, I hope you're having a good experience.

If you are, that's awesome. Then you know, take advantage of it. If you're not, you know, realize that things will get better. You know, so one of, you know, because this is a Y Combinator podcast, I should mention that one of the most influential essays that I ever read was Paul Graham's, Why Nurds Are Unpopular.

Oh yeah. It has an enormous amount of insight, I think. That's the beginning of Hackers and Painters. Yes.

Yes. So, you know, so buy his book, but if you don't want to buy it, he's also got it on his website. Yeah. And the basic argument that he develops there is that, you know, we, you know, a teenagerhood is sort of a creation of the modern world, right?

It used to be that, you know, once people would pass through puberty, right? Well, you know, either they would go out and get married, you know, right, that or they would apprentice themselves to some craftsman or, you know, maybe they'd be working in the field or whatever, right? But, you know, but in any case, they would not be in this sort of environment of high school, which is sort of an artificial environment that we've created because we don't know what else to do with people, right? And, you know, maybe there's some teaching of them that goes on, although if you look at how much knowledge the average high school graduate possesses, you know, it can't have been that much.

No, they're retaining not so much. That's right. That's right. But what you do get a lot of is sort of popularity contests that are, you know, can be sort of, you know, based on nothing, right?

And yet, if you want to do well in it, then you sort of have to devote almost all of your time to this. Right. And so that's the core of the effort. So a nerd, you know, in his telling is someone who is in that environment, but who's already thinking about the issues that matter in the wider world.

Yeah. And he says basically, like, they care more about being smart than being popular. Yeah. So, you know, and he says, like, it's very hard to accept that that is your priority, right?

But it seems like, you know, you would give anything, right? I mean, you know, you would even accept like a lowering of 30 IQ points or something just to not be in the situation that you're in, right? But except if someone actually gave you that choice, would you actually take it? Right.

So, but realize that, you know, there is a wider world of, you know, people who are going to appreciate, you know, sort of things that really matter, right? And, you know, you can try to get to that world sooner, depending on your circumstances. So, you know, so I actually left high school early. I got a GED from New York State when I was 15.

And I went to a place called Clarkson School in Upstate New York, which is a program for high school students who can take courses at Clarkson University and then, you know, apply to college from there. You know, almost every college rejected me. I mean, this was kind of a bizarre trajectory, but Cornell was nice enough to accept me. How old were you?

I was 16 when you started at Cornell. Yeah, yeah, and then I, since I already had one year, then I spent three years at Cornell. And then I went to Berkeley for grad school. Yeah.

So, so I was lucky to be able to leave it a little bit earlier, you know, and, you know, my parents, you know, were supported me. I mean, once it became clear that this was what I wanted to do, right? They, you know, they warned me, well, you know, this is going to make your social life like really, really difficult, which turned out to be 100% true. But, you know, the, I remember telling them at the time, look, you know, my social life already sticks.

So, you know, you know, it's all, I mean, you know, at least I could have, you know, I mean, I was lucky to have some very, very good, you know, few very, very good friends in high school. Some of them are still my wonderful friends, right? But like it was, it was only after, you know, I had been a postdoc for a while that I started finally figuring out how to drive a car, how to ask someone on a date. So, so I sort of did things in a weird order, right?

When you, yeah, when you wrote about, you've written about depression a little bit, yeah, yeah, yeah. Was that during this period or was that? Yeah, it was pretty much during this period. But, you know, but even starting before I had skipped any grades, so, so that's the thing.

I felt like I was already in such a, a constricted environment, right, that like, at least I could be learning some, you know, CS and math, right? You know, at least I could be in an environment that was, you know, where people cared about the intellectual things that I cared about, right? But, but, but, you know, you know, once you get into that environment, right, you are not the only one, right? Eventually, you know, you will be able to, you know, a great thing about the modern world is that people can sort themselves, right?

And you can find a group of friends who will care about the things that you care about. Yeah, so in other words, you know, put yourself out there and try things. Yeah, yeah, cool. All right, Scott, well, thank you so much for coming in.

Yeah, of course, thank you. All right, thanks for listening. So, as always, you can find the transcript and the video at blog.ycommodator.com. And if you have a second, it would be awesome to give us a rating and review wherever you find your podcast.

See you next time.