What's so exciting about quantum computing? (featuring Scott Aaronson)

Daniel and Kelly chat with Dr. Scott Aaronson about quantum computing, and try to bust through the most common misconceptions. 

See omnystudio.com/listener for privacy information.

Episode Transcript

Speaker 1 (00:06):
Hey, everyone, Daniel here. You know you hear the word
quantum a lot, like a lot a lot, mostly in
places where it makes no sense. I see it on
advertisements for pest control companies or financial firms or laser
tattoo joints. Okay, lasers actually are kind of quantum, so
maybe that one works. But the point is that the

(00:28):
word is so ubiquitous that it's come to mean very little.
But it does have meaning. It evokes something modern and mysterious,
because in the last one hundred years, physics has discovered
that the world is very mysterious and operates under very
different rules than the ones we are used to the
world that we experience, the one that Aristotle and Copernicus

(00:51):
and Galleo and Newton and even Einstein we're trying to
understand is something of an illusion. When we peel back
that layer of reality and see what's happening underneath, we
discover that the rules of the microscopic universe are very different,
almost alien to our intuition. And so of course people wondered,
almost immediately, hey, what can I do with this? Can

(01:13):
I take advantage of that to make my video games
faster or hack into my school computer and change my
grades because hey, what else is fundamental physics?

Speaker 2 (01:22):
Good form? All right?

Speaker 1 (01:23):
But jokes aside, quantum computing is something you hear a
lot about these days. There's a lot of information and
plenty of misinformation out there. Is it just another marketing
ploy like quantum wasps appers or is it like the
first computing revolution which completely transformed our society, our economy,
and our daily lives. So today on the podcast, we're

(01:45):
excited to be talking to Professor Scott Arenson, one of
the world's top experts in quantum computing and a renowned
communicator who can help us answer the question should we
be excited about quantum computing? Welcome to Daniel and Kelly's
Extraordinary Universe.

Speaker 3 (02:13):
Hello, I'm Kelly Waiter Smith, and I sort of think
I understand how quantum computing works, but I'm never really sure.

Speaker 4 (02:21):
Hi.

Speaker 1 (02:21):
I'm Daniel. I'm a particle physicist, and I simultaneously understand
and don't understand quantum computing.

Speaker 3 (02:27):
That's very appropriate. I think I think I understand it
enough to get that joke, which makes me feel pretty good.

Speaker 1 (02:33):
Oh, you're pretty clever.

Speaker 3 (02:34):
So what is your favorite product that has been pitched
as being quantum that makes you laugh.

Speaker 1 (02:42):
I once sat next to somebody on airplane who told
me she was a quantum messuse. I was really wondering
about how that worked, and I asked her a bunch
of questions and I didn't reveal my expertise, but I
didn't learn anything about quantum mechanics, and that conversation just
something about.

Speaker 5 (02:57):
People, you know, yeah, yep.

Speaker 3 (02:59):
It was it like maybe she's giving you a massage,
maybe she's not, and you don't know until you pay.
That's the thing that reveals if it happened or not.

Speaker 1 (03:07):
No, it was more like spooky action at a distance,
because she massages you without actually touching you. She like
waves her hands nearby, and that somehow, through quantum mechanics
influences your muscles and joints and whatever. So she was
charging a lot of money. Also, people were paying her
big bucks for this effect.

Speaker 3 (03:25):
I would be so grumpy if I paid for a
massage like that, like you really got to get into
my muscles if I'm paying you. But anyway, okay, well
that's amazing. I once heard it was a quantum self
help talk, and the whole time I just couldn't, could
not understand how quantum, like how thinking about it from
a quantum way was helpful at all, And it just

(03:47):
left me completely baffled.

Speaker 1 (03:48):
I think people just latching onto the idea that the
world is fundamentally different from the world we thought it was,
that it works in a different way, it follows different rules,
and that feels a little bit like magic. You can
sort of grab onto that and smear your business with
a little bit of that sparkly quantum physics stuff, And
this feels like maybe you can do something which seemed impossible.

Speaker 3 (04:11):
When I think quantum is particularly likely to get used
in that way because it's confusing. I mean, maybe it's
not confusing to the people who study it, but for
like lay people, it just sounds so unclear. And I
think that you can feel like you understand it and yeah,
but definitely feel like using the word quantum makes you
sound smart and then you just run with it. And
so I'm excited to see what our audience thinks quantum

(04:35):
computing is all about, because I until I married Zach,
who likes giving me literally three hour lectures on car
rides about what quantum computing is. Well, I'm driving and
can't escape. I didn't feel like I knew. So let's
see what does the you know, what does the general public,
in particular our audience think quantum computing is.

Speaker 1 (04:56):
So I reached out to our listeners and I asked
them what's different about it quantum computer. Here's what listeners
had to say.

Speaker 6 (05:04):
Quantum computers do multiple calculations at once, and each time
you add a bit it goes up by exponential numbers faster.

Speaker 7 (05:17):
But especially they do not overheat.

Speaker 1 (05:22):
I don't know anything about quantum computers.

Speaker 8 (05:24):
You can actually get an answer faster because you can
determine the probabilities rather than brute forcing it.

Speaker 9 (05:31):
Quantum computer works with superpositions instead of ones and zeros.
That gives it advantages for some calculations, but makes it
worse for other calculations.

Speaker 8 (05:43):
But quantum computer is like having five hundred and eighty
thousand people all typing one word of the book, all
at the same time, but in order.

Speaker 4 (05:54):
A quantum computer is different because you'll never show with
it to turn it on and off again or off
and on again.

Speaker 1 (06:00):
A quantum particle can be in.

Speaker 2 (06:04):
A superposition on off or on and off at the
same time.

Speaker 3 (06:10):
A quantum computer can use three bits I think spin up,
spin down, and I think something in between.

Speaker 10 (06:18):
A quantum computer runs on quantum mechanics, which makes it
capable of calculating the probabilities in a situation where randomness
is involved.

Speaker 8 (06:33):
Does a quantum computer not use binary code zeros and
ones so there can be more options, which.

Speaker 9 (06:41):
Makes it more powerful.

