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 are and this abstraction was was crystallized by people like touring and shannon and fun women into the theory of processing but unfortunately these abstractions are too narrow are 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 concept 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 its devices 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 adams and small particles atoms electrons and photons are and they found out that attempting to just to observe the state of a particle in general will disturb it and only.

Impartial information about but 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 . 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 at 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 I 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 sequin Freud are there is a well-developed mathematical theory of quantum information which I will not belabor you with most of the day.

Tails up are 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 of basic logic operations like 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 cubits which are quantum systems that are capable of two.

Distinguishable states an example would be a polarized photon or a spin one half Adam and similarly any processing that you want to do the quantum information can be done by acting on these qubits one into 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 u 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 of 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 phenomenal 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 a no 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 distinguish ability 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 course on the it states course on two 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 to 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 their 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 corazon ttle randomizes the diagonal kinds of photons in the measurement that distinguishes the diagonal photons randomizes the director linear ones and this fundamental limitation is what gives rise to the possibility of quantum money quantum banknotes and of corn cryptography are but before I describe those things i'm going to use this pedagogical animal analogy from my colleague of really motors 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 I is your polarization vertical horizontal and the pupil says I'm polarized about 55 55 degrees i believe i ask you a question ru 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 wheezing around 1970 and only published in nineteen eighty-three 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 Prince 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 known duplicato 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 Sheila breasts are like a collaborator at university of montreal and our students including John Smolin here at IBM who largely help me build this equipment of 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 feet and now this has been scaled up and done by real experiment lists so over this.

Census 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 we're 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 of photons polarization by some angle to 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 cute to Cuba 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 a0 nothing happens to the target bid and if it's a one the target gets flipped between 120 / 02 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 direct this sort of half angle bracket meaning that this 10 are not classical 10 there are two reliably distinguishable quantum states so what happens here is if the control qubit is a1 the target qubit gets rotated 90 degrees if the control cubed is a0 the target qubit doesn't get wrote.

Did so what would this do so this is a quantum version of this exclusive or it's called a control . 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 in 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 $PERCENT of 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 v4 a vertical photon so this diagonal photon is h plus V divided by square root of two repeat and the 135-degree diagonal the United States 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 dragons 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 for 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 hhv-8 the way to my getting HPV H&V 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 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 B and if we expand that out it's h plus h 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 at 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 waters 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 nieces pink another teacher asks Romulus and you get the same answer are 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 of 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 man entanglement is monogamous which is something else if these weren't very good at and the more entangled 22 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 of polarization so sometimes it will set up to vertical ones sometimes to angle theta sometimes to it 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 to 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 for version of a more complete argument that says any property at all that you would try to attribute to these Pope 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 tribute them separately this was the famous result of that John Bell discovered in 1964 well how do you explain it well the way that people do our 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 to 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 being someplace.

How would you even know where to send the message to so that's not a good explanation quantum mechanics gives the right explanation are 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 opposite pneus I mean the same this 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 ages and fees and so on it.

I 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 to and whenever you get around to measuring Romulus he will turn out also to be vertical.

Well this sounds like even worse thinking done 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 of pi 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 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 who 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 reported to the location of particle see and then we use that to rotate particle see 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.

I 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 see 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 on 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 are so well then Remus volunteer she 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 remiss 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 opposite pneus 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 a waters 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 cooked perfectly intact with each other they can't be entangled with anyone else and indeed the kind of classical correlation that is $OPERAND of two things.

Each being random but having the same random state because they're like they're two coins that actually are both heads are both tails not because they're in a state of opposite of mysterious oppositus 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 Alex Alice along some axes but not long 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 corners 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 with every one of them goes into a.

Superposition of being horizontal in the upper beam and vertical in the lower be in fact they all go into the same superpose 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 being 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 of 90 degrees and similarly the vertical and horizontal and we can say put a pecan optical element called a half-wave plate that does that takes horizontals that makes a vertical and virtual make some 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 of d 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 processing is a special case of 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 cubits 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 no 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 that 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 in entanglement so if entanglement is ubiquitous in almost every interaction between two systems produces entanglement why wasn't 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 because entangled the remaining ones behaviour 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 by 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 but 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 the p here's an example of a large number.

It's a if you if you are very smart you can realize that this number is the crease 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 it to 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.

Ionic on a pencil and paper or even on a pretty powerful classical computer is to take this number and figure out that these are it's too unique factors are however this job is easy relatively easy for quantum computer not a whole lot harder than multiplying and the reason is well I want to the reason exactly yet but it works because during the processing even though the question and the answer 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 will are known to help for and once where they wouldn't so it's not rich 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 aircraft a correction techniques which are heavily being researched in this laboratory now we'll do the rest so the quantum computation doesn't have to be perfect an example of a quantum error correction code is something that will take a state of one cubit and encoded into an entangled state of five cubits such that any one of these five cubits can be damaged and then undoing this operation sucks all the errors out into and throws them way into these ancillary cubits and the original one comes out unscathed now extending that kind of idea for a whole computation involves are continually feeding in our clean cubits 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 are 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 board 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 Cuban how much information is contained in a cubit 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-up somewhere quiet 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 to 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 there 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 nieces I don't believe that God placed ice and entanglement he said called it a spooky action at a distance or in german it's such bukkake fair and vehicle which e 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 what 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 he might say it was echoing a footballer said to Einstein when Einstein said that God doesn't play dice and horses stop telling god what 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 of 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 one is time for the second 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 his system are 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 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 and that's that's pretty much the way everybody thinks of it now even those they still can't agree with what language to describe it with now another person around the same time is as Einstein was shredding 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 during the wheel of your car and has 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 come 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 imagine application of it the reputation of these wrong ideas in the early nineteen eighties by Deeks and waters and zurich 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 quite 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 that meant 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 cubits compared to end classical bits are in analog variables and this is someone in ill-posed question because our 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 and you can get out a quantum system within particles has exponentially many complex numbers i have mentioned the fact that these numbers can be complex but there's exponential amount of information in it and yet you can only get in 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 disk 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 going to error correction for analog information if I have a slight error in a voltage that's . 5 4 3 volts instead . 544 how do I know that wasn't . 544 to begin with.

Rather than it was . 543 and had a hundred 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 is a SI information processor and the stomach is a food processor will leave the thing that's different between a classical computer in a quantum computer is the thing that similar is you give it a a classical input of n bits and you get a classical output of in 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 cubits where each of these numbers is it is an independent variable to to the end to the end 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 large dimension space where is 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 is . finding finding the period of a periodic function AA and it works we have we have in the computer we have two registers and call them the X register in the why 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 extra disturbing.

0the why register being zero the extra register is a uniform superposition of zero with why register and each individual value of x then the next thing we do is to reversibly compute this function is 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-ray gesture 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 magistrate 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 shorts algorithm that means you can factor the number now this is something actually very familiar physicists it's the problem of of multi slit diffraction so our multi slit interference as we know in the two-slit experiment are 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 will get is a maximum probability of of the photon landing here 0 probability here goes up to maximum down to zero and sewn in a 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 who's spacing is inversely proportional to the day 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 of 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 gonna get a little information about the slip 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 your slits and of course your adversary will say take all the sluts 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 slips there are so even one photon will give you a good estimate of the slip these and that's exactly what's happening in shorts algorithm and you would say well why don't you just build a large are diffraction grading 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 to two-factor uh a hundred bit number you would need a diffraction grating with 22 the hundred 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 cubits or if we have good error correction.

And build it the way we know how to build it now a few few billion cubits maybe would be needed.





##########################################