Home           Contact us           FAQs           
     Journal Home     |     Aim & Scope    |    Author(s) Information      |     Editorial Board     |     MSP Download Statistics
2012 (Vol. 4, Issue: 05)
Article Information:

Polynomial-Time Quantum Algorithms for the 0-1 Knapsack Problem

Zhong Yanhua and Nie Shuzhi
Corresponding Author:  Zhong Yanhua 

Key words:  NPC problem, quantum algorithm, quantum computing, 0-1-kiapsack problem, , ,
Vol. 4 , (05): 510-512
Submitted Accepted Published
2011 September, 23 2011 November, 16 2012 March, 01

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.
Abstract PDF HTML
  Cite this Reference:
Zhong Yanhua and Nie Shuzhi, 2012. Polynomial-Time Quantum Algorithms for the 0-1 Knapsack Problem.  Research Journal of Applied Sciences, Engineering and Technology, 4(05): 510-512.
    Advertise with us
ISSN (Online):  2040-7467
ISSN (Print):   2040-7459
Submit Manuscript
   Current Information
   Sales & Services
Home  |  Contact us  |  About us  |  Privacy Policy
Copyright © 2015. MAXWELL Scientific Publication Corp., All rights reserved