Speaker 2 (06:43):
Possibly quantum computers use q bits that are super cooled
and have many many states rather than the binary transistor
logic that only has off and on.

Speaker 5 (06:56):
Quantum computing is all about probabilities.

Speaker 4 (07:00):
With a quantum computer, you can't tell if it's on
or off until you hope the box it came in.

Speaker 11 (07:05):
A quantum computer uses quantum fluctuation for its processor and
explores every possible answer instantaneously.

Speaker 4 (07:17):
How this is useful for our computation is still beyond
my understanding.

Speaker 11 (07:21):
Computer uses quantum technology to search all the random variables
that possibly happen and come up a handurd solution.

Speaker 12 (07:29):
I think quantum computers process really small numbers. Do they
do computations on extremely tiny numbers? I'm not sure what
is different about a quantum computer that.

Speaker 10 (07:42):
Makes use of superposition of states to give nearly infinite possibilities.

Speaker 11 (07:48):
The size of the processor or the flip flops. So
now we're down on a quantum level versus the smallest
transistors we have at this moment.

Speaker 5 (07:57):
Other them its fast are really about nothing.

Speaker 7 (08:01):
What's different about a quantum computer. I don't really know
much about how quantum computers work, but there's something fundamentally
different about how the bits, essentially we're being.

Speaker 8 (08:12):
On or off.

Speaker 7 (08:13):
And that's not something I know the details of.

Speaker 3 (08:16):
I'm not surprised that our audience had detailed and insightful
responses to this question.

Speaker 4 (08:22):
That is awesome, But you know.

Speaker 3 (08:24):
You and I decided this is a complicated question, and well,
I'm sure Daniel could have explained it on his own.
We thought, you know, it might be a good idea
to bring in Scott Aronson, who's an expert on quantum computing,
has been working on it for a really long time,
and so we're bringing you a conversation that's a collaboration
between Daniel and Scott Aronson. So, Daniel, where do we start?

Speaker 1 (08:45):
So I think the place to start with understanding quantum
computers is first with the word computer, Like what do
we mean when we say computer? And this isn't just
like philosophical rabbit hole. I think it's important to think
about what a can is, what a computer does, not
just the kinds of computers that we have, but other
kinds of computers, what possible computers there are, because then

(09:09):
we can compare the different kinds of computers, we can
understand what they have in common and what they don't
have in common. Because computers are not just something that
sits on your desk or the thing inside your phone
that makes it go. A computer basically is something that computes.
It's something that gives you an answer to a question,
you know, and that can be something very simple, like

(09:30):
you can have a baseball and you throw the baseball.
That gives you the answer to what happens when you
throw a baseball, and that can be kind of a
complicated calculation. You know, you have to take into account
gravity and air resistance and the spin of the Earth
and all this kind of stuff, and the baseball does
that for you. It computes the answer to that question.
And that's not a very exciting computer because that's basically

(09:50):
all it can do other than let you play baseball.
That one just answers one question. In general, we're interested
in computers that can do lots of different kinds of calculations,
and one kind of computer is you. You know, back
in the middle of last century, what they called a
computer was a person like at NASA who sat at
a table doing calculations pencil and paper to figure out

(10:14):
how are we going to shoot this rocket and what
angle do we need to go at, because that was
the best way to do those calculations. And humans pretty
good at doing lots of different calculations. So a computer
can include the thing on your desk, the thing in
your phone, a baseball, even a person, right, and all
these computers, some of them are good at different kinds
of calculations, Like the ball is excellent at calculating where

(10:37):
the ball is going to go, but terrible at everything else.
A human is pretty good at some kinds of things
and not that great at other kinds of things. Like
a human is really good at doing things like spotting
a tiger in the grass. Your brain is really efficient
at noticing things that look like predators, not so great
at other things like adding up all the numbers between

(10:58):
one and a trillion. I mean, maybe you can find
some mathematical shortcut, but if you have to actually add
them up, it would take you a long time. It's
not the kind of thing your brain is efficient at now.
The kind of computer where, of course are interested in.
It's not baseballs or tigers. It's the kind that are programmable,
the kind that can basically do any kind of calculation.
And this is something that's kind of incredible that we

(11:20):
can even do. We have a question we want answer,
it's some calculation we want done, and we build a
computer which is like a machine, build a physical objects
that we can manipulate in a way to do our calculation.
That's the amazing thing about programmable computers that when you
build it, you don't have to know what kind of
calculations you want it to do. You can build it

(11:40):
in such a way that it can do almost any
kind of calculation. That's sort of amazing. We're taking a
real world problem and then we're building a device that
can calculate the answer as long as we can represent
that real world problem somehow in the language of that computer.
So these are deep issues and fascinating questions. To help
us understand what is computing and how quantum computing is

(12:03):
different from regular normal computing, we talk to Professor Scott Arenson.
He he's a professor of theoretical computer science at the
University of Texas at Austin. He's worked with open AI
on the theoretical foundations of AI safety. He writes a
wonderful blog about quantum computing called stettl Optimized, and he's
maybe most famously the author of quantum computing since democratis.

(12:25):
And he's a lot of fun to talk to. So
we're very glad to have Scott on the show. And
our first question for Scott, who's a professor of theoretical
computer science, is what is theoretical computer science anyway?

Speaker 4 (12:38):
So it's a field that's usually considered to have started
with Alan Touring in the nineteen thirties, who came up
with a theoretical model of what a computer could be,
which was called the touring machine.

Speaker 1 (12:50):
So when Scott is talking about a touring machine, he's
not talking about any kind of computer anybody's ever actually built.
This is like the computer science equivalent of a thought experiment, right,
It's a thought computer. It's something Alan Turing came up with.
It's the simplest kind of computer he could imagine, and
it's a computer that, again you would never build. But
it's very simple. Imagine a computer that has a tape

(13:13):
on which there are written numbers zeros and ones, for example,
and you can read the tape. It can move the
tape forwards and backwards. They can also write to the tape,
so you can do all the basic stuff that we
think computers can do. Right. It can read in information,
it can do a calculation and decide what it's going
to do next. It can write onto the tape, so
it can modify that. It can store information. And Turing

