Compact Genetic Algorithm with Quantum-Assisted Feasibility Enforcement
COM1 Level 3
MR1, COM1-03-19
Abstract:
We propose a quantum-assisted compact genetic algorithm that circumvents the problem by using a quantum amplitude amplification technique in the selection process.
In addition to using elitism mechanics where a single best candidate solution is kept to drive the probability vector, the amplitude amplification subroutine also acts as a mutation operator, which, with high probability, enforces the constraint
that the newly generated candidate is a feasible solution. We demonstrate this idea by applying the algorithm to the travelling salesman problem of size 3 and 4 cities on an IBM Qiskit simulator to show how one would construct the quantum circuit and how to encode the optimization problem into quantum states via Ising spin model encoding.
Bio:
Kamonluk Suksen received her bachelor's degree, Master's Degree, and Ph. D. in Computer Engineering from Chulalongkorn University in 2013, 2014, and 2022, respectively. After graduation, she was employed in the position of Head of Software & Information Technology by Yannix Co., Ltd. until 2020. Currently, she is a lecturer in Computer Engineering at Chulalongkorn University. Her research focuses on quantum computing and algorithms for optimization problems.