子集和问题的量子中间相遇搜索算法

摘要

子集和问题是NP完全问题,该问题是背包公钥的基础.现有最优的经典算法求解规模为n的子集和问题需要O(n2n/2)步运算.本文提出了基于时空折衷思想的量子中间相遇搜索算法,该算法可以在O(n2n/3)步求解规模为n的子集和问题,其存储复杂性为O(2n/3).由于NP完全问题可以在多项式时间内可相互归约,所以,在存储复杂性为O(2n/3)的条件下,量子中间相遇搜索算法使得NP完全问题的计算复杂性降为O(n2n/3).%Subset sum problem is one of the NP complete problems, which is the foundation of knapsack encryption schemes. Its computational complexity is O( n2exp(n/2) ) in classical algorithms. We present the quantum mechanical meet-in-the-middle algorithm,which can solve the subset sum problem in O( n2exp( n/3 ) ) with O ( 2exp( n/3 ) ) memory cost, and O(2exp (n/2) ) in quantum mechanical algorithm. The NP complete questions are mmimized in O( n2exp(n/3) ) under this algorithm be cause of their equivalence.