mod03lec18 - Grover's algorithm Programming

Summary

This video tutorial delves into the implementation of Grover's search algorithm using Qiskit, a quantum computing framework. The presenter guides viewers through creating a quantum circuit to search for an element in an array of size 16 using a 4-qubit register. The tutorial covers the creation of a phase oracle, the application of multi-controlled Toffoli gates, and the reflection about the uniform superposition state. It also explores iteratively applying Grover's oracle and reflection to increase the probability of measuring the marked element. The session concludes with a discussion on the algorithm's effectiveness and ponders future considerations like handling multiple marked elements and unknown quantities.

Takeaways

• 🔍 The video discusses the implementation of Grover's search algorithm using Qiskit, a Python library for quantum computing.
• 🧩 The example focuses on searching for an element in an array of size 16, which can be addressed using a 4-qubit register.
• 🌐 An ancillary qubit is required to store the state |-⟩, which is used to convert a standard oracle into a phase oracle.
• 🔑 Grover's algorithm involves creating a superposition of all states, applying the oracle, and reflecting about the uniform superposition state.
• 🎯 The oracle function, represented as f(x), is crucial for identifying the marked element, which is the element we are searching for.
• 🤔 The implementation of the oracle is demonstrated, showing how to use a multi-controlled Toffoli gate to achieve the desired functionality.
• 📊 The video uses a state vector simulator to visualize the state of the qubits throughout the algorithm's execution.
• 📉 The script includes a step-by-step guide on how to apply Grover's algorithm iteratively, including the use of phase oracles and reflections.
• 📊 A histogram is used to show the probability distribution of measured states, highlighting the marked element with the highest probability.
• 🔮 The video concludes with considerations for future exploration, such as handling multiple marked elements and scenarios where the number of elements is unknown.

Q & A

What is the primary focus of the video script?

The primary focus of the video script is the implementation of Grover's search algorithm using Qiskit, a Python library for working with quantum computers.

What is the size of the array that Grover's search is applied to in the script?

In the script, Grover's search is applied to an array of size 16, with indices labeled from 0 to 15.

How many qubits are required to address elements in an array of size 16?

Four qubits are required to address elements in an array of size 16, as 4 qubits can address elements from 0 to 2^4 - 1, which is 15.

What is the purpose of the ancillary qubit in the Grover's search circuit?

The ancillary qubit is used to store the state |-⟩ and is necessary to turn the standard oracle into a phase oracle, which is a requirement for Grover's search algorithm.

What is the marked element in the Grover's search example provided in the script?

The marked element in the Grover's search example is the element with index 13, which is represented by the bits 1 0 1 1 in reverse order due to Qiskit's least significant bit to most significant bit ordering.

What is the role of the oracle function in Grover's search?

The oracle function in Grover's search is represented by a function f(x), which is 1 if x is the marked element and 0 otherwise. It is implemented as a unitary operation that flips the phase of the marked state.

What is a multi-controlled Toffoli gate and how is it used in the script?

A multi-controlled Toffoli gate is a quantum gate that takes multiple control qubits and a single target qubit. If all control qubits are in state |1⟩, it flips the state of the target qubit. In the script, it is used to implement the oracle for Grover's search.

How is the reflection about the uniform superposition state achieved in the script?

The reflection about the uniform superposition state is achieved by first rotating the uniform superposition state to the state of all zeros using Hadamards, then reflecting about the state of all zeros, and finally rotating back to the uniform superposition state.

What is the initial state of the qubits in the Grover's search circuit as described in the script?

The initial state of the qubits in the Grover's search circuit is a uniform superposition of all states for the first n qubits, and the final qubit is in the state |-⟩.

How does the script visualize the state of the qubits during Grover's search?

The script visualizes the state of the qubits by projecting the state vector onto the 2D plane spanned by the marked state |a⟩ and the uniform superposition of unmarked states |e⟩, and then plotting the projection.

What is the outcome of running Grover's search algorithm as described in the script?

The outcome of running Grover's search algorithm as described in the script is that the highest probability measurement is the marked element, which is |1011⟩ in this case, demonstrating the effectiveness of Grover's algorithm.

Outlines

00:00

🔍 Introduction to Grover's Search Algorithm using Qiskit

The video begins with an introduction to implementing Grover's search algorithm using Qiskit. The focus is on searching for an element in an array of size 16 using a 4-qubit register. The importance of an ancillary qubit for the phase oracle is emphasized, which is necessary to transform the standard oracle into a phase oracle. The video explains the setup, including the need for n classical bits to measure the data qubits at the end of the circuit. An example of a marked element with index 13 is used to illustrate how the element is represented in binary and how the oracle function works in the context of Grover's algorithm.

05:00

🛠️ Implementing the Oracle using Multi-Controlled Toffoli Gates

The paragraph delves into the implementation of the oracle function using multi-controlled Toffoli gates. It explains the concept of a multi-controlled Toffoli gate, which acts on n control qubits and a single target qubit, and how it can be used to implement the oracle for Grover's algorithm. The video provides a detailed walkthrough of how to construct the oracle for a specific marked element, using the example of a marked element with all bits set to 1 and then generalizes to other cases, including the case where the marked element is '1 0 1 1'. The process involves applying Pauli-X gates to specific qubits before and after the multi-controlled Toffoli gate to ensure the correct implementation of the oracle.

10:03

🔄 Reflecting About the Uniform Superposition State

This section discusses the second key component of Grover's algorithm: reflecting about the uniform superposition state. The process involves creating a uniform superposition of all states, which is the initial state for Grover's algorithm. The video explains how to achieve this by applying Hadamard gates to all qubits, including the ancillary qubit. The reflection about the uniform superposition state is then described, which is necessary to move the state vector closer to the marked state. The video hints that the steps for this reflection will be similar to those used for the oracle application and that the multi-controlled Toffoli gate will be used again.

15:04

📈 Visualizing the State Vector and Grover's Algorithm Iterations

The focus of this paragraph is on visualizing the state vector and the effect of Grover's algorithm iterations. The video demonstrates how to use a state vector simulator to see the actual state of the qubits after each step of the algorithm. It shows the initial state vector and how it changes as Grover's algorithm is applied. The video then explains how to project the state vector onto the subspace spanned by the marked state and the uniform superposition of unmarked states. The changes in the state vector after each iteration of Grover's algorithm are visualized, showing how the vector rotates towards the marked state with each iteration.

20:05

🔍 Iterating Grover's Algorithm and Optimizing the Number of Iterations

This section discusses the iterative process of Grover's algorithm and how to determine the optimal number of iterations. The video explains that further rotations beyond a certain point will only decrease the angle with the marked state, so it's crucial to find the right number of iterations. The process involves computing the initial angle and then determining the number of iterations that will keep the state vector in the desired quadrant. The video then shows how to apply the full Grover's algorithm, including the oracle and reflection about the uniform superposition state, multiple times. The results are visualized to show the state vector's progression towards the marked state.

25:07

🎯 Finalizing Grover's Algorithm and Measuring the Qubits

The final paragraph covers the completion of Grover's algorithm and the measurement of qubits. The video demonstrates how to create an initial circuit with a uniformly superposed state and then apply the optimal number of Grover's oracle and reflection operations. The use of a quantum simulator to measure the qubits and obtain a histogram of results is shown. The highest probability measurement corresponds to the marked element, confirming the success of Grover's algorithm. The video concludes with further points for consideration, such as handling multiple marked elements and scenarios where the number of marked elements is unknown, encouraging viewers to explore these aspects on their own.

Keywords

💡Grover's Search

Grover's Search is a quantum algorithm designed to find a specific item from an unsorted database with a higher probability of success compared to classical algorithms. In the video, Grover's Search is implemented using Qiskit to search for an element in an array of size 16. The algorithm is central to the video's theme, demonstrating how quantum computing can be leveraged to solve search problems more efficiently.

💡Qiskit

Qiskit is an open-source quantum computing software development kit by IBM. It allows users to create, edit, and invoke quantum circuits. In the script, Qiskit is used to implement Grover's Search algorithm, showcasing its utility in practical quantum programming and its importance in the development of quantum algorithms.

💡Qubit

A qubit, short for quantum bit, is the fundamental unit of quantum information. Unlike classical bits, qubits can exist in a state of superposition, allowing them to represent both 0 and 1 simultaneously. In the video, a 4-qubit register is used to address elements in an array, illustrating the concept's role in quantum computing's parallelism and computational power.

