Translator: Christoph Sträter Reviewer: Claire Ghyselen
Thank you so much!
I study the capabilities and also the limits of quantum computers.
I like to call it the study of what we can’t do
even with computers that we don’t have.
(Laughter)
As a result, I’m sometimes asked by the person next to me on the plane:
“What is this, quantum computer?”
I say, “Well, it’s a proposed new kind of computer
that would exploit quantum mechanics.”
Then they say, “But why?”
“Well, you know, quantum mechanics is sort of the basic operating system
that the rest of physics runs on as application programs.
It hasn’t changed at all since the 1920s.
It ought to, we think, let us solve certain problems dramatically faster
than we know how to solve them with today’s computers.”
So then they say, “Well, why does quantum mechanics let you solve things faster?”
You know, it is possible to explain that to a lay audience.
It definitely is.
The only problem is that once you’ve really gotten started explaining it,
by then the plane has already landed.
(Laughter)
So, it’s no surprise
that for more than twenty years,
almost every popular article that’s ever been written on this subject
has taken an easy way out.
It has described quantum computers in ways that sound cool
but are just kind of wrong.
People correctly recognize, I think, just how important this is going to be
for the future of science and technology.
But it’s, sadly, one of the most mispopularized topics in science.
I was delighted when I was invited here, to Dresden,
specifically to talk about what quantum computing is not.
The first thing that it’s not, I guess, is whatever this is.
(Laughter)
When you do a Google image search for quantum computer,
that’s one of the first things that come up.
I’m a theorist, I don’t work in a lab,
but I don’t think that’s what they look like.
Okay, more to the point.
People say, “Well, quantum means small,
so how many times smaller is a quantum computer than today’s computers?”
Or, “It’s supposed to be faster, so how many times faster is it?”
A quantum computer is not just a smaller or faster version of today’s computers.
It represents a fundamentally new way of harnessing nature to do computation.
For certain problems –
adding up numbers, simulating the weather –
a quantum computer may help you little or not at all.
For other problems, a quantum computer could do things in seconds
that, as far as we know,
would take any existing computer longer than the age of the universe.
It all comes down to asymptotics.
What are the famous examples
of problems where a quantum computer gives you these huge speed-ups?
One of them is simulating quantum mechanics itself.
No surprise that a quantum computer helps you there!
But I think if we actually build one
that may actually be the most important economic application.
Because it is useful for designing new drugs,
designing high-temperature superconductors,
designing nano materials, better solar cells, all kinds of things.
The second famous application is that a quantum computer
can efficiently find the prime factors of an enormous positive integer.
Who cares about that?
Well, that and some related problems
would let you break almost all of the cryptography
that we use to protect our data online.
Anytime your web browser has that little padlock icon,
you are using something that a quantum computer could break.
(Laughter)
There are other codes that we don’t know how to break even with a quantum computer,
but those are mostly not the ones that we use today.
So, if you want to factor an n-digit number,
the best algorithms that we know with classical computers
use a number of steps that increases exponentially with n.
An exponential is a function like this one, 2 to the nth power,
which just kind of shoots up and just goes off the slide, out of the building.
(Laughter)
But multiplying two n-digit numbers is a lot easier.
Your computer can do that using only about n squared steps,
or, if you’re more clever, even close to a linear in n number of steps.
What a quantum computer would do is put factoring into that easy class.
So, factoring also would only take about n-squared steps for an n-digit number.
So the advantage over a classical computer is not by some fixed factor
but just becomes more and more enormous as you go to larger and larger numbers
until there’s just no comparison.
As I’ve already indicated,
a quantum computer is not a magic bullet that just solves all problems instantly.
It depends on the problem.
In computer science we like to organize problems into a sort of zoo.
At the bottom, we’ve got P. That stands for polynomial time.
You know, physicists give things much better names –
quark, black hole – but ignore that.
(Laughter)
P is basically all of the problems that are efficiently solvable
by an ordinary digital computer, like the one in your pocket.
NP stands for non-deterministic polynomial time.
That’s the set of all the problems
for which a digital computer could at least quickly recognize an answer
when given one.
But finding the answer might require an astronomical search.
P includes most of what we do with our computers:
multiplying, sorting, finding directions with Google Maps.
NP has many, many things we would love to do,
especially these NP-complete problems, which are the hardest problems in NP,
and that includes almost everything, like industrial optimization,
finance, trying to predict the stock market,
trying to optimize an airline schedule or playing Sudoku.
One of the great unsolved problems of mathematics in this century
is to formally prove that NP is larger than P.
If we were physicists, we would have just called that a law of nature.
But what physicists call a law, we in math have to call a conjecture.
Now, BQP stands for bounded error quantum polynomial time.
That’s the class of all the problems
that are efficiently solvable by a quantum computer,
the quantum generalization of P.
I drew it with this wavy boundary
because everything “quantum” is spooky and weird.
(Laughter)
The big surprise was that BQP contains a few problems, like factoring,
special problems that are neither known nor believed to be in P.
As you can also see from this picture,
BQP is not known nor believed to contain the NP-complete problems.
Can we prove it doesn’t? Well, no.
We can’t even prove that P doesn’t contain them.
But that would require a quantum algorithm
radically unlike any of the ones that we know.
For NP-complete problems,
quantum computers seem to give you some advantage,
like a square root kind of advantage, but probably not an exponential one.
Even quantum computers have limits.
But where do those limits come from?
If you read almost any popular article on this subject, it’ll say something like:
“Unlike a classical computer,
which just has to try every possible answer, one by one,
a quantum computer just tries them all in parallel,
in different parallel universes.”
(Laughter)
That does sound pretty powerful, right?
That does sound like that would crack the NP-complete problems
or whatever else.
The trouble is it is not that simple.
And here’s what the issue is:
In quantum mechanics, you can actually quite easily create
what we call a quantum superposition
over all the possible answers to your problem
even if there are astronomically many of them.
The trouble is if you want it to be useful,
at some point you’ve got to observe yourcomputer to read an answer out.
And if you just measure the superposition of answers not having done anything else,
the laws of quantum mechanics say
that what you’re going to see will be a random answer.
If you just wanted a random answer,
then you could have picked one yourself, with a lot less trouble.
(Laughter)
When people hear that, they say: “Oh, well, then it must be
that the quantum computer is just trying one solution or the other one,
and we simply don’t know which until we look.”
If you’ve ever heard about Schrodinger’s cat:
“Oh, it’s in a superposition of alive and dead states in the box
until you open the box and look.
Then it collapses to one or the other.”
Any ten-year-old who hears that is going to immediately ask:
“Well, why isn’t that just a fancy, pompous way of saying,
‘The cat is either alive or it’s dead, and you don’t know which,
so then you open the box and you look, and then you do know’?”
Then what’s the big deal about quantum mechanics?
Well, it’s not that simple.
The central thing that quantum mechanics says about the world
is that if you have an object that can be in two different distinguishable states,
it can also be in what we call a superposition of those states.
A superposition means I assign a number called an amplitude,
to each possible state.
In everyday life, we could talk about the probability of something happening.
But a probability is always a real number from 0 to 1.
There is never a negative 30% chance of rain tomorrow, that’s just stupid.
But amplitudes can be positive or negative,
in fact, they can even be complex numbers.
Everything else arises from that.
In the famous double slit experiment,
you have a photon that could reach a certain spot on a screen
in two different ways.
But one of those ways contributes a positive amplitude,
and the other way contributes a negative amplitude.
And the result is that they interfere destructively and cancel each other out
so that the photon is never seen there at all.
The amplitudes are used to determine the probability
that you will see something when you look,
but when you don’t look, they can interfere.
With a quantum computation, the goal is always to choreograph things
so that for each wrong answer,
some of the paths leading there have positive amplitude
and others have negative amplitude so they cancel each other out,
whereas the paths leading to the right answer should reinforce,
all have the same sign,
and when you measure, the right answer will be seen with high probability.
So that’s the strange hammer that quantum mechanics gives us
and the goal of quantum computing theorists
is basically to figure out what nails that can hit.
Quantum computing, as you’ve probably gathered by now,
is not just some random buzzword
to be added like a seasoning onto whatever is your tech startup idea.
It helps a lot with certain things and less so with others.
Figuring out which is which has been a fascinating challenge.
The other thing that quantum computing is not is that it’s not science fiction.
So what I’ve shown here is a chip
that was recently built by a group at Google.
This has a bunch of very high-quality interacting,
superconducting quantum bits or “qubits”:
systems that can be in a superposition of states representing 0 and 1.
Google’s current chip has about 22 qubits.
But they say that within the next year they’re planning to scale up to 49 qubits.
And there are other groups in Innsbruck, Austria,
and IBM in Maryland,
that have parallel efforts with all kinds of physical platforms.
Now, 50 cubits is probably not enough yet to do anything useful.
But it should be enough, we think,
to do something that at least is classically hard.
So, already within a few years, we may achieve what I think of
as the number one application of quantum computing,
which is just to disprove the people who say that it is impossible.
(Laughter)
Now, could it be impossible for some deep reason that no one has figured out yet?
Of course, but in some sense, that’s the more exciting possibility.
Because that’s the possibility
that means that we have to rewrite all the physics textbooks.
At this point,
I think that idea that, yes, eventually, with enough money and effort
you could build a quantum computer, and it will work as this theory says
and give huge speed-ups for certain things,
that’s the boring conservative possibility.
That’s the one that doesn’t require
changing what we already believe about physics.
So, embrace the future!
I’m not typically a huge fan
of these slogans that kind of everyone agrees with.
(Laughter)
I’m coming here from the US.
I don’t know if any of you have been reading the news for the last year or so.
Not everyone in the US has been totally into embracing the future,
which is kind of a pity.
(Laughter)
(Applause)
I’m sorry about that,
(Laughter)
but I do think that we should embrace the future.
But if we want to do that, I think a crucial first step
is to accurately learn and report what’s already known in the present.
Thank you.
(Applause)
Thank you so much!
I study the capabilities and also the limits of quantum computers.
I like to call it the study of what we can’t do
even with computers that we don’t have.
(Laughter)
As a result, I’m sometimes asked by the person next to me on the plane:
“What is this, quantum computer?”
I say, “Well, it’s a proposed new kind of computer
that would exploit quantum mechanics.”
Then they say, “But why?”
“Well, you know, quantum mechanics is sort of the basic operating system
that the rest of physics runs on as application programs.
It hasn’t changed at all since the 1920s.
It ought to, we think, let us solve certain problems dramatically faster
than we know how to solve them with today’s computers.”
So then they say, “Well, why does quantum mechanics let you solve things faster?”
You know, it is possible to explain that to a lay audience.
It definitely is.
The only problem is that once you’ve really gotten started explaining it,
by then the plane has already landed.
(Laughter)
So, it’s no surprise
that for more than twenty years,
almost every popular article that’s ever been written on this subject
has taken an easy way out.
It has described quantum computers in ways that sound cool
but are just kind of wrong.
People correctly recognize, I think, just how important this is going to be
for the future of science and technology.
But it’s, sadly, one of the most mispopularized topics in science.
I was delighted when I was invited here, to Dresden,
specifically to talk about what quantum computing is not.
The first thing that it’s not, I guess, is whatever this is.
(Laughter)
When you do a Google image search for quantum computer,
that’s one of the first things that come up.
I’m a theorist, I don’t work in a lab,
but I don’t think that’s what they look like.
Okay, more to the point.
People say, “Well, quantum means small,
so how many times smaller is a quantum computer than today’s computers?”
Or, “It’s supposed to be faster, so how many times faster is it?”
A quantum computer is not just a smaller or faster version of today’s computers.
It represents a fundamentally new way of harnessing nature to do computation.
For certain problems –
adding up numbers, simulating the weather –
a quantum computer may help you little or not at all.
For other problems, a quantum computer could do things in seconds
that, as far as we know,
would take any existing computer longer than the age of the universe.
It all comes down to asymptotics.
What are the famous examples
of problems where a quantum computer gives you these huge speed-ups?
One of them is simulating quantum mechanics itself.
No surprise that a quantum computer helps you there!
But I think if we actually build one
that may actually be the most important economic application.
Because it is useful for designing new drugs,
designing high-temperature superconductors,
designing nano materials, better solar cells, all kinds of things.
The second famous application is that a quantum computer
can efficiently find the prime factors of an enormous positive integer.
Who cares about that?
Well, that and some related problems
would let you break almost all of the cryptography
that we use to protect our data online.
Anytime your web browser has that little padlock icon,
you are using something that a quantum computer could break.
(Laughter)
There are other codes that we don’t know how to break even with a quantum computer,
but those are mostly not the ones that we use today.
So, if you want to factor an n-digit number,
the best algorithms that we know with classical computers
use a number of steps that increases exponentially with n.
An exponential is a function like this one, 2 to the nth power,
which just kind of shoots up and just goes off the slide, out of the building.
(Laughter)
But multiplying two n-digit numbers is a lot easier.
Your computer can do that using only about n squared steps,
or, if you’re more clever, even close to a linear in n number of steps.
What a quantum computer would do is put factoring into that easy class.
So, factoring also would only take about n-squared steps for an n-digit number.
So the advantage over a classical computer is not by some fixed factor
but just becomes more and more enormous as you go to larger and larger numbers
until there’s just no comparison.
As I’ve already indicated,
a quantum computer is not a magic bullet that just solves all problems instantly.
It depends on the problem.
In computer science we like to organize problems into a sort of zoo.
At the bottom, we’ve got P. That stands for polynomial time.
You know, physicists give things much better names –
quark, black hole – but ignore that.
(Laughter)
P is basically all of the problems that are efficiently solvable
by an ordinary digital computer, like the one in your pocket.
NP stands for non-deterministic polynomial time.
That’s the set of all the problems
for which a digital computer could at least quickly recognize an answer
when given one.
But finding the answer might require an astronomical search.
P includes most of what we do with our computers:
multiplying, sorting, finding directions with Google Maps.
NP has many, many things we would love to do,
especially these NP-complete problems, which are the hardest problems in NP,
and that includes almost everything, like industrial optimization,
finance, trying to predict the stock market,
trying to optimize an airline schedule or playing Sudoku.
One of the great unsolved problems of mathematics in this century
is to formally prove that NP is larger than P.
If we were physicists, we would have just called that a law of nature.
But what physicists call a law, we in math have to call a conjecture.
Now, BQP stands for bounded error quantum polynomial time.
That’s the class of all the problems
that are efficiently solvable by a quantum computer,
the quantum generalization of P.
I drew it with this wavy boundary
because everything “quantum” is spooky and weird.
(Laughter)
The big surprise was that BQP contains a few problems, like factoring,
special problems that are neither known nor believed to be in P.
As you can also see from this picture,
BQP is not known nor believed to contain the NP-complete problems.
Can we prove it doesn’t? Well, no.
We can’t even prove that P doesn’t contain them.
But that would require a quantum algorithm
radically unlike any of the ones that we know.
For NP-complete problems,
quantum computers seem to give you some advantage,
like a square root kind of advantage, but probably not an exponential one.
Even quantum computers have limits.
But where do those limits come from?
If you read almost any popular article on this subject, it’ll say something like:
“Unlike a classical computer,
which just has to try every possible answer, one by one,
a quantum computer just tries them all in parallel,
in different parallel universes.”
(Laughter)
That does sound pretty powerful, right?
That does sound like that would crack the NP-complete problems
or whatever else.
The trouble is it is not that simple.
And here’s what the issue is:
In quantum mechanics, you can actually quite easily create
what we call a quantum superposition
over all the possible answers to your problem
even if there are astronomically many of them.
The trouble is if you want it to be useful,
at some point you’ve got to observe yourcomputer to read an answer out.
And if you just measure the superposition of answers not having done anything else,
the laws of quantum mechanics say
that what you’re going to see will be a random answer.
If you just wanted a random answer,
then you could have picked one yourself, with a lot less trouble.
(Laughter)
When people hear that, they say: “Oh, well, then it must be
that the quantum computer is just trying one solution or the other one,
and we simply don’t know which until we look.”
If you’ve ever heard about Schrodinger’s cat:
“Oh, it’s in a superposition of alive and dead states in the box
until you open the box and look.
Then it collapses to one or the other.”
Any ten-year-old who hears that is going to immediately ask:
“Well, why isn’t that just a fancy, pompous way of saying,
‘The cat is either alive or it’s dead, and you don’t know which,
so then you open the box and you look, and then you do know’?”
Then what’s the big deal about quantum mechanics?
Well, it’s not that simple.
The central thing that quantum mechanics says about the world
is that if you have an object that can be in two different distinguishable states,
it can also be in what we call a superposition of those states.
A superposition means I assign a number called an amplitude,
to each possible state.
In everyday life, we could talk about the probability of something happening.
But a probability is always a real number from 0 to 1.
There is never a negative 30% chance of rain tomorrow, that’s just stupid.
But amplitudes can be positive or negative,
in fact, they can even be complex numbers.
Everything else arises from that.
In the famous double slit experiment,
you have a photon that could reach a certain spot on a screen
in two different ways.
But one of those ways contributes a positive amplitude,
and the other way contributes a negative amplitude.
And the result is that they interfere destructively and cancel each other out
so that the photon is never seen there at all.
The amplitudes are used to determine the probability
that you will see something when you look,
but when you don’t look, they can interfere.
With a quantum computation, the goal is always to choreograph things
so that for each wrong answer,
some of the paths leading there have positive amplitude
and others have negative amplitude so they cancel each other out,
whereas the paths leading to the right answer should reinforce,
all have the same sign,
and when you measure, the right answer will be seen with high probability.
So that’s the strange hammer that quantum mechanics gives us
and the goal of quantum computing theorists
is basically to figure out what nails that can hit.
Quantum computing, as you’ve probably gathered by now,
is not just some random buzzword
to be added like a seasoning onto whatever is your tech startup idea.
It helps a lot with certain things and less so with others.
Figuring out which is which has been a fascinating challenge.
The other thing that quantum computing is not is that it’s not science fiction.
So what I’ve shown here is a chip
that was recently built by a group at Google.
This has a bunch of very high-quality interacting,
superconducting quantum bits or “qubits”:
systems that can be in a superposition of states representing 0 and 1.
Google’s current chip has about 22 qubits.
But they say that within the next year they’re planning to scale up to 49 qubits.
And there are other groups in Innsbruck, Austria,
and IBM in Maryland,
that have parallel efforts with all kinds of physical platforms.
Now, 50 cubits is probably not enough yet to do anything useful.
But it should be enough, we think,
to do something that at least is classically hard.
So, already within a few years, we may achieve what I think of
as the number one application of quantum computing,
which is just to disprove the people who say that it is impossible.
(Laughter)
Now, could it be impossible for some deep reason that no one has figured out yet?
Of course, but in some sense, that’s the more exciting possibility.
Because that’s the possibility
that means that we have to rewrite all the physics textbooks.
At this point,
I think that idea that, yes, eventually, with enough money and effort
you could build a quantum computer, and it will work as this theory says
and give huge speed-ups for certain things,
that’s the boring conservative possibility.
That’s the one that doesn’t require
changing what we already believe about physics.
So, embrace the future!
I’m not typically a huge fan
of these slogans that kind of everyone agrees with.
(Laughter)
I’m coming here from the US.
I don’t know if any of you have been reading the news for the last year or so.
Not everyone in the US has been totally into embracing the future,
which is kind of a pity.
(Laughter)
(Applause)
I’m sorry about that,
(Laughter)
but I do think that we should embrace the future.
But if we want to do that, I think a crucial first step
is to accurately learn and report what’s already known in the present.
Thank you.
(Applause)
Please follow and like us: