## 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