- [Elisa] Okay good, so
as I mentioned before,
now that we have learned about edge
that shows the algorithm,
I would now like
to show you how to
implement that with Qiskit.
So, I've prepared some code,
but I will go slowly through that.
The first solace just some imports,
import numPy again,
import some Qiskit functions that we need.
We also need to load our IBMQ accounts.
if you sign in for the
IBM quantum experience,
you need to load your account
so that you can work can later
on use the extra devices.
- [Announcer] Elisa, could you please
zoom in on your screen so that the,
this is bigger thank you.
- [Elisa] Is that better?
So yeah, this is just up imports
and for plotting the histogram,
we will do that later as
well to see the outputs.
So now in the first step,
I'm defining my Deutsch-Jozsa oracle.
So what I do to define the oracle
is first of all I create
a quantum circuit.
So I call my quantum circuit, oracle QC
and I created just by saying,
okay, I want to do a quantum
circuit on N plus one qubits.
Now, the reason I have N plus one qubits
is I need the N-qubit that
are input for the function
that works on N-qubit.
But then the plus one comes from the fact
that for my oracle,
I told you before,
if we implement the face oracle
instead of the bit oracle,
which we're doing now,
we actually do need still
need this extra qubit,
the qubit that I call Y before
that is in the minus
state in the beginning
and in the end,
and we still need to have at
this qubit to act on that one.
Because this is how we actually
add the Y plus F of X
will be on this last qubit
So that's how I created not only N-qubits,
but N pplus one qubits.
So now I will the oracle function,
I defined it to have two inputs,
I can tell the oracle
which case I'm looking at
whether I look at the case
balance or the case constant.
And I will tell it whether
how many qubits I'm acting on.
So that, according to that
it creates a quantum circuit,
given the number of qubits end.
So let's first look at the case
where I have a balanced function.
Now there would be a lot of different ways
to create an oracle that
gives a balanced function.
One could for example just say,
okay the first N over two inputs will be,
so from out of my two
to the N bit strings.
The first ones will all be,
like if I sought them will all be zero
and the others will map to one.
In this case,
I could also just look
at one qubit and say,
okay, if this qubit is zero,
we will output zero if this
qubit is one will output one
but this is a bit although
it's a bit too easy.
So what I'm doing also easy
is I'm applying a C-NOT gate on each qubit
to the one that target qubit is the one,
the Y qubit
and the Y qubit is the last qubit.
So it's a qubit N plus one
but since I'm counting
from zero on my first qubit
is actually zero not one.
So the last qubit is not N plus one,
but the last cube is the qubit N.
So what I'm doing is for the first N-qubit
so the qubit zero to N minus one,
I take them all as control qubits
and controlling on them,
I apply a C-NOT gate onto the qubit N
so on the last N plus ones qubit
and in this way,
what that means is that
when my depending on how many
of my input qubits are one,
this will each time will flip
whenever there's a one in my input,
that string I will flip
the sign of the Y qubit
of the installer qubit.
So if I have an even number
of once in metric string,
and I will get the
outcome zero in the end.
and if I have an odd number,
I will get the output one.
So in the end,
I'm basically just taking
the parity of my input string
and this make,
with that and making sure
that half of the outputs,
half of inputs will map to zero
and half of inputs will map to one.
But that's as I mentioned,
just one way to have a balanced oracle,
very specific one.
Now in the case where
the oracle is constant,
so if the case is constant,
then I will,
it can be either zero or one
we know that physically
doesn't make a difference
so one could also just
leave all that stuff,
but, well to show it show the full thing.
I'm actually choosing randomly than,
I'm taking a random integer zero or one,
that will be my call output in the case
where it is the output is one
that means that I'm always outputting one.
So I will get,
I will apply X as it my F of X will be one
so I have to flip the installer qubit
where in the case where it's zero,
I'm not doing the steps
I'm not doing anything
which is exactly if the
oracle always output zero
then we know that it's not
doing anything it has no effect.
Now, I've created this quantum circuit
which depending on whether I'm a balance
or constant function applies some stuff
to my installer qubit
but what we need to do now is the circuit
because I don't wanna
later on when I plot it,
I do not want it to show me what I'm doing
like show all this C-NOT gates
that I'm applying in the
balance case for example,
but what do I instead when
I want this whole thing
to be a new gate
and just to be shown
as one gate as one big block
which I call the oracle.
So you will later on in the plot
and when I plot the quantum circuit,
you will see a box called oracle
which is exactly has all of that insight,
and then I return the oracle gates
or oracle gate is what I call it here,
or cluster name that will display later.
And this oracle gate is
then the quantum circuit
that I'm returning.
If I call this function.
Now I need a second function
where I define the actual algorithm.
So I call it the Deutsch-Jozsa algorithm,
where I input N and the case.
And so for,
what I do in the beginning
is I'm creating a quantum circuit again,
on N plus one qubits.
However, here I have N plus one, N
or maybe you've learned that
from yesterday already in the,
if you did the labs,
or if you had a look at Qiskit already.
So the first number if I,
before I only had one number, here,
which means I just
create N plus one qubits.
Now in this case,
I'm creating N plus one
qubits and N classical bits,
the classical bits I will need later
to store my measurement outcomes
so if I do a measurement,
I need to connect some qubits
to some classical output
so that I can later on read read out
the classical output bits.
But I do not meet N plus one
because then select qubit.
I never measure I never
care about that one, right?
I just needed to construct the oracle
but then in the end,
I only have an output
that says I'm measuring.
So now I'm going with,
I look at all my N-qubit
and on each of the qubits
I apply the Hadamard
gate in the beginning,
because that's what we do
in the first step of the chosen read.
If you look at the circuit here,
we have first we start
in state zero by default
then we apply the Hadamard
gates to all of them,
which is what I'm doing here,
Hadamard gate on every qubit.
Then I'm, why one needs to
set up my additional qubit
the N plus ones,
the qubit N plus one,
which is the qubit N
because we're counting from zero, right?
So on this one,
I want to prepare the
minus state as we learned,
we said we want,
and we wanna have the minus state
and the minus state I can,
for example, create by
first applying the X gate.
So I'm getting from zero to one
and then if I apply the
Hadamard gate to that qubit,
from one it brings me to the minus state.
So now I've created the minus state
on the installer a qubit,
and the Hadamard gate on all N-qubits.
And now, maybe you have noticed that here,
I put in case equal random.
So that's a python feature
if I create a function,
and I give it,
I have some variables that I put in.
So in this case,
I have the variable N
and the variable case.
If I lay on call this function,
I need to give a variable N.
And this because I already
set a default value,
and it don't need to give
something I can specify it
if I don't want the
case random for example,
if I want different cases,
if I want it to be balanced,
I can put in case equal to balanced
but I can also just not put anything here
and then it will by
default take this case.
So the case would then be random.
And now, so I wanted
to just test that case,
ready to have the case random as well,
we're just randomly chooses
whether I have constant or balanced.
So if the case is random,
then I'm choosing my variable, random,
which is an integer out
of one of two integers
so either zero or one.
If it is zero,
I choose the case to be constant,
if it's not zero,
so if it's one,
then I choose a case to be balanced.
That's just an additional feature.
And so now I call my oracle.
So I define oracle as
the function that I have,
I'm calling the function to define before
that I chose that oracle
that's the function we
had in there last time
and made up here.
And this gives me back a circuit
so oracle is now the work of circuit
that we defined earlier.
In the circuit,
I append to the circuit
that I already created,
because I already created the circuit here
with the N plus one qubits
and the Hadamard gate
and the minus state prepared,
and now I add the Deutsch-Jozsa
oracle to that circuit.
We have to specify
that so that to the circuit
don't show the circuit,
I append the oracle circuit
and I appended on the N plus one qubits.
Okay, so now I'm what I have,
if I look at this,
I have my state zero,
I applied the Hadamard gates,
I applied the oracle, UF.
Now what I need to do is to
play again Hadamard gates,
so for all qubits,
and then after playing the Hadamard gates,
I want to measure each qubit.
So I'm doing a loop over all N-qubits
just the N-qubits I do not
care about the last qubit
and for each of these qubits,
I have my circuit.h on the
and then I so I on the I-qubit,
because I'm going from,
I goes from zero to N minus one,
I'm playing the Hadamard
gate on each qubit
and then I do the measurement.
Where the measurement I
have to specify the qubit
that I'm measuring qubit I
for all the different I's
and then the second one
is the classical bit on
which will be stored.
When I told you,
before when I created the quantum circuit,
I have here my N bits classical
bits on which is storage.
so here in this case,
I will store it on my
I bit, classical bit,
and then I return the circuit.
So if I now call this function
that shows the algorithm,
I will return me the hopeful
Deutsch-Jozsa circuit.
And now I need to run triple cells
from this cell
and run this cell.
And now I can call it.
So for example,
we can say N equal to four
and then my Deutsch-Jozsa circuit
is I'm calling that
Deutsch-Jozsa algorithm,
and then I want to draw it.
So let's see.
Now here, we can see
we have our four first qubits
on which we just apply the Hadamard gate
and the fifth qubit,
which is called Q4 is the one
where we prepare the minus state.
We apply the oracle to all of it,
which is, as I told you just
one box now that says oracle,
so we actually don't know what
that's constantly balanced
it's just this black box.
Then we have again the Hadamard,
the four qubits and the measurements.
Well now we wanna see
what it actually does.
So we wanna see what happens
if we run it on a device
or first before we run
it on the actual device,
let's run it on the simulator.
So as a backend,
I first, I will now choose the simulator.
And I choose 1,024 shots,
which were the simulator
doesn't make a difference
because it's exact anyway,
we won't have any noise I mean,
but then for later on,
if we run it on the actual device,
it's important to have higher shot numbers
so that we see the
probability distribution.
Then I'm calling my,
I'm creating my circuits
by calling this function
that I said before.
If for example,
now I could say N on N-qubit,
and I defined to be four before,
and I can say I want it to be constant.
Then I execute the circuit
by just saying, execute,
then I give the circuit
that I want to execute,
I specify the backend,
and then specify the number of shots.
That means that I'm
executing the whole thing
and if I do that result,
then I'm getting all the results.
The results have a lot of
different features, though
but what I'm actually
interested in right now
is just to get the number of counts.
So as they resolved start to get counts
to then get a different
get all the different counts
for the different states
that I'm measuring in the end,
the different bit strings,
and I do plot histogram
to see an histogram of
the number of counts.
So if you run that,
well, this should not be surprising.
We see that the probability is one
to measure the state
zero, zero, zero, zero
which is exactly what we said
because we what we would expect,
because we gave,
we said it should be constant
and if it's constant,
we determined before that
then the probability to
measure the zero string,
that string is one.
So if we now choose balanced,
then we have probability one,
but for a different bitstream,
we do not have the bitstream zero anymore.
In theory, we could have
any other bit string.
However, the way that
I designed the oracle,
we would always get this
bitstream for that oracle,
but depends on how I'm
designing the balance oracle.
In this case it's that bitstream.
And so if we,
I told you before,
if I won't put anything in here,
you'll take it by default the random
so we're just randomly choose.
Now we get for example,
now it would be balanced,
and again balanced
and constant so it just,
takes random outputs.
Now, we did it on the simulator
and I think you'll know that
we can also on the IBM quantum experience,
use actually do our jobs run them
on actual quantum computers.
So I hope the queues are
not too busy now, let's see.
What I'm gonna do is
because if you look into
the IBM quantum experience,
you will see on the right side,
all the different devices
that you can run jobs on.
But you see some of them, for example,
have a very long queue.
We can see here that's 22 jobs in it
but some other are empty.
Okay, I did not refresh the page
so that might,
it was five minutes ago,
but we have some,
it actually does.
Okay, we can see the
numbers increasing here.
So we can see that some devices
are more busy than others.
So what I'm doing is I'm saying,
give me the least busy backend
and then I'm gonna find already now
so I can execute it in the background.
Now I have to zoom out a bit,
so we can,
because, so in addition to
giving me the least busy backend,
where here by the way,
I had to specify also
that the number of qubits
should be at least N plus one
so that I'm not getting the
otherwise I might get the device
that has only one qubit.
That would not be helpful for me,
we cannot run it there
so I want to have a device
that has at least N plus one qubits.
Then I'm taking the least busy one.
I'm running the circuit,
I'm calling the circuit,
the function Deutsch-Jozsa algorithm,
I'm running it on the backend,
whichever is the least busy backend
with a number of shots
specified before it was 1024.
And in addition to the simulator,
I'm now adding the optimization level
so putting the optimization
level equal to three
which is the highest
number that you can have
which means that the
device automatically tries
to choose on the map, choose,
for example, the map and the way
that my qubits are connected
because you saw I'm playing
a lot of C-Not gates,
but then it's better if you
have applied the C-Not gates
to qubits that are actually connected
because of course not all
occupants are connected.
If I go back here,
now for example, looking
at one of these devices,
you can see in this case,
we would have zero
and one are connected
one and two are connected
but for example,
two and four are not connected
and if I have to play
C-NOT gate on two and four,
this will have much many more errors,
because I have to like do swaps
between all the other qubits in between.
So having the optimization
level where for example,
optimize for the map,
but then also it will
optimize for some gates
if you can simplify them, for example.
So here we see this is
the backend is burning,
which is actually what we
saw here before as well.
And then I also have
the Kiska Job Watcher,
which is a feature that I like a lot,
which gives me this,
makes this thing here,
pop up in the corner,
that's why I had to zoom out.
So we see here we have this box,
I can click on that.
And now I see,
it's actually my job is already done.
My job is successful run.
Otherwise, I would see
where in the queue I am,
I would see my queue position
so I can see,
get an idea of how much longer
it's gonna take to my job is run.
And so once the job is run,
I can as before get the results,
and then get the codes of the results
and then plot the histogram.
So let's do that.
And we see this case.
So what it tells us is
we have a 37.5% to chance
to measure the string one, one, one, one.
Where we only have 0.06%.
Well as it looks very different from what
we had on the simulator,
where the reason is
that we of course now have a lot of noise.
And also we can see that
this number is quite small,
but we can still identify immediately
that this is the outcome that we wanted.
But that's why it's so important
that we have a high number of shots,
because let's say I'm only doing one shot,
the probability would not even be
would be even smaller than one half
that I'm getting the state
and I might just get any other state
and I would not have a clue
whether that was correct or not.
But if I'm getting doing a lot of shots,
I can get an impression of
what the actual state is
that I wanted to measure,
which in this case is one, one, one, one.
So we know in this case now,
the function was balanced.
Now actually, because I wasn't
sure how long I might need
to wait in the queue
so I run some jobs before.
And what I wanna show
you now as you can see,
here for example,
we had very similar,
okay, a bit higher,
but also like 56% chance to measure
the one, one, one, one, one string
that works for the balance function.
However, when I'm looking
at the constant function,
I'm getting 93%,
with 93% chance that right outcome,
which is of course much, much, much higher
than what we saw before.
So here the fidelity to get the
right outcome is super high.
And while the reason why
this is the case is that for,
in this case,
I had that constant function,
which means that my oracle,
we said my oracle actually
doesn't do anything, right?
it just it might apply the X gates,
but only on this,
it will not have any effect.
So then if we simplify,
it might not even do anything.
So we know,
we saw that the oracle will
not have an effect in the case
where we have the constant function.
But in the case where we
have the balanced function,
it will apply all the C-NOT gates
between all the qubits
and applying multiple C-NOT
gates causes a lot of noise.
That's why we have a
smaller success probability
for the other case.
But that's it for the Qiskit
implementation with virtuosa.
Maybe now I could take some more questions
and stop screen sharing.
Before then going to
the Grover's algorithm.
- [Announcer] Sure thing,
so I was looking through
I encourage people in the chat,
you had a question about
Qiskit itself this would be a great time
to ask a question about Qiskit.
We haven't seen any of the
questions get very high rank yet.
So one question
that's been lingering for a lot
of today's lecture is the mapping
of the oracle mentioned
in today's lecture,
the only form of arbitrary mapping
from X to Y to Y plus F of X.
And if so, why?
- [Elisa] I am not sure I'm
understanding the question fully
because I don't know
what arbitrary mapping
what they mean with that.
- [Announcer] Well,
here's one option we have,
this user we can invite them on screen
and have them explain it.
So let's see this is from Abhishek.
If you are currently active in crowd cast
and you're able to jump on,
let us know what your question is,
please let us know in the chat right now.
We'll give you about five
seconds here in the chat,
let us know,
otherwise, we'll hold on
to that one for later.
- [Elisa] Well I guess I mean,
otherwise, like someone answered there.
It's not the case that any
arbitrary Terry takes the form,
which is of course, right.
I'm not sure whether this is
answers the question though,
whether this was what the
person asking question meant.
Of course, not every
unitary takes that form
that is indeed just something
that helps us to,
that's our way to perform the
oracle to make it reversible.
- [Announcer] Hold on to that,
we'll mark that one is done for now.
We didn't hear from the person writing it
and we'll I think go back
to your lecture for now.
Grab some more questions later.
- Okay sure, then.
We will now continue
with Grover's algorithm.
So this algorithm is
famous to be an algorithm
that is searching an unsorted database.
And I'm not putting this in
exclamation marks because so,
as I told you before,
searching an unsorted
database is something
that we actually do not really see
as a very good feature,
like it's not very feasible
to search an unsorted database
because one would need to first freed in
all the full database in
order to apply it then
or at least it's not
clear how else one which
you sign the oracle as the search
that the oracle itself
does not take longer
than the full algorithm,
when classically implemented.
However, as I said before,
one can still have useful
applications with that.
So first of all let's,
so we're looking at,
we again define N to be
two to the power N elements
and now the good thing is in this case,
you can do it in starred up and time,
which by the way,
is the first algorithm word,
it's proven that it's faster
than then classical algorithm.
But so instead of calling it
searching an unsorted data base,
what I would rather say
is that we can find an X,
such that F of X equals one.
So this phone book thing
what people refer a lot to
when they talk about Grover's algorithm is
okay, yes, that is the correct name or no,
that is not the correct name
but as I said,
we this function F might more be like,
yes, all the mathematical
Boolean restrictions
that can pose,
imposed are correct or
no they're not correct.
So anyway this is,
the search algorithm.
And if we compare it to
a classical algorithm.
A classical algorithm meets on average,
and I can think about it
if I give you N names,
and I want you
and I'm wondering to which
belongs the phone number,
then you can tell classically,
you just go through one after the other
and on average you will
need N over two time.
So it scales with N.
So in this case,
we do not have an exponential advantage
because we need the classical
with a quantum algorithm we
need square root of N time,
but with the classical algorithm,
we need N pi of N time.
But we do have a polynomial advantage
and this one was actually proven,
like for other algorithms,
it's more that we cannot find.
For example, for the ones
where we have an exponential advantage,
we have an exponential advantage compared
to the best known classical algorithm,
but it's not clear
whether they would be even
better classical algorithm.
While in this case,
we know we can prove
that there's no better
classical algorithm.
So let's define the goal
again mathematically.
So the goal is we want to
find our winning element W,
given some oracle, UF,
which implements the function F
that has N input bits,
and outputs either zero or one.
And we define F of X
such that it outputs one
if X is the winning element
and zero if not.
So as I said,
the winning element can be the name
that corresponds to the phone number,
but it can also be the element
that satisfies all the constraints.
And then we actually also
need another function
which I call F zero of X,
which is very similar,
but it does not even depend on W.
So just output zero in the case
where we input the zero bit string,
and it outputs one in any other case.
So remember that UF,
the action of UF
was that if we apply UF on X,
it will give us minus one
to the power F of X times X.
So if we now define our function, UF
and we wanted to map W,
two minus W
because well, it's should get
the minus one in this case
and then we every other element X,
it should then output map to X
because it should,
we just have minus one to the power zero
for all X that much W.
And the way we can write this,
as a unitary
is by taking identity minus two
times the projection onto W.
Anyone can very easily
see that this is correct
because if we apply UF
now on to the element W,
we will get identity times W
which gives us state W minus two times
the projection onto W is
just one minus two times W.
So, we get minus W which
is exactly what we wanted.
If we however,
apply to if we apply to some state X
that is orthogonal to W,
then the projection onto X
so the second part will be zero,
and we will just have identity times X,
so we just get the state X,
which does exactly what we want.
Now obviously, we can do the
same for the function UF zero
where we have the input
stage zero to the power N,
which it should map to
zero to the power N.
And X it should map to minus X,
for all X that are not zero.
And then we can see that in this case,
the unitary just as before, this time,
just the opposite way we can write it
as two times the projector onto
that zero bit string minus identity.
Okay, now let me give you
the quantum circuit
for Grover's algorithm.
And then similar as before,
we will go through every single step
that's gonna be some calculation
but in this case,
I will give you a very
illustrative way to describe it,
which I think it's very nice
to see what how robust algorithm works.
Okay, let's start with a quantum circuit.
So we again start in the
state zero all qubits
and you might guess that
in the first step we apply
Hadamard gates to all qubits.
And then in the second step,
we apply our oracle, UF.
Then we have another
round of Hadamard gates.
So this so far,
it's just like the
Deutsch-Jozsa algorithm.
Then we apply the other oracle the one
that corresponds to UF zero.
And other round of Hadamard gates.
And finally some measurements.
And then the classical
outputs that I'm getting,
I will call it a bit string Y,
just some bit string on N bits.
Now, all the part
that are in purple here,
is what we call the diffuser.
You will later see the effect
of that and I call it V.
And now actually I did not,
this is not the whole algorithm,
but what we do is we apply both UF and V,
we repeated our times where
we specify with RS later.
So we have the Hadamard gates
then UV, UV, UV are times
and then the measurement
Now the claim is that
Y the outputs equals W
with a high probability
and the high probability
we'll also specify later,
how high that probability is.
It's increasing with N.
So, we going to prove this now.
For that we will first define
the uniform superposition state.
Which is the state where we have,
just what would have after applying
Hadamard gates to all or zero qubits.
So just the equal superposition
we can know that by now
where just get the equal superposition
of all two to the N states.
And this we call S.
And then what we also define,
already wrote that down though
as we define V to be H to the power N,
times UF zero,
times H to the power N.
And this we can even simplify a bit
because, we know that we
just wrote down before this,
how we can write the unitary
as a projection onto zero minus identity.
So we will now write it into terms,
here we have two times
projection onto zero,
the power N
and then H to the power N minus.
Know we have times identity
and times identity does not do anything
so we can just cancel that.
And now, what we know is that if we apply
here in the first case,
we can get the two out to the front
and then we have H to the power N on zero,
which is exactly S
and then on the other side we have,
so we have bra-ket or ket-bra S,
this is just from both sides
we get the superposition state, minus
and then here we have
Hadamard times Hadamard
which is identity as well.
So V simplifies to just
be two times S minus identity,
times projection onto S minus identity.
So Grover's algorithm.
What did in the N does,
is it carries out the operation
V times UF zero.
Sorry, V times UF to the power R
on the state S.
So we initialize
basically with the state S
because we have zero
and apply all the Hadamards
then we apply R times UF and V,
and then we do the measurement.
Now maybe it's confusing
where I'm writing V times U
and not U times V.
This is because if I have my state zero
and I apply a gate A,
and the state I'm getting
here is A times zero.
If I'm applying them another A, B,
I'm getting B times A times zero.
So, (murmurs) this B times A times zero.
So then first applying UF,
and then V I have to put the V to the left
and the UF and to the right.
Okay, now let's sigma,
last thing I really find now,
be the plane,
we need that one to illustrate everything
(murmurs)
we define sigma to be the plane
that is spent by R state S and W.
W the winning element,
S the superposition stage.
And then we,
okay sorry we defined another thing
we define W orthogonal
to be the state
that is orthogonal to W,
that lies in this plane
because there's, actually many
states that orthogonal to W,
but I want to have the
state orthogonal to W
that lies in this plane,
so that I can write it nicely
as a linear combination,
you will see that now.
So then I have also omega orthogonal,
you can define it as
one over screwed up two
to the N minus one.
That's my normalization
because I want to have,
I want it to be in the plane
with the superposition state
and the state X.
So what I want is
the stage the superposition
of all states X,
except for when it is that except for W.
So superposition of all
possibility to the N bit strings,
but not W
because it has to be orthogonal to W
which is now S
and then the other,
that's why the normalization factor
is two to the N minus one,
because we have only
two to the N minus one,
terms in the sum.
For the X now.
Given this, I can rewrite S,
in terms of just W orthogonal and W
is lays in the same plane.
So I can just write it as
two to the N minus one,
over two to the N.
So this is just
so that I'm getting the one
over two to the N factor
for every state.
One of us squared off two to the N,
plus and then here,
I have one over squared up
two to the N times omega.
I mean, I think you can see
now if I sum these two up,
I will get just the equal
superposition of all states.
And to simplify it in the illustrations,
I define my now some angles theta
such that I can write it this way.
So what I did is I defined theta
such that sine of theta over
two equals one over square root
of two to the N.
And then, we know
that sine squared,
equals one minus cosine squared.
So sine squared,
if I have sine squared to be that,
the other part has to be cosine squared.
So and we also know then that,
that means that feature has
actually two times arc sine
of one over square root of two to the N,
Good, so that was a lot of methanol,
but let's see how the protocol works.
Let's plot that especially.
So here, I'm gonna plot or plane sigma.
The plane sigma is the one that is
in which we have omega the winning element
And we also have omega orthogonal
which is orthogonal to
omega in the same plane.
And in the same plane,
we also have our superposition state S.
And we know by the definition
that we just made
that this angle here is theta over two.
So, we know S is very
close to omega orthogonal
because as is the
superposition of all states,
but omega wherever W
or, I think I mixed it up
calling it sometimes omega
and sometimes W.
It's a W orthogonal
is the superposition of
all states except for X.
so it's the superposition state
is much closer to W orthogonal than to W
So, in the first step,
we just prepare the state S.
So we just get,
we apply the Hadamard gates
and then we have zero
and apply Hadamard gates
and then we know where the green arrow is.
Then in the second step,
we apply, if I go back
to the quantum circuit,
we saw we first have,
the first step we apply,
we prepare the state S by
applying Hadamard gates,
then we have UF and then V.
So now we apply the second step UF
just given by identity minus two times
the projection onto W.
Now what does that mean?
If I'm projecting,
if I did take,
if I apply identity minus
two times projection onto W.
So identity means I'm basically starting
at where I ended before,
so sturting up here
and now minus two times
going into the direction of
because of minus two
to the direction of minus W
and the projection onto W.
So the projection of the element
that I'm just having
and here, I projected onto W.
So I'm getting this,
this is basically the projection.
And now I'm going minus two
times into the direction W.
So minus two means this and then this.
So I'm ending up here.
This is my state UF times S.
And this angle,
no I did not plot it very nicely,
but it has to be also theta over two.
So what step two corresponds
to is a reflection
at W orthogonal.
Then let's look at the third step.
In the third step we apply V.
V we notice we can write V
as two times the projection
onto S minus identity.
And similar to how I just showed you
that step two is a
reflection at W orthogonal,
we can show that applying V
is just a reflection at S.
So reflecting the F here,
an angle from where the orange,
at the end of the orange we're here.
So we have an angle theta to the state S.
So if we reflect we go up
by another angle theta here.
So here we have V times UF times S.
What that means is that
if we apply V times UF,
then this corresponds to a rotation,
by an angle theta.
Because we see we were
before after step one,
we had the angle theta over two,
and now we got another
angle theta to that state.
Which means that if I have
because in the quantum circuit,
I told you we're not only playing at once,
but we're actually applying it R times.
So if I have R applications,
of step two and step three,
then the state,
is rotated by R times theta
I think that makes sense.
One rotation corresponds to theta
so R rotations correspond to
a rotation by R times theta.
So now the question is how do we choose R?
We want to choose R in a way,
such that if we apply it,
if we do our rotations,
so we move by R time theta
plus the initial angle
that we had,
which was theta over two,
because we started in the
green state before and S.
That should give us
or it should be at least very close
to the angle 90 degrees this angle here,
which is pi over two.
And we can now solve this for R
and then we get
that R equals pi over two theta,
minus one half.
Another question equals theta.
Well, we have to find theta here
it depends on the number
of qubits that we had.
So we have theta equals two times arc sine
of one over square root of two to the N.
So we put that in here
we have pi over four times arc sine,
one over two to the power N square root,
and then minus one half.
If N is large,
then we were interested now it's better
than the arc sine will be similar
will be very close to the,
just, so arc sine of X
will just be X basically.
So we can write pi over four,
times square root
of two to the power N
and we don't even care about
the factor of one half then anymore
because we just want to see how it scales
and this scales S square root of N
So, with this we showed
that it actually scales
as square root of N.
Now, the question is,
the problem is this R
that I just determined,
in general it will not
be an integer, right?
It will not be,
you're not telling me that
I have to do five rotations,
but it will tell me
that I have to do 5.3
rotations for example,
so, then I will not be exactly on W
but I will be for example here.
And if I'm here,
I still have a small probability,
if I do a measurement
to measure some state
that is orthogonal to W
and I have a very high
probability to measure W
and other questions,
what is the probability?
So, if I apply R,
if I do R calls to the oracle.
And then do the final measurement.
And this will result in this state W
with a minimal probability.
And now we know,
so the probability to measure W.
Let's look what is the worst case
to determine the minimum probability.
And the worst case,
because we always rotate by theta
over by theta every time we,
or if we increase R by one,
we will do another rotation by theta.
So, the worst case is the case
where we have here W and
T we have W orthogonal
and in the worst case,
we end in a state here,
such that this angle is theta over two.
If it's small It's even better,
if it's larger,
we will just apply another round
and then be here on the side
but still be closer than theta over two.
So in the worst case, our angle
and the end will still be theta over two.
If we have theta over two here,
the probability to measure the state
and the state that is not orthogonal to,
that is not W is sine
squared of theta over two.
Actually the probability
to measure state W
or state W is cosine
squared of that angle,
so cosine squared of theta over two,
so we have one minus sine squared
of theta over two to measure that,
the reason I'm writing it with a sign
and that with the cosine is
because we know that sine
squared of theta over two,
if we go up here,
that's how we defined one over
square root of two to the N.
So now we squared
we just have one minus
one over two to the N.
So with a probability
of at least one minus
one over two to the N,
we will get the right outcome.
So if we have,
if our N is high enough,
we will get it have a
really high probability
to measure the right outcome.
And this is even though also this is
the worst probability
we might even be lucky
and get closer numbers get better numbers.
And that, as we'll see in examples
that we will do with
Qiskit in the next hour.
So I think now it's a good
time to have another one
or two questions
and then have another 10 minute break.
- [Announcer] All right, so
diving into the questions here.
Seems that May's questions
have been hanging out for a
big part of today's lecture.
So just getting through them.
The first question I
believe is already answered.
Is the Deutsch-Jozsa algorithm used
for search algorithms basically?
Believe the answer there is yes, correct?
- [Elisa] No the
Deutsch-Jozsa algorithm is,
no the Grover algorithm is the one
that is the search algorithm.
Deutsch-Jozsa algorithm is the one
that can tell us whether a
function is constant or balanced
and I do not see why this would
help for search algorithms.
- [Announcer] Perfect,
thank you for the answer.
Another question, just going
down a little bit here.
A few people asked
about the oracle itself,
asking if the oracle is
similar to a Turing machine
or Turing machine oracle's
- [Elisa] Well, in our case the
oracle would need to be able
to also act on quantum state.
So it would need to have,
be able to process superposition state
which the Turing machine oracle cannot do.
So you would need to is
not like classical oracle
but that's why
we have a unitary which cannot
only process classical states
but it can also process states
and superposition of quantum state.
So it's different.
