Kamonluk Suksen
Doctoral Thesis,
Faculty of Engineering, Chulalongkorn University, 2021
Research in the field of quantum technology remains a great challenge to researchers in the future to develop techniques for making large-scale quantum information processing a reality. The simulation of quantum systems is an important problem in many fields. A quantum algorithm is one of the topics being studied for solving NP-hard problems that take too long to solve on classical computers.
This thesis aims to propose Quantum compact genetic algorithm, that exploits the advantages of quantum computing. There is quantum superposition and quantum parallelism in Grover's search algorithm. It was combined with a compact genetic algorithm with an elite (cGA with an elite) in the selection process to get a higher performance in term of the solution quality. The proposed algorithm can be run on an IBM QASM simulator to solve the small-sized traveling salesman problem (TSP). Although the number of function evaluations of the proposed algorithm grows exponentially as the number of cities grows, it still outperforms the cGA with an elite in finding the optimal solution. The results also showed that utilizing the right number of Grover iterations increases the efficiency in finding the optimal solution, whereas the number of shots increases the reliability of the answers.
keywords: Quantum computing, Grover's search algorithm, Compact genetic algorithm (cGA), Traveling salesman problem