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

BAO Wan-su; SONG Zhen; ZHONG Pu-cha; FU Xiang-qun

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-16

- Quantum Mechanical Meet-in-the-middle Algorithm for Subset Sum Problem
- Acta Electronica Sinica Vol. 39, Issue 1, Pages: 128-132(2011)
- 作者机构：
  
  1. 解放军信息工程大学电子技术学院,河南,郑州,450004
  2. 湖南省岳阳军分区,湖南,岳阳,414000
  3. 解放军信息工程大学电子技术学院河南郑州,450004
  4. 湖南省岳阳军分区湖南岳阳,414000
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP301.6
- Published：2011
- 稿件说明：
移动端阅览
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：

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

Views

1564

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Quantum Algorithm for Prime Factorization with High Probability

An Efficient Solution to Yao's Millionaires' Problem

Convergence Characteristics of Multi-scale Quantum Harmonic Oscillator Algorithm

Capacity,Learning and Computational Complexity of Artificial Neural Networks

Analysis of a Public-Key Cryptograph Based on Multi-Discrete Logarithm Problems

Related Author

FU Xiang-qun

BAO Wan-su

ZHOU Chun

ZHONG Pu-cha

LI Shun-dong

DAI Yi-qi

YOU Qi-you

WANG Peng

Related Institution

Department of Computer Science and Technology, Tsinghua University

National Supercomputing Center in Shenzhen

Parallel Computing Laboratory Chengdu University of Information Technology Chengdu Sichuan China

National Supercomputing Center in Shenzhen Shenzhen Guangdong China

University of Chinese Academy of Sciences Beijing China

⁰