(13:35):
did something really cool, which is that he showed that
a Turing machine is very simple, basic kind of thought.
Computer can do any kind of calculation that any computer
could do. So if it was doable on a computer,
you could do it on a Turing machine. That doesn't
mean a Turing machine is the best way to do
it or the right way to do it, but because
the Turning machine is so simple, it let you think

(13:55):
about the kind of things computers could do.

Speaker 2 (13:57):
Well.

Speaker 1 (13:57):
You could say, if you can do it on a
Turing computer, then you could do it on any computer.
And it's easier to prove theorems and think about stuff
on a Touring computer. And again, a Turing machine doesn't
lend me you to thinking about the kinds of computer
that we've been building. It can explore the kind of
things any computer can do.

Speaker 4 (14:13):
When Touring used the word computer in the nineteen thirties,
you know, that was what it meant people, usually women,
who were hired to do computation. And he came up
with his model of the Touring machine by trying to
idealize what such a person would be doing. You know
that they'd be reading symbols on a piece of paper,
maybe you know, crossing them off, replacing them with new symbols,

(14:36):
you know, moving back and forth on the paper. They
would always be doing so according to some rule that
they knew or had been taught. There is nothing in
the concept that is tied to you know, it has
to be built out of transistors that are etched onto
wafers of silicon.

Speaker 2 (14:51):
Right.

Speaker 4 (14:52):
That happens to be the way that we do it
now because it worked so spectacularly. Well, okay, but you
know a computer could in principle be made out of
billiard balls, right, It could be made out of jets
of water.

Speaker 2 (15:05):
Right.

Speaker 5 (15:05):
You know, these would maybe not be very reliable.

Speaker 1 (15:08):
Methods, and also doesn't have to be programmable and infinitely powerful. Right,
anytime I build an experiment, I'm building a computer.

Speaker 4 (15:16):
Until very recently, you know, there was use in analog computers, right,
and people just building analog systems to simulate some physical process.
You know, at some point digital computing became so good
that it eliminated the use cases for that.

Speaker 1 (15:32):
So it's great that the kind of digital computers we've
been building can basically solve any problem. I mean, there
are cobbyists to that, there are things turn computers can't do.
But the crucial thing for understanding quantum computing and computing
more generally is that some problems are hard, and some
problems are easy. Some problems you can do quickly, and
some problems you can do very very slowly. And different

(15:54):
kind of computers are going to be good at different
kinds of things, so the same with it. Like you
as a person, you are a computer. You are fast
or slow at particular problems. Our style of computers, what
we call classical digital computers. These are good at some
kinds of things and slow at other kinds of things.
It's a feature of the kind of computers we've long developed, which,

(16:16):
of course you know isn't the only way to do it.
That's where we're going. But the origins of the digital
computer that we've been using go all the way back
to the middle of last century with John von Neuman.

Speaker 4 (16:27):
John von Neuman, who built some of the first digital computers,
was you know, directly inspired by tourings insights, in particular
the idea that you didn't want to build a different
machine for each possible function. You wanted to build one
universal machine and then have it simulate any other machine by.

Speaker 5 (16:46):
Giving it an appropriate program.

Speaker 4 (16:48):
This is, you know, an idea that today is so
obvious that, you know, it's hard to convince my students
that it was ever non obvious. So today what we
do in theoretical computer science is often about trying to
understand what problems can be solved efficiently.

Speaker 1 (17:04):
All right, And so when Scott talks about computers being efficient,
he's thinking about whether they're good at this kind of problem?
Can they do it quickly? As a problem gets bigger
and bigger, do they become unbearably slow at solving it?
Like you can add up the numbers between one and
five pretty quickly, you can add up the number between
one and one hundred, little less quickly. If it gets

(17:25):
to one in a trillion, it's hopeless, right, And so
for digital computers there are some problems that can be
solved in principle but would take a very very long time,
and the kind of computer we've been building. An example
of that problem is checking to see if a number
is prime. Like you can tell that eleven is prime
because you can't think of any two numbers that multiply

(17:46):
themselves together to give you eleven because it is prime.
If I give you an arbitrary number seven, four hundred
and seventeen, how do you know whether it's prime. Well,
a computer can do this by, for example, checking all
the numbers that go into it. That's just brute forcing it.
There are some more clever algorithms we'll hear about later,
but essentially it's very slow at checking prime numbers. So

(18:06):
computers can do a lot of things, and the way
we've usually built computers are good at some things and
slow at other things. So we ask Scott, who thinks
about this a lot, what kind of things our normal
computers are good at and our normal computers are bad at?

Speaker 2 (18:22):
Sure?

Speaker 4 (18:23):
So simulating physics, you know, which you mentioned, is a
great example of you know, something that computers have been
used for since the very beginning, right and in some sense,
you know, the entire program of physics since Galileo and
Newton has been to you know, understand nature. Well. It
off that we can put the initial conditions into a

(18:43):
computer and just have a computer tell us what is
going to happen.

Speaker 5 (18:48):
Simulating a differential equation, you know.

Speaker 4 (18:50):
In order to model fluids or gravitational dynamics, celestial mechanics.
These are our famous examples of things that you know,
comput uters.

Speaker 5 (19:00):
Are very good at. There are issues here, you know,
that have to do with discritization.

Speaker 4 (19:05):
Nature is traditionally modeled in physics as using a continuum
of numbers, and computers in the touring sense can only
deal with discrete quantities with bits with ones and zeros.
So we need some way to deal with that, right,
Typically we take continuous quantities and we truncate them, we
represent them only to a finite precision, and then you know,

(19:27):
we have to understand how.

Speaker 5 (19:29):
Much error that's going to cause and so forth.

Speaker 4 (19:32):
But you know, in terms of what computers can do efficiently,
you know, I think the classic examples that you know,
we would teach in computer science are going to be
things like, Okay, you know all of the arithmetic operations
that we learn in school, right, adding to integers, you know, multiplying,
dividing given Also, you know the thing that Google Maps

