Latest / Daniel and Kelly’s Extraordinary Universe / What's so exciting about quantum computing? (featuring Scott Aaronson)

Transcript

What's so exciting about quantum computing? (featuring Scott Aaronson) · Daniel and Kelly’s Extraordinary Universe

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