💡Oracle

In the context of Grover's Search, the Oracle is a black box function that can identify the correct solution(s) to a problem within a search space. The script describes how the Oracle is implemented in Qiskit, marking it as a crucial component that allows Grover's algorithm to function by differentiating between the marked item and the unmarked ones.

💡Phase Oracle

A Phase Oracle is a concept used in Grover's Search to introduce a phase shift for the correct solution state, making it distinguishable from other states. The script explains how the standard Oracle is turned into a Phase Oracle using an ancillary qubit, which is essential for the algorithm's ability to amplify the probability of the correct solution.

💡Multi-controlled Toffoli

The Multi-controlled Toffoli gate, also known as the MC-TOFFOLI or CCX gate, is a quantum logic gate used to implement the Oracle in Grover's Search. As described in the script, it takes multiple control qubits and applies a Toffoli gate to a target qubit based on the state of the controls, which is vital for creating the Oracle function that can identify the marked element.

💡Reflection

In quantum mechanics, reflection refers to the process of inverting the phase of a quantum state. The script discusses how Grover's algorithm uses reflection operators to invert the amplitude of the correct solution state, increasing its probability of being measured. This concept is central to understanding the iterative process of Grover's Search.

💡Uniform Superposition

A uniform superposition state is a quantum state where each possible state is equally probable. In the script, creating a uniform superposition state is the initial step in Grover's Search, achieved by applying Hadamard gates to each qubit. This state is essential for Grover's algorithm to explore the solution space effectively.

💡State Vector Simulator

The State Vector Simulator is a tool used in Qiskit to simulate the state of qubits in a quantum circuit. The script mentions using this simulator to visualize the state of qubits after each iteration of Grover's algorithm, allowing the viewer to understand how the algorithm manipulates the quantum state to find the solution.

💡Amplitude Amplification

Amplitude Amplification is a technique used in Grover's Search to increase the probability of measuring the correct solution state. The script explains how Grover's algorithm iteratively applies the Oracle and reflection about the uniform superposition state to amplify the amplitude of the marked item, bringing it closer to the uniform superposition state.

Highlights

Introduction to the implementation of Grover's search using Qiskit.

Importing the necessary Qiskit modules for the demonstration.

Explaining the case of searching for an element in an array of size 16 using a 4 qubit register.

Discussion on the need for an ancillary qubit to store the state |cat-⟩.

Creating a circuit with n data qubits and an ancillary qubit for the |cat-⟩ state.

Introduction to the concept of the oracle function in Grover's algorithm.

Marking an element with index 13 and its representation in binary.

Explanation of the oracle function as a reversible operation in the algorithm.

Introduction to the multi-controlled Toffoli gate for implementing the oracle.

Detailed explanation of the multi-controlled Toffoli gate and its function.

Implementation of the oracle for the case where the marked element is a string of all ones.

General case implementation of the oracle for a marked element of 1 0 1 1.

Discussion on the application of the multi-controlled Toffoli gate in the oracle.

Introduction to the concept of reflecting about the uniform superposition state.

Explanation of the steps to reflect about the state of all zeros using Hadamards.

Building the initial circuit with a superposition of all states and the |cat-⟩ state on the final qubit.

Running the circuit using a state vector simulator to visualize the state changes.

Projection of the state vector onto the subspace spanned by |ket a⟩ and |ket e⟩.

Iterative application of Grover's oracle and reflection about the uniform superposition state.

Computation of the initial angle theta naught for the state vector.

Discussion on the effect of multiple marked elements on Grover's algorithm.

Final circuit construction with the determined number of Grover iterations.

Use of the qasm simulator for a real-world scenario where the state vector is not accessible.

Observation of the highest probability of measuring the marked element at the end of the algorithm.

Conclusion and future considerations for the algorithm's application.

Transcripts

[Music]

uh hello everyone

today we look at the implementation of

grover search using kiskit

so let's get started

so first

as always we need to import

the cascade modules

so let's do that

now here we are going to look at the

case where we need to search for an

element

in an array of size 16

so here the elements are the indices are

labeled from 0 up to 15

and we can address this using a 4 qubit