(19:52):
does for us, right, find the shortest route between two
given cities, you know, or between two addresses in the
distance between each address and the immediately neighboring ones.

Speaker 5 (20:04):
Right, it's finding the shortest path in a graph.

Speaker 4 (20:06):
Okay. Now, there are a bunch of things that turn
out to have clever efficient algorithms, even though it is
sort of totally not obvious a priori that they would.
For example, I give you a bunch of students, you know,
I tell you who is willing to be roommates with whom? Okay,
and now I ask you pair off as many willing

(20:29):
roommates as you can. Right. This is called the maximum
matching problem. Find you know, maximum number of pairs of
people who are willing to room with each other A priori.
That seems like that might require an exponential search, right,
It might require considering an astronomical number of possibilities.

Speaker 5 (20:48):
But it was discovered in the nineteen sixties that it doesn't.

Speaker 4 (20:51):
There is an efficient way to solve that, That is,
there's a way to solve it that scales only like
the cube of the number of potential roommates something like that,
rather than exponentially.

Speaker 5 (21:04):
Another great example would be linear.

Speaker 4 (21:06):
Programming, right, one of the most important problems in industrial
you know, operations research, things like that, where you're given
a bunch of linear constraints on some variables like this
one plus this one can be at most ten, this
one minus this one has to be at least eight,
and so forth, and you're looking for a solution that

(21:26):
satisfies all of those linear constraints. Okay, that also has
an efficient solution primality. Right, I give you five thousand
digit number, and I ask you is it prime or composite?

Speaker 2 (21:39):
Right?

Speaker 5 (21:39):
Well, you know you can try some simple things.

Speaker 4 (21:42):
You know, if it ends in an even number, or
a zero or a five, right, then it's composite. But
you know you can check if three, if seven, if eleven,
go into it, right, But more generally, right, this is
a famous problem in math. It's even extremely important in
cryptoc Modern cryptography sort of uses gigantic prime numbers as

(22:05):
one of its central ingredients.

Speaker 5 (22:07):
Okay, Now it turns out that there is.

Speaker 4 (22:10):
An efficient algorithm that tells you whether a huge number
is prime or composite.

Speaker 5 (22:16):
Okay, it was discovered in the nineteen seventies.

Speaker 4 (22:18):
There are probabilistic methods, and in two thousand and two
even a deterministic method was discovered.

Speaker 5 (22:25):
Okay, you're very very non obvious.

Speaker 4 (22:27):
Now, Crucially, these methods only tell you if the number
is prime or composite. If it's composite, they don't tell
you what the prime factors.

Speaker 1 (22:36):
Are, all right. So those are some great examples of
what classical computers are pretty good at. What kind of
things are they slow at? Again, a great example is
prime factors. And this is really important because it turns
out that it's useful to a lot of people that
computers are slow at this. Like, if you know that
computers can't crack this puzzle quickly, you can use it

(22:58):
as a way to protect your information. The whole field
of cryptography, of building codes and protecting information relies on
some things being easy and some things being hard for
computers to do.

Speaker 4 (23:11):
The belief that finding the prime factors is hard is
actually also central to modern cryptography. So modern cryptography, you
have to be able to generate huge prime numbers quickly
multiply them together quickly, which we know how to do
all of that. That's how we generate the cryptographic keys

(23:32):
called the public keys, that people can use to send
us encrypted messages. But then the way that it works
is that in order to decrypt the message, we.

Speaker 5 (23:41):
Think, you need to know the prime factors.

Speaker 4 (23:44):
If anyone had a fast way to find the prime
factors of a gigantic composite number, most of the cryptography
that protects the Internet would be broken.

Speaker 5 (23:53):
Okay, so it is crucial that.

Speaker 4 (23:54):
You know, after half a century of effort, at least
the best publicly known methods for factoring numbers.

Speaker 8 (24:02):
You know.

Speaker 4 (24:02):
Of course, if the NSA you know knew something better,
then you know, I would have no reason to know that.
But the best publicly known methods you know use an
amount of time that scales exponentially with the number of digits,
or more precisely, exponentially with the cube root of the
number of digits.

Speaker 1 (24:20):
So when Scott talks about scaling with the number of digits,
what he's talking about is how long it will take
the computer to solve the puzzle, depending on the length
of the password. Problems that get much harder very quickly
when you add digits to your password. Those are good
for cryptography because it makes it easy to make the
problem impossible even if computers get faster. Like if computers

(24:44):
suddenly tomorrow get twice as faster next year they're five
times as fast. You don't want people to be able
to crack your passwords. The good thing about the prime
number puzzle is you can just add a couple more
digits to our keys to our passwords, and now the
puzzle is impossible. Again, this problem is easy to make
much harder because it gets exponentially harder as it gets bigger.

(25:05):
So it's easy to keep making the problem harder faster
than computers are getting better at the problem. That's the
key to these exponential problems. And there are a bunch
of problems like this that are very hard to solve
for our classical digital computers.

Speaker 4 (25:19):
So factoring is a famous example of a problem that
might be exponentially hard for all we know. Okay, but
there's maybe an even more famous class of problems that
are believed to be exponentially hard. And this includes, like
most of the problems in combinatorial search and optimization that

(25:41):
people care about in practice, and so examples would be,
I give you the distances between every city and every other.
I ask you to find the shortest path that visits
every city. That's the famous traveling salesman problem traveling salesperson.

Speaker 5 (25:57):
Call it today.

Speaker 4 (25:58):
Or I give you the mess of a bunch of suitcases.
I asked, can they all fit in the trunk of
your car? That's a problem with which many of us
have experience.

Speaker 1 (26:07):
The answer is always yes, you have to try.

Speaker 4 (26:10):
Arranging them in a different way. Or you know, I
give you a jigsaw puzzle, you know, can you solve it?
To make it hard, let's imagine a jigsaw puzzle with
no picture on it, okay, or a sudoku.

Speaker 1 (26:21):
The answer is always you can solve. It's just a
question of how many curse words are going to be the.

Speaker 4 (26:27):
Answer yes, yes, And if it's thousands of pieces, then
are we talking about more curse words than there are
atoms in the observable universe.

