|
Abstract
|
Article Information:
Polynomial-Time Quantum Algorithms for the 0-1 Knapsack Problem
Zhong Yanhua and Nie Shuzhi
Corresponding Author: Zhong Yanhua
Submitted: 2011 September, 23
Accepted: 2011 November, 16
Published: 2012 March, 01 |
Abstract:
|
In this study, designed a O(n2log2n) quantum mechanical algorithm, to solve the 0-1-knapsack
problem on a hypothetical quantum computer. Used the special characteristics of the quantum environment,
constantly divided the state of vector space, reduced the probability of state vector which don meet the
conditions of magnitude, increased the probability amplitude to meet the conditions, find a larger probability
of obtaining the solution. Owing to the problem of solving the time complexity by traditional exponential is
too complicated, turned it into the other problem which is relatively easy, then solving polynomial time wih
quantum computer, which can Reduce the difficulty of solving the problem. Analysised of the complexity of
the algorithm and implementation results showed that the designed algorithm is effective and feasible. This
algorithm can be extended to solve other NPC problems, such as TSP problem.
Key words: NPC problem, quantum algorithm, quantum computing, 0-1-kiapsack problem, , ,
|
|
Abstract
|
PDF
|
HTML |
|
Cite this Reference:
Zhong Yanhua and Nie Shuzhi, . Polynomial-Time Quantum Algorithms for the 0-1 Knapsack Problem. Research Journal of Applied Sciences, Engineering and Technology, (05): 510-512.
|
|
|
|
 |
ISSN (Online): 2040-7467
ISSN (Print): 2040-7459 |
 |
| Information |
|
|
|
|
| Sales & Services |
|
|
|
|
