Master's Thesis

Grover's algorithm in Quantum computing and its applications

Final Thesis 937.2 kB

Author of thesis: BSc Joseph Katabira

Acad. year: 2020/2021

Supervisor: doc. Mgr. Jaroslav Hrdina, Ph.D.

Reviewer: doc. Mgr. et Mgr. Aleš Návrat, Ph.D.

Abstract:

Quantum computing as a new field of computing is a quickly growing field which encapsulates the role of quantum phenomenon in our day to day lives. Because of the quantum characteristics, quantum computers have proved quantum supremacy over the classical computers. In this thesis we focused on discussing basics of quantum computing and in particular we focused on discussing the functioning, construction and implementation of Grover algorithm as a special case of quantum algorithms. We showcased its power as a database search algorithm over the classical non quantum ones through our algorithmic construction implemented through QISKit simulation environment. To simulate our construction, we made use of QASM Simulator and the State vector Simulator Aer backends and the results obtained correlated with the earlier discussed theoretical findings highly proving that Grover's algorithm provides quadratic speed up over the classical non quantum search algorithm which is a much better improvement but as at hand, the applicability of the algorithm as many others is  still limited by several factors amongst which includes high decoherence levels and gate errors.

Keywords:

Qubit, Superposition, Grover's Algorithm , Complexity, Oracle , Diffusion Operator, Quantum circuit, Quantum Gate, Grover Iterate, Initialization, Measurement, Algorithm, Search space, Bra- Ket Notation.

Date of defence

24.06.2021

Result of the defence

Defended (thesis was successfully defended)

znamkaDznamka

Grading

D

Process of defence

The student introduced his diploma thesis to the committee members and explained the fundamentals of his topic called Grover's algorithm in Quantum Computing and its Applications. The secretary read both reviews and the opponent's questions. The student had prepared slides with answers, which he presented to the committee. prof. RNDr. Josef Šlapal, CSc. Does it need a special quantum computer? doc. Mgr. Zuzana Hübnerová, Ph.D. You use coefficient ... for notation of probability? doc. Mgr. Pavel Řehák, Ph.D. What is the mean of brackets? The student's answers were not very convincing.

Language of thesis

English

Faculty

Department

Study programme

Applied Sciences in Engineering (M2A-A)

Field of study

Mathematical Engineering (M-MAI)

Composition of Committee

prof. RNDr. Josef Šlapal, CSc. (předseda)
prof. RNDr. Miloslav Druckmüller, CSc. (místopředseda)
doc. Ing. Luděk Nechvátal, Ph.D. (člen)
doc. Mgr. Zuzana Hübnerová, Ph.D. (člen)
prof. Mgr. Pavel Řehák, Ph.D. (člen)
Prof. Bruno Rubino (člen)
prof. Vladimir Protasov (člen)
prof. Matteo Colangeli (člen)

Supervisor’s report
doc. Mgr. Jaroslav Hrdina, Ph.D.

The thesis describes one of the most powerful algorithms of an area of quantum computing that is based on the principle of oraculum.  The core of the work is in chapter  3 where the author demonstrates the algorithm for databases of size 8. Chapter 2 introduces the necessary mathematical background and in the chapter 4 the author shows his own implementation in the chosen environment.  The student worked very individually.  I recommend the thesis to be defended.
Evaluation criteria Grade
Splnění požadavků a cílů zadání B
Postup a rozsah řešení, adekvátnost použitých metod B
Vlastní přínos a originalita C
Schopnost interpretovat dosažené výsledky a vyvozovat z nich závěry C
Využitelnost výsledků v praxi nebo teorii B
Logické uspořádání práce a formální náležitosti C
Grafická, stylistická úprava a pravopis D
Práce s literaturou včetně citací C
Samostatnost studenta při zpracování tématu B
Display more

Grade proposed by supervisor: C

This master’s thesis gives an introduction to quantum computing and is focused on the description of so called quantum Grover’s algorithm for searching in an unstructured database. The text is well written but is rather wide than deep, e.g. sections 1.4, 2.1, 2.2, 2.3 could be shorter or omitted and some other sections should be written more properly. The mathematical background is quite precise although I found some inaccuracies that question the right understanding of the mathematical framework by the author, see questions 1. As the main benefit of the work I consider a detailed computation of the algorithm in small databases and its implementation in Qiskit, an IBM open source software development kit. However, the computation is often inconsistent and it is difficult to follow it.
The question of right understanding of the mathematical framework arises again, see question 2. Since an amount of good work was done I suggest the evaluation by grade D if the questions are answered satisfactorily.
Evaluation criteria Grade
Splnění požadavků a cílů zadání D
Postup a rozsah řešení, adekvátnost použitých metod C
Vlastní přínos a originalita D
Schopnost interpretovat dosaž. výsledky a vyvozovat z nich závěry C
Využitelnost výsledků v praxi nebo teorii D
Logické uspořádání práce a formální náležitosti C
Grafická, stylistická úprava a pravopis B
Práce s literaturou včetně citací B
Topics for thesis defence:
  1. Show the first part of the Grover algorithm in the case of searching |11> in detail and compare it with searching |01>, including an explicit description of the corresponding oraculum.
  2. Please give a right definition of the Hermitian inner product on C^2 and explain the notion of a normalized qubit.
Display more

Grade proposed by reviewer: D

Responsibility: Mgr. et Mgr. Hana Odstrčilová