Title :
Study on Quantum Heuristic Search in an NP-hard problem
Author :
El-fiky, Mohamed ; Ono, Satoshi ; Nakayama, Shigeru
Author_Institution :
Dept. of Inf. & Comput. Sci., Kagoshima Univ., Kagoshima, Japan
Abstract :
A study on quantum heuristic search (QHS) in knapsack problem is presented. The algorithm starts with superpositions of all possible search states for the problem. It uses problem cost structure to shift the phase of the state´s amplitude, and a problem independent mixing operation combines the amplitude from different states. The simulator implemented in this study has shown that QHS could shift the amplitude toward solution states on average at each step, and the comparison with conventional heuristics has revealed its search performance.
Keywords :
combinatorial mathematics; knapsack problems; optimisation; quantum computing; search problems; NP-hard problem; QHS algorithm; combinatorial search; knapsack problem; problem cost structure; problem-independent mixing operation; quantum computation; quantum heuristic search algorithm; Computer science; Concurrent computing; Costs; NP-hard problem; Parallel processing; Phase estimation; Quantum computing; Quantum entanglement; Quantum mechanics; Vectors;
Conference_Titel :
ICCAS-SICE, 2009
Conference_Location :
Fukuoka
Print_ISBN :
978-4-907764-34-0
Electronic_ISBN :
978-4-907764-33-3