Speaker 1 (26:52):
So we've reminded ourselves what it digital computer can do.
Some things it can do really well and very quickly,
and other things it does more slowly, and as a
problem to bigger, becomes unbearably slow. But the topic of
today's episode, of course, is other kinds of computers. What
if you decided to build a computer using something other
than zeros and ones. Remember, computer is just some arrangement

(27:13):
of a physical system that lets you do a calculation.
Doesn't have to be based on like bits that flip
between zero and one and half precise values. What if
you found something in the universe that operated differently, that
wasn't so crisp, right, that operated under a different set
of rules that you could then exploit to do different
kinds of calculations, or to have some calculations be faster

(27:36):
or slower. That would be awesome because it would complement
our current computer system.

Speaker 2 (27:40):
Right.

Speaker 1 (27:40):
We already know that this is possible in principle. You
know my example of a baseball that can do a
very precise calculation that includes all sorts of effect wind
resistance and the tug of Jupiter and all sorts of
stuff that would be very laborious for a traditional computer
to do. It can do it very very quickly, in
like the time you throw a baseball. But the question,
and of course, is can you make a programmable computer

(28:03):
not a specialized one off thing like a baseball, A
programmable computer that is good at the kinds of problems
that classical computers are slow at. And that's where quantum
mechanics comes in, because quantum mechanics does operate under different rules,
and we can exploit those rules to build a different
kind of computer. The crucial things to understand about quantum

(28:24):
mechanics in just a few minutes are that rather than
having to have definitive states like this bit is zero
or this bit is one, quantum bits from what we
call cubits, can be in a superposition of states. A
superposition just means it has a chance to be in
more than one state, So rather than being a zero
or a one, it can be like, well, this one
has a thirty percent chance of being a zero and

(28:46):
a seventy percent chance of being a one. That one
over there has a ninety percent chance of being a
zero and a ten percent chance of being a one.
So a superposition just means two things laid on top
of each other doesn't have to be zero or one.
It can be some probability of zero or one. And
the fact that it can maintain these superpositions lets it
do something that classical bits can't do, which is interfere

(29:10):
If you've heard of the double slit experiment, this is
like a beam of photons that go through two slits,
and maybe the photons come from one slit, and maybe
the photons go through another slit, and the possibility that
they've gone through both slits interferes with each other, creating
this interference pattern on the final screen. And it's the
fact that the photons can be in a superposition of

(29:31):
those states, that they can be maybe through slit one
and maybe through slit two. Those possibilities are the things
doing the interfering. So that interference is very important part
of what quantum systems can do and what classical systems
cannot do because the classical system like if you throw
a base ball through a double slit experiment, it either
went through the left one or through the right one.

(29:51):
There's no superposition and there's no interference. Now these are
quantum systems that can do this weird thing of having
multiple possibilities at the same time. But then when quantum
systems interact with classical systems, when you ask the quantum system, hey,
what is the value of this bit? Because eventually you
want to know the answer from your computer, right you
have to make a measurement, you have to do something,

(30:12):
you interact with it. That's when the universe picks one
of the options. So there's a spread of possible outcomes
for any quantum interaction. There's a superposition that describes the
various possibilities, and measurement is the thing that collapses it
that makes the universe pick one of those outcomes. So
this is the way the universe works in the microscopic scale,
which is weird and amazing and very different from our

(30:34):
experience and the macroscopic scale, and it opens the door
to doing different kinds of computation. Remember a computer, it's
just a physical system we've arranged to calculate something we're
interested in. We take advantage of the way that physical
system works to represent some kind of calculation and hope
that that computer that we've built is good at that
kind of calculation. And because quantum computers work with these

(30:56):
very different rules, it means they can do different kinds
of calculation, and they can do different calculations quickly, and
they have different strengths and weaknesses than classical computers. So
here's Scott telling us more about that.

Speaker 4 (31:08):
Let's now imagine a computer that operates by these principles
of quantum mechanics, we'll call it a quantum computer, so.

Speaker 5 (31:15):
A classical computer.

Speaker 4 (31:17):
Typically, for simplicity, we like to imagine it as having
a state that's built up out of bits out of
you know, zeros are ones, right, and if there's one
thousand bits, then there's two to one thousand power possible
configurations of that computer's memory, okay. But now with a
quantum computer, there's going to be vastly more configurations than that, okay,

(31:39):
because if I have even one quantum bit or you know,
what we call a cube bit, right, then it can
have some amplitude for being zero and some amplitude for
being one at the same time. So it can be
in what we call a superposition of the zero state
and the one state, you know, at.

Speaker 5 (31:57):
Least before we look at it.

Speaker 4 (32:00):
Once we make a measurement, then we'll force it to
snap to either zero or one, and then it will
probabilistically collapse to one or the other.

Speaker 5 (32:08):
But before we look it can be in this superposition state.
And now if I have let's.

Speaker 4 (32:13):
Say three cubits, okay, then it's not enough to give
amplitudes for each cubit separately from the others. Right, The
rules of quantum mechanics are unequivocal. I have to give
an amplitude that the three bits are zero zero zero.
I have to give an amplitude that there are zero
zero one. I have to give an amplitude that they're
zero one zero, you know, and so on, so I

(32:35):
have to give eight amplitudes.

Speaker 1 (32:37):
So it's sort of more information dense because the amount
of information grows exponentially. But why does that allow us
to do different kinds of computation? Why does that allow
us to solve different kinds of problems efficiently than classical computers.

Speaker 4 (32:50):
Yes, I mean, of course that's the point, and that's
where this is ultimately headed. But we have to be
very careful about it, because if you take these three
cubits and you measure.

Speaker 5 (32:59):
Them, don't see those eight numbers.

Speaker 4 (33:01):
Now, the cubits collapse and you just see three bits each,
you know, with some probability. Right now, if I have
one thousand cubits, right, then that's two to the thousand
power amplitudes to keep track of their state, right, which is,
you know, more than you could write down in the
whole observable universe. Okay, so there seems to be that

