Study on Quantum Heuristic Search in an NP-hard problem

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.