register

the 4 qubit register can address

elements from 0 to 2 to the power 4

minus 1 which is 15

and apart from these four data

data qubits we also need an ancillar

qubit to store the state cat minus

as we had seen in the theory lecture

this allows us to turn the standard

oracle into a phase oracle

so

let's see

so we have n is 4 n is the

number of bits

for for the index

and we create n plus one qubits

uh so we have n qubits to address uh

these indices and then

an extra qubit for the ancillary state

get minus

and our circuit also has n classical

bits these are used to measure the

end data qubits at the end of the

circuit

so let's say we have one element marked

which is the element with index 13.

since 13 in binary is 1 1 0 1

the marked element is represented by

these these bits in the reverse order

which is 1 0 1 1.

the reason being that cascade considers

the queue bits from lsb to msb that is

from least significant bit to most

significant bit so if i just

order these bits 1 1 0 1 from the least

significant bit to most significant bit

i get 1 0 1 1 so the 0th qubit is 1 then

0 then 1

so our marked

element is represented by the index 1 0

1 1

and ah now let's see how does our oracle

look like

the oracle function

uh

now is is represented by some function f

where f x is one if x is the marked

element or the amount index and 0

otherwise

so we need to be able to apply this

reversibly as we had seen in the theory

lecture again this can be represented by

unitary which maps the state get x

where x is the data register

or the index register and get y where y

is a single output qubit

so this is mapped to get x and get y x

or f x we had also seen that when y is

in the state get minus this will bring

it to minus 1 to the power f x

get x and k minus

so we now have to implement such an

oracle so note that over here we already

know the marked element but in general

in in a general setting we will be just

be given this oracle as a black box we

won't have to implement it right so in

our case for for the purposes of

demonstration we are also implementing

the oracle

ourself so first let's see that how do

we actually implement such an oracle uh

to do so we need the concept of

something called as a

multi-controlled toefl so let's see what

is actually a multi controlled toefl

so a multicontrolled toefl gate is a

general gate

which takes n

control qubits say x 1 up to so on x n

these are our control qubits

and it takes a

single

single target qubit so we have n control

qubits

next we have a single

target qubit

and if these are in this

classical or standard basis state x one

up to x n and y

then the output after the application of

multi control toefl is going to be just

x 1 up to x n and then y

xor

and of x 1 up to x n so let's see how it

is going to be so the symbol for multi

control topoly is very similar to a c

naught in fact this gate is quite

similar to a c naught it is a

generalization of c naught to n controls

and here ah

the output is also going to be x 1 x 2

up to x n

and then y

xor

x 1 up to

x n so this is an and of x 1 up to x n

and then we

take an xor with y

so let's write it so u might be

controlled awfully which i'll

uh which i'll abbreviate it as msmct

acts on the control register x

and the output register y

and it produces x

and

y plus

x 1 up to x n the and of these things

so x is actually

x 1 up to x and only i am just

abbreviating it as x over here

so what is happening is that if each of

these x i's are 1 then the output bit is

flipped

if any of them is 0 it is not flipped so

we are essentially taking and of all

these

and this is how mighty control toefl

gate looks like now why are we

discussing this over here the reason why

we were looking at this was to implement

our oracle

so our oracle

uh

was supposed to be f x

which equals

1

if

x is

marked

index and 0 otherwise

now if you see

what we actually had to

do was that we had to implement this

oracle u subscript f which acts on x and

y

and it produces x

get x and get y x or f x

so suppose if the marked element if

marked index was just

marked index was

a string of all ones

for this case i uh we have just

implemented our effects why because this

is what the multi control toefl was

doing

so if the market element was on the

string of all ones then we know that f x

is going to be just x 1 x 2 up to x n

right because if each of these x is

going to be 1 then f x would be 1 if any

of them is 0 then this product or this

and is also going to be 0 so for f x

equals x 1 up to the product of x 1 up

to x n or the and of x 1 up to x n we

have we have we already know that

this circuit is going to be just mct

the multi controlled of fully right

so we have already seen how to implement

the oracle for the case where x is a

market index and which is that we just

have to use the multi controlled top

value

uh with xs control and y is the target

qubit

now let's take another case

say if marked index was say all zeros

let me say i work with just four