(33:22):
this exponentiality, you know, beneath the surface. And this is
certainly a problem if you wanted to simulate quantum mechanics
on a conventional computer. Okay. And actually chemists and physicists
have known that for generations, right. They're like, once they
started trying to apply the Schrodinger equation to you know,
calculate the behavior of even quite simple molecules, right, they

(33:46):
have to write down a wave function that has like
more and more dimensions, you know, the more electrons you add, right,
and this you very quickly get the problems that would
tax you know, the fastest supercomputers of today. You know,
let alone of the nineteen fifties when they started doing this, right,
And so you know, chemists and physicists invented all sorts

(34:07):
of hacks and approximation methods for dealing with these exponentially
large wave functions. Okay, But it was not until the
early eighties that a few physicists like Feineman and Deutsch,
you know, started saying, well, if nature is giving us
this computational lemon, you know, it is making it so

(34:28):
hard for us to simulate atomic physics on computers.

Speaker 5 (34:32):
Then why don't we make lemonade? That is, you know,
why don't we build.

Speaker 4 (34:35):
A computer that itself would exploit quantum mechanical principles, you
know what they called a quantum computer.

Speaker 5 (34:42):
And then what would that be good for?

Speaker 4 (34:44):
Well, if nothing else, it would be good for simulating
quantum mechanics itself, right, And that was sort of the
original application that they had in mind, And forty years later,
I think that that's still, honestly, you know, the most
important application economic that we know. A bet that's the
truth of the matter, right.

Speaker 5 (35:03):
Anyone who is.

Speaker 4 (35:04):
Trying to design better batteries or better solar cells, or
high temperature superconductors, or better chemical reactions for making fertilizer
or better drugs that you know buind a receptor in
a certain way, right, they're basically dealing with a many
body quantum mechanics problem. And these problems can be incredibly

(35:25):
hard for classical computers for reasons that you know, ultimately
come from the exponentiality of the wave function, right, and
a quantum computer could potentially help with any of that.

Speaker 1 (35:39):
Scott is pointing out a really crucial feature of quantum systems.
Not only do they have these cubits that can be
in superposition, but the cubits can be entangled with each other,
which means the value in one bit can be linked
to the value in another bit, and that's what makes
them much more information dense than classical computers. It's like,
instead of having three independent axes where you can just

(36:01):
pick a number along the access, you have three pieces
of information. You semble those into a three dimensional space,
so now you have a three D volume of information.
So they're capable of storing information much more densely because
of these connections between the bits, which creates this information space,
and this makes it very hard for classical computers to

(36:21):
simulate a quantum system. It takes a lot of normal bits,
classical zero one bits to calculate what a quantum system
will do or what a cbe bit will do. So
the first thing that quantum computers could be good for
is to just describe quantum systems. It's kind of a
natural application. You know, the quantum computer follows similar rules
to the quantum system, and so it's natural to describe

(36:43):
it in that way, the same way like the baseball
follows the rules of the baseball. So it's a good
way to calculate what a baseball will do. But of
course we wonder, like, is that all quantum computers can
do simulate some nerdy quantum experiment or are quantum computers
also good at doing other things? Here's Scott telling us
all about it.

Speaker 5 (37:03):
That was the original promise.

Speaker 4 (37:05):
But you know, as long as that was sort of
the only promise, I think, you know, this remained very
much a niche interest of some weird physicists pursuing this idea.

Speaker 5 (37:16):
And you know, the eighties, the early nineties.

Speaker 4 (37:19):
Now, the big discovery that put quantum computing on the
map for you know, most of the rest of the
world was that a quantum computer can sometimes also help
to get exponential speed ups, even for problems that have
nothing to do with quantum mechanics, at least for a
few very specific such problems.

Speaker 1 (37:40):
Can we predict these kinds of problems in advance?

Speaker 4 (37:43):
Welcome to what my colleagues and I have been trying
to do for the last thirty years.

Speaker 5 (37:46):
Yeah, I mean, for the whole history of this field.

Speaker 4 (37:49):
We are trying to figure out what is the border
between what is efficiently solvable by a quantum computer and
what isn't and we know a lot about it, but
you know, there is.

Speaker 5 (37:58):
A great deal that we still don't know.

Speaker 4 (38:00):
The big discovery that sort of started quantum computing as
a field, I would say, you know, as opposed to
just an idea, came in nineteen ninety four, Okay, and
that was when Peter Shore, who was a mathematician then
at Belle Ebs, discovered that there is a fast quantum
algorithm for factoring numbers.

Speaker 5 (38:21):
Okay, So he discovered that the factoring.

Speaker 4 (38:23):
Problem, the problem of factoring a huge composite number into primes,
and some various closely related problems of central importance in
modern cryptography are all solvable on a quantum computer using
a number of steps that grows like the size of

(38:43):
the number. You know that you're trying to factor squared maybe,
but not exponentially with the size.

Speaker 2 (38:49):
Of the number.

Speaker 1 (38:50):
So this is a big deal because, as you're saying,
you know, we can use billiard balls to calculate how
billiard balls move, and we can use quantum systems to
simulate quantum systems. But now we're using a quotum system
to describe something that's fundamentally not quantum. So it gives
us a clue that like, maybe we can open up
a whole new category of problems.

Speaker 4 (39:07):
It is totally not obvious a priori that a quantum
computer should help you for factoring numbers.

Speaker 5 (39:13):
You know, what does that have to do with quantum mechanics?

Speaker 4 (39:15):
Right? And of course this problem is hugely important because,
for better or worse, we base the whole security of
the modern Internet on the belief that factoring is hard. Okay,
What Sure was saying is that if and when someone
builds a large quantum computer, a scalable quantum computer with
you know, thousands or millions of cubits, then that is

(39:38):
no longer true. Okay, then you can break all of
the encryption that we use to protect the Internet.

Speaker 5 (39:44):
So a bunch of things happened, you know after that.

Speaker 4 (39:47):
You know, one was people you know kind of like
with the story of Rumpelstiltskin, Right, It's like, if you
can spin this much straw into gold, and then why
not more? And people said, well, maybe all of the exponential,
really hard problems that we're you know, dealing with, maybe
quantum computers can solve all of them.

