Original title: Simplification of quantum circuits for modular exponentiation
Translated title: Zjednodušení kvantových obvodů pro modulární umocňování
Authors: Fišer, Petr ; Ivánek, Jiří (advisor) ; Nentvich, Libor (referee)
Document type: Master’s theses
Year: 2015
Language: eng
Publisher: Vysoká škola ekonomická v Praze
Abstract: [eng] [cze]
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. 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: circuit; computer security; optimization; qbit; quantum computer; uniform design; kvantový počítač; obvod; optimalizace; počítačová bezpečnost; qbit; uniformní design

Institution: University of Economics, Prague (web)
Document availability information: Available in the digital repository of the University of Economics, Prague.
Original record: http://www.vse.cz/vskp/eid/53039

Permalink: http://www.nusl.cz/ntk/nusl-261826


The record appears in these collections:
Universities and colleges > Public universities > University of Economics, Prague
Academic theses (ETDs) > Master’s theses