four qubits which is the case we have so

and we have these four bits so let's say

the marked index was zero zero zero zero

in this case

uh

my fx should be one only if each of

these is 0 each of my xi's are 0 and it

should be

1 otherwise right

so one way to implement it is as follows

that i can say that my f x is going to

be

uh

x1 complement

x2 complement

x3 complement and x4 complement so note

that in each of these is 0 then the

product or the and of x1 complement x2

complement x3 complement x4 complement

is going to be 1 otherwise it is going

to be

0 right because if any of these is 1

then the corresponding complement is 0

and so the whole and is going to be 0.

now let's take the general case or

let us take the case which we have over

here

wherein the marked element is say

uh

say mark element

is

what we have over here which is

1 0 1 1 in kisskids ordering right

so

here my f x would have been

x 1 x 2 complement

x 3 x 4 and if you see that this is

going to be 1 if and only if x 1 is 1 x

3 is 1 x 4 s 1 and x 2 complement is 1

which means x 2 is 0 right so basically

if x is the math element it is going to

be 1 otherwise it is going to be 0 and

now if you notice the general pattern

what we have to do is that we have to

define f x to be the bit flip over all

those cases where the index

wherein the marked index has that width

0 otherwise if the index is 1 then we

don't flip that bit and this is the

general thing

and now once we flip those bits we can

actually apply the multi control toefl

right so it's actually controlling on x

i being zero if if the marked element

has if with zero and controlling one x i

being one if the marked element is i

output one

so here this actually gives us a very

simple circuit

circuit for

u or a curl or u f

which is that

say we have x one and so on up to x n

and then i put uh

i put in poly x

if

i switch is 0

otherwise i don't put a poly x on each

of these ith bits and then i control and

then i apply this multi controlled

toefl

which controls my target register y

right because once we have uh applied an

x i can actually i'm controlling on

those bits being zero

which have which have the uh

which which basically have the uh

element marked index being zero at that

bit so

but i also need to now correct these

back so if the isbit is 0 i am going to

apply x once before mct and once after

mct so that i restore the state

of the input register and then i don't y

xor

ah

f x right so this is what i will be able

to get

so just think about it convince yourself

that it works

and now let me let us go back to the

so here essentially we look for those so

here this is our function apply

underscore oracle

this takes as input our circuit in which

is in the variable ckt it takes as input

the

marked index as a list of bits

these bits are in the same order as

biscuits orders its bits

and then i have an integer n which is

the number of data qubits this excludes

the cat minus state right this n

excludes the get measured because

including that we would have had n plus

one qubits and ah what we do in the

circuit is that uh we look for uh those

bits which are which are not

uh which are zero ah in the index of the

marked element okay so we look for those

bits which are zero in the index of the

marked element ah we apply a poly x

scales on precisely those qubits

and uh then we do a multi controlled

properly

again the

the control is the are the control the

controlling qubits are those from zero

to n minus one crystal starts the

ordering of the bits from zero and the

target is the qubit n which is the final

qubit

and then finally we again ah do a poly x

on the same qubits we did poly x earlier

this actually restores the states of the

input qubits

right so this is our complete function

to apply the oracle

now

uh the second ingredient of the growers

search algorithm which we had seen in

the theory lecture also was that we need

to be able to reflect about the uniform

superposition state

ah and as we had seen in the theory

lecture the way to do that was to first

rotate the uniformly superposed state to

the state consisting of all zeros and

you know that you can do this using

hadamards then you reflect about the

state of all zeros and then you again

rotate the state of all zeros back to

uniformly superpower state

now interesting thing now is that how do

we reflect about zeros

uh the hint is that the steps are going

to be very similar for the steps for the

application of oracle

and one more thing is that you will

again need to use the multi-controlled

toefl gate

i have given the reference to the same

her in the cell

and uh

just

to

uh re-emphasize what this my tk uh the

multi-controlled affiliate requires is

that it requires us input the list of

control qubits and the target qubits we

don't need answer lucky bit over here

so you will have to use this library to

implement the reflection about the

uniformly superposed state

okay so this is left as an exercise for

you

i have already implemented it so i am

just going to import this from my

solution

uh now once you would have implemented

the superposition of so so let us start