Speaker 1 (40:05):
Is there any way to intuitively understand the idea here?
Like what it is about quantum computing that makes this
problem easier to do.

Speaker 4 (40:13):
I teach a whole undergrad course where you know, at
the end of it, I hope that people will have
the intuition for these things.

Speaker 8 (40:19):
Right.

Speaker 4 (40:19):
But like, if there were a one sentence way to
say the intuition, then you wouldn't have needed Shore and
Grover to discover these things, right, you know, it could
have been obvious from the beginning.

Speaker 5 (40:29):
Right. But let me say this, right, so, you know.

Speaker 4 (40:32):
What almost every popular article about quantum computing wants to
say is something that sounds really appealing and is totally wrong. Okay.
In fact, Zach Kelly's husband and I made a whole
cartoon about exactly this eight years ago.

Speaker 1 (40:47):
So throw cold water on some clickbait for us. What's
wrong about quantum computing descriptions?

Speaker 4 (40:52):
What almost every popular writer has wanted to say is
that a quantum computer just tries every possible solution in parallel.
You know, it tries each one in a different parallel universe,
or you know, all of them in superposition or whatever,
and then somehow magically the best one gets picked. Right.
If that were how it worked, then quantum computers would solve,

(41:14):
not only factoring, but also np complete problems. Right, they
would break not only the cryptosystems that currently protect the Internet,
but they would break all other possible cryptosystems you know
that are based on hard problems. Okay, but that is
not what we believe that quantum computers can do, right.
We believe that they're more limited than that. So the

(41:35):
question is why are they more limited? Okay?

Speaker 5 (41:37):
And it all has to do with the restrictions of measurement.

Speaker 2 (41:41):
Right.

Speaker 4 (41:42):
It's true that with a quantum computer you can create
an equal superposition over all the possible solutions to your
hard problem. That's even an easy thing to do if
you have a quantum computer, right, like create a superposition
or each of these two to the thousand and power
possible solutions has some amplitude. You know, that's just like

(42:04):
very simple, it's done, Okay. The trouble is for a
computer to be useful, at some point you have to
look at it. You have to measure, you have to
get an output. You know, you have to read something out. Okay.
And if you took an equal superposition over all the
answers and you just measured it, not having done anything else,
then the rules of quantum mechanics are very clear on

(42:26):
what you're going to see. It's a completely random answer.
And if you had just wanted a completely random answer,
then you could have just flipped a coin a bunch
of times, or just you know, use a random number
generator that's inside your classical computer. Right, You didn't need
to spend all these billions of dollars to build.

Speaker 5 (42:42):
A quantum computer.

Speaker 4 (42:43):
Right, So the only hope of getting an advantage from
a quantum computer is to exploit the way that these amplitudes,
you know, being complex numbers, work differently from conventional probabilities. Okay,
And the central thing that amplitudes can do that probabilities

(43:04):
cannot do is that they can interfere with each other.
They can cancel each other out. And so with a
quantum computer in particular, the idea with every algorithm for
a quantum computer is that you are trying to choreograph
things in such a way that for each wrong answer,
because each answer that you don't want to see, some

(43:25):
contributions to its amplitude are positive and others are negative,
so they're canceling each other out.

Speaker 5 (43:32):
Whereas for the.

Speaker 4 (43:32):
Right answer, the answer you do one you want all
the contributions to its amplitude to reinforce each other, okay,
to add up constructively. If you can arrange that, then
when you look, you're going to see the right answer
with a large probability.

Speaker 5 (43:49):
That's the name of the game.

Speaker 4 (43:50):
Now. The hard part is you have to do all
of that even though you yourself don't know in advance
which answer is the right one.

Speaker 5 (43:58):
You know, if you already knew, what would be the point?

Speaker 4 (44:00):
Right, And you have to do all of this faster
than even the cleverest classical algorithm could do the same thing.

Speaker 5 (44:08):
Otherwise what would be the point?

Speaker 4 (44:09):
Okay, so nature is giving us this really really bizarre
hammer and a priori.

Speaker 5 (44:16):
It's not obvious whether.

Speaker 4 (44:17):
There's any nails that that hammer can hit, you know,
other than just the obvious one of simulating quantum physics itself, right,
And it really it took more than a decade for
people to discover those nails and factoring the problem that
Peter Shore designed his algorithm for. That was the first
big example, and some people hope that that would be

(44:37):
followed by a flood of other examples, and you know, unfortunately,
you know, thirty years later, factoring remains one of our
pre eminent examples.

Speaker 1 (44:47):
So I have a crazy question for you. You're telling
me that quantum computers work by maintaining all of these
different amplitudes and the superpositions, but that we don't have
access to all the superpositions because we have to take
the measurement. So we have to play clever games with
interference so that we can use this system to do
something useful. But we don't have access to the superpositions

(45:08):
because of the measurement, only because we are classical objects
and classical interactions with quantum systems collapse the measurement. What
if we were tiny, we were microscopic, we were quantum,
could then we use quantum systems in a way that
didn't collapse all their wave functions and access all of
those amplitudes.

Speaker 4 (45:28):
So I hate to break it to you, us being
microscopic wouldn't help. Right, You can be as tiny as
you like, But if you interact with a quantum system
in a way that carries away the information about you know,
which branch of the superposition we're we in, then that
has exactly the same effect of collapsing the state. Right,
So it's not our physical bigness that's the issue. It's that,

(45:50):
you know, sort of we want an answer in our universe, right,
what we can say, You know, there are people who
are very gung ho about the interpretation of quantum mechanics,
where they would say, collapse is not real, right, collapse
is just a figment of our limited perspective. Right. Really,
what's going on is it's just the Schrodinger equation all

(46:12):
the way. And so they would say that whenever you know,
you measure a quantum computer that's in a superposition, Actually
the whole universe then splits into all these different branches,
and each branch is equally real.

Speaker 5 (46:25):
We have an experience of one of them where.

Speaker 4 (46:28):
We perceive some answer. So a many worlder, that's what
these people are called, right, a Mani worlder would say
that there is some branch of the universal wave function
in which you do get the right answer right, in
which you try all the possible answers in superposition. You know,
they would say, well, there's some branch where you get

