Shor算法能夠在多項(xiàng)式時(shí)間內(nèi)分解一個(gè)大數(shù)的質(zhì)因子,對(duì)現(xiàn)行RSA公鑰加密體系的安全性提出嚴(yán)峻挑戰(zhàn)。很多研究人員提出了Shor算法的改進(jìn),其中Zalka的改進(jìn)使用改造的Schonhage-Strassen算法來降低Shor算法的復(fù)雜度,并提出量子電路來計(jì)算Schonhage-Strassen算法中用到的快速費(fèi)馬數(shù)變換。然而,Zalka提出的電路會(huì)產(chǎn)生垃圾位。在量子計(jì)算中,沒有得到處理的垃圾位會(huì)和運(yùn)算結(jié)果糾纏并對(duì)其產(chǎn)生影響,最壞情形下會(huì)導(dǎo)致運(yùn)算結(jié)果出錯(cuò)。本文提出一個(gè)不產(chǎn)生任何垃圾位的量子電路來計(jì)算快速費(fèi)馬數(shù)變換。對(duì)于長(zhǎng)度為b的n+1位整數(shù)序列,已知最好的電路需要使用17/2 nblog b個(gè)Toffoli門來計(jì)算該序列的費(fèi)馬數(shù)變換,同時(shí)會(huì)產(chǎn)生3/2b log 6位垃圾位；相比之下,本文提出的電路則需要使用19/2 nb logb個(gè)Toffoli門來完成同樣的任務(wù),但是不會(huì)產(chǎn)生任何垃圾位。這個(gè)結(jié)果是通過洞察運(yùn)算結(jié)果和垃圾位之間的關(guān)系,并審慎地選擇垃圾位清除方法而得到的。本文提出的電路為Shor算法的時(shí)間復(fù)雜度從O(n³)降低為O(n² logn l...

【文章頁(yè)數(shù)】：46 頁(yè)

【學(xué)位級(jí)別】：碩士

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 研究背景和意義
    1.2 論文結(jié)構(gòu)
第二章 傅里葉變換
    2.1 離散傅里葉變換
    2.2 快速傅里葉變換
    2.3 數(shù)論變換
    2.4 Schonhage-Strassen算法和費(fèi)馬數(shù)變換
第三章 量子線路模型
    3.1 NCT門庫(kù)
    3.2 常用電路模塊
        3.2.1 VBE加法器
        3.2.2 CDKM加法器
        3.2.3 減法器
        3.2.4 比較器
        3.2.5 識(shí)別器
    3.3 清除垃圾位的通用方法
第四章 快速費(fèi)馬數(shù)變換量子電路
    4.1 蝶形結(jié)電路設(shè)計(jì)
        4.1.1 計(jì)算和與差
        4.1.2 模運(yùn)算
        4.1.3 移位并取模
    4.2 電路代價(jià)分析
        4.2.1 每個(gè)蝶形結(jié)的代價(jià)
        4.2.2 整個(gè)費(fèi)馬數(shù)變換的代價(jià)
        4.2.3 代價(jià)差異來源分析
    4.3 其它可能的計(jì)算方式
        4.3.1 使用其它分步方法
        4.3.2 使用其它快速傅里葉變換算法
第五章 總結(jié)與展望
    5.1 工作總結(jié)
    5.2 展望
致謝
參考文獻(xiàn)
附錄 攻讀碩士學(xué)位期間完成的論文



本文編號(hào)：3912320