量子线路研究快速费马数变换的量子线路逻辑实现

发布时间：2024-02-27 03:41

　　Shor算法能够在多项式时间内分解一个大数的质因子,对现行RSA公钥加密体系的安全性提出严峻挑战。很多研究人员提出了Shor算法的改进,其中Zalka的改进使用改造的Schonhage-Strassen算法来降低Shor算法的复杂度,并提出量子电路来计算Schonhage-Strassen算法中用到的快速费马数变换。然而,Zalka提出的电路会产生垃圾位。在量子计算中,没有得到处理的垃圾位会和运算结果纠缠并对其产生影响,最坏情形下会导致运算结果出错。本文提出一个不产生任何垃圾位的量子电路来计算快速费马数变换。对于长度为b的n+1位整数序列,已知最好的电路需要使用17/2 nblog b个Toffoli门来计算该序列的费马数变换,同时会产生3/2b log 6位垃圾位；相比之下,本文提出的电路则需要使用19/2 nb logb个Toffoli门来完成同样的任务,但是不会产生任何垃圾位。这个结果是通过洞察运算结果和垃圾位之间的关系,并审慎地选择垃圾位清除方法而得到的。本文提出的电路为Shor算法的时间复杂度从O(n³)降低为O(n² logn l...

【文章页数】：46 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景和意义
    1.2 论文结构
第二章 傅里叶变换
    2.1 离散傅里叶变换
    2.2 快速傅里叶变换
    2.3 数论变换
    2.4 Schonhage-Strassen算法和费马数变换
第三章 量子线路模型
    3.1 NCT门库
    3.2 常用电路模块
        3.2.1 VBE加法器
        3.2.2 CDKM加法器
        3.2.3 减法器
        3.2.4 比较器
        3.2.5 识别器
    3.3 清除垃圾位的通用方法
第四章 快速费马数变换量子电路
    4.1 蝶形结电路设计
        4.1.1 计算和与差
        4.1.2 模运算
        4.1.3 移位并取模
    4.2 电路代价分析
        4.2.1 每个蝶形结的代价
        4.2.2 整个费马数变换的代价
        4.2.3 代价差异来源分析
    4.3 其它可能的计算方式
        4.3.1 使用其它分步方法
        4.3.2 使用其它快速傅里叶变换算法
第五章 总结与展望
    5.1 工作总结
    5.2 展望
致谢
参考文献
附录 攻读硕士学位期间完成的论文



本文编号：3912320