基于量子计算原理的Shor算法优越性验证  

Verifying the superiority of Shor algorithm based on the principle of quantum computing

作　　者：刘安航 李浩昱 关佳[1] 张志华[1] 方恺[1] 赫丽[1] 沈军[1] LIU An-hang;LI Hao-yu;GUAN Jia;ZHANG Zhi-hua;FANG Kai;HE Li;SHEN Jun(School of Physics Science and Engineering,Tongji University,Shanghai 200092,China)

机构地区：[1]同济大学物理科学与工程学院,上海200092

出　　处：《物理实验》2022年第4期7-12,共6页Physics Experimentation

基　　金：教育部产学合作协同育人项目(No.202002123019);同济大学实验教学改革项目(No.202149)。

摘　　要：从理论上分析了分解大数质因子的量子算法——Shor算法,将大数的质因子分解问题转换为求解函数的周期问题.设计了基于Shor算法的实验,并通过比较应用于求解同一函数时量子计算方法和经典计算方法分别需要的运算次数.实验结果表明:量子计算方法在函数的周期求解问题中仅需要多项式级别的复杂度,从而证明了量子计算在大数的质因子分解问题中具有明显的优越性.The quantum algorithm for decomposing the prime factors of large numbers,that is the Shor algorithm,was analyzed theoretically,and the problem of decomposing the prime factors of large numbers was transformed into the problem of solving the period of a function.Experiments based on Shor algorithm were designed.By comparing the number of operations required to solve the quantum computational method and the classical computational method respectively when applied to the same function,it could be concluded that the quantum computational method requires only polynomial-level complexity in the problem of solving the period of a function.This conclusion demonstrated the obvious superiority of quantum computing in the problem of decomposition of large numbers by prime factors.

关 键 词：Shor算法 量子并行计算 量子傅里叶变换 

分 类 号：O413[理学—理论物理]