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

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

从理论上分析了分解大数质因子的量子算法——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.