Translator: Ilze Garda Reviewer: Denise RQ

When I was in grade five or six, I liked puzzles like this one.

What is the last digit of number 17 to the power of 1,000?

At first, this looks like an impossible question.

How would you ever do that?

But actually it has a simple and nice solution.

So these interesting puzzles led me to various mathematics competitions.

I liked solving puzzles, and I also liked competing with others.

Then I became a scientist, mathematician, and I'm still solving puzzles,

except that now those puzzles are difficult scientific problems

for which nobody in the world knows the answer,

and maybe I will be the first to solve them.

(Applause)

Another thing that I liked in grade five or six was programming.

I came across this book,

- this is a popular book about programming -

and I really liked the idea of programming

except that it was year 1986, it was Soviet Latvia,

nobody had computers at home.

So I could only write programs on paper, and I did indeed write solutions

to most of the exercises in this book on paper,

without being able to try them on an actual computer.

(Laughter) (Applause)

Ironically, this is a bit like what I'm doing now.

(Laughter)

Later, I finished school, I finished university,

and then I decided to do a PhD in computer science, and I went

to the University of California, Berkeley.

I learned many new things when I was at Berkeley,

and one of them was quantum computers.

And I don't have a quantum computer.

Nobody in the world has a fully-functional quantum computer.

But I am programming them, I am trying to figure out

what one would be able to do when one builds quantum computers.

Today I will tell you the story of quantum computers,

how they emerged, what they can do,

and how far we are with building one.

This story begins in 1981

with the famous physicist Richard Feynman.

Feynman was a brilliant physicist, Nobel Prize Laureate.

He was also excellent at explaining physics to anyone,

and he also had an excellent sense of humor.

All that together made him

the biggest personality in physics at this time.

At the International Congress on Theoretical Physics

he asked a question: can we simulate physics on a computer?

The answer was: not exactly.

A part of physics is quantum physics

which studies behavior of atoms and particles.

If you try to simulate quantum physics on a computer,

there is a major problem.

As Feynman said,

the full description of quantum physics has so many variables

that you can't keep track of them all.

Here's what he meant.

Let's say that one particle is described by two variables.

Then to describe 30 particles,

you need the number of variables that is two to the power of 30.

That's roughly one billion.

Well, computers have that much memory, even though that's a big number.

But if you go to 100 particles,

then the number of variables becomes two to the power of 100

which is roughly one with 30 zeros.

Computers don't have so much memory, and they never will.

Actually many physicists knew about this problem,

but Feynman was the first who suggested something else.

He suggested that one can turn a problem into an effect.

If quantum physics is too hard for normal computers,

maybe we can use it to build better computers.

What happened next?

Immediately, nothing happened.

The idea of quantum computers was so new and unusual

that nobody knew what to do next.

But eventually, Feynman managed to inspire a small number of people

who started thinking: what would a quantum computer look like?

Now, let me take a step back from quantum computers to quantum physics.

Quantum physics emerged about 100 years ago

from trying to understand various puzzles about the nature of matter and light.

And one puzzle was color.

Why is this circle red and not green?

Answering this puzzle involved realizing that atoms and particles behave

according to different physical laws from what we see in our everyday life.

In the Solar System, we have the Sun, and we have the Earth rotating around it.

In an atom, we have atom's nucleus, and we have electrons rotating around it.

But there is one difference between them

discovered by a Danish physicist Niels Bohr exactly 100 years ago.

In the Solar System, the Earth can be at any distance from the Sun,

it can be where it is now, it can be 10 meters closer.

Nothing in physics prohibits that.

In contrast, in an atom, electrons have certain orbits,

and they can be in those orbits, but not in between them.

And a particle of light, or photon, might hit an electron,

and then it would jump from one orbit to another.

The color of the photon corresponds to the distance between these two orbits,

and each atom can absorb only the light that corresponds

to the difference between two orbits of the electron in this atom.

This explains why each atom absorbs only the light of certain colors,

and why objects have color.

Around the same time, other puzzles about nature were solved.

Eventually, that led to the theory of quantum mechanics

which explained all of that from a few very simple basic principles.

From the moment when it was invented,

quantum mechanics was an object of an intense debate.

A couple of quotes from very famous physicists:

"Anyone not shocked by quantum mechanics has not yet understood it."

"Nobody understands quantum mechanics."

(Laughter)

These quotes were said

by the best physicists of the 20th century,

but I completely disagree with that.

Quantum mechanics has a complicated and twisted history

consisting of many steps.

When people learn quantum mechanics,

usually they learn all this complicated history,

and then they think it's complicated.

But if you take the final result, it's not that complicated.

One has to assume that certain things work differently than in usual physics.

There is a couple of such assumptions,

but once you make those assumptions,

you get a mathematical theory that is simple and beautiful.

Now, back from quantum mechanics to quantum computers.

A quantum computer computes according to quantum mechanics.

It encodes information into quantum particles,

it manipulates them and computes by doing that.

Quantum computers would be able to do many things

faster than ordinary computers.

The one that is heard most frequently

in newspapers and popular science magazines

is code breaking.

