Bachelor's Thesis

Simulation and Analysis of Quantum Circuits

Final Thesis 1.79 MB

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.

Abstract:

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.

Keywords:

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)

znamkaAznamka

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

  1. Jak by bylo obtížné uvedené techniky integrovat do stávajících nástrojů pro práci s kvantovými obvody?
  2. Jak velká MTBDD vznikala během simulací?
  3. Můžete prosím zkusit shrnout vaše zapojení do projektu?
  4. Existuje numerické řešení simulací, které jste prováděla?

Language of thesis

English

Faculty

Department

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 report
doc. 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í.

Evaluation criteria Verbal classification
Informace k zadá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.

Práce s literaturou

Studentka dostala zadanou základní literaturu a zbytek si dohledala sama.

Aktivita během řešení, konzultace, komunikace

Aktivita byla příkladná, studentka práci pravidelně konzultovala.

Aktivita při dokončování

Obsah práce byl dostatečně konzultován, práce byla dokončena v dostatečném předstihu.

Publikační činnost, ocenění

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.

Points proposed by supervisor: 95

Grade proposed by supervisor: A

Reviewer’s report
Ing. 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 criteria Verbal classification Points
Náročnost zadání

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ů. 

Prezentační úroveň technické zprávy

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.

96
Formální úprava technické zprávy

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.

95
Realizační výstup

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.

95
Využitelnost výsledků

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). 

Rozsah splnění požadavků zadání

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. 

Rozsah technické zprávy

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 s literaturou

Práce cituje relevantní zdroje, nejčastěji články z konferencí a odborných časopisů. Citace jsou dle zvyklostí.

94
Topics for thesis defence:
  1. Jak velká MTBDD vznikala během simulací?
  2. Jak by bylo obtížné uvedené techniky integrovat do stávajících nástrojů pro práci s kvantovými obvody?
Points proposed by reviewer: 95

Grade proposed by reviewer: A

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