Shor整数分解量子算法的加速实现

基于半经典量子Fourier变换的实现方法, 提出了整数k的3元二进制表示生成向量和生成函数概念, 构造了生成函数的真值表, 证明了由其逐比特生成的整数k的3元二进制表示向量是整数k的一种NAF表示, 且表示中非0元个数的最大值为[([logk]+1)/2], 并基于此重新设计了Shor算法的量子实现线路. 与Parker的Shor算法量子实现线路相比, 计算资源大体相同(所需的基本量子门数量均为O([logN]³), 所需的量子比特数量前者较后者多2量子比特), 但实现速度提高了2倍.     

Shor整数分解量子算法的加速实现

基于半经典量子Fourier变换的实现方法,提出了整数k的3元二进制表示生成向量和生成函数概念,构造了生成函数的真值表,证明了由其逐比特生成的整数k的3元二进制表示向量是整数k的一种NAF表示,且表示中非0元个数的最大值为[(「logk■+1)2],并基于此重新设计了Shor算法的量子实现线路.与Parker的Shor算法量子实现线路相比,计算资源大体相同(所需的基本量子门数量均为O(「logN■3),所需的量子比特数量前者较后者多2量子比特),但实现速度提高了2倍.