diplomová práce

Groverův algoritmus v kvantovém počítání a jeho aplikace

Text práce 937.2 kB

Autor práce: BSc Joseph Katabira

Ak. rok: 2020/2021

Vedoucí: doc. Mgr. Jaroslav Hrdina, Ph.D.

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

Abstrakt:

Kvantová výpočetní technika je rychle rostoucí obor informatiky, který přenáší principy kvantových jevu do našeho  každodenního života. Díky své kvantové podstatě získávají kvantové počítače převahu nad klasickými počítači. V této práci jsme se zaměřili na vysvětlení základů kvantového počítání a jeho implementaci na  kvantovém počítači.  Zejména se zaměřujeme na popis fungování, konstrukci a implementaci Groverova algoritmu jako jednoho ze základních kvantových algoritmů. Demonstrovali jsme sílu tohoto kvantového algoritmu při prohledávání databáze a porovnávali ho  s klasickými nekvantovými algoritmy pomocí  implementace prostřednictvím simulačního prostředí QISKit. Pro simulaci  jsme použili QASM Simulator a State vector Simulator Aer backends a ukázali, že získané výsledky korelují  s dříve diskutovanými teoretickými poznatky. Toto ukazuje, že Groverův algoritmus umožňuje kvadratické zrychlení oproti klasickému nekvantovému vyhledávacímu algoritmu,  Použitelnost algoritmu stejně jako ostatních kvantových algoritmů je ale stále omezena několika faktory, mezi které patří vysoké úrovně dekoherence a chyby hradla.

Klíčová slova:

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

Termín obhajoby

24.06.2021

Výsledek obhajoby

obhájeno (práce byla úspěšně obhájena)

znamkaDznamka

Klasifikace

D

Průběh obhajoby

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.

Jazyk práce

angličtina

Fakulta

Fakulta strojního inženýrství

Ústav

Ústav matematiky

Studijní program

Aplikované vědy v inženýrství (M2A-A)

Studijní obor

Matematické inženýrství (M-MAI)

Složení komise

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)

Posudek vedoucího
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.
Kritérium hodnocení Známka
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

Známka navržená vedoucím: C

Posudek oponenta
doc. Mgr. et Mgr. Aleš Návrat, Ph.D.

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.
Kritérium hodnocení Známka
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
Otázky k obhajobě:
  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.

Známka navržená oponentem: D

Odpovědnost: Mgr. et Mgr. Hana Odstrčilová