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

Quantum Mechanical Meet-in-the-middle Algorithm for Subset Sum Problem

作　　者：鲍皖苏[1] 宋震[1] 钟普查 付向群[1] 

机构地区：[1]解放军信息工程大学电子技术学院,河南郑州450004 [2]湖南省岳阳军分区,湖南岳阳414000

出　　处：《电子学报》2011年第1期128-132,共5页Acta Electronica Sinica

摘　　要：子集和问题是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 minimized in O（n2exp（n/3）） under this algorithm because of their equivalence.

关 键 词：量子算法 子集和问题 计算复杂性 中间相遇 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]