Quantum Computing Applied to Optimization
Yuzhen Ge, T Watson Layne · Computer Science Technical Reports (Virginia Tech) · 1999
Optimization problems represent a class of problems that can be time consuming to solve and very complex. In this paper, a quantum algorithm for solving optimization problems is proposed. The algorithm utilizes the encoding scheme from genetic algorithms to encode the problem and then uses Grover's unitary transformation to seek out a solution. The efficiency of the algorithm depends on the length of the chromosome or the coded variable. As a simple example the satisfiability problem, an NP-complete problem, is examined using the algorithm and the time complexity of solving this problem is greatly improved. The traveling salesman and minimum spanning tree problems are also briefly discussed.