Home           Contact us           FAQs           
   Journal Page   |   Aims & Scope   |   Author Guideline   |   Editorial Board   |   Search
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
   Contact Information
  Executive Managing Editor
  Email: admin@maxwellsci.com
  Publishing Editor
  Email: support@maxwellsci.com
  Account Manager
  Email: faisalm@maxwellsci.com
  Journal Editor
  Email: admin@maxwellsci.com
  Press Department
  Email: press@maxwellsci.com
Home  |  Contact us  |  About us  |  Privacy Policy
Copyright © 2009. MAXWELL Science Publication, a division of MAXWELLl Scientific Organization. All rights reserved