| 0/1背包问题的量子算法 |
| |
| 引用本文： | 钟艳花,余超凡. 0/1背包问题的量子算法[J]. 微计算机信息, 2006, 22(36): 273-274 |
| |
| 作者姓名： | 钟艳花 余超凡 |
| |
| 作者单位： | 1. 529020,广东江门市江门职业技术学院计算机系
2. 510000,广东广州市广东教育学院物理系 |
| |
| 摘 要： | 近年来针对各种问题提出了许多量子算法,这些量子算法都利用了量子态的可迭加性(Superposition)和纠缠性(Entan-glement),本文在量子环境下对0/1背包问题进行求解,介绍了量子算法的基本思想及相关概念。然后分析并给出求解0/1背包问题的量子算法,在量子物理环境下它能在多项式时间内求出所需要的解。这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等。
|
| 关 键 词： | NPC问题 0/1背包问题 量子算法 量子计算 |
| 文章编号： | 1008-0570(2006)12-3-0273-02 |
| 修稿时间： | 2006-04-28 |
A Quantum Algorithm to Resolve the 0/1-kiapsack problem |
| |
| ZHONG YANHUA,YU CHAOFAN. A Quantum Algorithm to Resolve the 0/1-kiapsack problem[J]. Control & Automation, 2006, 22(36): 273-274 |
| |
| Authors: | ZHONG YANHUA YU CHAOFAN |
| |
| Affiliation: | ZHONG YANHUA YU CHAOFAN |
| |
| Abstract: | The scientists have given various kinds of quantum mechanical algorithms for different kinds of problems in recent years. Because of massive quantum parallelism and entanglement,quantum computer can solve many problems more efficiently.0/1- kiapsack problems is a typical NPC problem.Its computing complexity is steps. This paper gives a quantum mechanical algorithm to solve 0/1- kiapsack problems,the algorithm find a solution for the n- element knapsack problem in polynomial time.This algorithm can be extend- ed to solve other NPC problem,such as TSP problem. |
| |
| Keywords: | NPC problem 0/1- kiapsack problem quantum algorithm Quantum computation |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
