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

鲍皖苏; 宋震; 钟普查; 付向群

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2025-07-16

- 子集和问题的量子中间相遇搜索算法
- Quantum Mechanical Meet-in-the-middle Algorithm for Subset Sum Problem
- 电子学报 2011年39卷第1期页码：128-132
- 作者机构：
  
  1. 解放军信息工程大学电子技术学院,河南,郑州,450004
  2. 湖南省岳阳军分区,湖南,岳阳,414000
  3. 解放军信息工程大学电子技术学院河南郑州,450004
  4. 湖南省岳阳军分区湖南岳阳,414000
- 作者简介：
- 基金信息：
- DOI：
  中图分类号： TP301.6
- 纸质出版：2011
- 稿件说明：
移动端阅览
鲍皖苏, 宋震, 钟普查, 等. 子集和问题的量子中间相遇搜索算法[J]. 电子学报, 2011,39(1):128-132.

BAO Wan-su, SONG Zhen, ZHONG Pu-cha, et al. Quantum Mechanical Meet-in-the-middle Algorithm for Subset Sum Problem[J]. Acta Electronica Sinica, 2011, 39(1): 128-132.
鲍皖苏, 宋震, 钟普查, 等. 子集和问题的量子中间相遇搜索算法[J]. 电子学报, 2011,39(1):128-132. DOI：

BAO Wan-su, SONG Zhen, ZHONG Pu-cha, et al. Quantum Mechanical Meet-in-the-middle Algorithm for Subset Sum Problem[J]. Acta Electronica Sinica, 2011, 39(1): 128-132. DOI：

摘要

子集和问题是NP完全问题

该问题是背包公钥的基础.现有最优的经典算法求解规模为

的子集和问题需要

(

)步运算.本文提出了基于时空折衷思想的量子中间相遇搜索算法

该算法可以在

(

)步求解规模为

的子集和问题

其存储复杂性为

).由于NP完全问题可以在多项式时间内可相互归约

所以

在存储复杂性为

)的条件下

量子中间相遇搜索算法使得NP完全问题的计算复杂性降为

(

Abstract

Subset sum problem is one of the NP complete problems

which is the foundation of knapsack encryption schemes.Its computational complexity is

(

2exp(

/2)) in classical algorithms.We present the quantum mechanical meet-in-the-middle algorithm

which can solve the subset sum problem in

(

2exp(

/3)) with

(2exp(

/3)) memory cost

and

(2exp(

/2)) in quantum mechanical algorithm.The NP complete questions are minimized in

(

2exp(

/3)) under this algorithm because of their equivalence.

关键词

Keywords

references

浏览量

1564

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

具有高概率的整数分解量子算法

姚氏百万富翁问题的高效解决方案

多尺度量子谐振子算法的收敛特性

人工神经网络的容量、学习与计算复杂性

基于多离散对数问题的公钥密码的分析