cc
>> Tom Zinnen: Welcome, everybody, to Wednesday Nite at the Lab.
I'm Tom Zinnen. I work here at the
UW Biotechnology Center, and I also work for UW Extension
Cooperative Extension.
On behalf of those folks and the Science Alliance and Wisconsin
Alumni Association, thanks again Public Television and Wisconsin
for coming to Wednesday Nite at the Lab. We do this every Wednesday
night, 50 times a year. Tonight I'm delighted to be able to introduce to you
He's with the Department Marty Lichtman.
of Physics here at UW Madison. He'll be talking about
to Quantum Computing." "A Historical Introduction
A little more... He holds a SBC, which I think is like a BSC, only it's from Brown University.
[LAUGHTER] >> What's that? >> A little more highfalutin. >> Highfalutin, excuse me.
From Brown University in Providence, the one in Rhode Island.
And he's got a master of
aeronautics and astronautics from Stanford University, and he's currently a PhD grad
student here at UW Madison. His previous adventures include growing up in Manhattan.
Yes, Kansas, New York. The one in Kansas?
>> Kansas, New York, okay. [LAUGHTER]
only she was from Lawrence. Co-founding a surgical robotics company and working in the Because she's from Kansas
rockets. aerospace industry on hybrid
in his age division. Marty is also a short track speed skater and is the current Wisconsin state champion
What is your age division? Never mind. >> Not going to answer that one!
It's not every day
that we get to have a topic that baffled Einstein. [LAUGHTER]
So I'm really looking forward to seeing how Marty handles the whole issue of quantum things,
Please join me in welcoming Marty to Wednesday Nite at the especially quantum computing.
Lab. [APPLAUSE]
Marty Lichtman: Hi. Thank you for coming on this
So as Tom said, I'm going to lovely day. You chose to be here.
talk to you about quantum computing which is a wonderful magical device, the quantum
computer, and as I'll explain it
can do pretty much everything. It slices, it dices, it factors numbers in polynomial time.
And I'm going to walk you through this in what I call a sort of historical introduction because I think that that's a
good way to talk about what we
mean by the quantum computer is by comparing it to what is a regular computer.
So first of all, I'm going to start out by giving an example
current computer can already run of why you might want a faster, better computer when your
Halo 3 or whatever it is perfectly well. And then I'm going to go back in
time and I'm going to explain,
I'm going to start with the computer part, and I'm going to explain what exactly we mean by aa computer.g.
And then I'm going to explain why a quantum computer is better, and then I'm going to explain how the quantum computer
works.
We'll get there. And don't worry I will let you
about quantum mechanics right from the very beginning, and know everything you need to know
that's going on including in my lab, as Tom said I'm a graduate then I'm goistudent.lk a little bit about the current research
the physics department. And I'll also mention a little I'm in my second year here in
state of the art is in terms bit about other research that's going on and what the current
group and other groups here at of where we're at with actually building a quantum computer and research that's going on in my
you an example from genetics. Now my lovely wife is there in So I figured we're in the genetics building so I'll give
two things. One, that biologists are the fourth row, and she's a biologist and so I've learned
biology is very complicated. complicated, but the other is that I've learned from her that
This may be a review for some of you, especially if you've been to others of these talks,
but you know that everything
about you is coded on 23 pairs of chromosomes. Of course, that's just the
nature part, of course there's
the nurture. A lot also goes into who you are
But all of the information as you grow up.
that's passed down from your parents is on 23 pairs of chromosomes.
And on those chromosomes
you have sequences of adenine, cytosine, thymine, guanine, ACTG, repeated over and over
again in different patterns.
different possible proteins that are in the human genome. TAll of that boils down to a, very, very compact package.
In each cell you only have
of data, what would it take to 3.3 picograms of actual genetic information in there. And if you look at that in terms
store that on a computer? It's about 800 megabytes which is a bunch but it's not really
that much in terms of today's computers.
800 megabytes, you could fit that on a compact disk.
But things start to get interesting if you look at the
field of bioinformatics. Bioinformatics is what I like to
think of it as data mining in order to cure diseases. And what data mining is,
like Google or another is something typically a company
advertising company would collect a lot of information about you and everyone else all
around the world who uses their websites and they would try and filter that down to figure out
So it's taking a lot of data and what do you want to buy.
they're collecting a lot of information about your DNA and So what the people in bioinformatics are doing is
exposed to, in order to figure also a lot of your life experiences, what you've been
out what causes diseases. What part of it is caused by your genes, what part of it is
caused by environmental factors.
And they can go farther than that in order to try and deduce what drugs are more effective on
people with certain genes because not all drugs work
And beyond that they can equally well on all people, and they're trying to sort out why.
actually, in the future, possibly create custom drugs for
genetic makeup so that those certain people based on their
drugs will be more effective. Now, well I just want to mention that those 3.2 billion
base pairs that you have in you,
billion people on the Earth and doing all the cross-correlations it's not huge, but when you start multiplying that by seven
between it, that starts to become a very large number and
this starts to become a rather
difficult problem. It's still within the realm of
computers but it's getting what we can do today on normal
towards the limit. And where we go even beyond that
at, well, what exactly do those genes do when they code for proteins. So the chemicals that a protein
is composed of is not the end of
the story because what most of the functionality of a protein
So DNA will, through the is is in its shape.
in about 10 microseconds, all of cellular mechanisms, form a string of chemicals that is a protein and then very quickly,
those molecules will fold up into some complicated shape.
does is defined by that shape because it can either be a And most of what the protein
somewhere else, and it's not at all obvious how you go from the DNA sequence to the actual shape it can transport them to
So we try and do this on a of the protein.
computer using computer simulation, and the problem is those 10 microseconds of folding
in nature, it takes 30 years to simulate on your average Intel
So they try and get around this, desktop computer. 30 years.
for example, with parallel computing there's a really cool project called Folding@home.
It's a project out of Stanford
University where you can download a program onto your own
using your own computer, the computer and whenever you're not
idle cycles will be used to help them calculate the folding of these proteins.
And so this is a massive project
that's managed to simulate about a dozen of these proteins and how they fold.
So parallel computing is not
going to get you there. You need something else. And that is the quantum
computer. But let's go back in time for a little bit. Let's go back to this picture.
So I have a question for the
audience. Does anyone think they know what this is a picture of?
Guesses?
>> A graduating class? >> A graduating class?
So this is actually a picture of No, not quite.
But in order to get there, we need to go back a little further first computer. And I will explain why.
So Edmond Halley, in 1682, he saw later what would become known as his comet. This inspired in him a love of
astronomy, and he was quite a good scholar. And he, by the year 1705, he had
in 1682 was the same comet that had been seen every 75 or 76 figure out that what he had seen
And actually up there I have years going all the way back to the year 240 BC.
written 467 BC, since then we've found records of even another sighting that was probably the
same comet. And in order to sort of prove his theory, to be like, you know, obviously this is the same
thing and I'll show you why, he needed to predict when it was going to come back. He needed to say what year is
this comet going to come back,
and then when it showed up people would believe him and say
makes sense. yes, comets are periodic, it all
And he tried to do this in a method that we would call analytically.
And analytically means you come up with one equation that describes how the orbit of the
system. And we know from Kepler's laws comet goes around the solar
that all of the planetary bodies are supposed to go in nice
beautiful ellipses. The problem is they don't because it would only go in an
in the solar system was the sun. ellipse if the only other body
up with one equation to fit to And Halley realized this. He realized that the problem, the reason that he couldn't come
was because the large planets, all the data for all of these comet sightings, 75 or 76 years at a time throughout history,
Jupiter and Saturn, were perturbing the orbit of the comet.
But nevertheless, he couldn't figure out what to do about it
because he was stuck in this motive: I need one beautiful
equation to sort this out.
And he was never able to predict the comet to any better than
So the actual prediction was it's every 75 or 76 years.
left to a French astronomer by the name of Alexis Claude Clairaut, and what Clairaut did
was something very clever.
So he said, okay, we know at a He decided he was going to do a method that we would call numerically.
certain time exactly where the comet was because we had these
reliably where all of the planets were. And at that time they had sNewtons laws, and so they knowy
what the gravitational pull on
that comet is from the sun and all of the large planets. And they could calculate, okay,
at that given time we know where
the planets are, we know how much they're pulling on the comet so we know its
acceleration. So in a short amount of time
very accurately where it would later, say maybe a week or even just a day, they could predict
and the new position of all the planets, which were fairly And then they do it again based on the new position of the comet
could do it again. reliable because they're much larger than the comet, they
They could calculate based on those positions. What is the gravitational pull
on the comet, what is it
acceleration, and tomorrow where will it be? And they do this over and over
and over again and they had to
iterate this forward one day at a time for 75 or 76 years in order to figure out when is the
comet going to come back around again to perihelion, which is the point of closest approach to
And what they had found was that the sun.
it was going to come back in the year 1859, which was interesting
77 years, and when it turned out because it's actually closer to
than one month, that was a that they were right and they had predicted the return of the comet to an accuracy of less
triumph for what we would call the numeric method. So what this picture is, the
only man in the picture in the
back, Professor Edward Charles Pickering, was the director of
And what he saw was the industrial revolution going on the Harvard College Observatory.
in which you took human beings and you put them on an assembly
line and each person was
responsible for one small job. They'd take something, screw it in, pass it to the next person.
And he decided to apply the same
thing to numeric calculations where you would have a team of people each doing one small job.
They would take a number from the person before them, do
probably not even division, addition, subtraction, pass it something easy to it, multiplication, division,
And he hired these teams of all women, and their job description to the next person. One tiny job.
was computer because that's what they did, they did computations.
And these small computations
built up to the large calculations that he needed in order to calculate these
astronomical tables.
So really, in every way that counts, this is the first computer.
Now, of course, people started
using machines in order to automate the tasks that previously humans had been doing
in factories and you can do the same thing with numbers.
in 1822 he proposed to the Royal And the first person to realize that was Charles Babbage, who,
Astronomical Society that he wanted to build a machine to do this.
He never actually completed the machine but his designs were
reconstruction which is at the shown to be completely valid, for example, by this
to the computers that we have Stoday in that it had an. Aninput/output system, it wasrs aninstruction-based, it had ance
separate memory for the program and for the data, and, more importantly, it was programmable.
You could change what it was
the Countess Ada Lovelace, who capable of doing and what calculation it was going to do. One fun thing to note is that
is the daughter of the poet Lord Byron, she's actually considered
programmer because she wrote the world's first computer
algorithms for this machine that didn't even work. But her algorithms were
perfectly valid.
Ada, and it was only three years And she was honored in the year 1960, one of the first computer languages was named after her,
after Fortran, which was the first computer language.
mechanical computers were made So of course eventually
a minute this is sort of a functional. And people outside the field of astronomy began to realize wait
useful method that we can use for other stuff, in particular for military uses.
And this is a German example
which sort of speaks to that. Well, the US had its own hand in that and upped the ante a little
bit where, during World War II, the US Army commissioned ENIAC, the Electronic Numerical
And this was designed at the Integrator and Computer.
University of Pennsylvania by John Mauchly and Presper Eckert, and it was not actually, they
funded it for the purpose of
calculating artillery ballistics, which is to say that if you've got a large gun and
you know how much wind there is and how far away the person you're trying to shoot is, you
that tells you what angle do I want to have a look up table
point my gun at and how much charge do I put in it in order
And it's actually, when you take to hit that person.
turn out all these numbers for into account the wind, it's a fairly complicated problem. So they wanted a computer to
all their various guns that they could distribute to the army. And it was not actually
completed until 1946, by which
time, of course, the war was over. However, the programmable nature
of ENIAC made it really useful. It was actually operated until
1955 because it could be applied to all sorts of different
problems. And a nine-year life span is
PC probably lasted. Now, all these computers actually pretty good if you think about how long your last
basically the same thing as your modern computer they've just
gotten faster and faster
according to what's called Moore's Law which says that every 18 months computers get
twice as fast and twice as small
and twice as cheap. But they can do all the same calculations.
Now, we call this being Turing
complete. Being Turing complete means that all these computers are
equivalent to a thought experiment by Alan Turing.
He came up with in 1936 which is a really boiled down version of
the computer. And it only has a couple of elements. I'm going to use the mouse so
that this will show up on the video here, but we have here a
tape and that tape has some data on it.
Ones and zeros in a row.
And then we've got a head, and the head can move back and
And it can only read the data that's next to it. forth.
It could be just a sequence of And the head has what we call a state.
numbers. And then there's some instructions, and the
instructions tell this machine
the head and what is the what to do. And the instructions are only based on what is the state of
adjacent data. And what the instructions can be
the head, write a different piece of data to the tape next things like change the state of
And using those basic elements, you actually can do all of the to it or move the head. And that's it.
calculations that any modern computer is capable of.
This was formalized by Alonzo Church in the Church-Turing thesis, which basically says
is computable by a Turing machine. that anything that is computable
the idea that the hardware And at the heart of the Church-Turing thesis, this is
doesn't matter, that the human computer, the Babbage difference
Duo, that they are all basically engine, ENIAC, your Intel Core 2
equivalent and some might be faster than others. Now, in the last 25 years or so
physicists have thrown their
hats into the computer science arena, and we've decided that that is not the entire story,
that the hardware does, in fact,
follows, dispute the matter. Enter the quantum computer. And I'm not going to, in what
essentially the same things, completeness of what is computable by a Turing machine. A quantum computer can compute
however, there are certain reasonable sized problems which would take a supercomputer the
size of the Earth longer than the lifetime of the universe to calculate that is reasonably
in your lifetime. Now, a computer is not much good sized quantum computer could do
So I consider this a fundamental to you if it can't give you the answers before you're dead.
difference in capability. That quantum computers for certain problems are so much
faster that it makes possible in
this universe problems that a regular computer could not do. The history of the quantum
computer, like many things in physics, goes back
titled Simulating Physics With to Richard Feynman. Richard Feynman, in a talk
Computers, he proposed this quandary that was really disturbing him, that it had been
proven that in order to simulate
a physical system with all of the full laws of quantum mechanics that on a regular
computer the number of bits that
it would require, or the amount of information storage that it takes to simulate that system,
is exponentially larger than the
number of particles in the system itself.
information at the atomic or So even if you were storing
even subatomic level, you still would need a computer that was massively larger than the system
you're trying to simulate.
And he said now wait a minute, nature can do it. If you want to know what happens
in a physical system like shaking up this glass of the
water, all nature needs is the particles that are in this
bottle in order to figure it
out. So he said there must be some mode of logic that we're
missing.
to another as his logical And what heelements. was to use And he had a really interesting trathought because he was aate
theoretical physicist that like many theoretical physicists has a lot of problems with the idea of quantum mechanics because
it's weird. And he suggested that if we are able to build this thing, first of all it will be wonderfully
useful to physicists because
we'll be able to figure out what will go on in a lot of
physical systems. But also, by looking at how the actual device works once we've situations, simulate a lot of
teach us something about quantum built it, it might actually
mechanics. The next step in the evolution
three years later. of the quantum computer was in
David Deutsch figured out that actually the quantum computer that Feynman had proposed would
be useful for more than just
simulating physical systems, that it actually was the
of the Turing machine. universal computer in the sense
And he called this a quantum Turing machine but that it was
problems that a Turing machine capable of solving all the same
would be able to solve. Now, this didn't really go anywhere.
It was interesting to physicists
little bit of a nerdy and mafascination.puter scientists. But it was still sort of a
Until, in 1994, Peter Shor came up with Shor's algorithm. And what Shor's algorithm does wouldn't that be cool.
numbers and it factors them into is it takes large composite
their prime factors. Now this also just seems like a kind of esoteric thing that why
is that interesting?
Well, the reason that it's interesting is because all
commerce, the security of all financial transactions, is based Internet security, all Internet
on the notion that factoring numbers into their prime factors
is difficult. So this was a shocker because all the sudden people said wait a minute, if we can build one of
these things, that changes
everything. And all the sudden there was funding for it because every
government wanted one.
So this was sort of when really things started ramping up with people really wanting to build a
quantum computer. Now, I'm going to pause for a minute to explain how the quantum computer works, and in
order to do that I need to teach
you a little quantum mechanics. So, the most famous example in quantum mechanics, I think,
is Schrodinger's cat. Most of you have probably heard of this but what the details of the setup are, this is a thought
experiment by Edwin Schrodinger,
and he was a man who did not like cats.
the chair of our department in I actually had a discussion with
which he told me that they had looked into hiring Schrodinger
moral issues. [LAUGHTER] but they couldn't because of
But the way that Schrodinger's Not sure exactly what the details of that were.
cat experiment works is you take a small amount of radioactive material, not enough that it can
actually hurt anyone, not enough
to hurt you, not even enough to hurt the cat, but what radioactive material does is it
emits particles at completely random intervals. That's what makes it
particles. radioactive, the emitting of
a Geiger counter, and the Geiger So you take that and you put it in the box. And then also in the box you put
counter sets off a click every time it sees an emitted particle.
And you hook up the Geiger
counter to a mechanical hammer and underneath the hammer you put a capsule of poisoned
cyanide gas and you put that all
in the box and you put a cat in the box and you close it up. So what's going to happen?
After a certain amount of time, there is some probability that
The Geiger counter clicks, the radioactive chunk has emitted a particle.
probability that it didn't the hammer smashed, the capsule broke, and the cat is dead. But there's also some
intervals and no particle has been emitted yet and the cat is particles still alive.dioactive material is at completely random
we know which one it is? So the box is closed so how do
Well, the quantum mechanical answer is that it is both.
alive and dead. It's what we call a quantum superposition. It is in the state of being both
proposed this in order to demonstrate, not how much sense quantum mechanics makes, but how Now, Schrodinger actually
He brought this up as an example little sense it makes.
to say that well this is absurd, you can't talk about a cat being
time. And the problems here is that quantum mechanics does not work bovery well with large systemse
because there's too much going
The walls of the box are always going to transmit vibrations There's no way you can possibly isolate this.
Unless the wall, it's a double even if you seal it perfectly with a vacuum around it.
wall with both walls being perfectly at absolute zero, there will both be radiation
emitted between the walls of the
It does raise a lot of box so there's no way to do it. So we can't actually seal it up perfectly.
But that's better left for philosophical questions about what state does the cat think it's in.
discussing over a beer at the terrace. But what I do want to stress is
that for small systems, ones
that we can isolate very well, we actually do see behavior like
experiments are concerned, a this where as far as all the
small particle can be in multiple states at the same time.
And I'm going to give you an
example of that. So this is possibly the most
mechanics which is the famous experiment in quantum
which has a bit of silver in it. Stern-Gerlach experiment. And the way this experiment works is you have a furnace
And the silver heats up and those atoms get very hot and they start bouncing around and
they want to fly out of the box but there's only one small hole so they all have to fly out in
So you end up with a beam of the same direction.
magnetic field that we've set up silver atoms. And then we're going to shoot those silver atoms through a
here by having opposing north and south poles. Now, silver is, I believe,
element number 47, anyway it's
definitely an odd number, and that's important because you have one unpaired electron.
And the one unpaired electron means that these atoms will have
magnets. some magnetic moment, they'll act like tiny little bar
through, and they're all Now, if classical physics had its way, what would happen when we shoot these tiny bar magnets
around every which way, they randomly oriented because they're super hot in that furnace, so they're bouncing
have no predefined disposition to be in a certain direction. Well, some of them would be
aligned with the magnetic field.
Their north poles would be facing the south pole and they'd
And they would be bent down. be attracted to it.
much. There's no force to the left or right because the magnetic field might go down but not quite as
So they would go down but not quite as much. gradient is only vertical.
magnetic field, and they would And some of them would be perfectly perpendicular to the
just go straight. There'd be no force on them at all.
And some of them would go up a
little bit and some of them would go up a lot. And you'd get sort of a smear
and you see that here.
The classical prediction is just a smear of atoms. But that's not what they saw.
They saw two distinct dots. The atoms went either up or down
and they did so by exactly the same amounts.
There was no in between.
And this was completely shocking to the physics community at the time.
This ran counter to all of the
current physics thought at the time. And it was really the beginning
of the quantum era. It really convinced a lot of
Because there's no other way to explain it unless the, what we people that quantum mechanics was valid.
call the spin of the electron, which is what gives it its
magnetic moment, is quantized.
It can be aligned with the field, it can be aligned against
choices. it and there are no other
What's interesting about this is that where you put your magnetic
It was our choice, our conscious field matters.
which I'll talk about in a choice, to align the magnetic field vertically. We could have put it side ways,
measurement. minute. But we aligned it vertically. And that was essentially a
The applying of the magnetic field to these atoms is a measurement which forces them to
choose one state or the other,
but before that time they were in a quantum superposition of being up and down.
And that is a really useful notion. In classical computers, your
Zeros and ones. And a bit can be either a zero information is stored in bits.
information, if it's an essay or or a one. And when you want to store more
a picture, you build this up out of little zeros and ones. And you put it all together you
have some code, ASCII code gives
you the alphabet. That's how you store all of your data.
In a quantum computer, we use what we call a quantum bit, or a
quantum system, it can be in a qubit for short, and a qubit, because it is a manifested as a
quantum superposition of two states at the same time.
Stern-Gerlach example we can So, for example, in the
counts as being in the zero have eitherstate.up or spin down. Well, we'll say that spin down
And spin up counts as being in the one state.
And what this funny notation
here, this is called Dirac notation. It's really useful for doing a
lot of calculations in quantum
mechanics. You don't need to worry about any of what that means right now
except that everything from this
bar to this greater than sign with the zero in between, that means being in the zero state.
These numbers before them, the
alpha and the beta, those tell you the probability of finding
And those are complex numbers which means that they have both an amplitude and a phase. And their squares, it's actually
their squares that tell you the probability.
And their squares need to sum to one because, of course, the
probability of finding this system in some state is 100%. The probability that those atoms
because they have to go one way or the other. So they're in either the up or went either up or down is 100%
zero or one, but not until you down state, they're in either
actually measure them. Before then, they can be in a mixture of the two.
They can be in a pure state if
we set them up that way. But we can set them up to be in a quantum superposition.
And I'm going to explain how you
can do that. First I'm going to show you a picture that explains a little
more graphically about the qubit
at the top I have the zero state or the two level system which are equivalent. So this is the block sphere, and
at the north pole there. At the bottom I have the one
And this sphere shows you that state at the south pole.
all of the surface of this sphere are valid places for the value of your qubit to be.
Because you have that alpha and beta, they're both complex
numbers. They need to sum to one.
So that gives you one equation
which tells you that it has to be on the surface of that sphere.
The length of this vector has to
be one. That puts it on the surface of this sphere.
And also we disregard any overall phase between alpha and beta because there's no way to
really matter. measure that and it doesn't
And anyway the end result is that you can picture the value
on this sphere. So it can be zero, it can be of that qubit as being somewhere
one, or it can be somewhere in between.
And a 50/50 chance would be somewhere on that equator.
Well, let's think about what So how are we going to set this up?
So we only let through atoms would happen if we took the Stern-Gerlach experiment and we block the beam that went down.
that were spin up. I'm going to represent that as
The up arrow means that this is a filter for spin up silver atoms. this entire box here.
oriented atoms and the only ones So we send in a beam of randomly
that make it through this are spin up. So 50% of them will make it
through.
Well, what happens if we put another one after?
It's totally predictable. All the atoms that make it Completely what you think.
through the first one are spin ups, and when we filter for spin
up again, they will all take the
upper path and they will all make it through the second
Then what happens if we turn the apparatus.
second one upside down? If we filter for spin up and then we put a spin down filter
after that, all of them are blocked.
If we then measure which It makes sense because they all are spin up.
direction is the spin, none of them will have spin down, none
It makes sense, right? of them get through.
Because remember, there were Starts getting interesting when we ask, what happens if we turn the apparatus on its side?
only two choices for which way the atoms would go when we put
experiment. They either went up or down. it through that initial
They had no preference left or right.
There was no information about
it because the only choices were up or down. Well, what ends up happening is
all the spin up atoms that go through, because they are exactly halfway between being spin left and spin right, if we
turn this apparatus on its side and filter for spin left, 50% of
Now, we say that the atoms at this point were in a quantum them will take the left path. And they will make it through.
superposition of being spin left and spin right because they had
absolutely no information about whether or not it's left or right.
completely randomly oriented Despite the fact they were
here, we forced them to all be spin up by measuring them using this vertical magnetic field and
taking only the ones that are spin up.
The up state is a quantum superposition of being in the Itstate's left and right.um It gets even more interesting if
we put three of them in a row because remember when we
filtered for spin up and then we filtered for spin down, nothing
got through.
of makes no sense at all because But if I stick a third one in between the two, all the sudden I get atoms through which kind
at this point they were all spin ups.
down, none of them should be So when I check if they're spin
spin down. But they are because measuring
completely perpendicular to the up/down basis, and they lose all them in the left/right basis is
When we force the atoms to be spin left here by only letting information about the fact that they were ever spin up.
that they were up before. They're not left and a little through thebit up.f them that There's no such thing as lefte
and a little bit up because there are only two choices. There's no such thing as right
There are only two choices, and it depends on what direction I and a little bit up.
measured in. But in this case, at this point,
they're either left or right, and there's no other information
that can be carried along with them.
So then when they're all left and I measure whether or not
of the up and down states and now I get half of them coming they'rthrough this one., spin lefSo half through here, halfon
through here, and half through
there, an eighth of the atoms that made it through initially actually make it out even though
if I took away this middle one, none of them would make it
through. So that's how you can create a
quantum superposition using a real physical system. And we use that.
in a quantum superposition is equivalent to a logical state of We say that that physical system
Well, how is that useful? Let's say I was a hacker and I being a superposition of a zero and a one at the same time.
Now if I just had a regular computer, I would have to try the passwords one after another after another one at a time, and
it would take me a very long
time. But if I have a quantum computer I could create a quantum
superposition of all of the possible passwords and put them through whatever checking algorithm for the password there
is all at the same time.
Now I'm skipping over a little bit of detail because obviously if we could do everything all in
one step then quantum computers would not only be exponentially faster, they could do any algorithm in one step.
The difficulty comes in in actually reading out whether or not you found the correct
another day because it's answer, which I will save for
complicated how the algorithms actually work.
a little bit after the talk, we can talk about that. If you'd like to talk about that
algorithm exactly how this would But I want to give you an example going back to Shor's
work. So here I have two large numbers, six-digit numbers, that
I have happen to know that those
Now, if you were to multiply are prime numbers because I looked them up on a list of prime numbers.
those two together you'd get another big number. But it's still pretty easy to
do. You punch that in your
calculator, it gives you the answer, it's not a hard problem.
That is equivalent to the way that a computer checks whether
The numbers that you put in needs to multiply with another or not you have the correct password.
secret number and give you the correct number.
Now, doing the reverse problem, if I were to give you this huge number, 10 billion, 967 million-something, and I asked
you what two numbers multiply together to give me that number,
And that is a very hard problem, I think that would take you a very long time to figure out.
quickly on a classical computer. and it's traditionally always been difficult. No one knows how to do it
However, it's not hard if you can try all the possibilities at the same time.
This is where the quantum superposition comes in. If we create a quantum
possible numbers that are less superposition of all of the
less than the square root of than this and it's actually easier than that. You only have to do the numbers
that in order to find the factors because one will be less than the square root and one
will be more than the square
get the answer. So this gives what we call an exponential speed up, and what numbers at the same time and you
up is that on a classical computer doing this algorithm would take a number of steps we mean by an exponential speed
number of bits in your that is exponential in the
passwords. So N here would be the number of
And so A to the N, where A could bits in your password.
be any number, like two, would be how long it would take.
depending on the details of your And that base A it could change
algorithm. But, for example, if you had a
two to the 100 hundred bits in your password,
is over 10 to the 30. So one with 30 zeros after it. A huge number.
However, on a quantum computer, Shor's algorithm can do this in what we call polynomial time, which means that the N is in the
base and the A is in the
exponent, which is quite different.
the 100, 100 to the two, that's just 10 to the fourth, that's 10,000, which in comparison to If you look at instead of two to
gets bigger and bigger, these numbers diverge explosively. 10 to the 30 is tiny, and as N
have been factored by a quantum computer? SoWell, they have successfullyf the art in terms of numbers that
three and five. So three times five is 15, and factored the number 15 into
21. Does anyone know what the prime therfactors of 21 are?are working on factoring the number
together to give me 21? [INAUDIBLE] Seven and three. What two numbers multiply
[LAUGHTER] Very good.
So you are all as smart as the world's most powerful quantum computer.
Congratulations.
[LAUGHTER] Another aspect of how powerful
densely they can store quantum computers can be is how
information. So how the amount of information
qubits, more quantum bits, to your system. storage builds as you add more
It doesn't just go linearly. It's not like one qubit gives
you one more unit of
information. Because the system of states, represented again by this funny
Dirac notation here, this is a
state, this is a state, and this is a state, we have all the possible permutations of those
individual qubits, and if you wanted to, I could store a
qubit being in each state and making an analogy between that number in the amplitude of each state so the probability of a
I have eight possible states. And so by turning on and off the and bits. So for example, for three qubits
probability that that qubit is in a certain state, I can treat
those as bits and effectively I have two to the N bits of storage for every qubit, and I'm
because all of these amplitudes do need to, their squares need subtracting one off of there
to sum to one so that means that you can't have them all be zero
which takes away one
possibility. So how much is that?
Chamberlin Hall, we are working on building a 64-bit quantum Well, in my lab over in
of storage, that's equivalent to computer. So if I had two to the 64 bits
4.6 million terabytes. And my laptop has a one-half
actually is pretty large but terabyte hard drive which
it's nothing compared to this. So it would be the equivalent of
So how do you like them apples? [LAUGHTER] over nine million MacBooks Pro.
different ways that you can make All right, so now remember when I went through all of the
a classical computer, in the same way there are a lot of different ways that you
can make a quantum computer.
The quantum Turing machine is a theoretical model the same way that the classical Turing
machine is. And there are a lot of different
ways that we can instantiate it. So we really only need two
things. We need a system that's very
that the effects of quantum mechanics are obvious and we can small in order so that it behaves quantum mechanically so
And we also need to be able to use these quantum superpositions.
isolate it from the rest of the world so it's not like the cat in the box where the quantum
state decoheres because there's too much interference with the
outside world. And we would like to be able to
control it also.
So a number of ways that you can do that.
a wonderful quantum entity First of all, a single photon is
get any smaller than that. because it's pretty much as small as you can get. A massless particle, you can't
quantum computer was to use the Anpolarization states ofe original way that Richard Feynman proposed to build a
way, there has been some success individual photons. The problem with doing it that
with that method but you can't do logic between multiple qubits
interact with each other, you need some sort of mediator like an atom. that way because photons don't
nuclear magnetic resonance which There are groups that have used
is the exact same technology that you have in an MRI that you
this case they're going to scan a little vial of some molecules and what they can do is they can would get scanned by except in
for example, hydrogen atoms in a detect the state of individual,
long molecule. And they'll say that each hydrogen atom represents a
qubit, and its state tells you
whether or not that qubit is a zero or a one.
Wisconsin, Professor Robert McDermott is working on a method Now, here at the University of
called Josephson junctions which they use a superconducting
charged island. It's a very tiny device they
have in a giant refrigerator and they get it very cold, and the
charge that is going around a small circuit is actually quantized, and that can only
use that to represent their qubits. Another method also being worked have certain levels, and they
Wisconsin by Mark Eriksson is called the quantum dot. And the quantum dot is another on here at the University of
Josephson junctions, where they have a small circuit that actually traps a single electron solid state technique, just like
And the advantages of these techniques is that they use the same manufacturing process that we use to make all of our
microchips today. They use lithography and
So this a good avenue to go towards because once they get this working, they will be able to scale it up very easily
because we already have the technology to make large
circuits this way. But the current leader in terms
of number of qubits, which is 14
by the way, the largest quantum computer that has been built they've successfully entangled
14 qubits, are the ion trappers.
And that's actually a group in Innsbruck that holds that record
And what that means is that you have an ion which is just a charged particle. It's missing one electron so it
has some overall positive charge. And you can manipulate it easily.
All you have to do is charge up two plates and you can apply and
So you can trap them very easily electric field and you can move that ion around.
and you can manipulate them very easily. Also, they have a large electric
field themselves because they are charged.
And so that can affect other ions that are nearby.
And that's how they do the
communication between qubits and have logic work between multiple
The problem with this method is that you can't turn that qubits.
interaction on or off. The ions always have whatever
charge that they have and it's
difficult to control it. So my group, my adviser,
atomic physicist, which means that traditionally he studies the interaction between light Pand atoms, and we are applying
the methods of atomic physics in
order to try and build a quantum computer. We are not the only ones.
There are other groups working
on it. But what we do is we, our atom
And what is interesting about cesium is it's one of the alkali of choice is the cesium atom.
periodic table. And all of the atoms in that atoms which means it's on the far left-hand side of the
column share something in common which is that they have one
lonely valence electron.
All of the other inner shells are completely filled. They're happy, there are no more
electrons that can be put in
there. So if you shoot a laser beam at this cesium atom, chances are
it's only going to affect that
higher state without actually knocking it off the atom. So we can change the state that anthe cesium atom is in. a
So as a result, what we can do
is we can manipulate one electron, but we only have to hold on to an entire atom, which
is a lot easier than holding on to a single electron. And so that puts us in a pretty good situation.
And the way that we trap these
cesium atoms is in something called a magneto-optical trap.
does is you would have your cesium atom right in the center there and there's a laser beam And what a magneto-optical trap
six directions, each of these arrows represents a laser beam coming in from each side, all
direction, it sees a laser beam coming at it, and if it moves another direction, it sees a So if the atom moves in one
which ever direction it goes, it's slowed down by those laser beams pointing at it. laSo we can cool this atomnd
tremendously, and we can get it down to micro-Kelvin
temperatures, which is wonderfully cold.
And actually the coldest things in the world, Bose-Einstein condensates, have been made using magneto-optical traps like
this along with some other
our set up is still at room temperature, and we don't need a But we can get it colder than anything in the universe while
huge fridge in order to do it. So that's really convenient.
And what we are planning on doing then is we're going to
make an array, an eight-by-eight array of 64 of these
magneto-optical traps, and we're
going to trap 64 cesium atoms and we're going to have a lot of lasers pointing at this thing
that it needs to be very
precisely controlled in order so that we address the correct atom
states the way that we want and we can turn on the interaction and that we can change the
And this here is a picture of my between these atoms by changing what state they're in.
lab and it's very messy. But I like to think this is somewhat of a visual analogy
between this and ENIAC, which is
also this huge room filled with boxes and wires. What you're seeing here is these
are optical tables covered with a bunch of mirrors and lasers and beam splitters, all basically preparing the correct
frequencies to point at our tiny
off at the correct time in order little array of atom traps. And then we have computers in order to turn the lasers on and
to manipulate the atoms in the way that we want. And if everything goes according
to plan, we will have a 64-bit
that the largest supercomputer quantum computer. And for reference, there is a study that I read that showed
in the world currently is equivalent to a 40-qubit quantum computer for a certain problem.
Now, unfortunately that would be
40 perfect qubits. So a physical qubit might not exactly behave the way you want
because it has some temperature,
other atoms sometimes come into your trap and knock your atoms out.
Problems happen so we have to have error correction.
And error correction means you need redundancy.
So we actually need more
physical qubits than we will have logical qubits and depending on how on the fidelity
of our gates and our state
preparation, that ratio may be as bad as five to one.
like 12, 13, 14 qubits. But if our system turns out that So we may end up with something
we do it better than that and we isolate it better and there's
lower noise, we may get more
than that. So that would be very exciting
64-qubit quantum computer. and so we're hoping to build a
If we work quickly enough, it may be the largest supercomputer in the world, although being the
smallest. Now this is not my last slide,
this is my second to last slide. I would like to thank my
adviser, Professor Mark Saffman,
and our funding agencies and everyone who works in my lab. So I'm still learning a
tremendous amount about this
subject. I think it's very exciting. My last slide is I'd like to
give you a little more
information if you are curious to look up. I thought it was better to leave
you with some other directions
to go if you want to know more. And a few things to look at. The page about all of the
quantum computing research going
on at the University of Madison, QC.physics.wisc.edu, and
you actually can zoom in on these things and take a picture and it will take you right if your smartphone is capable,
But if it's not, don't worry, just Google it. If you want a really in depth treatment of quantum mechanics,
the go-to book
He's a really cool guy. This was at a conference. He had answers to every single last month.
even if it was not his talk. question that anyone asked
And his book is wonderful. I recommend that. This link will take you
to the Amazon page. That's a fairly long book, but
if you want really the reference for quantum computing,
that's what to look at. And this last link is to the
a transcript of a talk original paper by Richard Feynman, actually it's
by Richard Feynman. And if you want to find it, just Google Simulating Physics with
Computers by Richard Feynman. And that's a really interesting read because everything that
was just explained really beautifully. he's ever written or said
So that is what I will leave you with.
Thank you very much.
[APPLAUSE]