Quantum Computing Day 1: Introduction to Quantum Computing

Quantum Computing Day 1: Introduction to Quantum Computing

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

25 thoughts to “Quantum Computing Day 1: Introduction to Quantum Computing”

  1. 31:35
    Is it precisely true that a quantum gate job is just to evolve the wave function?
    I know it is true. However, how to do such gate in the physics context? or how does a gate works in the physics' sense?

  2. So at the end he provides a link to a curated list of literature on Quantum Computing, which I assume all Google employees can access. How are us self learners supposed to access those resources?

  3. You could look them up, or just take a course on the subject. It's not like this information isn't available elsewhere.

  4. You just don't get it Mr. Foam. it's all about the Hindenburg Uncertainty Principle. It's an extremely esoteric physical phenomena, with it's roots in Combusting German Airboat Theory… It describes a lowest limit for German Blimp Navigation and it includes all the major phenomena, and incorporates new and previously incompatible ideas… such as.. Quantized Gravity + weak + strong forces + relativistic revisions of quantum mechanics + the CBF (i.e. Combusting Blimp Force). A complete theory

  5. can you FEEL the difficulty and POWER of HINDENBURG UNCERTAINTY?!??!!?….


  6. Contrary to some of the other negative comments, I thought this was pretty good. I didn't follow the details of the algorithms he showed at the end, esp. without being able to see the equations. But I understood the idea of that well enough, and overall I thought he covered the ideas well.

  7. did me good! Had been studying the basic quantum mechanics and encountered fascinating terms related to quantum computing frequently..the three days of these talks left me better..

  8. so you only have to send 1 bit through the processor and it runs on all your super positioned bits still in ram ?

  9. @MrTeaB – A Q computer by itself? No. However, imagine a hybrid (binary/quantum) computer 100 years from now. The conventional (binary) side will be literally HUNDREDS OF THOUSANDS of times faster than today's fastest supercomputer. It alone would whip a Go grandmaster silly. I'll even predict that a conventional computer (at least 100 times today's best) will do so using Chess like algorithms in about 10 to 20 years. In 50 to 100 years, hybrids will be playing games beyond human comprehension.

  10. @ObserversParadox – (p2) The IBM Blue Brain project (/watch?v=8iDR8Z-e_GU) is working towards emulating a tiny part of a rat's brain. In the US, a full cat's brain. Still others, the human brain. They are all proceeding on a fundamental/modularity approach where any of the fundamentals or module-level components can be experimented with to create many "intelligence" paradigms. These coupled with quantum computers will be well beyond the awareness and intelligence of total humanity in < 100 yrs.

Leave a Reply

Your email address will not be published. Required fields are marked *