If the secret service of some country builds a quantum computer,

they will be able to read all secret communication over the Internet.

But there are many other fascinating things

that quantum computers can do.

They will be useful to scientists for doing virtual experiments.

You could use a quantum computer to model

how atoms behave at very cold temperatures

without actually cooling atoms to those temperatures.

Or you could model chemical processes on a quantum computer

because every chemical process is essentially a quantum object.

Perhaps, this would eventually lead to new chemicals or drugs

which would be discovered

by first modeling them on a quantum computer.

Another thing for which quantum computers would be useful

is searching large amounts of data.

Let's say that you have a big phone book,

and you want to find out who has this phone number.

As usual, a phone book number is ordered by names of people rather than by numbers.

So, if the phone book has one million phone numbers,

then, to find this number, you have to look through them all

and it might take you one million steps.

A quantum computer could do this faster.

If this was a quantum phone book, one would be able to search it in the time

that is roughly the square root of the number of phone numbers:

1,000 instead of 1,000,000.

And more generally, quantum computers would be useful

whenever you have to search for a needle in a haystack,

whether this needle is a person with this phone number

or something entirely different.

Here's another example which this time is something that I discovered myself.

Let's say that we have a large number of numbers

and we want to find two equal numbers among them.

If there were one million numbers here and only two of them would be equal,

this would be a difficult task.

A normal computer might have to look at all one million numbers

before it finds two equal ones.

A quantum computer would be able to do that faster.

And there is an interesting story how I discovered that.

It was winter 2003.

I was taking a bus from Riga to my parents' home

about 100 kilometers east of here.

It was quiet and dark on the bus,

I was thinking of various things, and then an idea occurred to me:

what if we use a quantum particle

to work on the sets of those numbers to solve this problem?

Then I spent next three or four months working out all the mathematical details

and verifying whether it indeed works.

And it did.

But, as you see,

the first spark of imagination can occur in the most unexpected places.

Now, you're probably wondering:

why are quantum computers better than normal computers?

There are two basic effects:

quantum parallelism and quantum interference.

First, quantum parallelism.

Any computer, ordinary or quantum,

processes information by encoding it into zeros and ones.

If you have 20 zeros and ones

that gives you roughly one million numbers.

An ordinary computer can be in one of those one million states.

A quantum computer can be

in a quantum combination of these one million states

called superposition.

A quantum computer can do this dual computation

in this combination of one million states.

So what would happen is that a quantum computer would do

one million computations at the same time.

It's almost like having one million computers working for you,

except that you don't need to build one million computers.

You can take 20 particles and use the one million states that they have.

The second effect is quantum interference.

Let's say that there are two ways to get to the destination,

and you take each of them with probability 1/4.

What is the probability that you will get to the destination?

In the normal world, that's 1/4 plus 1/4 is 1/2.

But, if instead of a car you had a quantum particle,

then, a quantum particle taking one path

could interfere with itself taking the other path.

Then, 1/4 plus 1/4 could add up to 1.

Usually, these two effects are used together.

Quantum parallelism is used to do

a large number of computations at the same time,

and interference is used to combine the results into one.

Here's how a prototype quantum computer looks like.

This is a device called the ion trap from the University of Innsbruck, Austria,

which is one of the world leaders in this technology.

An ion trap is a device for capturing ions.

An ion is an atom that has lost one or more of its electrons.

An ion trap uses electric and magnetic fields

to capture individual ions and to keep them at very precise locations.

By using this device, the group in Innsbruck has captured

14 ions and arranged them on a line at regular spaces.

Then, you can shine a light on those 14 ions,

encode information into them, and compute with this information.

One interesting thing is that actually there are many ways

of building quantum computers.

Instead of ions, one can use particles of light.

And actually, one can open a physics textbook,

and there will be five or ten other ways of doing that.

Quantum mechanics describes many physical systems,

and any of them can be used to do quantum computation.

The big challenge is to scale up either of those technologies

from 14 ions to hundreds, thousands, tens of thousands of particles.

And there is a very difficult task.

What one has to do is one has to learn

how to control single particles with very, very high precision.

And that's very difficult.

On the other hand, that it is also a very central task in physics,

and physicists would be trying to do that,

even if nobody had invented quantum computers.

When we succeed with that,

it will also be useful for many other purposes.

Another benefit of quantum computing

is that it provides a new way of looking at physics.

Actually, I am not a physicist, I am a computer scientist

who did not know [about] quantum mechanics until going to Berkeley.

The way I learned quantum mechanics is by first learning quantum computing

and only then learning quantum mechanics.

And I think that's the simplest way of learning quantum mechanics,

and maybe in 20 years that would be the standard way of doing that

because quantum computing illuminates the basic ideas of quantum mechanics

like nothing else.

And for myself, the big question is still:

what else can we do with a quantum computer?

I think there are many other applications for quantum computers

that we have not discovered yet.

Some of them might be very unexpected,

and I hope to discover them together with my group of researchers and students.

Maybe there is a killer application of quantum computers

about which no one knows yet.

My dream would be to discover it over the next few years here in Riga.

Thanks.

(Applause)