Video summary
Scott Aaronson explains that the term "quantum supremacy," coined in 2012, refers to a specific historical milestone where a quantum computer performs a well-defined task significantly faster than any known classical algorithm. It is crucial to understand that this does not imply solving useful problems or tasks outside the realm of computability; rather, it demonstrates an advantage in efficiency while remaining within Alan Turing's definition of computation. Classical computers can theoretically simulate any quantum process if given enough time and memory by storing all state amplitudes and performing linear algebra, but they do so exponentially slower than their quantum counterparts for large inputs. The core distinction lies in computational complexity: classical algorithms scale polynomially with input size to be considered efficient, whereas simulating a quantum system often requires exponential resources, making the task practically impossible for classical machines as the number of qubits increases. To demonstrate this supremacy without needing error correction or solving practical problems immediately, researchers shifted focus from single-answer tasks like factoring numbers to "sampling problems." In these experiments, such as Google's recent work involving 53 qubits, the goal is not to find a specific solution but to generate samples from a complex probability distribution. Quantum computers achieve this by applying random sequences of operations that create constructive and destructive interference among amplitudes, resulting in outputs where some strings are exponentially more likely than others due to their alignment or lack thereof. While every possible output remains unlikely compared to uniform randomness, the quantum device naturally biases its results toward specific patterns dictated by these interference effects, creating a distribution that is extremely difficult for classical computers to replicate quickly. Verifying such claims requires rigorous statistical tests because one must ensure the result isn't merely luck and rule out faster-than-expected classical spoofing methods. Google utilized a test called the linear cross-entropy benchmark, which involves calculating probabilities on a classical computer for a subset of generated samples to check if they align with the expected distribution more often than random chance would allow. This verification process is computationally expensive; running it requires roughly $2^{53}$ calculations, amounting to about nine quadrillion operations. Interestingly, this specific number represents the upper limit where current supercomputers like Summit at Oak Ridge National Lab can barely keep up with the quantum device using much more time. Aaronson notes that having too many qubits, such as 100 or more, actually hinders verification because classical computers would no longer be able to simulate the results in any reasonable timeframe, rendering the experiment unverifiable by current standards. Theoretical computer science provides further evidence against the possibility of a fast classical algorithm spoofing these experiments through mathematical reductions and complexity theory arguments. While scientists cannot definitively prove that simulating quantum mechanics is hard without resolving major open problems like P versus NP, they can show that if such an efficient classical simulation existed, it would imply breakthroughs in other areas believed to be computationally difficult. Researchers have exhaustively tested known methods for simulating quantum circuits and confirmed their exponential scaling across the specific parameters used by Google's experiment. Consequently, while absolute proof remains elusive due to unknown algorithms, the consensus is that any successful spoofing method would need to rely on techniques vastly unlike anything currently known in computer science, thereby validating the claim of quantum supremacy based on empirical evidence supported by theoretical constraints.
Read the full video transcript
Google mmm announced with their work in
the paper in nature with quantum
supremacy yes can you describe again
back to the basic what is perhaps not so
basic what is quantum supremacy
absolutely so quantum supremacy is a
term that was coined by again by John
Prescott in 2012 not not everyone likes
the name you know but uh you know it's
sort of stuck you know we don't we sort
of haven't found a better alternative
quantum computational compare mister
that's right that's right and but but
the basic idea is actually one that goes
all the way back to the beginnings of
quantum computing when richard fineman
and david deutsch people like that we're
talking about it in the early 80s
and-and-and and quantum supremacy just
refers to sort of the point in history
when you can first use a quantum
computer to do some well-defined task
much faster than any known algorithm
running on any of the classical
computers that are available okay so you
know notice that I did not say a useful
task okay you know it could be something
completely artificial but it's important
that the task be well-defined so in
other words you know there is it is
something that has right and wrong
answers you know and that are knowable
independently of this device right and
we can then you know run the device see
if it gets the right answer or not can
you clarify a small point you said much
faster than a classical implementation
what about sort of what about the space
with where the class there's no there's
not it doesn't even exist a classical
algorithm so so so so maybe I should
clarify everything that a quantum
computer can do a classical computer can
also eventually do okay and the reason
why we know that is that a a classical
computer could always you know if it had
no limits of time and memory it could
always just store the entire quantum
state you know of your you know of the
quantum great store in a list of all the
amplitudes you know in the state of the
quantum
pewter and then just you know do some
linear algebra to just update that state
right and so so anything that quantum
computers can do can also be done by
classical computers albeit exponentially
slower okay so I on computers don't go
to some magical place outside of Alan
Turing's a definition of computation
precisely they do not solve the halting
problem they cannot solve anything that
is uncomputable in how an Turing sense
what they what we think they do change
is what is efficiently computable okay
and you know since the 1960s you know
the word efficiently you know as well as
been a central word in computer science
but it's sort of a code word for
something technical which is basically
with polynomial scaling you know that as
you get to larger and larger inputs you
would like an algorithm that uses an
amount of time that scales only like the
size of the input raised to some power
and not exponentially with the size of
the input right yeah so I do hope we get
to talk again because one of the many
topics that there's probably several
hours with a competent conversation on
is complexity which you probably won't
even get a chance to touch today but you
briefly mentioned it but let's let's
maybe try to continue so you said the
definition of quantum supremacy is
basically design is achieving a place
where much faster on a formal quantum
computer is much faster on a formal
well-defined problem yes it's not that
is or isn't useful yeah yeah yeah right
right and and I would say that we really
want three things right we want first of
all the quantum computer to be much
faster just in the literal sense of like
number of seconds you know it's a
solving this you know well-defined
you know problem secondly we want it to
be sort of a you know for a problem
where we really believe that a quantum
computer has better scaling behavior
right so it's not just an incidental you
know matter of hardware but it's that
you know as you went to larger and
larger inputs you know the classical
scaling would be exponential and the
scaling for the quantum algorithm would
only
be polynomial and then thirdly we want
the first thing the actual observed
speed-up to only be explainable in terms
of the scaling behavior right so you
know I want I want you know a real world
you know a real problem to get solved
let's say by a quantum computer with 50
cubits or so and for no one to be able
to explain that in any way other than
well you know the to the this this
computer involved a quantum state with
two to the fiftieth power amplitudes and
you know a classical simulation at least
any that we know today
would require keeping track of 2 to the
50th numbers and this is the reason why
it was faster so the intuition is that
then if you demonstrate on 50 cubits
then once you get to 100 cubits then
it'll be even much more faster precisely
precisely yeah and and you know and and
and quantum supremacy does not require
error correction right we don't you know
we don't have you could say true
scalability yet or true you know uh
error correction yet but you could say
quantum supremacy is already enough by
itself to refute the skeptics who said a
quantum computer will never outperform a
classical computer for anything but one
demonstrate quantum yeah supremacy
and two what's up with these new news
articles I'm reading that Google did so
yeah well what they actually do great
great questions because now you get into
actually you know a lot of the work that
I've you know I and my students have
been doing for the last decade which was
precisely about how do you demonstrate
quantum supremacy using technologies
that you know we thought would be
available in the near future and so one
of the main things that we realized
around 2011 and this was me and my
student alex arkhipov at MIT at the time
and independently of some others
including a Bremner josa and shepard ok
and the realization that we came to was
that if you just want to prove that a
quantum
computer is faster you know and not do
something useful with it
then there are huge advantages to sort
of switching your attention from
problems like factoring numbers that
have a single right answer to what we
call sampling problems so these are
problems where the goal is just to
output a sample from some probability
distribution let's say over strings of
50 bits right so there are you know many
many many possible valid outputs you
know your computer will probably never
even produce the same output twice
you know if it's running as even you
know assuming it's running perfectly
okay but but the key is that some
outputs are supposed to be likelier than
other ones so sorry to clarify is there
a set of outputs that are valid and said
they're not or is it more that the
distribution of a particular kind of
output is more is the specific
distribution yeah there's there's
there's a specific distribution that
you're trying to hit right or you know
that you're trying to sample from now
there are a lot of questions about this
you know how do you do that right now
now how you how you do it you know it
turns out that with a quantum computer
even with the noisy quantum computers
that we have now that we have today what
you can do is basically just apply a
randomly chosen sequence of operations
all right so we you know we in sometimes
you know we you know that part is almost
trivial right we just sort of get the
qubits to interact in some random way
although a sort of precisely specified
random way so we can repeat the exact
same random sequence of interactions
again and get another sample from that
same distribution and what this does is
it basically well it creates a lot of
garbage but you know very specific
garbage right so you know of all of the
so if we're gonna talk about google's
device there were 53 qubits there okay
and so there are two to the 53 power
possible outputs now for some of those
outputs you know there are there was a
little bit more destructive interference
in their amplitude okay so their
amplitudes were a little bit small
and for others there was a little more
constructive interference
you know the amplitudes were a little
bit more aligned with each other you
know that and so those those that were a
little bit likelier okay all of the
outputs are exponentially unlikely but
some are let's say two times or three
times you know unlikely er than others
okay and so so you can define you know
the sequence of operations that gives
rise to this probability distribution
okay now the next question would be well
how do you you know even if you're
sampling from and how do you verify that
right how do you exam how do you know
and so my students and I and also the
people at Google we're doing the
experiment came up with statistical
tests that you can apply to the outputs
in order to try to verify you know what
is you know that that at least that some
hard problem is being solved the the
test that Google ended up using was
something that they called the linear
cross entropy benchmark okay and it's
basically you know so that the drawback
of this test is that it requires like it
requires you to do a two to the 53 time
calculation with your classical computer
okay so it's very expensive to do the
test on a classical computer the good
news I think of a numbers - it's about
nine quadrillion okay it doesn't help
what well you want any like scientific
notation I don't know what I mean it
yeah it is it is it is adjustable to run
honest yes that we will come back to
that it is just barely possible to run
we think on the largest supercomputer
that currently exists on earth which is
called summit at Oak Ridge National Lab
okay
so I ironically for this type of
experiment we don't want a hundred
qubits okay because with a hundred
qubits even if it works we don't know
how to verify the results okay so we
want you know a number of qubits that is
enough that you know click the biggest
classical computers on earth will have
to sweat you know and we'll just barely
you know be able to keep up
with the quantum computer you know using
much more time but they will still be
able to do it in order that we can
verify that was just where the 53 comes
from for the cube a well I mean I mean I
mean I mean I mean that's also that sort
of you know the mote I mean that's
that's that's sort of where they are now
in terms of scaling you know and then
you know soon you know that point will
be passed and and then when you get to
larger numbers of qubits then you know
these these types of sampling
experiments will no longer be so
interesting because we won't even be
able to verify the results and we'll
have to switch to other types of
computation so with it with the sampling
thing you know so so the test that
Google applied with this linear
cross-entropy benchmark would basically
just take the samples that were
generated which are you know a very
small subset of all the possible samples
that there are but for those you
calculate with your classical computer
the probabilities that they should have
been output and you see are those
probabilities like larger than the mean
you know so is the quantum computer bias
toward outputting the strings that it's
you know that you want it to be biased
toward okay and then finally we come to
a very crucial question which is
supposing that it does that well how do
we know that a classical computer could
not have quickly done the same thing
right how do we know that you know this
couldn't have been spoofed by a
classical computer right and so well the
first answer is we don't know for sure
because you know this takes us into
questions of complexity theory you know
you know the I mean questions on the of
the magnitude of the P versus NP
question and that right we you know we
don't know how to rule out definitively
that there could be fast classical
algorithms for you know even simulating
quantum mechanics and for you know
simulating experiments like these but we
can give some evidence against that
possibility and that was sort of the you
know the main thrust of a lot of the
work that my colleagues and I did you
know over the last decade which is then
sort of in around 2015 or so what led to
Google deciding to do this experiment so
is the kind of evidence you first of all
the hard P equals NP problem the
and the kind of evidence the year were
looking at is that something you come to
on a sheet of paper or is this something
are these empirical experiments it's
it's math for the most part I mean it
you know it's also trot you know you
know we have a bunch of methods that are
known for simulating quantum circuits or
you know quantum computations with
classical computers and so we have to
try them all out and make sure that you
know they don't work you know make sure
that they have exponential scaling on on
you know these problems and and not just
theoretically but with the actual range
of parameters that are actually you know
arising in Google's experiment okay so
so there is an empirical component to it
right but now on on the theoretical side
you know what basically what we know how
to do in theoretical computer science
and computational complexity is you know
we don't know how to prove that most of
the problems we care about are hard but
we know how to pass the blame to someone
else yeah we know how to say well look
you know I can't prove that this problem
is hard but if it is easy then all these
other things that you know you know
first you you probably we're much more
confident or we're hard that then those
would be easy as well okay so so we can
give what are called reductions this has
been the basic strategy in you know an
NP completeness right in in all of
theoretical computer science and
cryptography since the 1970s really and
so we were able to give some reduction
evidence for the hardness of simulating
these sampling experiments the sampling
based quantum supremacy experiments so
reduction evidence is not as
satisfactory as it should be one of the
biggest open problems in this area is to
make it better but you know we can do
something you know certainly we can say
that you know if there is a fast
classical algorithm to spoof these
experiments then it has to be very very
unlike any of the algorithms that we
know which
kind of in the same kind of space of
reasoning that people say P equal not
equals NP yeah it is it's in the same
spirit
you