Simplification of quantum circuits for modular exponentiation
| Thesis title: | Simplification of quantum circuits for modular exponentiation |
|---|---|
| Author: | Fišer, Petr |
| Thesis type: | Diploma thesis |
| Supervisor: | Ivánek, Jiří |
| Opponents: | Nentvich, Libor |
| Thesis language: | English |
| Abstract: | 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. |
| Keywords: | qbit; computer security; quantum computer; circuit; optimization; uniform design |
| Thesis title: | Zjednodušení kvantových obvodů pro modulární umocňování |
|---|---|
| Author: | Fišer, Petr |
| Thesis type: | Diplomová práce |
| Supervisor: | Ivánek, Jiří |
| Opponents: | Nentvich, Libor |
| Thesis language: | English |
| Abstract: | 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ů. |
| Keywords: | optimalizace; uniformní design; qbit; počítačová bezpečnost; kvantový počítač; obvod |
Information about study
| Study programme: | Aplikovaná informatika/Informační systémy a technologie |
|---|---|
| Type of study programme: | Magisterský studijní program |
| Assigned degree: | Ing. |
| Institutions assigning academic degree: | Vysoká škola ekonomická v Praze |
| Faculty: | Faculty of Informatics and Statistics |
| Department: | Department of Information Technologies |
Information on submission and defense
| Date of assignment: | 8. 8. 2015 |
|---|---|
| Date of submission: | 7. 12. 2016 |
| Date of defense: | 23. 1. 2017 |
| Identifier in the InSIS system: | https://insis.vse.cz/zp/53756/podrobnosti |