背包问题的量子计算算法

作者：钟普查 鲍皖苏 范得军 徐浩量子算法grover算法固定相位背包问题

摘要：背包问题属于NP完全问题，经典算法对规模为n的背包问题求解的时间复杂度为O（2^n）。给出了基于固定相位的背包问题量子计算算法，证明了该算法在多解的情况下，能够以不低于98%的成功率在O（√N/M）步完成对规模为n的背包问题求解（M是解的数目），而基于原始Grover算法的背包问题量子计算算法计算复杂度为O（√N/M），成功率是50%～100%。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社