Information is Quantum

ok yeah I’m going to tell you today about how
some things discovered by physicists in the early 20th century have changed our
view of the fundamental nature of information which is at the heart of the
information revolution that really got going in the end of the 20th century well like other parts of mathematics the
theory of information and information processing originated as an abstraction
from everyday life uh if you’re a student of Latin you’ll
know that calculation is a manipulation of pebbles and the digit is a finger or
toe uh and this abstraction was was crystallized by people like Touring and
Shannon and Van Neumann into the theory of information and information processing
but unfortunately these abstractions are too narrow, uh, the quantum theory which
was developed in the early 20th century by physicists and chemists now provides
a more complete and natural indeed arena for developing the concepts the abstract
concepts of communication and computation so what people who do information
processing and storage and computing have used as information carriers like
like a signal on they on an ethernet cable or a hole in a punch card were
what a physicist would call a classical systems that is their states are in
principle reliably distinguishable and you can read the state of something
without disturbing it and are almost so fundamental an idea that nobody even
thought of saying it to describe thoroughly describe two things. it suffices
to describe each one separately well those ideas actually were known to
be already not right in the early 20th century in the context of physicists
studying atoms and small particles, atoms, electrons and photons. uh and they found
out that attempting to just to observe the state of a particle in general will
disturb it and only obtain partial information about the
state was before you disturbed it that’s generally called the uncertainty
principle and they also found that two particles can exist in an entangled
state in which they behave in ways that can’t be explained by supposing that
they were that the each particle had some state of its own maybe state that
you don’t know so most of the 20th century passed by
where quantum effects were understood because you needed quantum theory to design
transistors and so on but they were regarded from the point of view of
information processing as a nuisance because they cause these tiny
microscopic devices they kept getting smaller and smaller to become less
reliable are because of the effects of the uncertainty principle but toward the
end of the 20th century it was understood that quantum effects have
positive consequences that they make possible new kinds of information
processing like like quantum cryptography and dramatically
speeding up some classically hard complex computations and to understand
how these things work you really need to understand entanglement which is an idea
that the average person on the street doesn’t really understand. So I’m going
to try to explain the difference between ordinary classical information or what
we call information which everybody knows about because we’re in the middle
of information society and quantum information by comparing quantum
information to the information in a dream. Unlike the information in the
book the information in the dream is private in the sense that if you try to
to explain your dream to somebody or describe it you forget what the dream was and only
remember what you said about it and it’s inherently private you can lie about
your dream and nobody will catch you except maybe your spouse but unlike the
theory of of of dreams despite the best efforts of Sigmund Freud there is a
well-developed mathematical theory of quantum information which I will not
belabor you with most of the details of so there are important
differences but also there are important similarities to ordinary what a
physicist we call and what I will henceforth called classical information
we all know that uh information can be reduced to very simple primitives just
the digit 0 and 1 for example you can encode a letter of the alphabet in five
bits are and all processing of information can be reduced to basic
logic operations like and and not acting on these bits so that you only have to
handle bits one or two at a time to do anything that you would need to do with
classical information similarly quantum information is
reducible to what we call qubits which are quantum systems that are capable of
two distinguishable states an example would be a polarized photon
or a spin one half atom and similarly any processing that you want to do the
quantum information can be done by acting on these qubits one and two at a time oh and uh just as classical bits the
fact that information processing that software is independent of hardware so
that you can by making the hardware smaller and faster you make information
processors more and more powerful they can do the same computations similarly
in principle although we don’t have have not proceeded very far towards a quantum
computer the things you do with quantum information are independent of the
particular physical embodiment that’s why i say they are fungible among the
different quantum systems just as classical bits are fungible among the
different ah storage and transmission media that you use for them. So what is
the central mathematical principle of quantum mechanics and quantum
information it’s called the superposition principle and it says that
between any two reliably distinguishable states and physical system there are
other states that are not reliably distinguishable from either original state now of course
uh we observe this phenomenon all the time if we scribbled a note there may be
a letter that might be a might be an a an A or it might be an O and if we
scribble it badly enough or gets smeared in the rain it’s not perfectly
distinguishable but this is a different kind of imperfect distinguishability it
says that with the most perfect equipment you could not distinguish
these two states so quantum systems are systems in which there are
distinguishable states but not all states are distinguishable and the way
these states behave is that every quantum system corresponds its states
correspond to directions in space and any two perpendicular directions
correspond to distinguishable states and any two directions that are not
perpendicular correspond to states that are intrinsically imperfectly
distinguishable so any direction is a possible state but states are only
reliably distinguishable if their directions are perpendicular and in the
simplest case which is two reliably distinguishable states we’re talking
about directions in two-dimensional space like directions the compass needle
and this is nicely illustrated by the behavior of polarized photons so I’ve
got a perspective drawing here of a beam of light in which the photons are coming
along they’re all horizontally polarized in this perspective view and we can use
the fact that protons can be horizontally polarized or vertically
polarized as down here as a way of distinguishing them because if you send
photons into a calcite crystal or or oriented this way and then horizontally
polarized they’ll go straight through whereas if they’re vertically polarized
they’ll get deviated while they’re in the crystal and then come out on a
shifted path and this means if we wanted to encode bits in the photons we could
fit one bit in each photon and count them as they came out in these two
different paths the receiving end well of course the photons can be
polarized also at any intermediate angle so photon is coming towards you it can be polarized
at any angle relative to the vertical if it’s sending towards you and what
happens if you send some of these theta polarized photons into the same
equipment well you might think that they since
they’re intermediate between horizontal and vertical they would be deviated by
an intermediate amount but that’s not what happens what happens is that some
of them become horizontal and the other ones become vertical and these two
things happen with probabilities that depend on the angle theta in other words
identically prepared systems the state of polarized photons behave differently this is one of the amazing things about
quantum mechanics they behave differently and randomly and they forget
their original polarization we’re going to come back to that a lot so if i have a a crystal like this and
two detectors i can use it as i said before to carry one bit of information
for photon if I prepare these photons in these rectilinear states that is
horizontal and vertical avoiding other directions and if i wanted to i could
rotate the whole equipment 45 degrees and send through a chain of 45 and
135-degree photons are and again distinguishing them perfectly reliably
but there’s no way to distinguish all four kinds because the the measurement
that distinguishes vertical from horizontal randomizes the diagonal kinds of
photons in the measurement that distinguishes the diagonal photons
randomizes the direct to linear ones and this fundamental limitation is what
gives rise to the possibility of quantum money quantum banknotes and of quantum
cryptography ah but before I describe those things i’m going to use this
pedagogical analogy from my colleague William Wootters at Williams College
he says how do you explain how a quantum system behaves when you measure
it he said well it’s really very much like the old-fashioned kind of school where the students were not supposed to
ask any questions and where they were only supposed to answer the questions
the teacher asks so this the the pupil is the is the quantum system and the
teacher is the measuring apparatus so here we have a polarized photon coming
along and the teacher says is your polarization vertical or horizontal and the
pupil says I’m polarized about 55 55 degrees. i believe i ask you a question
are you vertical or horizontal? horizontal sir have you ever had any other polarization?
no sir I was always horizontal so that’s how quantum system behave when you
measure them so this impossibility of of determining the polarization of a single
unknown photon carries with it equivalent impossibilities you can’t
measure it exactly it you can’t clone it because if you could clone it into a lot
of identical copies and then you could measure them along all different axes
and find out in which case you can measure determine the angle theta with
arbitrary precision now there is a device that amplifies photons that
clones them in a sense and that’s called a laser but lasers don’t work very well
unless they have at an input signal it isn’t too weak and if you supply a laser
with an input signal that is just a single photon the laser generates enough
noise so that even though the output is brighter it’s no more useful in
distinguishing the polarization than the input was in fact if you send a single
photon into one of these ideal lasers two things happen equally often you get
two copies of the original or you get the one original and one photon of
random polarization so how is this used for making money that’s impossible to
counterfeit this was discovered by Stephen Wiesner around 1970 and only
published in 1983 the idea is you take a 20 of polarized
photons of these four kinds and put them in perfectly reflective boxes on the money 20 of them now that’s
possible in principle but actual photons die-off in in a unit fraction of a
second or even a fraction of a millisecond if you try to put them in
reflective boxes but going on with the what’s possible in principle we then say
the the mint that prints this money knows what’s stored there and when it’s
presented at a bank the bank makes the correct kind of measurement on each of
those photons and verifies that they’re all as expected that is that makes a
diagonal measurement on the first one a rectilinear measurement on the second
and so on and if they all pass inspection the bank gives you your
hundred reasoner’s of gold whereas if even one of them fails that
you get arrested oh so whereas ordinary banknotes often
contain a warning about how long you go to prison if you if you counterfeit them
this one just has a saying in Latin says non duplicator or meaning meaning i
shall not be duplicated well this is pretty impractical because
of it the photons don’t last long enough but a related device is much more
practical and that is using the photons to carry quantum information rather than
distorted in this at the bottom of the figure you see the quantum of
cryptography apparatus this is a clearly a piece of experimental equipment built
by theorists uh Giles Bressard my collaborator at university of montreal
and our students including John Smolin here at IBM who largely helped me build
this equipment and it allows the users to generate a shared secret
information by communicating over public channel in a channel subject to
eavesdropping by their adversary even though they share no secret information
initially which is a useful cryptographic feat and now this has been
scaled up and done by real experimentalists so over distances of of hundreds of kilometers well i would say the most remarkable
manifestation of quantum information is however entanglement and I want to talk
about where entanglement comes from how to understand it and what it
can be used for it arises naturally during interaction between quantum
systems because of the superposition principle that you already know about
now remember that I said that any processing on quantum data can be done
by one or two qubit operations so this means if i have a bunch of qubits
passing through these wires or quantum wires or optical fibers then anything I
want to do to the state of that bundle of qubits can be done by acting on them
one and two at a time one at a time means just rotating a photon’s
polarization by some angle. two a time would mean using one photon say the one
in this wire to control what happens to the one in that wire and the only two qubit
interaction we need is the one that corresponds to what in in classical
information processing is called the exclusive or in other words a
conditional bit flip where the control of a bit if it’s a 0 nothing happens to
the target bit and if it’s a 1 the target gets flipped between 1 to 0 or 0 to 1 so let’s do that here and we’ll use a vertical photon to represent one and a
horizontal photon to represent 0 and will keep the horizontal photon to be
orange and the vertical photon to be green just so we can tell them apart this is standard notation for quantum
states introduced by DIRAC this sort of half angled bracket meaning that this 1 and 0
are not classical 1 and 0 there are two reliably distinguishable quantum states
so what happens here is if the control qubit is a 1 the target qubit gets
rotated 90 degrees if the control qubit is a 0 the target qubit doesn’t get rotated so what would this do so this is a
quantum version of this exclusive or it’s called a controlled-NOT by quantum
people. what does a superposition of inputs do it’s just it’s a quantum
computing elements so it has to obey the superposition principle of superposition
of inputs is the direction intermediate between horizontal and vertical for
example a 45-degree diagonal direction which can be represented by this vector
in in a two-dimensional space and what it does is not as a what you might think
of rotating this target qubit by half half the angle and making to 45 degrees
know what it does is a superposition of these two situations it has to do that
to follow the superposition principle and that means it produces a
superposition of both photons being horizontal and both photons being
vertical and that’s called an entangled state. and the fancy color and lettering
suggest it’s a different kind of state which can’t be even described in the
language that we use for classical information this entangled state is a
state that is as if you have to say what it is it’s a state which is perfectly
definite even though the two photons don’t have full realization of their own it’s a state of sameness of their
polarizations so this means that its not the same as both
photons being 45 degrees well let’s see why why it isn’t why this
state is not the same as that state and we just have to do a little four
dimensional geometry here so i am trying to show that this direction in
four-dimensional space is a different direction from this direction now to see
that the entangled state on the left is different from the one on the right we
have to do a little algebra and it makes it easier instead of draw all these
arrows to call H for a horizontal photon and v for a vertical photon so this diagonal
photon is H plus V divided by square root of two, and the 135-degree
diagonal that is the perpendicular diagonal direction is H
minus V over square root of two and you can see those directions are
perpendicular it’s like this is H this is V this is one diagonal and this is
the other diagonals so the two diagonals are perpendicular and the vertical and
horizontal of perpendicular well we know that what is the state it’s a single
photon lives in a two-dimensional space and if we have two separate photons a
green one an orange one we can think of four distinguishable directions because
whenever I say two letters the first one is green I’m going to
pronounce it with a green tone of voice hh hv v wait hh, hv, vh and vv are
all distinguishable because for example the first two can be distinguished by
measuring the orange photon so we know that the states of two photons live in
four-dimensional space and we can work out the state of this this entangled
system on left it just says what it is it’s H H plus V divided by square root of
two we’ve got that but what about this one well this one is H plus V and so is
this one H plus V and if we expand that out it’s H H plus H V v + VH + VV all
divided by 2 and that’s a different direction in four-dimensional space so
this is that this state can be described by
giving us polarization to each photon and this one cannot be described the
best you can say is it’s a state of sameness of the polarization well here’s
an example of of William Wootter’s idea of the the students behaving randomly an
entangled pair of students i’m going to call them Remus and Romulus are very bad
students they don’t they don’t answer any sensible answer to any question they
always answer random randomly but they even give they always give the same
answer even when you question them separately so a teacher could ask Remus
what color is grass and growing grass and he says pink another teacher asks Romulus
and you get the same answer. now if you weren’t happy with that metaphor and
there’s another one from my own past i was in san francisco in 1967 known as
the summer of love and there it was very easy to meet people who thought they
were perfectly attuned to one another even though they had no opinions about
anything and the the hippies at that time I thought that if you had enough
LSD then everybody could be in perfect harmony with everybody else now they were not known to be a very
good at mathematics and now that we have a mathematical theory of entanglement we
know that entanglement is monogamous which is something else if these weren’t
very good at and the more entangled two, two systems are with each other the less
entangled they can be with anything else well I’ll say now how these entangled
particles behave in the laboratory and how to explain it in everyday language
if you don’t want to deal with four dimensional geometry. well so as I said
the two photons are created at the same time they come out of some apparatus and
if you measure either one of them along any axis it gives a random result for
example it turns out to be vertical here and the other one turns out also to be
vertical and even physicists will say it causes the other one to become vertical
but that is a very bad way of thinking is I will tell you
later so how would we explain this perhaps the easiest explanation that
comes to mind is to say well the apparatus isn’t actually producing the
same state each time it’s producing a pair of photons of the same polarization
but from one shot to another every time you press the trigger on it it will give
a different polarization so sometimes it will set up two vertical ones
sometimes two at angle theta sometimes two at horizontal and so on it’s very easy to imagine that kind of a
random two bullets shooting gun ah but this doesn’t work as an
explanation because if you set up the equipment up to measure the vertical vs
horizontal polarization well sometimes the source would admit two diagonal
photons and if each of them had a diagonal state and interact with the
apparatus without any communication the other one then they would each behave
randomly and that means they would sometimes come out with opposite of
polarizations in fact when you do the experiment they always behave the same
now this is this is a toy model of a well of toy version of a more
complete argument that says any property at all that you would try to attribute
to these two photons does not explain the strength of the correlation
of their polarizations not merely to say did they have a polarization but did
they have any property that you could contribute to them separately this was the
famous result that John Bell discovered in 1964. well how do you
explain it well the way that people do but they know that it’s a bad way of
talking is instantaneous action at a distance and the reason that’s a bad way
of talking is so we create this pair of Einstein Podolsky Rosen particles that’s
another name for entangled particles and one of them happens to pass through a
vertical polarizing filter and that means that it was vertical and the other
one is vertical too it sends a message says all you got to become vertical and
so when we measure it turns out to be vertical of course that violates a
special relativity that messages can travel faster than the speed of light besides even if you could send messages
faster than the speed of light this photon amount of bounced off a lot of
mirrors and be in some place how would you even know where to send
the message to so that’s not a good explanation. quantum mechanics gives the
right explanation and you can go back to the algebra that I gave one of
the few slides ago and get the exactly the predictions of the oppositeness I
mean the sameness along any axis but if you have to explain it to somebody in a
dinner party and you say well let’s start thinking in four dimensional
geometry we got H’s and V’s and so on it my experiences this doesn’t work very
well so you have to come up with something else to say about it and so
this is not this is this is not really very a rigorous but it’s a little better
than saying that it sends an instantaneous message to the other
particle telling it what to do so what can say it sends a random
uncontrollable message backward in time that is when this photon gets measured
it decides at that instant to be vertical and then it decides it always
was vertical this dotted line is the message backward in time and of course
its twin Romulus over here of course since it had just decided to be vertical
its twin of course has to be vertical too and whenever you get around to measuring
Romulus he will turn out also to be vertical well this sounds like even worse
thinking than these hippie entanglement because if you could send a message
backward in time you could tell your broker what what stocks to buy or sell
yesterday and and of course I mean even even if you’re not rich and don’t own
any stock you could certainly avoid some mistakes that you’ve made in life by
just tell giving yourself good advice uh well the that the the answer to this
argument is that the word message is really not right if if you can’t control
the message it doesn’t work as a message you can’t help you can’t give yourself a
useful advice or your your broker by a message that you can’t control and so
entanglement behaves like having a pair of magic coins that no matter how far
apart take them and toss them you’ll always
get the same answer but you can’t control either one now this is one of two logical
situations in which a message backward in time is harmless the other one is the
Cassandra myth where the message gets propagated it gets chosen by the future
event but then when you send it into the past nobody believes it well what how does this entanglement is
what can we use it for one of my favorite things the for using it for is what is called
quantum teleportation which is a way around the problem of getting complete
information out of one quantum system and putting it into another and it looks
like that would be impossible because there’s no way of measuring the state of
a single photon and getting its polarization exactly so how can you get
that information out of one photon and put it into another one that has never
been near the near the first one well in fact if you try to do that you would
measure it and you would get some information and use that to produce a
copy here but it wouldn’t be a perfect copy the polarization might be wrong by
10 or 15 degrees because you wouldn’t have learned what this polarization was
but you would have ended up spoiling this photon well here’s how we get
around that using entanglement and we now we have three photons we have an
unknown photon over here whose state we want to transplant to a different photon
and then we have an entangled pair of photons here there were never any where
near this one they’re just entangled with each other
and what we do is we do a measurement of A and B and we don’t ask the what’s the
properties of A, we ask them what’s their relation so we measure the relation
between A and B and then we take the result of that measurement and we
report it to the location of particle C and then we use that to rotate particle
C into what turns out if you do the math into an exact replica of the state
of particle A before you destroyed it so we don’t clone the information because
we have to destroy A before we can produce the copy and
we don’t send it faster than the speed of light because this message goes only
as fast as the speed of light and if you try to measure this particle C before
you’ve applied the corrective treatment it behaves completely randomly so
despite the name it’s not a way of transportation it’s
just a useful primitive in quantum information processing which goes on
among other things in the in the operation of a quantum computer well here’s my human analogue of of
quantum teleportation suppose uh we have somebody let’s say call her Alice who
has witnessed a complicated crime in chicago and the FBI wants to know what
the story was but they know that her memory is in a kind of fragile dreamlike
form and they have to ask her just the right questions in just the right order
and some of these questions have a sensitive information in it that they
don’t want to disclose to the Chicago Police so for sure the Chicago Police
are going to ask her wrong questions that will just confuse her so they they tell her they like to her
to come to Washington but she says she doesn’t like to travel and if they
subpoena her she’ll probably get un cooperative so they decided to send one
of their own guys down there but that isn’t very good because these guys all
have opinions and they don’t trust each other to interrogate her alone interview
her alone i should say interrogate has it more sinister meaning. so well
then Remus volunteers he says I don’t know anything about this case so i’m not
going to influence her unlike any of you besides I like to
travel just ask my brother so Remus goes to Chicago to meet Alice and they
explained to them they’re not supposed to talk about the crime or anything
they’re just supposed to have a speed date and decide whether they like each
other well it pretty soon they decide they
can’t stand each other and the police tell Alice she can go home and then they
get on the phone to Washington say well Alice and Remus don’t get on and they
have actually maneuver themselves into a state of perfect oppositeness and that
means you can go to Romulus and ask him all the same questions you would have
asked Alice except are you have to turn the answer
around and whenever he says yes Alice would have said no so that’s the human
analogue of quantum teleportation for what it’s worth I think after Wootters
told me his his analogy and then I I kind of overdid it he may be sorry well the principle i
mentioned earlier that is that if two particles are perfectly entangled
with each other they can’t be entangled with anyone else and indeed the kind of
classical correlation that is if two things each being random but having the same
random state because they’re like they’re two coins that actually are both
heads or both tails not because they’re in a state of oppositeness, of mysterious
oppositness. ordinary classical correlation typically comes about from attempts to
clone entanglement now of course cloning it you can’t do it oh because entanglement is monogamous so
here’s what happens suppose Alice and Bob maneuver
themselves into an entangled state a state of perfect sameness of
polarization and then Bob decides he wants to become entangled with somebody
else to call her Judy down here and so he does the same maneuver they did up
here but the only the effect of that then is that the entangled with alice is
spoiled it’s merely classical correlation so bob
is correlated with Alice along some axes but not along others and also is
correlated with Judy along so this is this is just ordinary classical
correlation like we’re all used to and it doesn’t display the hallmarks of
entanglement so let’s speak about the origin of quantum randomness how
entanglement explains the origin of quantum randomess. i should put back here going
back to your all of these actions are reversible if I stop here and just undid
this interaction i get back to this state and then undid this interaction to
get back to that state so let’s look at this in the case of polarized photons so
we have these polarized photons come in here and what I said before is that some
of them going to this beam and become horizontal and some of them
going to this beam then become vertical but what I really should have said is
that they do not yet behave probabilistically. what every one of them
goes into a superposition of being horizontal in the upper beam and
vertical in the lower beam. in fact they all go into the same superposed state but
when this state gets to these measuring apparatus these detectors that that then
it has to decide whether it’s going to be horizontal in the top beam and
vertical in the bottom beam so if we avoid the measurement and just let those
two photons these photons going to the two separate beams now these are photons
that haven’t interacted with anything yet and therefore we can switch the
horizontal photon to a vertical photon by rotating it 90 degrees and
similarly the vertical and horizontal and we can say put an optical
element called a half-wave plate that does that takes horizontals that makes a
vertical and verticals make horizontal and then put them back
through the same crystal the same size crystal of the same material and they
will recombine and be back to their original polarizations so what has
happened here is that I’ve produced an entangled state and then de-entangled
it and I go back to everything the way it was originally and what this means is
that the the public embarrassment of the pupil it having to say what is
polarization is in front of the whole class it’s what makes them forget the original
polarization in principle if you took the teacher and all the other students
and in any Mouse or that was listening and made them all forget what they heard
the student could get his original polarization back. so now I’ve argued
that classical ordinary information and information processing is a special case
of quantum information processing and we should really develop the whole theory
on the quantum foundation and that means we’ve got the obligation to explain what
we mean by classical bit well that’s easy we just say classical
bit is the qubit with one of two standard of a distinguishable values for example
horizontal and vertical and a classical wire is a wire that carries qubits and
give that carries these zeros and ones faithfully but randomizes superpositions
of them now why would a wire randomize the superposition it’s because the
ordinary wires that we have a most of our computers the signal passing along
the wire i’m drawing this is as thick classical wire is is really equivalent
to a quantum signal that interacts with an environment down here representing
the environment here by another wire and it interacts by this this gate that I
just showed you about this controlled not gate and what that means is if the
signal is 0 or a 1 the environment gets a copy of it and if it’s anything in
between the environment becomes entangled with it but if you lose track
of the environment for example if it escapes out the window or gets lost in
in the 10 to the 23rd other photons that are in the room then the remaining one
this is the student whose whose classmates have have gone out to recess
and you can’t get them to forget what they heard the remaining one behaves
randomly and this means that a classical channel is a quantum channel with an
eavesdropper and a a classical computer is a quantum computer with eavesdroppers
on all its wires so among other things called the quantum theory of information
explains the close connection between cryptography these the art of of
defeating eavesdroppers and privacy and a computation ….entanglement. so if
entanglement is ubiquitous in almost every interaction between two systems
produces entanglement why wasn’t it discovered until the 20th
century. the reason is because of monogamy but most systems in nature
other than tiny ones like atoms or photons especially photons interact so
strongly with their environment that they become entangled with it almost
immediately and that means that if you lose track of any of these things that
become entangled the remaining ones behave
just as if they’re classically correlated in other words we have world
that appears to be full of randomness and correlations among things that are
individually random which can all be explained but they all have some
particular state and we just don’t know what it is and yet that whole view
arises as a side effect of this subtle thing that we didn’t know about until
the 20th century and we didn’t realize it had to do with information processing
until the last 30 years of the 20th century well of course the main reason people
are so excited about quantum information is a practical reason that is if you
could build a quantum computer it would greatly speed up some hard problems like
the most famous one is factoring large numbers now here’s a problem
here’s an example of a large number it’s ah if you if you are very smart you
can realize that this number is the the result of multiplying these
two now in fact you don’t need a a a quantum computer to do that if you have
that too to multiply these two numbers you could do it on a quiet weekend is 3
times 7 is 21 that’s where that one comes from it carry the two and then
someone if not too many people are bothering you you can actually do it and
you could prove that this times this equals that but what’s hard to do on it on a on a pencil and paper or even on a
pretty powerful classical computer is to take this number and figure out that
these are its two unique factors however this job is easy relatively easy
for quantum computer not a whole lot harder than multiplying and the reason
is well I won’t say the reason exactly yet but it works because during the
processing even though the question and the answer are classical information the the
fast algorithm for doing this involves entangled intermediate states so we have
to build a computer in which the intermediate data is protected from
eavesdropping until the computation is done of course we’re for most of my life we’ve been facing
the end of Moore’s law but it’s really happening as computers can’t keep
increasing exponentially in their in their power and cheapness because
they’re going to be already near atomic dimensions so can quantum computers give
Moore’s Law new lease on life and how soon we have them are well i’m going to
be somewhat discouraging about that because there is a whole theory being
developed of the classes of problems that quantum computers would probably
help for or are known to help for and ones where they wouldn’t so it’s much
more complicated. some problems which if we have every reason to believe
are hard even for a quantum computer and then some problems that are easy like
multiplication for a classical computer and certainly quantum computer and then
a some number of these intermediate problems which appear to be hard for
classical computer but easier for easy for quantum computer. of course in order
to build a quantum computer you have to keep the eavesdroppers out of it and
that looks like an impossible job but it isn’t it isn’t possible because you
don’t have to isolate it completely from its environment if it’s can be isolated
about a little more than ninety-nine percent from its environment quantum
error correction techniques which are heavily being researched in this
laboratory now will do the rest so the quantum computation doesn’t have to be
perfect an example of a quantum error correcting
code is something that will take a state of one qubit and encoded into an
entangled state of five qubits such that any one of these five qubits can be
damaged and then undoing this operation sucks all the errors out into and throws
them way into these ancillary qubits and the original one comes out unscathed now
extending that kind of idea for a whole computation involves continually
feeding in our clean qubits into the processor sucking the errors out and
through and then doing your processing and then doing it over and over again it’s able to correct even errors that
occur during the error-correction itself so this is a field of great of interest
and activity to design efficient quantum fault-tolerant computations so in
conclusion I would say that quantum information provides a coherent basis
for the theory of communication computing and interaction between
systems in which classical behavior is just a special case and a classical
channel is just a quantum channel with an eavesdropper and a classical computer
is a quantum computer that’s handicapped by having eavesdroppers on all its wires
so the right question isn’t why do quantum computer speed up some
computations and not others it’s why does the lack of privacy slow
down some computation of course lack of privacy eavesdropping is bad for privacy
but actually slows down computations are some things which if somebody is looking
over your shoulder are really much harder to do and so I would finally say
that this ought to be part of liberal arts curriculum just like the roundness
of the earth, even non-science majors should learn a little bit about quantum
information and entanglement because it is so fundamental to everything about
the world uh that we inhabit although it was only realized in this last century
now I have a few extra topics uh one of them is the famous Einstein Bohr debate
and how Einstein i would say suffered from a tragic misconception and the
other is the kind of questions people often ask people working in quantum
computing which is a well really what is a qubit how much information is
contained in a qubit compared to a classical bit isn’t a qubit just the
same thing as an analog bit that is that something can have a continuous value
between 0 and 1 instead of just having to be a digital value oh and the other is how do these quantum
speed-ups where did they come from well let’s look at the first one so the
this weird behavior of atomic subatomic particles was discovered in the early
20th century by physicists and niels bohr became the main spokesman of the
new theory and he said that physicists have to learn to accept it not everyone
agrees with the way he described it but the two new phenomena were this
indeterminacy the fact that individual particles even when they’re completely
controlled and how they’re prepared behave differently they behave randomly. an
entanglement which I just talked about a lot there’s two particles that no matter
how far apart behaves in ways that can’t be explained they’re individually random
but too strongly correlated to have been acting independently so Einstein was
really impressed by both of these things and didn’t like either of them he called
the first one the indeterminacy God playing dice and he said I don’t believe that
God plays dice and entanglement he said called it a spooky action at a distance
or in german it’s spukhafte Fernwirkung which the idea was if if two
things are too far apart to have any plausible influence on each other it
almost looks like some paranormal things going on are there shouldn’t be a way
for what one of them does to influence the other and he spent the rest of his
life trying to find a more naturalistic explanation of the these quantum
phenomena which in which every effect would have a nearby cause so he has two
problems here he’s got an effect without a cause that’s random behavior and in
effect which if you try to find a cause for the cause isn’t nearby and this was
just unacceptable meanwhile the rest of the physics world
went on and and started using these complicated these these phenomena and
the mathematics that explain them and yet they couldn’t agree with the right
language describe what was happening so one of
the famous slogans i’m not sure who came from was people argue about what’s
really going on in quantum systems they don’t disagree about what will happen
when you do an experiment but they disagree about how to describe what’s
going to happen and the serious-minded quantum physicist says just shut up and
calculate don’t tell me what you think is happening in you might say it was
echoing what Bohr said to Einstein when Einstein said that God doesn’t play
dice and Bohr says stop telling God what to do oh well now it’s pretty clear that this
most celebrated scientific mind of the 20th century that the the one scientist
whose name is a household word was not flexible enough to take this new fact in
and his mistake was in viewing entanglement is some kind of influence
of one particle on another and the paper that he wrote with Podolsky and Rosen
describing that the the the predicament that this phenomenon of entanglement
produced in quantum mechanics and it must be some there must be some better
theory in quantum mechanics because this is unacceptable this was called Einstein Podolsky Rosen
paper and it came out in 1935 and one of the important notions in that paper was
what they called an element of reality if you can determine some property of a
system without touching the system without touching anything nearby the
system and be able to predict perfectly what it would do there must be some this
is what Einstein, Podolsky and Rosen said there must be some element of reality in
the system that you haven’t touched that was already there before you worked on
the other one and what the the the the logical jumping to a conclusion that
they did was to get to have the idea that these elements of reality a thing
that is about not about what you do to this system but something that was
always there before you touched it that this element of reality had to be
localized so in other words the right way to think about it is to say that
it’s not true that if the whole isn’t a perfectly definite state that each part
must be in a perfectly definite state entangled state is a different kind of
state of the whole which is perfectly definite but requires the parts to
behave randomly and making any measurement on one of the two particles
gives you a random result but allows you to perfectly predict what the other
particle would do if you made the same measurement on it and that’s that’s pretty
much the way everybody thinks of it now even though they still can’t agree with
what language to describe it with now another person around the same time as
as Einstein was Schrodinger and he had a really better understanding of
entanglement an Einstein did and he called this effect steering that is that
if you do you measure one system you find out exactly what the other system
it’s remotely steering another system finding out exactly what it would do
under certain conditions but steering is a really bad name for as anybody who’s
driven a car would know because what we’re talking about is a case where you
turn this steering wheel of your car and it has a completely unpredictable effect
on your car but has the same effect on the other guys car of course if he turns
the steering wheel the same thing so if you had cars like that you wouldn’t
realize there is anything strange about them except that they were terribly
dangerous until you compare your crash reports afterwards and you realize this
eerie correlation is present a mistakenly believing that entanglement
could be used for long-range communication Nick Herbert published a
paper and Jack Sarfati tried to patent this imagined application of it the
reputation of these wrong ideas in the early nineteen eighties by Dieks and
Wootters and Zurek is part of what led to the birth of modern quantum information
theory but this wrong idea like perpetual motion is so appealing that is
perpetually being rediscovered and as i said earlier the proper understanding of
entanglement not only explains why it can’t be used to communicate but also how if you generate an
entangled state and lose part of it the remaining parts behave randomly so the intense correlation the monogamy the inability to make multiple
copies of the same correlation and the random behavior of the parts are all
things that fit together mathematically and you can’t have one without having
the others but people often ask how much information is in that in our in qubits
compared to end classical bits or in analog variables and this is somewhat an
ill-posed question because ah it neglects entanglement and also its
there’s two kinds of information in the state how much information is required
to to specify it and how much information can you get out of it so let’s look at the separate answers to
these questions the information required to specify a digital state of n bits and
bits and the information you can get out of it is n bits if if you have in real
numbers numbers between 0 and 1 and it takes an infinite amount of information
to specify the number but you with any particular hardware you can only get an
limited precision on the answer so that’s an example where there’s more
information in the system than you can get out. a quantum system with n
particles has exponentially many complex numbers i haven’t mentioned the fact that
these numbers can be complex but there’s exponential amount of information in it
and yet you can only get n bits out so you can get out less than if it were an
analog variable and yet the amount of information required to describe the
state is much more but there’s another difference between digital, analog
and quantum information that is why we are so excited about quantum computers
and that is that there is good error correction for digital information there
isn’t good error correction for analog information if I have a slight
error in a voltage that’s .543 volts instead .544 how do I know that wasn’t
.544 to begin with rather than it was .543 and had a
hundredth of volt added to it so there isn’t good analog error
correction but there is good quantum error correction and that means there’s
the hope of building reliable quantum computers. so another way I mean by the time I’ve I missed lunch
and I’m getting pretty hungry by now if you think of a computer as a
information processor and the stomach is a food processor.. well the thing
that’s different between a classical computer and a quantum computer or the
thing that is similar is you give it a a classical input of n bits and you get a
classical output of n bits but the classical computer its intermediate
state always has a particular one of these digital states so there’s an
intermediate state of the computer a quantum computer because of
superposition and entanglement the intermediate state can be a
superposition over exponentially many of these distinct states of its qubits
where each of these numbers is it is an independent variable two to the nth, two the nth numbers weights on these elements of the superposition which you
can even be complex numbers just makes it twice as bad and so we say we have a quantum
computers like a big stomach which has a lot of room for maneuvering to process
the information which is just actually rotation in a large dimensional space whereas a classical computer is limited and therefore it can do some kinds of
problems better that’s just a very hand-waving argument. i can speak of the
particular most famous quantum algorithm which is Shor’s algorithm for factoring
now the first part of Shor’s algorithm boils it down to a problem of period finding,
finding the period of a periodic function ah and it works we have we have
in the computer we have two registers and call them the X register and the Y
register and we start out with them both in the 0 state and the first thing the
quantum computer does is taking a rather small number of steps it generates a
uniform superposition over all the values of the X register so instead of
both the X register being a zero and the Y register being zero the X
register is a uniform superposition of zero with Y register and each
individual value of X. then the next thing we do is to reversibly compute
this function this periodic function we computed in superposition so we fill the
computer up with a graph of this periodic function where repeats a very
large number of times and then we do something that I haven’t shown you why
it’s easy but it is easy taking only a few quantum operations to make a Fourier
transform of the X register is so instead of having a periodic function we
have something that has peaked which is very sharply peaked here at multiples of
the inverse frequency and so then we just measure the X register
and we get a random one of these peaks because it never is finds itself in the
space in between and if these peaks are sharp enough that’s enough to determine
the period of the periodic function and in the case of Shor’s algorithm that
means you can factor the number now this is something actually very familiar to
physicists it’s the problem of of multi slit diffraction or multi slit
interference as we know in the two-slit experiment ah if you send a single if
you send a light beam in here and you have this midpoint of the two slits
lined up exactly with the with the axis of this horizontal axis what we’ll get is a
maximum probability of of the photon landing here zero probability here goes up
to maximum down to zero and so on sinusoidal way whoops in a sinusoidal
pattern and so I this will allow me to measure the slit spacing by measuring
the spacing of the interference pattern and what I sometimes do when i’m in a
lecture room with a white wall is take a laser a laser pointer which has a very
definite wavelength of light and shine it through my shirt on to the wall and
you can see stripes on the wall whose spacing is inversely proportional to the distance between the threads in my shirt
but anyway even if we have two slits we get this kind of pattern and if you have
enough photons we can determine the slit spacing but suppose somebody says
alright i’m only going to give you one photon how far apart are the slits and
then we have a problem because that this sinusoidal variation this is not
guaranteed to be on a maximum it might be anywhere here except that one of
these absolute minima so we only get a little information about the slit
spacing from the impact point of one photon and so let’s say will say well
okay you’re not going to give me more photons how about giving me more slits and
of course your adversary will say take all the slits you want so I say okay I’ll take a million slits
here like this and we still only get one photon but now the interference pattern
if you worked out is extremely sharply peaked more sharply peaked the more
slits there are so even one photon will give you a good estimate of the slit
face and that’s exactly what’s happening in Shor’s algorithm and you
would say well why don’t you just build a large diffraction grating and use
that to factor large numbers the reason is that the number of slits is
exponential in the size of the quantum computer register so in other words to
factor two, to factor uh a hundred bit number you would need a diffraction
grating with two to the hundredth slits and even if they were very close together
this would be several light-years many light-years in diameter and of course it
wouldn’t something that big you can’t use it for fast computation as well as
being hard to build so this is essentially the quantum because of the
nature of quantum information some problems that look like they require an
exponentially large amount of classical resources to do this to do this multi
slit interference can be folded up and made exponentially smaller and put into
a quantum computer that has only a few hundred qubits or if we have good error
correction and build it the way we know how to
build it now a few few billion qubits maybe would be needed

Leave a Reply