(46:49):
lucky and you measure the right answer, right. And they love,
you know, all sorts of crazy thought experiments, like you know,
quantum suicide, right, Like why not.

Speaker 5 (46:58):
Use a quantum random number?

Speaker 4 (47:00):
Generator to pick a lottery ticket and then just decide
to kill yourself if it doesn't end up being winning,
and then in all the branches of the wave function
where you still.

Speaker 5 (47:10):
Exist, you know you'll have won the lottery.

Speaker 4 (47:13):
Now, I do not recommend that any listeners try that, Okay.
I don't think there's any principle of reason that says,
you know, you get to condition on being in a
branch of the wave function where you're alive.

Speaker 1 (47:27):
Yeah, it sounds like a cool premise for a streaming show,
but not a way to live your life.

Speaker 4 (47:31):
That is the one thing that I can say in
the direction of what you were hoping for, and it's
not very useful, I'm afraid.

Speaker 2 (47:54):
All right.

Speaker 1 (47:54):
So you're sort of famous for, you know, throwing cold
water on mis explanations of quantum computing and maybe even overhype.
Let me flip that around and ask you what is
the most under hyped aspect of quantum computing. What is
the thing that you're most excited about that would make
you like, take your family money and invest it in
somebody's quantum startup if you heard them doing it, if

(48:14):
I had that.

Speaker 5 (48:15):
Kind of risk tolerance.

Speaker 4 (48:16):
There are so many things that I knew about when
they were small, that I should have been investing in.
And you know, clearly it's probably for the best that
I became a professor and not an investor. I mean,
one thing I think that a lot of people don't
realize is that, you know, we are just within the
last year the experimentalists have gotten very very close to

(48:37):
the degree of control, you know, over cubits that would
be needed to build a scalable quantum computer with with
what we call quantum error correction, which is the technology
that would ultimately allow you to sort of keep your
cubits isolated, keep them from being prematurely measured by their environment,

(48:57):
and you know, do an arbitrarily long quantum come computation
with them. Right, So people have been talking about these
ideas for thirty years now, and you know, so some
people you may have gotten fatigue with quantum computing. What
we've known since the mid nineteen nineties is that if
you can control two pairs of cubits well enough, like

(49:18):
if you can get the error the noise in a
two cubit interaction to be sufficiently small, then there are
these very very clever quantum error correcting codes that can
get you the rest of the way that can encode
like a single logical cubit across an entangled state of
tens or hundreds of physical cubits, you know, in such

(49:39):
a way that you can survive and recover from, you know,
an error on any one of.

Speaker 5 (49:43):
The physical cubits.

Speaker 4 (49:45):
And you know, these codes have the effect of pushing
your effective error rate down closer and closer to zero. Right,
but only after you've passed this critical point at which
the error correction becomes a net win, which it starts
making things better rather than making them worse. It's almost
as if like you have to pass the critical mass

(50:07):
for a nuclear reaction. Right, if you're halfway there, you
don't get half the reaction, right, you know, you need
to pass criticality, okay, And so that's sort of been
the engineering goal of the people who, unlike me, have
labs and not just blackboards, right, who are actually trying
to build these devices. You know, that's been their goal
for thirty years, and I think you know, many people

(50:28):
might not realize just how close they are. So basically,
you know, the estimate is that you want to be
able to, you know, apply a two cubit gait, that is,
you know, do a desired operation on two cubits with
about ninety nine point nine nine percent accuracy, about four
nines of accuracy, and that ought to be enough to

(50:49):
get this quantum error correction, you know, self sustaining reaction started.
And when I joined the field, which was in the
late nineteen nineties, such as a few years after shores
and grovers algorithms had been discovered, right, it would have
been amazing if you could do like a two cubit
gate with fifty percent accuracy, right, Like that would have

(51:10):
been a nature paper, okay. But then at some point
the fifty percent became ninety percent, and then that became
ninety five ninety nine percent, and within the last year
we've seen like ninety nine point nine percent accuracy, okay,
in several different groups. You know, the neutral atoms grew
Querra and Boston, the trapped ions which like Quantinuum in

(51:34):
Colorado does superconducting cubits, which at Google and IBM are doing.
So you know, so a bunch of different approaches are
you know, being pursued simultaneously, but you know, several of
them are getting up to this, like ninety nine point
nine percent accuracy, and it looks like just one more
nine and you should be at the point where you
know this self sustaining reaction works. So I think that's

(51:57):
the central case for optimism right now. For just looking
at the hour raid as a function of year, it
looks like either you get there in the next decade
or else something surprising.

Speaker 5 (52:07):
Happens, you know that explains why you didn't get there.

Speaker 4 (52:10):
That's one aspect of the story that maybe is not
so well appreciated.

Speaker 1 (52:15):
All right, So that was our interview with Scott in
conversation about quantum computing. I think the answer to the
question should you be excited about quantum computing is yes.
This potentially represents a whole new era of computing computers
that are good at solving different kinds of problems than
our traditional computers and opens our minds to the way

(52:37):
computation can be done. Maybe there are other kinds of computers,
not just classical or quantum computers, but other kind of things.
Ways we can take advantage of the universe to do
the calculations that we want to do. Thanks Scott very
much for joining us, and thank you to everybody for listening.
Tune in next time.

Speaker 3 (53:00):
Daniel and Kelly's Extraordinary Universe is produced by iHeartRadio. We
would love to hear from you, We really would.

Speaker 1 (53:07):
We want to know what questions you have about this
Extraordinary Universe.

Speaker 3 (53:11):
We want to know your thoughts on recent shows, suggestions
for future shows. If you contact us, we will get
back to you.

Speaker 1 (53:18):
We really mean it. We answer every message. Email us
at Questions at Danielankelly dot.

Speaker 3 (53:24):
Org, or you can find us on social media. We
have accounts on x, Instagram, Blue Sky and on all
of those platforms. You can find us at d and Kuniverse.

Speaker 1 (53:34):
Don't be shy write to us