Přístupnostní navigace
E-application
Search Search Close
Bachelor's Thesis
Author of thesis: Bc. Sára Jobranová
Acad. year: 2023/2024
Supervisor: doc. Ing. Ondřej Lengál, Ph.D.
Reviewer: Ing. Vojtěch Havlena, Ph.D.
Simulation of quantum circuits is a key tool for future advancements in the promising field of quantum computing. Due to the fact that this task is very computationally demanding, the performance of state-of-the-art simulators on more complex circuits is still far from satisfactory. In this thesis, we propose a new approach to simulate quantum circuits and present an implementation based on this approach. Our simulation technique allows for accurate simulation and is based on multi-terminal binary decision diagrams. We extended the usual process of a decision diagram-based simulation by symbolic execution of repeating structures in a quantum circuit (such as loops), where we compute the big-step semantics of this structure and do not re-evaluate the gates. We show that symbolic loop execution significantly accelerates the simulation and that the implemented tool is not only competitive with other state-of-the-art simulators, but also greatly outperforms the state of the art for many quantum circuits.
Quantum computing, Simulation of quantum circuits, Multi-terminal binary decision diagrams, Symbolic execution
Date of defence
10.06.2024
Result of the defence
Defended (thesis was successfully defended)
Grading
A
Process of defence
Studentka nejprve prezentovala výsledky, kterých dosáhla v rámci své práce. Komise se poté seznámila s hodnocením vedoucího a posudkem oponenta práce. Studentka následně odpověděla na otázky oponenta a na další otázky přítomných. Komise se na základě posudku oponenta, hodnocení vedoucího, přednesené prezentace a odpovědí studentky na položené otázky rozhodla práci hodnotit stupněm A.
Topics for thesis defence
Language of thesis
English
Faculty
Fakulta informačních technologií
Department
Department of Intelligent Systems
Study programme
Information Technology (BIT)
Composition of Committee
doc. RNDr. Milan Češka, Ph.D. (předseda) Ing. Zbyněk Křivka, Ph.D. (člen) doc. Ing. Peter Chudý, Ph.D., MBA (člen) Ing. Jiří Matoušek, Ph.D. (člen) Ing. Jaroslav Rozman, Ph.D. (člen)
Supervisor’s reportdoc. Ing. Ondřej Lengál, Ph.D.
Sára Jobranová ve své práci vyvinula a implementovala techniky pro pokročilou simulaci kvantových obvodů založených na binárních rozhodovacích diagramech a symbolické exekuci. Na některé třídě obvodů tento simulátor zásadně poráží veškerý současný state of the art a i na obvodech mimo tuto třídu je kompetitivní (obzvlášť, pokud se zaměříme jen na simulátory provádějící přesnou simulaci). Velmi pozitivně hodnotím zapojení Sáry do psaní článku zaslaného na konferenci ICCAD'24, kde je nyní v recenzním řízení. Dále kladně hodnotím to, že se (mimo rozsah práce) podařilo najít a reportovat chyby v jiných nástrojích pro simulaci kvantových obvodů (SliQSim ze skupiny Jie-Hong Rolanda Jianga a Quasimodo ze skupiny Toma Repse). Z výše uvedených důvodů navrhuji hodnotit práci stupněm výborně (A) a navrhuji práci na další ocenění.
Zadání bylo náročné, studentka se musela seznámit za prvé se základy kvantového počítání, za drhué detailně pochopit datovou strukturu binárních rozhodovacích diagramů a za třetí pochopit princip symbolické exekuce kódu. Na těchto základech pak měla za úkol navrhnout a implementovat simulátor kvantových obvodů. Z dosažených výsledků jsem nadšen: vyvinutý simulátor na třídě obvodů provádějících opakovanou amplifikaci amplitudy poráží veškerý součastný state of the art o několik délek.
Studentka dostala zadanou základní literaturu a zbytek si dohledala sama.
Aktivita byla příkladná, studentka práci pravidelně konzultovala.
Obsah práce byl dostatečně konzultován, práce byla dokončena v dostatečném předstihu.
Práce studentky byla prezentována na studentské konferenci Excel@FIT v letech 2023 a 2024 a byla zde oceněna 1) cenou odborného panelu, 2) cenou firmy Honeywell a 3) cenou odborné veřejnosti. Dále byl na základě práce studentky spolu s vedoucím a partnery z Taiwanské Academie Sinicy a National Taiwan University napsán článek zaslaný na konferenci ICCAD'24 (CORE A), což je flagship konference mezinárodní komunity v oblasti automatizovaného návrhu.
Grade proposed by supervisor: A
Reviewer’s reportIng. Vojtěch Havlena, Ph.D.
Práce Sáry Jobranové přínáší novou techniku simulace kvantových obvodů založenou na reprezentaci kvantových stavů pomocí MTBDD. Uvedená technika byla implementována v nástroji MEDUSA a experimentálně vyhodnocena na existujících benchmarcích s působivými výsledky, kde vytvořený nástroj poráží v rychlosti stávající simulační nástroje. Práce byla navíc zaslána na prestižní konferenci ICCAD'24. Z těchto důvodů hodnotím známkou výborně (A). Přikláním se rovněž k udělení ceny.
Evaluation level: obtížnější zadání
Zadání považuji za obtížné. Práce vyžadovala od studenta pochopení základů kvantového počítání, práci s binárími rozhodovacími diagramy a seznámení se s již existující přístupy k simulaci kvantových obvodů. Práce navíc vyžadovala vyvinutí vlastní netriviální invence při vymýšlení nového přístupu pro efektivní simulaci kvantových obvodů.
Jednotlivé kapitoly v práci jsou informačně vyvážené a navazují na sebe. Oceňuji s jakou pečlivostí byla práce napsána. Práce srozumitelně uvádí simulaci kvantových obvodů, přehled již existujících přístupů a potom vlastní techniky a jejich efektivní implementaci. Vše doplněno názornými příklady a obrázky. Pojmy v práci jsou formálně definovány s minimem nepřesností. Oceňuji formální popis uvedených technik.
Práce je velice zdařilá po typografické, tak i po jazykové stránce. Oceňuji psaní práce v angličtině. Práce obsahuje minimum gramatických chyb.
Realizačním výstupem práce je simulátor kvantových obvodů MEDUSA, napsaný v jazyce C. Program simuluje zadaný kvantový obvod (zapsaný v standardním jazyce pro popis obvodů) a produkuje symbolický kvantový stav na výstupu (ve formě MTBDD). Programové řešení mi bylo předvedeno a je funkční. Součástí programu je i podrobná nápověda včetně vstupů kódující kvantové obvody.
Práce přináší nové výsledky z oblasti efektivní simulace kvantových obvodů. Dovedu si představit, že se uvedená technika může stát součastí velkých existujících nástrojů pro práci s kvantovými obvody. Práce byla navíc ve spolupráci s vedoucím práce zaslána na konferenci ICCAD'24 (Core A).
Evaluation level: zadání splněno
Zadání považuji za kvalitně splněné. Výsledkem práce je technika simulace kvantových obvodů pomocí multi-terminálních binárních rozhodovacích diagramů (MTBDD) včetně efektivní implementace, která dle rozsáhlého experimentálního vyhodnocení dokáže porazit stávající metody na existujících benchmarcích.
Evaluation level: je v obvyklém rozmezí
Práce je v obvyklém rozmezí, neobsahuje zbytečné části a jednotlivé kapitoly jsou informačně bohaté.
Práce cituje relevantní zdroje, nejčastěji články z konferencí a odborných časopisů. Citace jsou dle zvyklostí.
Grade proposed by reviewer: A
Responsibility: Mgr. et Mgr. Hana Odstrčilová