论文摘要
Shor量子计算算法的提出，展示了量子计算机强大的并行计算能力，使得大整数分解和有限域上离散对数问题可以在多项式时间内被求解，量子计算技术对现代密码（特别是公钥密码）的安全性产生了重大影响。本文针对高概率的量子计算算法和量子线路的加速实现方法进行了深入研究，取得了以下结果：1、具有高概率的整数分解量子计算算法。基于量子Fourier变换给出了一个新的整数分解量子计算算法，通过多次量子Fourier变换和变量代换，使得r变成相位因子（r是从模整数环中所选元素的阶），进而可使非零的非目标态的几率幅变为零，算法成功的概率大于3/4，高于Shor整数分解量子算法，且不再依赖于r的大小（Shor算法成功的概率依赖于r的大小），同时还将新算法的资源消耗情况与Shor算法进行了对比。2、Shor整数分解量子计算算法的加速实现。针对半经典量子Fourier变换输入逐比特的特点，提出了整数的3元二进制表示生成向量和生成函数概念，构造了生成函数的真值表，证明了其逐比特生成的整数k的3元二进制表示是整数的一种NAF表示，且该表示中非0元个数的最大值为[（[log12k]+1）/2]；由于求解该表示是由低位至高位逐比特输入的，与半经典量子Fourier变换相反，因而提出了一个改进的半经典量子Fourier变换；基于整数的3元二进制表示向量重新设计了Shor算法的量子实现线路，与Parker等人的Shor算法的量子实现线路相比，计算资源大体相同（所需的基本量子门数量均为O（[logN]3），所需的量子比特数前者较后者多3量子比特），但实现速度提高了2倍。3、求解Chor-Rivest背包公钥密码的多项式时间量子计算算法。提出了一个求解Chor-Rivest背包公钥密码的多项式时间量子计算算法，利用变量代换和多次量子Fourier变换使得除全零态外的非目标态的几率幅变成0，刻画了观测值与待求向量(M0,M1,...Mp-1)之间的关系，给出了算法成功率与公钥参数p、h之间的关系式，算法运行一次成功的概率接近于1，计算复杂性是O（p3），所需量子比特数和基本量子门规模分别为（p+2）（[log r]+1）、O（（p+1）r）。