building the circuit now okay so these

were the basic ingredients of our

circuit uh when we start building our

circuit

uh we first need to create a

superposition of all states right this

is this is because this is going to be

our initial state so this is for the

first n qubits the qubits from 0 to n

minus 1

on the final qubit

we have to put in the state cat minus

okay so this is something which we have

to do and what you can do is that if you

apply a hard amount on the qubits from 0

to n minus 1 you will be able to obtain

a uniform superpose state on those

on the final qubit which which is

initially in the state get 0 as all

qubits are uh what you will do is that

we will first apply a polyx which will

bring it to state 1 and then we will

apply a hard amount which will bring it

to the state ket minus okay hard amount

on cat 1 is going to be 10 minus

so let's see so we do uh

poly x on the last qubit

we apply a harder mode on all the qubits

including the last one and this will

give me my required initial state

so let us see how the circuit looks like

so now the circuit looks like as follows

there is an x on the final qubit there

is a hard amount on all the qubits

including the final ones the final one

is change to the state get minus the

first four as in from 0 to 3 they are

changed to the state

of the uniform uniform superposition of

all all possible classical speech

so let's run the circuit and we'll

obtain the state vector

to

since we want to actually obtain the

state vector we are going to use state

vector simulator

ah this actually allows us to see the

actual state

of the qubits note that in real world

you won't have access to the state

right because this forbids the laws of

quantum mechanics but right now we are

doing a demonstration just to see that

how how these states actually rotate

under the influence of these reflection

operators so just to see the effect we

we are going to use the state vector

simulator ah to be able to run the

simulator we first need to assemble our

circuit using the assemble function and

then we run our simulator on the

assembled queue object and we obtain the

result

from the result we can obtain the data

which is the state vector

now we want to look at the state vector

only on the first 10 qubits the final

one we already know it will always

remain in get minus so to look at the

first and qubits we index the elements

from 0 up to 2 to the power

this gives us the state vector on the

first n qubits this is size 2 to the

power n

and now since it's very difficult to

visualize such a large vector we will

actually plot it ah we'll plot it

projection on the 2d plane we actually

know that this vector lies in the 2d

space spanned by get a and cat e so cat

a is the marked element over here and

ket e is the superposition of all the

unmarked states right so you can refer

back to the notation from the theory

lecture

so let's build our get a and get e

states

right so cat a uh is is just a

vector with with one uh element which is

one which is the thirteenth element

right so this is the

this is just a basis state uh

corresponding to the 13th element and

ket e is the superposition of all other

states and how we obtain it is that uh

so it's it's basically first

we have a

so there's a 0 in the 13th position and

then there is a uniform superposition on

the remaining ones so we obtain just by

creating a vector of all ones and then

subtracting k a which gives a

a 1 on every bit except the 13th one and

and then we normalize it

so this is our cat a vector so note that

there is one in the 13th position this

is a get e vector note that there is 0

in the 13th position and the remaining

are

equal and this vector is again

normalized

so

let's project let's write a function to

project our vector on to subspace

spanned by these two vectors

so we have this function get projection

this basically just takes the dot

product of psi with get a and get e

respectively note that k e and k e are

already normalized so there is no

further normalization needed on the

projection vector

so we can actually obtain the projection

vector once we are done we also have

written a function to plot this

projection vector

so let us see how does our initial

vector look like when we have run the

circuit to produce a statement

so we see that this is our initial

vector so cat a is the x axis over here

get e is the y axis over here that is

the marked element okay

so get a is the y axis get e is the x

axis

so here uh we see that it is quite close

to

x axis right it's further away from y

axis so actually

it's close to ah so it's since it's a

uniform superposition state ah it's

actually a bit far from the actual

marked element it lies more closer

towards the uniform superposition of

unmarked elements

and

so let's now bring it closer to y axis

which is the mark limit state

and to do that we need to

iteratively apply our phase vehicle and

the reflection about the uniform so let

us first apply our phase oracle

okay so we already have written the

function above

and let us draw the circuit so this is

how the circuit would look like

okay so note that here

our

marked index was

labeled as 1 0 1 1 since the qubit 1

since the first qubit is in the state 0

for the marked set of marked indices

we have an x

before and after mct and then there is

an mct in between okay so we have

