摘要：子集和问题是NP完全问题,该问题是背包公钥的基础.现有最优的经典算法求解规模为n的子集和问题需要O（n2^n/2）步运算.本文提出了基于时空折衷思想的量子中间相遇搜索算法,该算法可以在O（n2^n/3）步求解规模为n的子集和问题,其存储复杂性为O（2^n/3）.由于NP完全问题可以在多项式时间内可相互归约,所以,在存储复杂性为O（2^n/3）的条件下,量子中间相遇搜索算法使得NP完全问题的计算复杂性降为O（n2^n/3）.

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

单位：解放军信息工程大学电子技术学院; 河南郑州450004; 湖南省岳阳军分区; 湖南岳阳414000