Zjednodušení kvantových obvodů pro modulární umocňování
| Název práce: | Simplification of quantum circuits for modular exponentiation |
|---|---|
| Autor(ka) práce: | Fišer, Petr |
| Typ práce: | Diploma thesis |
| Vedoucí práce: | Ivánek, Jiří |
| Oponenti práce: | Nentvich, Libor |
| Jazyk práce: | English |
| Abstrakt: | This thesis is based on top of the previous thesis "Security of modern encryption protocols" where we introduced a new paradigm for constructing quantum circuits. We have built circuits for modular arithmetic (addition, multiplication and exponentiation) in order to break El-Gamal asymmetric cryptosystem.
Current thesis reviews all proposed circuits and discusses possibilities of their further optimization in goal of lowering the number of used qbits at least by an order of magnitude. It also shows that this is not possible due to existence of COPY gates which make the design inherently unoptimizable.
Getting rid of COPY gates is, however, not possible without substantial rewrite of the whole paradigm. The overall estimate of number of qbits used in circuits thus remains O(log(m)log^2(N)) where m is a processed number and N is a modulus.
The thesis also proposes optimization of the modular multiplication circuit that, if issues with COPY gates are resolved, allows us to lower the number of used qbits by about O(log(m)) at the price of a longer execution time. |
| Klíčová slova: | qbit; computer security; quantum computer; circuit; optimization; uniform design |
| Název práce: | Zjednodušení kvantových obvodů pro modulární umocňování |
|---|---|
| Autor(ka) práce: | Fišer, Petr |
| Typ práce: | Diplomová práce |
| Vedoucí práce: | Ivánek, Jiří |
| Oponenti práce: | Nentvich, Libor |
| Jazyk práce: | English |
| Abstrakt: | Tato práce navazuje na práci "Security of modern encryption protocols", ve které bylo představeno nové paradigma návrhu obvodů pro kvantový počítač. Zde byly představeny obvody pro modulární aritmetiku (sčítání, násobení a umocňování) na kvantovém počítači, jejichž cílem bylo, ve výsledku, rozbít El-Gamalův asymetrický kryptosystém.
Aktuální práce reviduje všechny navržené obvody a stavební bloky s cílem snížit počet kvantových bitů, které potřebují ke svému fungování, a diskutuje možnosti jejich optimalizace.
Dále ukazuje, že původní odhad použitých qbitů O(log(m)log^2(N)) (m zpracovávané číslo, N modulus), nelze zlepšit, což je způsobeno vlastností paradigmatu - přítomností tzv. COPY hradel. Tato hradla nelze odstranit bez nutnosti velkých zásahů do stávajícího paradigmatu.
Práce navíc podává návrh na optimalizaci obvodu modulární násobičky který, za předpokladu že se povede vyřešit potíže s COPY hradly, umožní na některých fyzických implementacích kvantového počítače snížit počet použitých qbitů řádově o O(log(m)) za cenu zvýšení počtu výpočetních kroků. |
| Klíčová slova: | optimalizace; uniformní design; qbit; počítačová bezpečnost; kvantový počítač; obvod |
Informace o studiu
| Studijní program / obor: | Aplikovaná informatika/Informační systémy a technologie |
|---|---|
| Typ studijního programu: | Magisterský studijní program |
| Přidělovaná hodnost: | Ing. |
| Instituce přidělující hodnost: | Vysoká škola ekonomická v Praze |
| Fakulta: | Fakulta informatiky a statistiky |
| Katedra: | Katedra informačních technologií |
Informace o odevzdání a obhajobě
| Datum zadání práce: | 8. 8. 2015 |
|---|---|
| Datum podání práce: | 7. 12. 2016 |
| Datum obhajoby: | 23. 1. 2017 |
| Identifikátor v systému InSIS: | https://insis.vse.cz/zp/53756/podrobnosti |