discussed it in detail now

now let us see how do we reflect this

vector about the uniform state

so

to reflect it about the uniform state

and to do so

we will actually use the function which

you have to complete as part of the

exercise so i have already imported this

function

uh

so but you will have to implement it

again for the exercise

and

this is how the grover circuit now looks

like

once we have the

grovers oracle and then we have the

reflection about the uniformly

superpower state okay

now we are going to run the circuit

again and

we will actually plot the state vector

again after running the circuit

so

we again repeat the steps we obtain our

state vector simulator we assemble our

circuit we run the state vector

simulator on the assembled circuit

okay and then we obtain the result from

which we get the state vector we project

the state vector onto the state spanned

by uh the subspace standard by k a and k

t and then finally we project uh we plot

the vector we plot the projected vector

so we see that uh the angle where the x

axis is increased or it has moved

towards the y axis which consists of the

marked elements so earlier this was how

the vector looked like now it is making

a larger angle with the x axis right its

its a bit closer to y axis now

so we have indeed rotated it

now let us do another step of the phase

oracle followed by reflection about the

uniform okay so we apply our oracle and

then we reflect about the uniform

superposition

let's

draw the circuit now and see how it

looks like

so the circuit has now

uh two iterations of

of a grover's required followed by

reflection about the uniformly

superposed state

so this is four parts now so

uh

go versus recall reflection about

uniform supposed state global required

reflection amount uniform supreme coast

speed

and again we follow the same steps

to obtain the state vector after running

this complete circuit we also then ah

project the state vector onto this space

bandwidth at e and get a and this is how

it looks like and now we see that it is

very close to y axis right it is moving

closer and closer so initially

this is how it looked like after

rotation thing once this is how it

appears after rotating another time this

is it was

so we see that it indeed rotates

clockwise towards the ket state

so let's now do another step of

grover's vehicle followed by reflection

about the uniform superpower state and

now we see that this big chunk of the

circuit is now repeating thrice

so this is the term as a

global circle followed by reflection

globalization followed by reflection

about uniform globals that require

followed by reflection about uniform so

this these two steps are repeated thrice

and we as before we obtain the state

vector and we project it on to the 2d

space and then we plot the statement

and now we see it is going in the second

quadrant

right so after this

further rotations are only going to

decrease its angle with the y axis so

further rotations will not help much

uh in real world we actually can't plot

the state vector again and again we

actually need to decide the number of

iterations in advance so let's do that

now to do so we first need to compute

the initial angle theta naught

ah okay and

this is again an exercise for you

to compute the initial angle of the

state vector

once you are done so if this angle is

theta naught we know that each rotation

increases this angle by twice theta

naught after t rotation it is going to

be 2 t plus 1 theta so you need to find

the largest such t so that it remains in

quadrant one

this is again left as an exercise for

you

and

now to

complete the story we are going to run

it capital t number of times so i have

already obtained the value of capital t

since i had implemented that

and ah now we create an initial circuit

which consists of uniformly superposed

state on first n cubits and i get minus

on the final qubit and next we are going

to apply capital t times our oracle and

our

reflection about the uniform and then

finally we measure our qubits right

so this is how the final circuits looks

like

okay

and

let's see the effect this time we are

going to use the quasim simulator uh the

reason being that

we want to actually just measure the

qubits we are not looking at the state

vector now this scenario is closer to

real world also

so we have obtained our result and let's

obtain the count of every element after

which we can plot on histogram

and we see that uh

the highest probability is that of

measuring the state to be one month zero

one right and this was actually our

marked element also

so we this grover's algorithm indeed

does work

ah

and

here are a few more points to ponder

about in future

what happens when there are more than

one among element right so figure out

how the algorithm is going to change

how much what would be the initial angle

in that case how much would be the

rotation in each step and if possible

you can implement it also in criscite

this is not graded this part is an

ungraded part but it will be good for

you to think about

and what if you don't even know the

number of elements and what would be the

modifications that will be needed there

so these are questions to ponder about

for future uh these are not for

evaluation as such

ah

okay so this ends the session for today

uh

the original paper for

for

double research was given by love grover

in 96

here you can read about it more from the

elson and charles book also and the

implementation you can also see from

discrete text

okay