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)
Another Scott debunks some common misconceptions about quantum computing, covering P vs NP, the problem of the requirement of observation for useful results, and describing quantum computing as a strange hammer in search of nails. Perhaps unsurprisingly, we don't learn much about what problems quantum computing can help us solve.