Quantum Computing Day 1: Introduction to Quantum Computing


Uploaded by GoogleTechTalks on 14.12.2007

Transcript:
>> NEVEN: Thanks for coming to the first part of the three part TechTalk on quantum computing.
The first is about introduction to quantum computing. And actually what I'm trying to
do is to take an unusual look at quantum computing. We want to take a look from the vantage point
of synthetic intelligence. Essentially a notion I would like to promote is the idea that in
order to create artificial intelligence, and by this I mean, tasks like pattern matching,
machine learning, has a lot to gain from employing quantum computers. Actually what I would claim
is if you were to have a working quantum computer of sufficient size on your table today, the
business of doing, let's say a machine with a learning algorithm, would entirely change.
And since this has such dramatic effect you might want to know, "Okay, do I have to bother
or worry about quantum computing before I retire?" Actually is another thing I would
like to get across. Working quantum computers will may--are probably or may be only a few
short years out. Actually in the next talk, we would go as far as this computer here,
this little laptop, has actually a MATLAB program on it that ties via Webservice and
Java and Webservice into a quantum chip that is admittedly still small, but despite of
what you have maybe read in the blogs or popular press, this is a real quantum chip that exists
today. And actually what we have done with it is take a human level task, object recognition,
and build a pipeline, a mix of classical and quantum algorithms to break this task down,
map it unto the quantum chip and bring it all the way back. And I think this type of
task will--I have a feeling that quantum computing might be the missing link that brings true
human level intelligence to machines. So, [INDISTINCT] this--my idea are not very farfetched,
as so does the brain have anything to do with quantum computing? So actually today the answer
would be bluntly, no. Neurobiology as the current paradigm has it that in order to understand
higher brain function, all we need to look at is an organizational level above the single
neuron and beyond. So essentially looking at neurons as classical devices that cooperate
or compete with each other, bringing about the neuro-dynamics that this is all you need
to understand higher cognitive function. But something I would like to predict is that,
sort of the pipeline of the nature I have described before and our increased understanding
how we might harness quantum processes to perform meaningful computation, this paradigm
might get challenged or is ripe for review. So probably, quantum computing will inform
our search for the quantum box as John Ekards [ph] would call it. Okay. So, after this introduction
to the introduction, let me jump to the first part, the basics of quantum mechanics. Again,
the intended audience is computer scientists and I realize it's a tall order to bring the
base concepts of quantum mechanics across in less than an hour which normally is taught
within a semester. But, let me try. First, let's look at a few base experiments. And
I kind of assume that everybody of you knows to various degrees about quantum mechanics.
I'm sure you have seen something on TV or read a book. You're an educated audience.
So first thing, an experiment from which--which likely shows the property of nature from which
quantum mechanics got its name, the so called Stern-Gerlach Experiment. And how this works,
and I'll try to use the mouse instead of my hands. You have a little furnace out of which
silver atoms come. And silver atoms have a magnetic moment so you can think of it classically
as a little, sort of compass needle coming out of your furnace. And of course they are,
sort of randomly organized, so there's this cloud of little compass needles flowing out
of your furnace. And then there this big inhomogeneous magnet that pulls and pushes on these magnets
depending on their orientation. And then, what you would expect because it's random,
some get pulled up, some get pushed down but it's essentially a random mix. So what you
see here on a classical prediction, if you put a photo plate behind it, this elongated
patch is what you would expect to see. Now what you really find is you only see two patches.
So this is, if you would have a little compass would mean, if you look at it you will only--two
things, compass needle up or compass needle down. So this is contrary to our, sort of
microscopic experience, and shows sort of first fundamental effect or a fact. Physical
observables are quantized. So it's like money, it comes sort of, in the smallest denomination,
as you one cent of nature. Actually this is--typically this cent of nature is typically denoted by
h--hbar, the Planck constant. And this [INDISTINCT] observable, it's like quantized is true for
energy, for angular momentum, for many important physical observables. So first effect. But
this effect has an important impact on how we observe nature. So let's look at something
that physicists do all day long, speed measurement. Essentially you can think of a speed measurement
in the following way: I have a little radar gun here in my example, and you shoot little
photons towards a car to measure its speed. So if you think about it, really those photons
have momentum and they push the car a little bit. But you would agree, you will not get
away with the excuse saying, "Hey officer, I wasn't that fast. [INDISTINCT] really pushed
my car." The reason you won't get away with this excuse is obviously the momentum of the
photons is so small that it doesn't really affect the system on the observation. But
now assume we want to observe something microscopic. So the car gets smaller and smaller, and given
that nature is quantized, I cannot always--or I do not always have the luxury of having
a probe fine enough that it is much smaller than the system on the observation. Or a different
way of looking at it, if sort of your probes would get larger, and here in this example
you would shoot bowling balls at the car, then obviously this measurement will affect
the state of the system, yeah? And this is in the microscopic world generally true that,
"observation affects the state of the system," okay? Second important fact. The third important
fact, here's sort of the quintessential experiment in quantum mechanics, is the double-slit experiment.
I'm sure you have heard of it in various ways. Now think of it in the following way, there's
a light wave coming through the first screen here, screen one, and it spreads out, think
of it like a water wave and now you have thrown a stone into a lake that was calm before.
So this wave spreads out, reaches the second screen and then, sort of two waves, come out
from there. So it's like throwing two stones into a lake. And we all know that the effect
in sort of these waves interfere, they can be superimposed and you have constructive/destructive
interference. And it creates an interference pattern like shown here, these black and white
stripes. But now if you would take a closer look, essentially again realized by a photo
plate, and you look at this picture here on the right side, the abc, and we look, we--it
gives a photon stream, make it very weak so that only one photon per time unit comes through.
Then we see a build up like this, sort of, you get little impacts on the photo plate,
and essentially you get this wavy pattern here. So essentially what we see if you take
closer look, that this wave pattern only gives us a probability where we might find the impact
of a particle. And this is also called the wave particle duality. And you can do this
with photons, meaning with light, or you can do the same thing with electrons. And again,
you can do it even if only one electron at a time goes through the slits. So it interferes
with itself. So the important lesson here, in superposition, a sort of a fancy word of
this wavelike behavior is that you can superimpose the states. So superposition, again it worked
for electron and photons, is a general principle in nature. Those three important facts. So
here comes the big jump, I don't want you to go home without formulas. So the philosophy
of these talks will always be give some intuitions and then jump to the formulas and I cut out
the middle piece. So here's pretty much all quantum mechanics, the kind of we'll ever
need, or you can derive the rest from this one single sheet. So how does quantum mechanics
formalism describe nature? First, if you describe the system, you want to know what its state
is. So, its state is here denoted by psi and these funny brackets around psi and the so
called Dirac Notation. So, this is just a way how a quantum physicist denote a vector.
So psi is just a vector and the funny thing around is the vector sign. And the state of
a system lifts in a Hilbert space. A Hilbert space, essentially for all purposes you can
think of it as a linear vector space with a scalar product over it. It's a complex vector
space. And moreover, we wanted to norm of the state vector is 1. And we will see in
a second why this is. Okay, now we know what a state is in quantum mechanics. Next thing
you want to know; how does my state change? So how the temporal evolution--fancier word
for it--comes about is essentially in non-relativistic contacts through the so called Schrödinger
equation. You see, the Schrödinger equation is basically a differential equation that
shows his changes--the first derivation according to time of the change of your state dependent
on what’s here on the right side, and what's on the right side is called an operator acting
on the state and this operator is called the Hamiltonian. The Hamiltonian essentially has
to do with the overall energy that's in your system. So depending on how much energy is
in your system and how it's structured spacial temporally, the state will change in different
ways. And actually, there's an equivalent way of writing it. If you go here to the right
side, essentially here the Hamiltonian is put into evolution operator. So basically,
you have a state here, psi as in time to zero. Then you--evolution operator think as a black
box and now you push your state in at time T and then you get the state at time T out
of there. So, state and temporal evolution. Now, it's important to see the differential
equation here was linear, the states base is linear, so we have a linear theory. And
this allows for an important fact that in particular means, if I have two possible states,
psi 1 and psi 2, then any linear combination, for example, like psi 1 plus psi 2 is a solution
as well. So here you see the super position reflect it. So two states, I can superimpose
them and again I have a valid state. Now comes the third part, how do I measure the state?
And here in classical mechanics you wouldn't find much, you know, as the position of the
car, yes sure I measure the position of the car. So there's the state of the system and
what you observe is kind of the same thing. But earlier in the speed measurement example,
we discussed that in quantum mechanics this is more involved. So in quantum mechanics
you describe an observable, like energy, magnetic momentum, through a matrix your A, an operator,
and this operator self-adjoined which basically means it allows for a spectral decomposition
into eigenvalues of this nature, that where the eigenvalue is m as a possible measurement
outcomes. And because this operator is self-adjoined, it guarantees that those measurement outcomes
are real numbers. Remember, everything before was complex numbers and you don't really see
complex number too observable to nature. You only see real numbers. The fact that this
observable is described by self-adjoined operator ensures this. So basically--and it has a complete
basis. So the eigenfunctions of A are complete basis for the Hilbert space where the state
lives in. So you can express any state in a decomposition like this, as sum c i over
the difference states. So again, as a large linear com--super position of the individual
eigenstates of your operator under consideration. And then the probability of finding a measurement
outcome is essentially the modulus square of the coefficient in front of the eigenstate
where you find your system, okay? This is called the Boen rule. And after the measurement,
your system would be in state a i corresponding to what you measured, okay? So that's my--the
trickiest part to understand. Observable corresponds to self-adjoined operator meaning it has a
set of revalued eigenvalues. These are the possible measurement outcomes and essentially,
if you decompose a state the way it’s written here the Boen rule gives you the probability
of finding the system in a certain state. Okay. So the last part that traditionally
was not taught as an important fact is how do you compose two quantum systems? You have
one and you have a second. But you can imagine if you want to build a quantum computer this
will often happen that it would be built or composed out of subsystems. So subsystem composition
is actually not that difficult. What you do is you take two Hilbert spaces, H1 and H2,
and you form the outer product of those Hilbert spaces. So this is now the total space your
system lives in and then you can--and the simplest way, take a state out of--one of
those two spaces and, like here, it says psi, and then you take a second state out of the
second system and you build the outer product, the tensor product of these two vectors and
you get a new state. So these special states are called separable states. But again, we
can build super positions; we can put a sum in front of sub states and get what this so-called
entangled state. So just in case--so here's sort of an important off ramp, if you ever
have heard about the Einstein Prodosky Rosen South Experiment or about quantum teleportation,
the ingredient you need to do things like quantum teleportation are entangled states
and we're not going to explain those today just sort of, if you study literature this
is sort of the off ramp. You have to get to--you have to understand what an entangled state
is, then you can proceed understanding what is quantum teleportation is. Okay. So, wow,
this--might be a little bit too much on this one sheet. Let's try to break it down. I think
in the next slides it will, sort of--I see a lot of shocked faces. I hope, sort of applying
this a little bit will make things simpler. So let’s a look at a very simple situation,
let’s take what's called a potential well. We take a particle that's an electron and
we put it into a box and we don't want to let it out. And here's a classic analogue
would be, let's say you go into a hole or let's say you have a large bucket and you
put a basketball in there and it bounces around, in such a situation you want to look at. So
the Schrödinger equation for this situation is written up here, and again, you recognize
it here was the Hamiltonian we have to use in this. And the Hamiltonian was, sort of
associated with the total energy of the system and you might know if you have something like
a bouncing ball, you have essentially two types of energy, the kinetic energy, how fast
this ball is flying around, and the potential energy, how high is it above the ground. So
these two terms together make up the total energy of this particle. So here we have now
differential equation. At first glance for the non-mathematicians thinks, "Oh, damn it.
Looks difficult to solve," but from here on, it's only mathematics. And it's a little bit
simplified by the fact that because the potential doesn't change in time, the Hamiltonian is
time independent. And then this allows for a solution that's down here, where the main
thing I want you to look at, is that this solution is again, a linear superposition
of this states psi, and psi are the eigenstates to the Hamiltonian. So this is how you can
compose a general solution for your Schrödinger equation. And here let's look at a special
case where our potential, you know, is sort of infinitely large then what you see here,
you know, in your little box, the wave functions, was the name for those solutions, for different
eigenvalues E, different amount of energy your particle can have. So that is how they
look, you know, you little bend it like a parabola, wavy, sort of wave with a shorter
wavelengths. So these are solutions. So now, more interesting, let's go to a situation
where the box is not infinitely high, it's not an infinitely deep well but it’s only
finitely deep well. So this is here shown in the right side. So what you see here is
something very important and we get the first sense of how this can help us in computation.
You see that the wave functions don't go down to zero right away where the border of the
potential well is. Actually they--there is still a finite probability of finding your
particle outside of the well and this is called the tunnel effect. So then I could use it--imagine
it would not be in the well but just sort of a barrier. So essentially, a potential
well but with a thin barrier. So then this particle could escape there even though it
doesn't have enough energy to jump over the barrier, it goes through, hence tunnel effect.
So think of it, here's this basketball, denotes a situation classically. If this basketball,
if I throw it in, if it doesn't have enough kinetic energy at that point to jump over
this wall, it will never get out of this potential well. So now for--and this is for computer
science. Everybody of you who has worked let's say with optimization problems will know that
getting stuck in a local energy minimum is a major curse whenever you express your problem
as an energy optimization problem. So, I think you will have a taste for the fact, "Hey,
I have a new mechanism here to get out of a local minimum." And that's indeed an effect
that we will harness for computation. Actually, adiabatic quantum computers do basically this;
they help you finding the global minimum and then the energy function by exploiting the
tunnel effect. Okay. So, let's sort of go through this one more time. Again, we have
learned that a state of the quantum system described at T-zero by a state function psi
of a T-zero, and then we have essentially two ways how this state can change. The first
one is continuous severe unitary evolution or via the Schrodinger equation, sort of a
continuous change over time of your state. And then, some nasty physicist comes along
or any human and will do a measurement. And then, oops, after this measurement, sort of
I drastically disturb my state and I come out in this state a i one of the possible
measurement outcomes in my measurement. And then, from there on, if nobody interferes
again, it will continue to evolve again like a unitary evolution via the Schrodinger equation.
So, that's basically what's--was on the cheat sheet, but as--it's like an ugliness this
is, you wonder when does a measurement really occur? Shouldn't the measurement instrument--I
mean, those are part of reality, too. It's a box with some pointers and some iron and
cables; shouldn't this obey quantum mechanics as well and shouldn't it sort of, follow an
unitary evolution along Schrodinger equation also? So, what does really constitute a moment
where measurement happens? And as the original--so when quantum mechanics came up, the first
complete formulation, the Copenhagen formulation of quantum mechanics, unfortunately failed
to do--give a clear definition of what is a measurement. And this--and at least, in
two cases, you can imagine that this yields problematic or paradoxical results. One is
a closed system. So, you have a box and you have some things in there, like let's say,
decaying nucleus and a cat. And we saw that when the state evolves--actually, we didn't
show this, but the Schrodinger equation sort of likes your preposition. So, it takes a
clean state and sort of spreads it out and then creates those super-positions we saw
about. So, what does this then exactly mean for a cat when it's in a superimposed state,
in particular if we would just think of it as a cat that is alive or dead. So, I'm sure
you have heard about the Schrodinger paradox. In this situation, essentially a cat in the
box and no observer involved. And this essentially has to do with the fact that we don't have
a clear prescription of what a measurement is. And this leads us to--and this is a key
question when it comes to interpreting quantum mechanics. What constitutes a measurement?
And again, in 1927, when the Copenhagen interpretation was formulated, again, it unfortunately failed
to give a clear definition of what is a measurement. So--and in '32, for Von Neumann came and said,
"You know what, I do it much cleaner. I also treat the measurement apparatus as a quantum
mechanical object. And I use only quantum mechanics to describe the whole thing end-to-end;
essentially of my state, I have my measurement device and I have sort of an observer that
looks at it. And then I analyze it in those terms." And essentially, what you see and
you have a state here in a superposition, a general situation, then you bring it in
contact--please remember existing composition. You bring it in contact with the measurement
apparatus here--and let's say and the state ready and you also bring them in contact with
an observer, again, in state ready. And now, here is this little arrow. Arrow essentially
denotes Schrodinger evolution again. Then, what will happen? What Schrodinger equation
does, it will bring about--it's like a zipper. Anything that the state touches goes into
a superposition as well. So, as soon as the system we want to observe, which is in a superposition
gets in contact with the measurement device, causes the measurement device to go into a
superposition as well. And then even worse, if the observer looks at it, it will go into
superposition as well. So, this is contrary to our everyday experience. Let's say, here's
this water bottle, it seems to be only at one position. It's not in a superposition
of multiple states, and we rarely see somebody in a superposition between life and death.
So, essentially the Von Neumann program, depending on how you look at it, failed. Essentially,
the way out that Von Neumann suggested is to say the final wave function collapse so
that you get sharp real states measurement outcomes as we experience them, this only
occurs--this final measurement occurs in the observer's mind. And I just--so, what happened
at that point is that essentially the observer's mind becomes a primitive notion that is foundational
to constructing physical reality. And I'm just mentioning this. This was '32. So Von
Neumann is not a new age kind of guy, you know. He was a very--I mean, as you are really
familiar with his career. What I want to point out is that quantum mechanics by its very
nature is very suggestive of bringing, of giving the observer special status, you know.
And this will of course be very important in the third talk when we look at the brain
in quantum mechanics. So, the last way to deal with what constitutes a measurement and
a very radical one, but one that's very popular among people who do quantum computing is Hugh
Everett's many world interpretation. So, what he essentially said is essentially a very
beautiful and very symmetric idea of it. He’d say, "You know what? It's not only one measurement
that comes out. There are thousand possibilities. All possibilities will occur eventually. Just
they happen in different parallel universes, in different classical universes." So, in
this notion to give you a feeling for this, I tried to use this, a time-proven allegory
of Plato, where Plato discusses human perceptual abilities in a situation where you have a
fire and prisoners in the cave only watch sort of two-dimensional projections of really
a three-dimensional world. And he discusses their limitations and how--what--picture of
realities that would construct, you know. So, in the "Many Worlds" or maybe better called
"Many Minds Interpretation," is a similar situation. The wave function psi is this enormously
high-dimensional beast. And what we seem--and this is sort of reality. However, what we
perceive as reality are low-dimensional projections. So essentially, our classical world as we
see it in this view would be only a tiny sliver of the much richer reality. So, this is the
Many World/Many Minds Interpretation which from an epistemological--or sort of an internal
consistency view, if it is correct that quantum mechanics is a linear theory, then this is
probably the cleanest interpretation of quantum mechanics. Okay. So, these were the basics
of quantum mechanics. So, you can take a ten seconds breathing. And we go now to quantum
computing. How can we use this now to build better mousetraps for our trade? Let's quickly
review classical computing. I don't have--I think this audience doesn't need any explanation
what a Turing machine is as a model for computing. And you probably know that any Turing computable
function can essentially be brought into form, where you have a function f that goes from
a binary, an n dimensional binary space to an m dimensional binary space. And basically,
you have the option for a physical, logical realization. That's those gates like Ngates,
Orgates, Notgates. And basically a program on its lowest level can be broken down as
you have a bunch of zeros and ones. And then you push those through a set of gates. And
at the output side, you--essentially here in the space, and the n-dimensional binary
space you look at your result. And you also know that I don't really need all those gates.
Subsets are enough to construct everything like, for example, a FANOUT gate and a NAND
gate as a universal set of gate. So this is pretty much all you need to represent any
Turing computable function. And so this is essentially the gate model using logical gates
for classical computation. Now let’s look how this looks in quantum computing. Actually
very similar. You start with a state. Here, denoted 100. This is actually--I simplified
from [INDISTINCT] notation. I had explained what a composed system is using this tens
of product symbol. I sometimes leave it out and just concatenate the individual vectors
like this or just write a vector like this. So these are all just different ways of notation.
So the main story here is you start with a state and you push it into a gate--actually
in quantum mechanics, the way to think of a gate is just Schrödinger equation doing
its job for, let's say, a fraction of a second. Now, again--or as a way of saying it, you
have an evolution operator that acts for a finite time on the state and then you get
some result. It's a very analogous in a way to a classical computation. And now comes
the--a trick. Let's replace the state by a superposition state. And if I had, let's say,
three cubits acting here, you can, let's say, use a state like this and push it through
the gate. And the gate doesn't care. The gate again is represented by a unitary operator
that it doesn't care whether it got just sort of a single basis state or a superposition
state like this. It will do its same job. And hey, that's cool. So it was one gate operation.
I can act on all these guys with one clock cycle. And I need to do this more. So you
go make a more radical superposition and you realize if you had sort of in binary notation
and digits, then the number of basis states that you have available grows as two to the
power of N. In one clock cycle, you can act on two to the N basis states. Now, it's fun.
I think it's obvious that you can expect some computational gains from this. Unfortunately,
superposition states, as you make larger, they're fragile. They tend to break. This
is one of the engineering challenges and we'll discuss on the next talk how to keep this
decaying of superposition states at bay. We have some of the intuition phase. A different
way of understanding the power quantum computers is as follows. And I mentioned it earlier.
You know that many problems can be expressed as finding sort of the minimum in some objective
function, you know. Or if--in the physics context, if this would be some energy landscape,
I want to find the minimal point. And again, doing this--now this is some computationally
expensive proposition--and doing this with classical [INDISTINCT] like--probably familiar
with gradient descent or simulated annealing or genetic algorithms; they are essentially
all flavors of gradient descent and they're all bound in some way or the other to get
stuck in a local minimum because there's this fundamental limitation. But remember the tunneling
effect, this can help us in certain conditions to get out of this local minimum and find
the deepest. In some ways, the quantum mechanical particle can see, if you want to allow this
metaphor, where the lowest state is and has--you have--in a gradient descent approach essentially
gets its quantum boost that comes from tunneling. And this is the second model of quantum computing.
There was gate model we looked at earlier, the adiabatic quantum computing principle,
which I will show actually in the second talk. They're equivalent, the adiabatic quantum
computing. So thinking about quantum computing in this picture and the gate picture we looked
at before, so those are equivalent. >> MAN: Remind us what adiabatic means.
>> NEVEL: Adiabatic means slow. And I will--the next talk will be extensively about adiabatic
quantum computing. So we'll explain this why the term slow enters there. Last, intuition.
And I actually wanted to take this slide out initially and take it with a grain of salt.
But still, I find it a powerful metaphor. That's not too wrong. Let's put it like this.
If you--again you know that many problems can be posed in form of a decision tree. And
if you are sort of a person confronted with decisions, so you have a classical particle,
then finding, let's say where the longest branches in your decision tree. The way how
you go, you go down one branch and check its length and then you go back and to take the
next branch down. And we have all these different algorithms how to do this in a smart way.
But at the end of the day, you have to always try one branch and come back. A quantum mechanical
particle, again by virtue of exploiting super positions, has a much easier time sort of
grasping all possible states a system can be in and sort of explore this decision tree
in a much more economic way. So this is--again, with a grain of salt. But I gave you--the
two first intuitions were exact and this is sort of a little bit metaphorically speaking.
So, now again, jump in to the calculus. At first, introduce this qubit, which the name
suggests it's a quantum bit. It's a quantum generalization of a bit. And the--like sort
of the bit in classical computation, it's a simple two-level system you can think of.
Essentially it--we are in a Hilbert space that is isomorphic. Meaning it looks like
C2, C being the complex numbers. So basically, I have two states here denoted as zero and
one. These are two linearly independent states. And again, you have heard it again, super
proposition, super position, super position. We can have a general state psi, you using
a general linear superposition of these two base vectors. And then what you heard earlier
also was that a state vector needs to be normalized; meaning the norm of this vector, which is
shown here, needs to be one. Actually, I still owe you the explanation why this is--you heard
me talking several times about the Born Rule and how quantum mechanics, the calculus essentially
doesn't tell you exactly what's the outcome is, in general. It only gives you probabilities.
But in order to properly speak about probabilities and have a probability calculus, it just needs
to be normed. Then hence sort of—-quantum mechanical states need to be normalized so
that probability interpretation makes sense. And then there's one more thing. So actually,
when you look at the state, you would say, "Okay, my quantum bit basically is described
by a complex number alpha and the complex number beta." And, you know, each complex
number can be represented with two real numbers. You would say, "Okay, I get this qubit. It's
essentially equivalent to four real numbers." Not quite. Again, we had already one knocked
out of this equation here. It takes one of the four out. And there's actually a second
one that goes out and you cannot understand why. As we said earlier, all measurements
results are always modulus square of the coefficients in front of a state. So essentially a phase
factor whose modulus square is one just makes it to be multiplied by one, so it has no physical
meaning in the sense it wouldn't change you're measurement outcome. So you can take any quantum
state and multiply it by a phase factor of this form and your measurement predictions--that's
all what quantum mechanics does; gives you measurement predictions--wouldn't change.
So actually there's a second parameter that goes down to drain. So once we've realized
this, we can essentially express by doing some--bit of massaging and expressing the
complex numbers by angles. And you see that the general state--it's actually a general
qubit psi can be represented like this with two angles; theta and phi. And essentially
qubit hence can be visualized as a unit vector moving on a sphere. And this sphere is called
the Bloch Sphere. So maybe another thing to take away from here is that a qubit instead
of--is not an analogue nor a digital thing. It's something in between. Before it's measured,
the state itself is obviously an analogueue entity but when I measure it, I will only
get two outcomes, it's in state zero or one which is eminently digital. So this is something
beyond digital or analogue. It's not either or; it has properties of both. So, going to
the general gate model of quantum computing, I think you can already imagine how this goes.
Again, various--we looked at it already. It's just sort of repeat. Essentially, how it works,
you have--you prepare your state with--let's say you have a bunch of qubits here, those
of size, initial qubits and you have gates, single qubit gates or multi qubit gates. Again,
these are little evolution operators acting for some finite time and they massage your
qubits into some final state of your qubit and then you measure it and, hopefully, you
get the result you are looking for. So now let's--and one more time, three steps for
a quantum computer. First, prepare your quantum computer in a well-defined state like, let's
say, 000 and a bunch of qubits. Then manipulate the state using unitary transformations and
it will lead to some final state, psi F, and then you measure the state F and read out
the result. And that's how quantum computer works. So now let's see what you're kind of
probably waiting for, show us that the quantum computer does something more powerful than
a classical computer. So the first algorithm to illustrate is the so-called the Deutsch
Josza Algorithm. It's a very artificial example. It doesn't do anything beyond showing. Actually,
historically, it was the first example where it could show that quantum computer does something
faster with less clock cycles than a classical computer. So the problem goes as follows.
You have a so-called function F that goes from zero one to zero one. This function happens
to be called an oracle. So you have the oracle function F. And essentially, here's a little
table that shows there are only four possible functions. If you give it a binary variable
X which can be a zero or one, then this oracle function you have four realizations of it.
Two of them was a function that's constant, so whether the input is X or one, its output
is zero and here F0 and F3 are constant oracles and F1 and F2 are not constant or in this
context called balanced. So the think about it, classically, how many runs of the oracle
would you have to do in order to find out whether your function is constant or balanced
now then? >> Four?
>> NEVEN: Four? That's actually only two, you know? You apply your oracle to zero and
you apply oracle to one and then you can see which of the four functions it is. So classical,
two runs. But now shows that with the quantum algorithm, we can do with only one run. And
this works as follows; here's our gate model. We prepare two qubits, one in state zero and
one in state one. And we have some gates here, two types of gates, one is called the Hadamard
gate and one is called the oracle gate and they bring those qubits into new states. Actually,
we're ignoring what's happening down here. We are only interested in what happened to
the first qubit here, then we will measure it. And even though we present these two qubits
only once, we go through this algorithm only once; we nevertheless get to know whether
F, the oracle, is balanced or constant. And I will show this here. So first, I have to
explain you what a Hadamard oracle gate is. Again, those are just unitary operators acting
on qubits. So essentially, here the--you see how the Hadamard gate acts on a state zero.
Basically, these guys produce superpositions. It takes zero and brings it over to zero plus
one, and as the Hadamard gate acts on a state one, then you get to superposition zero minus
one. So we create superposition, and you saw earlier that it's helpful to have superpositions
because you push one superimposed state through your gates and the eight gates act on all
basis states. And then there's the oracle gate which you see we have put the F in there,
so essentially the oracle gate takes a qubit XY and brings it over to X and here on the
right side, you have Y, X or FX. So if you verify it, the oracle gate is a unitary operator
and we are not concerned at this point how we can physically realize it. And so let’s
assume because it's a unitary operator there's some physical realization for it. Whether
that’s easy or not, different story? So now, let's run it. We start with zero one,
we, let's say [INDISTINCT], so the Hadamard gates act on our state 01, and produce this
state. Then the oracle gate acts on those and you can just punch in those formulas and
you see you get this unwieldy expression here. Then I massage this a little bit and then
I get this expression here, sorry, like here, you see where the mouse is moving? And then
we ignore this portion here. We only look at the first qubit which is in this superposition
state. Actually I pull this out, this piece here, and then we apply a Hadamard gate one
more time, and then we get a state that's down here, that's the state for first qubit,
it's a superposition of zero and one which is here in the last line. And now, if you
take a closer look, you'll see in the exponent F of the value zero, X OR F of the value one.
And this X OR operation if you go back here, if you look at the truth table, this X OR
can only be--will be zero for the constant functions, and will be one for the balance
functions. And then if you, plug this in here, you see that if it's constant, then it’s
zero, then essentially the second term here disappears, and the output of my first qubit
will be zero, and if the function is balanced then this here will cancel itself out and
you get as a result, one. So, it’s either zero or one depending on whether the function
is balanced or not, and again, we have done this by only a single run.
>> Why is it important whether it's balanced or constant?
>> NEVEN: It's not necessarily important. It's a guinea pig problem. It's just an illustrative...
>> [INDISTINCT] possibilities of it’s own? >> NEVEN: Yes, this is just how the problem
is posed. As I have said, it's an artificial, very simple problem, has no application. So,
probably what you think now, "Oh, Hartman is doing a poor job here. This is, oh Jesus,
I mean I cannot get it. We used unitary functions and we go just work off the calculus and then
we get a result. But really, intuitively I don't quite get this." Actually this is part
of the lesson. The lesson is that, the gate model of quantum computing I personally also
don't find terribly intuitive and inventing new algorithms as a framework is not all that
easy. However, in the next lesson, we will talk about adiabatic quantum computing which
has a much nicer geometric meaning, where it’s much easier to design algorithms. It's
a question of taste. I think for people who have a good algebraic mind, they will come
up with good algorithms in this word, but sort of, it is--using the gate model is tricky.
And there are only a few known algorithms that do something useful in the gate model;
might have to do with the fact that it's a bit unwieldy. I'm only a few minutes left,
so we'll rush through the next example which is quantum search. And again, in posing the
problem is very similar. Again, we have an oracle function F but right now it's from
the binary space n dimension binary space to zero and one. Essentially what this function
does, it marks one item in the input space, let's call this item X zero, and it marks
it as one. And this function as zero for all other input possible input values and the
goal is to find X zero. So that's already more meaningful, you know, quantum search.
And, we will just study a very simple case, where we assume that N is two. So finding
one item marked out of four, this is what we would like to do. And in order to calculate
it, I assume that the marked item is--is 1-0, the binary number 1-0, okay? So, finding one
marked item out of a number is a quantum search, and it's solved--its called--solved this so
called Grover Algorithm. Again you have--here's this gate model where you have Hadamard gates,
you have this oracle gate again, you know these guys already. And then there's this
ugly big D-gate in there and if you look closer it gets even uglier, but it does something
very simple. So we will look at this in a second. Again, think about it classically;
if you want to find one marked item in N, then basically, you have not--any of the best
algorithm you cannot come up with will be of big O-N. Basically you have to look at
all your items. With the quantum algorithm you can do this in square root of N. And again,
as the proof of this, all it needs is you construct an oracle gate where again you put
your function F in there, and then you prepare your state, an initial state like 0-0-1, and
then we will go through this now only in a superficial way; we apply the Hadamard gates
that generate a superposition, then I evaluate my function by using the oracle gate, and
then I get the result here. So, in the, before last line, this one here, and you see, what
this did already, out of the four states, remember I have assumed that F marks the state
1-0, you can see after those massages, the state 1-0 is marked with a minus--Oh, I have
marked it already. But unfortunately I haven't marked it good enough because minus one; again
modulos square if you measure it, is the same as one. So I cannot really discriminate minus
one from one here as a pre-factor. So, what this ugly big D does is nothing but essentially
changing the phase factor into amplitude and what--if you apply D, what you get as a result
is the end result, 1-0, okay? And again, what you can show for a larger N, this algorithm
finds a marked item out of N with big O and square root of N. Okay. So here's the last
slide which is another famous quantum algorithm, Shor's Algorithm, this actually is a crowning
achievement so far. And what Shor's Algorithm does it finds the prime factors in a composite
integer. And you have, maybe read in the press about it--this is important because if you
can do this well, many cryptography codes are actually based on the fact that it's hard
to find the prime factors in a large integer. And the best known classical algorithm if
you have a number N is actually exponential in lock N, this more complex expression. And
Shor's Algorithm does the same thing getting, rid of the exponential. So it's essentially
an exponential speed up over what you can achieve classically. And rather than going
against your lengthy how this works is, maybe let's conclude with what's today believed;
it's not proven but it's believed that this is sort of how the complexity classes relate.
You're probably familiar with the class NP which is essentially a complexity class of
problems which I can verify, not solve, but verify in polynomial time. And this class
NP has of course a sub-class; these are the problems I can solve in polynomial time. And
then there are these nasty [INDISTINCT] NP complete problems. These are sort of the hardest
problems in the space. They are essentially characterized by the fact that any other problem
in NP can be mapped in polynomial time onto NP. And then this whole thing is embedded
in P space, this is the complexity class for all algorithms that have polynomial space
requirements. And then here is what we care for, BQP, Bounded Error Quantum Polynomial,
so these guys--he is factorizing. So essentially this class seem--is probably--is believed
to be larger than P but it doesn't necessarily cover NP. And that's also a lot of the controversy
and some of the misunderstandings, so you cannot say that a quantum computer solves
NP complete problems. And so, this is the overall lay of the land, summarizing the computational
gains, you get from a quantum computer over a classical computer. Okay, that was it for
the first session. You might have seen I realized, again, in one hour cramming all this material
and this is tough to follow but there's a lot of literature on quantum computing. You
can see in the talk announcements, there's a list on fish, you can link to this and maybe
I finished with the shameless plug what we going to do next time. Next time, we will
show the image recognition algorithms we have realized on an adiabatic quantum computer.
And the main topics will be decoherence theory, this essentially deals with how do superposition
states, you have seen superposition states were so crucial, but unfortunately they are
fragile. So decoherence is essentially is the process of the superposition state breaking
apart. So we need to understand this if you want to build quantum computers. Then, you
asked it earlier, we will look at the adiabatic quantum computing principle more, then we
will look at a special or hardware implementation of this, done by D-wave. Actually next week
I will be joined by Geordie Rose who is the CTO of D-Wave, and who has built this first
adiabatic quantum computing chip. And then we will show how we did image matching using
this chip, and then I want to conclude with some implications it has for machine learning
and I want--I haven't solved it yet, but I want to entice you looking at some machine
learning problems that I think we should map onto a quantum computer because it's what
yield huge gains for this field. Okay, thank you. That's it.