OK.
Scott Aaronson.
Scott is the David J.
ranted Centennial professor of
computer science at the University of
Texas Austin and also directs the Quantum
Information Center that I've known
unknowns God since he was a grad student
you got to be with you Michel as a run.
And then went to the post arts and
went on my T.V.
for a while and just a couple years ago.
Just this year doing this about it.
Yeah no no no it's got a long
time since Stratford will any
more than a few of my old questions.
For you guys got really you know
one of the best known figures in
quantum computing.
He's won a number of awards Most notably
the US a few case in the Waterman but
Waterman prize one of being
goes like this of wife
because the work that
you think you're signed.
You got bit of a chemist.
And.
And besides doing all sorts of great
research legal talk some about today.
He's also a political writer he has.
One of the best.
Blogs in computer science and
has written a book
on a computer since the time of
the marketing machine that right.
Very close up close enough.
So I tried to find my copy to
show you all but you know so.
You know.
Yeah well that's the they also
I heard you know so they get.
Paid for it.
Anyway though I should stop you
just got to much better speakers.
Are well.
Thank you Vance for the introduction.
For some inexplicable reason this is
actually my first visit to Georgia Tech
sure that it will be the last it's
really great to be here see so
many old friends and
new and so so I want to.
Tell you about the limits
of quantum computers and
some other things that that's connected to
so when I did a google image search for
quantum computer this is one of
the first things that came up
now you know it will be obvious from this
talk that I am not an engineer I don't
actually build these things than anyone
about me into the lab I'm a serious but
I don't think that that's
what they look like.
All right but my my starting point for
this talk actually has nothing to
do with quantum mechanics it's just
about you know let's try to understand
what are the limits of technology you know
there are certain things that would be
wonderful to have and yet somehow we
never see them one example is warp drive
you know where is it we've been waiting
a second example is the perpetual motion
machine you know the only real solution
to the world's energy problems and
thirdly is what I'll call the computer
this is a device that doesn't you know
tell you the meaning of life or anything
like that but it immediately answers any
well posed mathematical question
that you put to it OK so
here we see it saying Goldbach Conjecture
true next question right so
you know if you know you know any
math you know is ever even number for
a greater the sum of two primes
that immediately answers.
So you know I think some people have
the impression that this is already
what computers are but sure you know
I don't have to tell people here that
even computers have limitations you
know there are certain things like
the halting problem that
we know that no computer
program can solve even in principle
there are other things like N.P.
complete problems where although they
are solvable by computer we believe.
I don't know if Dick Lipton is
here most of us believe that
that any algorithm to solve them will
require an astronomical amount of time OK.
So so now the point I want to make is
that in the first two of these cases
we know something about why we don't
see these technologies which is more
informative than just well you know
the engineers ran out of funding or
you know they just you know clever enough
to build it OK there are fundamental
physics physical principles
involved in the case of.
Warp drive those principles are those of
special relativity or we could just say
the causal structure of space time
you know if you could send any signal
faster than light then in someones frame
of reference you're sending that signal
backwards in time and then you've got to
deal with you know what happens if you go
back in time and you kill your grandfather
and therefore you're never born but
therefore no one kills your
grandfather therefore you are born and
so on right now and
no one wants to have to deal with that OK.
With the perpetual motion machine you know
the principles that rule it out are those
of thermodynamics you know the second
law OK but what about the third case.
You know.
What are the fundamental physical
limits on what we can compute or
feasibly compute and
if we understand those limits
then would they have any
implications back for physics so
those are sort of those questions are sort
of my starting point for this talk.
OK so I thought you know I should
have one slide where I just you know.
You know I know that Lance doesn't need
this slide and you know in may and
may you know and many people don't but
just to reacquaint you with
the universe where computer
science this like to spend
a lot of time the complexity
classes by the way you know
I have a website that I made in grad
school complexities do dot com which has
five hundred of these classes
here I'm just showing four OK so.
So you know in order to talk about
the limits of computation we do talk about
some a few classes of
problems polynomial time is
all the decision problems that we could
solve efficiently with a standard
digital computer like the one in your
pocket whereby efficiently we mean using
a number of steps the grows like the input
size raised to a fixed power you know this
in compas is most of what we do with our
computers on a day to day basis N.P.
non-deterministic polynomial all
the problems where you know if there
is a solution then there
is a sure witness for
the solution that can be
efficiently verified.
The N.P. hard problems are the ones
that are at least as hard as any N.P.
problem and the N.P. complete problems
are the ones that are both N.P.
hard and themselves in N.P.
So sort of the hardest problems in N.P.
a great discovery that really got C.S.
theory off the ground in the early
in the seventies was that you know
hundreds of problems that people care
about in practice turned out to be N.P.
complete including
solving Sudoku puzzles
Super Mario Brothers and various things
of less practical interest like airline
scheduling and you know and so forth OK.
You know and then there are also N.P.
problems that seem to inhabit a twilight
zone where we don't know
them to be in pity but
we're also pretty sure that they're not
N.P. complete you know these sorts of
problems often play very important
roles in cryptography and
as will say See also very important
roles in quantum computing
OK So of course the literally
million dollar question here
is whether P equals and piggy.
You know Lance has written
a whole book about this question
it's also you know we know it's important
not only because of that but because it's
been on at least you know on The Simpsons
and Futurama on various other T.V.
shows that are not as good so
we won't talk about them.
You know and if you solve this you get
a million dollars from the clay math
Institute it's one of seven such problems
along with the Riemann Hypothesis
the punker a conjecture which was solved
by Perelman although he turned down
the prize and for
other problems now I think that says N.P.
is just clearly the most important
of all seven of these problems
one simple argument for that is that if P.
equaled N.P. and
if Moreover the algorithm were efficient
in practice well then that
would solve this question but
it would also mean that you could solve
the other six because you would simply
ask your computer to find the proof for
you write your you know you could
if there was a proof of the Riemann
Hypothesis in some formal language Z.F.
set theory that was at most a billion
symbols long then you know you were saying
it would be saying your computer could
find that proof in time you know not not
dramatically greater than it would
take to write the proof down OK so so
our computers almost would become those
computers from the previous
slide Not quite but almost.
OK.
So you know so so P.
Versus N.P. Of course you know there is
an enormous amount to be said about it
I actually wrote one hundred twenty page
survey article about it which was supposed
to be a ten page survey article this
year for anyone who's who's interested.
You know you know could do
a whole lecture or a whole course
on just this question but you know
which by the way I should say that.
I along with most computer
scientists conjecture that P.
is not equal to N.P. that you know that
there are problems in other words for
which brute force search will be needed
and you won't be able to avoid it
I like to say that if we were
physicists we would have just the clear
that to be a law of nature OK and
we would give ourselves Nobel prizes for
the discovery of the wall if later
it turned out that peak was N.P.
Well that would be fine we would just
give ourselves more Nobel Prizes for
the was over throw OK But
you know there's you know working
in an interdisciplinary field like quantum
computing you know you you are in that you
know there are differences of terminology
so what the physicists call law
you know we in mass call conjecture so
fine.
But you know now for
me where things get even more interesting
is when we bring physics
into the picture P.
Versus N.P.
itself is a purely mathematical question
right whatever is the answer to it
you know the answer is completely
independent of the was a physics OK but
then you know we can ask.
A related question which is well can N.P.
complete problems be solved in polynomial
time by any physical means right including
possibly computers that would exceed
the limits of Turing machines you know of
the kind of computers that we use today
so you know the key presupposition
that connects the P.
Versus N.P. problem to the real world is
the extended church Turing thesis E.C.T.
which I'm go going to state as just
the assertion that any physically
realistic computing device can be
simulated by a deterministic or
at least a probabilistic Turing machine
with it most a polynomial over head
in time in memory of the original
church Turing thesis would would
be the same thing but without this
proviso about the amount of overhead OK
now it's not clear that church or
Turing themselves would have endorsed
any statement of this kind you know
that it actually makes a falsifiable
Imperial claim about physics OK but
if they didn't then they should have so
what will so we'll just call this
the church Turing thesis OK.
So.
You know it.
You know you know but you know there's
you know that this extended church story
thesis is not a theory it's not
even susceptible to proof right
it's a falsifiable claim about physics at
the end of the day right there would be
some universes that satisfy this
thesis and others that don't and
so it behooves us to ask well
how sure are we of this thesis
What would a challenge
to it even look like.
You know what do we know about you
know the most powerful kinds of
computers that are compatible with
let's say the known laws of physics and
do any of them challenge this thesis OK so
so
before I get to quantum computing you know
you know obviously I'm headed there but
let's see a few other examples of
challenges to the extended church Turing
thesis that there have been over
the years just so we get a sense for for
what they're like so one of my favorite
proposals comes from goes back
to the sixty's and it's simply that you
would take two glass plates you put
pegs between them in whatever pattern
you want and then you dip the resulting
configuration into a tub of soapy
water and you take it out and
you look at the soap bubbles the form in
between the pegs and you know bubbles
like to relax to a minimum potential
energy state and you could roughly
model that by saying that well that you
know the bubbles would like to form
the minimum total length of line segment
connecting all these pegs together.
As as in this picture here OK but
now this raises a puzzle because finding
the minimum total length of line segment
that connects a collection of points
in the you could be in plain is called
the minimum Steiner tree problem and
this is well known to be an N.P.
hard problem OK So you know and yet.
It seems like these soap bubbles
just solve it instantaneously OK SO
SO SO SO SO SO SO here's our question
is a tub of soapy water doing what all
the world supercomputers cannot do
you know could you break cryptographic
codes using big vats of soapy water.
Well you know there was a discussion
of that on the Internet some
you know some years ago and some people
made what I think is the right analysis of
the situation which is well systems
in nature like to reach their mini
state of minimum potential energy but
they don't always succeed for
example if we had a rock and some
crevice on a mountainside it could reach
a state of lower potential energy by
rolling up first and then rolling down but
it's rarely observed to do that OK so
why not say the same here
that these soap bubbles could get stuck
in a local optimum which is different
from the global optimum OK And
then you know someone else responded and
he said well this is just an academic
computer science party line I bet that not
one of you is actually done the experiment
you have no idea what you're talking about
and so forth so you know I told you I'm
a theorist This led to the one foray
into experimental physics
of my career I guess so
I built the thing it's a really fun
experiment you should try it at home but
if you do use plexiglass and not glass so
you don't cut your hands ASCO you know.
So you know I you know basically you know
you do you do with four pegs five pegs and
so forth and you find Typically
it does find the minimum start or
tree you know and you can even watch
it relax do it it's a lot of fun but
you know when you start having more like
six pegs seven pegs it does not always
find the minimum Steiner tree and in fact
sometimes you get like an intermediate
cycle of bubbles which is then like
a proof that whatever it is cannot be
minimal OK now I didn't try every possible
brand of soap but you know I think that
there are some circumstantial evidence
here that nature is not solving N.P.
complete problems by magic you
know now this may sound silly and
yet you know every year or so you will
read in the popular press something
you know some new about some new
analog computer to solve N.P.
complete problems where you know
it's basically isomorphic to this OK
you know there was something called
meme computing recently that you know.
You know people talk about protein
folding right protein folding
can be reasonably modeled as again an N.P.
hard problem and
yet every cell in your body solves
that problem every second right so
does that mean that biology exceeds
the extended charge during thesis
you know people have had you know we
learned discussions about that OK but
to me you know I would say Well
first of all for the proteins that
arise in real biology there's tremendous
selection pressure on them you know for
them to fold in a reliable way which
would generally mean not getting stuck in
a vocal Optima OK even
despite that we know that
some sometimes proteins do get to
fold into local up the money so
pretty on the agent of mad cow
disease seem to be an example of that.
If you engineered a protein where
in order to fold it into its lowest
energy state you would have to prove the
Riemann Hypothesis you know and the fact
that protein folding is N.P. complete you
know means that in principle one could
do that well I wouldn't expect that
the fold very well I haven't tried it.
OK next example you know you know everyone
talks about quantum computers but
why what about the other great theory
of twentieth century physics why not
a relativity computer OK So the idea
of a relativity computer is simple you
start your computer working on your hard
problem you leave it on Earth then you
board a spaceship OK the spaceship
accelerates to relativistic speed
then a diesel or eight and it returns to
Earth now in earth's frame of reference
billions of years of now past
civilization has collapsed
you know if we didn't already collapse by
like twenty nineteen or something you know
all of your friends are long dead but
if you can you
know dig your computer out of the rubble
and it still connected to a power source
then you can just read out the answer to
your hard problem you know now to me this
raises an immediate question which is why
doesn't anyone try this I mean if you're
worried about your friends then just
bring them on the spaceship with you.
Well you know so so you know what you know
is there any fundamental principle of
physics the rules the cell I think that
there actually is an interesting answer
here and it has to do with the amount of
energy that it would take to accelerate to
this kind of relativistic speed so
one can calculate that if you wanted to
get an exponential computational speed
up by this kind of approach then you
would need to get to exponentially
close to see the speed of light but
to do that would require
an exponential amount of energy so
the other day we're basically
trading one exponential for
another one because you know now we're
talking like does it take exponential time
just like fuel fuel up your
spaceship before with off the right
where you're going to get an exponential
amount of fuel you know I don't know.
OK so a related example is what I call
the computer now this is a computer
that does the first step.
Of its operation in one second
the second step in half a second
third step in a quarter second and an
eight second sixteenth second and so on so
that after two seconds it's the an
infinitely many steps OK easy to solve
the halting problem that way OK but you
know again you could wonder why doesn't
anyone try that one this case I think
the answer is you know there are people
who effectively try this there are people
who overclock their microprocessors
you know they run it faster than the
recommended speed but many of you may know
the danger in doing that which is that
if you run your microprocessor too fast
it will overheat and it will melt
OK this is why computers have fans.
You know but you know again we could ask
So what is the fundamental limit on clock
speed a clock rate of a computer
well as you ran it faster and
faster you need more and
more cooling which would cost more and
more energy you know
again with the energy.
You know to really run fast you might
want to cool with liquid nitrogen or
with with helium as people used to
do with some supercomputers OK but
as the computer becomes fast you
know even faster we might as well
just talk about the energy that is
inherent in the computation itself and
as far as current physics can say
the fundamental limit here would occur
right around when you're doing
one operation per Planck time
which is about ten to the forty
three operations per second OK
now a computer that ran that fast
Well you know the sort of simplest.
To a model of such a computer might
be a photon which balances back and
forth between two mirrors ten to the forty
three times a second in this case
the mirrors would be separated by one
planck length which is ten to the minus
thirty three centimeters OK now what
what would happen with such a photon
Why couldn't we get it to sort of tick
off time steps even faster than that well
you know if you have a photon that's
confined to that small region
then you know it you know by equals H.V.
right its energy gets larger and
larger the smaller is its wavelength and
when it's when it's balancing back and
forth you know it was between two
mirrors a Planck length apart you.
Calculate that the photon has so
much energy that it exceeds its own
Schwarzschild radius OK if you don't
know what that means is just a fancy
way of saying that your computer
then collapses to a black hole.
Which you know I've always liked is
nature's way of telling you not to
do something.
So you know so so so
it's another nice example for
how we feel look at just saw aspects
of the laws of physics in isolation
you know it can look like you have
computational superpowers but
you really have to look at how you
know all of the known laws of physics
put together right and then you know
there's a whole literature about so-called
hyper computation right where people
write papers about things like this and
I just you know they ignore that the world
is ultimately quantum quantum mechanical.
You know which then you know puts
these these limits once you get to
the Planck length and the Planck time OK.
OK but what about quantum computing
you knew it was coming so
here so I'm happy spin one half particles
again I don't think that's
actually what they look like but.
You know in order to tell you what
a quantum computer is I first have
to spend a slide or two to tell you
what is quantum mechanics OK now.
Some people get scared at this
point because they've heard that
quantum mechanics is somehow
complicated or hard but
I can let you in on a secret not
being a physicist which of quantum
mechanics turns out to be really really
simple once you take the physics out of it
OK You know the way I think of it is
that you know it's really like an ass
that the rest of physics runs on is
application programs OK it's not even
physics it's a level below that it's
a certain generalisation of the rules of
probability which you could call
probability theory but with minus sides.
OK so Richard Fineman
used to say that you know everything
in quantum mechanics is contained
in one experiment you know the double
slit experiment which shows us this one
phenomena an interference that just
keeps showing up over and over and
is behind every weird quantum
effect that you've ever heard of or
ever will hear of OK and the double
slit experiment is this thing where
you know you shoot photons one of the time
at a screen with two slits in it and
you look at where the photons and
up on a second screen and you know so
so where the photon away ends
is probabilistic you know with
identical initial conditions sometimes it
lands in one place sometimes another but
that by itself is not the weird part OK
Forget everything you heard about you know
you know God playing dice and that's
mysterious like you know if it was just
randomness you could invent twenty ways to
explain that before breakfast OK The weird
part is that you know it seems to follow
completely different rules of probability
than the rules that were used to OK So
in particular what happens is that
when both slits are open there
are certain spots on the second screen
that are dark meaning the photon never
seems to appear there OK and yet
if I close off one of the slits then
the photon could appear there OK So
decreasing the number of ways for
something to happen actually increases
the probability that it happens OK And
you know Worse yet you know these
dark spots if we just look to see
which slit the photon is going through
then we don't see them anymore OK So
measuring to see which slit so
that the photon
goes through destroys the interference
pattern as the actually any
kind of interaction that would take
the information about which slit
the photon went through and records it in
any other degree of freedom in the world.
So.
You know after seeing like hundreds of
phenomena that were kind of like this
venture early in the one
nine hundred twenty S.
physicists realized that they
needed a new set of rules for
how to calculate probabilities OK and.
The basic idea is that you know beneath
probabilities are more fundamental
quantities which we call amplitudes
unlike probabilities which are real
numbers from zero to one amplitudes
can be positive or negative and
in fact they can even be
complex numbers OK And
you know if you the amplitudes are related
to probability that you'll see
something in particular when you measure a
system the probability that you see it in
a particular state is equal to the squared
absolute value of its amplitude
OK that's called the Born rule one of the
basic rules of quantum mechanics OK but
when you're not measuring when the system
is isolated from its environment you know
the amplitudes kind of do their own thing
which is very different from from what
probabilities would do and in particular
if I want to know the amplitude for
my system to get to a certain state
I have to add up the amplitude for
all the possible ways that the system
could have reached that stage and
now if one of those ways like say
the photon going through the first of it
you know had a positive amplitude and
another way had a negative
amplitude than those two contributions
can as we say interfere destructively and
cancel each other out with the result
being that the total amplitude for
that outcome is zero and
you never see it happen at all OK but
if I close off one of the slits then
noticed that the amplitude would be only
positive or only negative so
then it's non-zero and
then you can see the thing happen
OK that is quantum interference.
OK so a bit more precisely the key claim
of quantum mechanics is that if we have
any isolated object and it can be in
two perfectly distinguishable States
which as computer scientists we
like to call zero or one and
you know as a little sop to the physicists
will use these weird brackets that they
like to use then it can also be
in what we call a superposition
of the states which is just
a complex normalized complex
linear combination of them that's
what it means OK a zero plus B.
one where N.B.A. are the complex
numbers called amplitudes satisfying
absolute value of A squared plus absolute
value of be squared equals one so
if we restrict it to real
amplitudes only then they possibly
possibilities are given
by a squared plus B.
squared equals one which of
course defines the unit circle K.
like this so I could have the zero
state the orthogonal one state or
any kind of intermediate possibility such
as this zero plus one over a square root
of two in equal superposition of zero and
one now if I measure that state and
I ask it whether it's a zero or a one I
force it to make up its mind about which
it once the big and then it tells me
that it's zero with this probability and
that it's one with that probability and
whichever choice it makes it then sticks
with it right so it's snaps to that
one and then it stays there so
measurement in quantum mechanics
is a destructive process.
OK So now what's the idea of
quantum computing Well if I have
not just one of these quantum bits
are cute bits but let's say a thousand
of them will then the rules of quantum
mechanics say that I need an amplitude for
every possible configuration of all
thousand of the bits together that's two
to the thousand power amplitudes that
happens to be way more complex numbers
than could be written down inside
the entire observable universe OK and
yet you know quantum mechanics since one
thousand twenty six has been telling us
that we need that many complex
numbers just to describe
a general state of a thousand
measly particles OK And
every time something happens to
the particles you know nature has to like
cross off all of those to the files in
complex numbers and replace them with new
complex numbers OK That's a staggering
amount of computational work for
nature to be going to right I mean you
know we don't we don't directly say it and
yet you know it's implicit in our
best theory for how nature works so
you know so that's that's that's really
something right and you know chemists and
physicists in some sense have known
this for generations they've known it
mainly as a practical problem you know
when you're trying to simulate quantum
mechanics on a classical computer you know
to learn something about chemistry or
material science or
whatever you know in general
the complexity of the simulation grows
exponentially with the number of
particles that you're trying to simulate
right this is you know part of why a good
fraction of all the super computer time in
the world is used for quantum mechanical
simulations and you know chemists and
physicists have gotten very good at
it inventing approximation methods that
sometimes get around this problem.
But you know they have not had any way to
get around it in full generality OK so
it was not until the early eighty's that
a few physicists such as David Deutsch and
Richard Fineman had the amazing idea well
why don't we sort of turn that women
into lemonade OK why don't we build
computers that themselves would take
advantage of superposition and
interference and so forth and
that would be built out of cubits
Now of course they immediately faced
the question well supposing that we built
such a computer what would it be good for
OK Now at that time Fineman was only
able to give one answer to that question
which is such a computer would be good for
simulating quantum mechanics itself
that sounds kind of tautological but
I think you know if and when we get
practical quantum computers I think this
is still by far the most important real
world application of them that we know
right it is something that could a drug
discovery in designing
new materials you know
maybe high temperature superconductors
maybe new solar cells you know maybe.
You know new kinds of chemical reactions.
You know anything where I have many
many interacting particles AND
I NEED TO GET THE in Tangled
quantum behavior correct.
And this is also something where we're
quite confident that a quantum computer
really will help you you know
in contrast to some of the other
things that you hear about OK so.
But yeah so.
OK So that that's the main application
I think you know there are as well say
you know as we know there are other
applications but at this point I should
probably address what I think of as the
fundamental misconception about quantum
computing this is the thing that recurs
in just about every popular article
that is ever been written on this
subject even though it's wrong OK And
you know I've been pushing this
particular boulder up the mountain for
the way as decade you know just
trying to correct this over and
over on my blog even you know have this
point as like the tagline of my blog so
no one misses it OK but you know what
everyone wants to say is that well
a quizzical computer works just by trying
it possible answer one after the other
a quantum computer gets a speed up because
it can just try all the possible answers
in parallel you know in different
parallel universes or something.
So you know let's.
Pinpoint exactly why that
explanation is wrong OK Well
you know it is true that using a quantum
computer you can create a superposition
over all the possible answers to some
problem you want to solve like an N.P.
complete problem that's actually a very
easy thing to do with a quantum computer
and the trouble is for the computer
to be useful at some point you've got
to measure it somewhere you've got to read
out an answer and if I just measure it in
equal superposition over all the possible
answers not having done anything
else than the Born rule of quantum
mechanics tells me that what I'm going to
see will be a random answer and of course
I just wanted a random answer while I
could have picked one myself with a lot
less trouble OK So you know the entire
hope of getting a speed up from a quantum
computer relies on the the fact
that amplitudes work differently than
than conventional probabilities do.
So amplitudes being complex numbers
can interfere with each other
OK The key idea with every
quantum algorithm is
to choreograph things in such
a way the For Each wrong answer
to your problem each answer that you don't
want it some of the paths leading to
it have positive amplitudes and
others have negative amplitudes so
that on the whole they all cancel each
other out OK whereas for the right insert
the answer you do want you to like all the
different paths leading to their to be in
phase with each other so they'd all have
positive amplitudes are all negative or
something like that if you can arrange
that then when you measure the right
answer will be observed you know
least with high probability and
you know if you don't see the right answer
once you can always just rerun your
algorithm several times you know in to
boost the probability that you'll see
the right answer you know just like you
do with a classical randomized algorithm
OK So you know now that the tricky part
is that you need to choreograph that
pattern of interference that concentrates
the amplitude on the right answers
despite not knowing yourself in
advance which answers are the right
ones because if you knew that that
would trivialize the thing right so
it's you know nature gives you this
really weird hammer and it is far from
obvious you know which nails it hits OK
it took people a while to figure it out.
But you know being one thing computer
scientists can do is that they can take
any concept and associate to it
an inscrutable sequence of capital letters
OK So that is what my former
advisor from Berkeley the Rani.
Together with his student Ethan Bernstein
did in one thousand nine hundred three
they defined the quantum generalization
of the class pay the Class B.
Q piggy back on that era quantum
polynomial time by the way one thing
I'll give the physicists is that
they've got much better names for
things you know quare black hole you
know we're stuck with B.Q. pig OK but.
This is the basically just the class of
all problems you know decision problems
that are solvable efficiently by a quantum
computer with a bounded probability of our
great now the famous discovery
of the ninety's that really got
everyone excited about quantum
computing was of course the result of
Peter sure that said that
the factoring problem is in B.Q.
page or you know some decision version
of factoring OK So you know if you
build a quantum computer sure showed
how you could use it to factor in and
digit integer only about and squared steps
whereas the best known classical algorithm
uses something like exponential in cube
root of insteps OK now this you know
made a lot of people excited including
people you know who had not been excited
about quantum computing before because as
you may know you know if you can factor in
a gers efficiently and do some related
things like calculating discrete
logarithms which sure is algorithm also
lets you do then you can break almost
all of the public key cryptography that
we currently use to secure the Internet.
You know there are other public key
cryptosystems out there that we don't know
how to break even with a quantum computer
most famously the lattice based crypto
systems but those are just not widely
used today you know we would we would so
so someone builds the quantum computer
we will you know we will have to switch
what kind of crap that we use Ok so
to draw a new map so
I drew you know the clay as big Cupid or
what we currently know about it over here
I drew it with a wavy border you know
because everything quantum is smooth and
weird but you know B.Q.
pig contains at least some problems
such as factoring which are not known to
be in Piggy Well of course we don't really
know whether they're in pity or not.
As you can see you know
I we don't know if B.
Kewpie contains the N.P.
complete problems many of us would guess
that it doesn't we also don't know if B.
Q.P. is contained in N.P. there might
be problems that a quantum computer
can solve for which a classical computer
cannot even verify the answer but
at any rate be Q.P. generalizes piggy
you know anything a classical computer
can do a quantum computer can do as well
so like you can use a space shuttle to
drive down you know the you know
your driveway or something OK.
OK so for some reason when I give talks
one thing people always want to know
is can quantum computers
actually be built so I write so
let me talk a little bit about that.
So you know in terms of using
sure's algorithm to factor numbers
I'm proud to report that after you know
more than a billion dollars of investment
in quantum information worldwide sure
is algorithm has been used to factor
twenty one into three times seven
with high statistical confidence
I believe the thirty five
is on the near horizon OK
now you know of course you know it sounds
not very impressive if you put it that way
well you know as we'll see there are other
types of quantum algorithms where
actually we can do much more
impressive things already and
even more so will will probably
have within the next year OK But
you know fundamentally why is scaling this
up such a hard problem was understood
since the beginning that it's super hard
to do because of what's called decoherence
that means unwanted interaction
between your cubits and their X.
terminal environment which has the effect
of prematurely measuring them and
forcing them back down to
a classical state right so
you know to measure a cubit to have
the effect of measuring it it doesn't
have to be a person who looks at it or
even a recording device it could be any
stray you know photon that happens
to pass through and that carries
away some information about the state
of that tube it whether it's a zero or
a one if anything like that happens well
it's like you're baking a souffle and
you open the oven too early right
it collapses it's state OK or
at least I'm told I've
never big this is the way.
But.
You know so so so what this means is
that in order to build a useful quantum
computer you have to keep the cubits
incredibly well isolated from their
environment but they also have
to be interacting very strongly
with each other OK And not only that but
in a precisely choreographed pattern
to solve your problem OK it is those twin
requirements you know that make this
incredibly hard you know in fact it's so
hard that a few skeptics in C.S.
and physics have argued that it could
never work it's just fundamentally
impossible OK now what I always say to
them is well I hope that they're right
because you know if there's some deep
reason why this could never work with and
that you know that overturns a century
of physics right we have to rewrite
the physics books to understand what was
wrong with our understanding of quantum
mechanics that makes this not possible
you know there'd be there'd be many
Nobel Prizes in that right compared to
that just building a quantum computer and
having it work that's the boring outcome
that's the conservative outcome OK so.
Yeah but either way of course
we would love to learn the truth
my personal bet is that you
know is on the boring outcome
right that indeed you know it it will you
know alternately be possible to do this.
You know so you know for me you know you
know the number one application of quantum
computing you know even more than
quantum simulation is just disproving
the people who come to my blog and
say that it won't work.
So you know but you know the key discovery
from the ninety's you know that convinced
most of the field that this is merely you
know a super hard engineering problem you
know and not a problem of principle was
what's called the quantum fault tolerance
theorem and what that basically said is
that you know if you want to build do
an arbitrarily large quantum computation
then you don't have to get the rate
of decoherence down to zero you merely
have to make it sufficiently small and
once the decoherence rate becomes small
enough like let's say you know a one in
one thousand chance of losing a cubit
you know per cubit per gate time or
something like that then you can
apply very clever correcting codes
which in code the cubits that you care
about non-locally across many physical
cubits in such a way that even if for
example any one percent of the your
cubits were to leak out into
the environment you could still recover
the information you care about from
the remaining ninety nine percent OK So
you know we are you know what's happened
just within the last couple of years is
that some of the experimenters have
gotten cubits you know that can do
one cubit into cubit operations
with high enough fidelity that
in isolation you are already at this
fault tolerance threshold right so
like you know for two cubits in isolation
you know you can you can act on them with.
Decoherence Ray where if you could
maintain that scaling up then you could
you know already do these are a correcting
codes and you know and then scale to as
many cubits as you want now of course
you know that of course there is a catch
The catch is that as you scale up you
know the cubits have all these unwanted
interactions with each other that pushes
the decoherence rate back up OK but
just within the last few years the
components are finally gotten good enough
that it starts to make sense to
integrate you know twenty of them fifty
of the one hundred of them and you know
see if you can do something interesting
OK but that was the you know the practical
side you know on the theoretical
side you know a fundamental question
since the beginning of this field but
you know what you know what are the limits
of what you can do with a quantum computer
you know assuming that when you
have a perfect one let's say
you know in particular can
quantum computers solve N.P.
complete problems in polynomial time
well as I said we don't know you know
most of us conjecture know can we prove
that they can't well of course we can't
prove that we can't even prove
that he is not different from N.P.
so far less could reprove the U.P.A.
doesn't contain N.P. OK but
one thing that we do know is we do if
you treat your N.P. complete problem
as just an abstract black box just
like a space of possible solutions
where the only thing that you knew how
to do is just check each solution and
you know see whether it's valid or
not valid and you're searching for
a valid solution then in this setting
we understand exactly how much speed up
a quantum computer can give you OK So
there's after Shore's algorithm
probably the second most important quantum
algorithm is called Grover's algorithm and
this is an algorithm that can
search through any list of possible
solutions only about the square
root of and steps OK So this
is much more widely a political ball than
Shore's algorithm but the disadvantage
is that it's only a square root speed
up and not an exponential speed up.
OK So and now.
Fundamental result by Bennett Bernstein
Brossard and Vasa Ronnie says that for
this task of sort of black box
searching you know just looking for
a needle in an abstract haystack Grover's
algorithm is actually optimal OK so
even a quantum computer will not give you
more than the square root speed up OK what
that implies is that if you wanted
a quantum algorithm that would solve N.P.
complete problems in polynomial
time then it would somehow have to
exploit the structure of the problems
just as a classical algorithm for
and be complete problems would have to
OK So it kind of pushes the question to
well what is a quantum algorithm that
would try to exploit the structure of N.P.
complete problems to solve them
faster Do we have any candidates for
such an algorithm All right well there's
been one really big candidate for such an.
Algorithm which is called the A.T.O.
Batek algorithm proposed by Ed for he and
his colleagues in one thousand
nine hundred ninety nine and
you can think of it as sort of
like a possibly quantum enhanced
version of simulated annealing OK so
it's a horrific algorithm
you know we usually wouldn't be
able to prove that it works but
you know but in practice you
know maybe maybe it would work.
And so would involve starting by applying
an operation called a Hamiltonian
you know with a known and
easily prepared well with energy state and
then slowly varying it through a different
operation whose lowest energy state
in codes the solution to the N.P.
problem that we're trying to solve and
now a fundamental theorem says that as
long as we did this transition slowly
enough we would have to end up in
the lowest energy state of our final up.
Ration which would then solve our N.P.
complete problem so you know so
it's a beautiful idea many of you might
know that there is a startup company in
Vancouver called the wave which has spent
hundreds of millions of dollars just
building these special purpose
devices that or you know just for
trying to implement this eighty a bag of
them so they're like very very special
purpose quantum computers the most the
latest model has two thousand cubits and
it OK And they've actually sold a few
of these commercially right one to
google one to Lockheed Martin I think
a couple of others you know and
this has gotten an enormous amount of
press and you know they were on the cover
of Time magazine you know this and
that but you know until a few years ago
I would say that you know this device
was literally a black box but.
You know because they sold some people
were able to do independent experiments on
them and we now know a lot more
about what is going on with them and
you know it's a very complicated and
evolving story but
you know Wong story short I think
that if you do a fair comparison
you are not seeing a speed up
with this device compared to
the best classical algorithm for solving
the same problem OK you are seeing So
you know the device does an optimization
problem and there is some
quantum behavior in the cubits but
the quantum behavior that's there we can't
really see that it's playing a causal
role in helping you solve the problem
faster than you could have solved it
without that quantum behavior and and
there's really you know a couple of
issues here right one is the just
the hardware issue that you know these
you know in order to scale up so
fast the wave had to take kind
of old fashioned cubits meaning
like two thousand and
three cubits right and you know and just
you know they were optimizing for just
getting as many of them as possible as
fast as possible and not for
the cubits being really good for
maintaining their quantum coherence for
as long as possible and
you know our best current guess is
that if you wanted a real speed up
you would need cubits of higher
quality than these ones OK but
there's even a second issue which is
that even if these cubits were perfect
you know for this particular
task of eighty a bad decision
we still don't really understand how
much speed up you know a quantum
computer is going to give you you know
over the best classical algorithms if any.
So the hope from the beginning
was that the A.T.O.
Batak algorithm would solve optimization
problems faster by exploiting in effect
called quantum tunnelling OK And what
this means is imagine that I'm trying to.
Find the global minimum in this you
know kind of fitness landscape that is
like a big basin with
a spike in the middle OK
now if I run simulated annealing where you
want you know a good question the more
eventually get over this spike but you
know it could take exponential time for
simulated annealing to do it by
contrast depending on the height and
width of the spike for he Goldstone and
Gottman showed in two thousand and
three that a quantum dealer could get over
this spike and down to the global optimum
in only polynomial time OK by you know in
effect that the physicists call tunneling.
The trouble is well in general you
know in order to know the running time
of the eighty Benteke algorithm it depends
on a quantity called the minimum spectral
gap OK which is the sort of
the gap between the smallest and
second smallest eigenvalues of your
Hamiltonian as you vary it basically
the time you have to run it for
goes inversely with the spectral gap OK So
if these two things two curves
ever got exponentially close
then the algorithm will
take exponential time for
he told me the wonderful story that
you know around two thousand water so
they went to you know he went to an expert
in condensed matter physics because
they've been you know have decades of
experience calculating the spectral gaps
for their own reasons and for he explained
the eighty Barack algorithm to him and
he said you know based on your experience
with like you know analogous physical
systems do you think that our spectral
gap will decrease polynomially or
exponentially as a function of the number
of particles and the guy thought about it
and he said I think that your gap will go
down exponentially OK Now that was not
the answer the four he wanted to hear so
he said Why what's the physical reason for
that and I thought about it some more and
he said well it's because otherwise
your algorithm would work.
Right now.
Now you know I love this because I think
that there's something deep here right
which is that you know once you've
had enough experience with nature
making seeming to make it hard for you to
solve N.P. complete problems one way or
the other right you might be tempted
to take on board you know the physical
intractability of N.P. complete problems
as a basic principle you know analogous
to no faster than light signalling or
the second law of thermodynamics or
whatever and you might be tempted to say
well what what other things can I use
that principle to explain you know can I
use it to explain why we don't see close
timelike curves in nature or why quantum
mechanics is perfectly linear or
why these condensed matter systems have
such small spectral gaps OK So I think
you know remains unclear how much useful
speed up eighty Batek optimisation will
give over the best classical her wrist
Pixie even assuming perfect hardware.
OK so I just wanted to in a couple
of minutes just tell you a couple
of things about my own recent work and
then sum up so
so a lot of what I've been doing you
know over the last few years relates
to a very very early goal of quantum
computing research something that's
been saddled with the unfortunate
name of quantum supremacies So
you know I made a lot of jokes about
this all through two thousand and
sixteen you know am I going to disavow
support from the quantum supremacists and
Anyway none of it is funny anymore.
So but what we mean by this term
is just getting a clear speed up
John Prescott going to by the way so
I feel getting a clear speed up for
some task not necessarily
a useful one OK and
ideally with quantum devices that
we could build in the near future.
So in twenty eleven my student Alex Arca
Pavane I propose something called Bose
on sampling which is a way to use a very
very rudimentary optical device where you
just generate a bunch of photons send them
through a network of beam splitters and
then measure where they ended up you
know and that's all you do so it's not
a universal quantum computer probably not
even a universal classical computer OK but
what we did is we looked at well what
probability distributions does this kind
of thing what you sample from and
how hard it would it be to sample
from those same distributions
using a classical computer OK and
we argued that well you know if you could
sample these distributions in classical
polynomial time then that would have some
pretty dramatic consequences up to and
including a collapse of
the polynomial hierarchy.
You know and then you know we just
were interested in this theorists but
once we proposed that the quantum
optics experimentalist kind of.
It up and you know so they've done a bunch
of experiments actually demonstrating it
the most recent being with six photons
OK now the six photon bows on sampling
can be silvery simulated classically Well
you know like you know exponential in
six time so you know you're can classical
computers not breaking a sweat yet
but you know to help perform
a classical computer for
this problem it would probably be enough
to do it with about forty or fifty photons
scaling it up is really challenging
because we don't yet have good enough
single photon sources that would just
output a single photon you know exactly
when you want it but you know the Explore
the optics people have a lot of ideas for
how they might build that in
the meantime a super exciting thing
that is sort of happening you know
this year is that Google and I.B.M.
and actual also group at University of
Maryland are sort of in a race to build
a fifty cubit devices you know you know of
quite high quality right you know I mean
the wave already has two thousand cubits
but these are fifty cubits that really
do what you want OK which you know I'm
personally more excited about than two
thousand the down and you know fifty
cubits probably not yet enough to do
anything useful but it should be enough to
do something that classically is pretty
hard like takes to do the fiftieth time
this simulator something like that right
and so you know so student Ligi Chan and
I had a recent paper
you know proposing what exactly you could
do with these devices to sample from
a distribution over fifty bit strings you
know that we're pretty sure based on some
reasonable complexity is the option would
take something like two to the fiftieth
time to simulate classically OK And again
these are experiments that they're going
to be trying to do over the next year.
So I had one more slide about the comp
you know how quantum computing theory and
our understanding of the limits of quantum
computers has actually been feeding into
our understanding of the black hole
information paradox in the last few years
since I'm running short on time what I
might do is just tantalizing you with this
and then conclude and then if someone
wants to ask me about it I can go back to
it OK so it involves something
called the firewall paradox and.
Anyway so let me just summarize now
quantum computers are the most powerful
kind of computer allowed by currently
known laws of physics the first
clear quantum speed up at least for
a contrived task may be achieved
within the next year useful.
Speed ups will take longer but you know
I think that's also a serious prospect
contrary to what you read you know we
expect exponential speed ups only First
certain special problems where we can
really choreograph this interference
pattern and polynomial Grover type speed
ups for a much wider range of problems
you know to me the profile of what a
quantum computer can and can't do is kind
of weirder inside of our than any science
fiction writer would have had the Imagine
the imagination to invent right if you
were writing a short story you just say
you would solve N.P. complete problems by
trying all the answers in parallel you
never invent something that you know can
do factoring or discrete log but not N.P.
complete problems like you know what's
with that right so you know you know these
are the kinds of things that you
know we know we need nature for OK.
But you know even though even
quantum computers would have limits
you know these limits are what could help
you know protect our cryptography even in
a world with quantum computers and you
know these recent connections to the fire
wall paradox suggest that
the limitations of quantum computers may
even play a role in protecting spacetime
geometry let me stop there thank you
thank.
You.
OK.
Yeah sure if this is all right.
OK so.
Right.
So OK So so what is the black hole
information problem this is a problem that
sort of set the agenda for
a lot of fundamental physics research for
the last forty years OK so
in the seventy's Hawking famously asked
how information can escape from
a black hole it seems the half
if you believe the quantum mechanics
is universally valid Well then you know
everything you know it you know except
measurement which you know you know or
even measurement depending
on your interpretation but
basically you know everything in
fundamental physics should be unitary
which means in principle reversible it
should never destroy information OK so
if you had a quantum theory of
black holes then you know whatever
bits you dropped into a black hole they
should you should eventually be able to
get them out you know this seems
problematic OK but now famously Hawking
also discovered in the mid seventy's
that black holes do radiate OK they emit
this Hawking radiation and
you know venture into into the nothing but
his calculation that suggested that
the Hawking radiation that comes out is
totally uncorrelated with the with
whatever information fell in OK so
we needed some kind of picture where you
know from an outside observers perspective
you know when you drop something into a
black hole it doesn't hit the singularity
and disappear you know it just stays
pancaked on the event horizon for
a while until eventually it fizzles
off in the Hawking radiation OK but
from the perspective of an info
an observer they would have to
see something very different they
would have to see the information
actually just cross the event horizon
with general relativity would
say is not even a very special
place to it in full an observer and
then yes would hit the singularity OK so.
Need you know somehow both
perspectives have to be valid for
the two different observers and
so this led to a famous proposal
by Lenny Susskind and Gerard Hoffa
in the one nine hundred ninety S.
called Black Hole complementarity
basically said you know what is on
the event horizon and what's inside the
black hole are not two different states
they're just the same quantum state being
looked at in two very different ways
OK now I always found that weird
I didn't understand it and
then what happened in two thousand and
twelve was that all the leading experts on
quantum gravity agreed that they didn't
understand it either OK So something
you know you may have heard about was
proposed called the fire wall paradox.
Kinski and solely amps and
what they say they did is
they proposed a hypothetical
experiment that observer Alice OK you
know they you know like Alice and
Bob originated in crypto in C.S.
they migrated to quantum information and
now they are regularly found even in
string theory and black hole physics OK So
Alice stays outside of a black hole
she waits for it to mostly but
not completely evaporate for a black hole
the mass of our sun that would take about
ten to the sixty seven years will assume
that Alice has a very long Grant OK She
then routes all the photons of Hawking
radiation into a quantum computer and
processes them in some particular
way in order to make a measurement
that shows that these Hawking photons
actually do in code the internal state of
the black hole next she jumps
into the event horizon for
the sake of science OK to
see what is inside and
because of this computation
that she did earlier
you know all the existing ideas about
black holes are led to a firm prediction
that what Alice will encounter
now is an end of space time at
the event horizon that is what's called
the fire wall OK now to be clear
Alice was supposed to encounter
an end of space time but
only at the singularity this is
too soon right you know she's not
supposed to you know just you know
die at the at the event horizon
right you know space is supposed to
continue past that So something is weird.
So there were hundreds of papers
published trying to you know resolve this
paradox you know reject one or more of
the assumptions that lead into it but
to my mind maybe the most interesting
response was the one by Daniel Harlow and
Patrick Hayden in two thousand and
thirteen I was a string theorist Hayden
is a quantum information person OK and
they teamed up to say well
you know how hard would it be for
Alice to actually do this experiment
you know as a practical engineering
matter OK And you know and
what they say there is they gave
very strong arguments that for
Alice to actually do this quantum
computation on the Hawking radiation
that would give rise to the problem she
would need to solve a problem that is
exponentially hard even for
a quantum computer game by exponential
here I don't mean ten to
the sixty seven years I mean to do
the ten to the sixty seven years OK so
long before Alice had made a dent in
the problem the black hole would have
long ago evaporated anyway you know so
maybe there's no problem in
the worry about right so you know so
it's this amazing view where the geometry
of spacetime is somehow protected by
computational complexity OK but now when
they came to the crucial point why is this
problem exponentially hard you know they
actually knew better than just to say well
we don't see how to do it faster you know
they actually gave a reduction OK What
they showed was basically that if you had
a polynomial time quantum algorithm to do
this kind of task then it would lead to
a polynomial time quantum algorithm for
finding collisions in exponentially
long lists of numbers OK but
that problem is something
that I studied it might be H.
D.
thesis in two thousand and four and
the central result there was that that
problem considered as a black box
problem at least is exponentially
hard even for a quantum computer.
OK so that when I kind of had no choice
but to get interested in this you know
who knew that I was proving something
about black holes OK so since then
I improved Harlow and Hayden's argument so
it no longer relies on my Ph D.
thesis now I can just show that you
know if you have any injective one
way function which is hard to invert
with a quantum computer you know so
if any even private key cryptosystem
that a quantum computer cannot break
which seems like a pretty safe assumption
then they're you know decoding the Hawking
radiation will be a hard problem
OK More broadly we've been
able to use ideas from quantum computing
theory to get new insights you know
to not only quantum gravity but condensed
matter physics and even classical C.S.
their results about classical complexity
classes for which you know you know the I
think the simplest known proof actually
goes through quantum ideas right so
you know even before building practical
quantum computers we can get a lot of
these intellectual spinoffs All right
thanks thank you and the other.
Yeah yeah.
Yeah there are my factory
where well you could but
we do know that the issue is that
with Shores algorithm First of
all there's there's you know a good
deal of overhead right to factor it and
bit number you probably want at least like
for a bit sore something like that and
secondly Shore's algorithm is
very intolerant of small errors
so like when you soon as you start scaling
it up you start wanting to do quantum
error correction as soon as you need our
correction Well you know theoretically
that's only like a constant factor at
worst a logarithmic factor overhead OK but
the constants are kind of bad OK you know
in the constants it can look like well
you know to really do sure is
algorithm you might want thousands
of physical cubits for
every logical cube it you know and
then you're talking millions
of physical cubits right and
you're talking you know yeah maybe you
know with a Manhattan project of someone
spent a trillion dollars they could do
this and you know if not we're waiting for
a new idea to you know make that
more practical right now you know
I think they probably will try shores
algorithm but you know I don't expect that
they'll be able to factor a sort of
interesting the big number right
you know they'll do other than you know
they'll do whatever they can do with these
systems I mean they're all you know try to
demonstrate like simple white America or
acting codes they might try to do
some simple quantum simulations but
you know I think I think of you know
using Sure is algorithm to do like
Factor an interesting size number that
actually one of the last things will
be able to do in the technological
development of quantum computing
you know because of the strict
requirements for error correction Yeah.
So.
Yes yes.
Well you know I don't know right I mean
I mean you know that you know the question
is like you know you know similarly for
the D wave device or whatever right ones
you know like it doesn't do your thing in
polynomial time and then the next question
be well does it do anything faster than
you know just to stay in their digital
computer simulating it right in the case
of the soap bubbles I don't know I would
expect that whatever speed up you would
get would sort of have a constant factor
kind of character why well because
you know at worst I could sort of write
a classical algorithm that would sort of
simulate the dynamics of the bubbles
right and you know as long as it's only
classical physics that's relevant than you
know whatever local optimum the bubbles
themselves could find I would expect that
simulation to be able to find as well.
Thanks.