The local optima problem is one of the biggest obstacles in compact
genetic algorithms since each bit in the problem encoding string is
independent of the others. We propose a quantum-assisted compact genetic
algorithm that uses a quantum amplitude amplification technique in the
selection process to circumvent the said problem. In addition to using
elitism mechanics where a single best candidate solution is kept driving
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 traveling salesman
problem of size 3 and 4 cities on 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. We then show
space and time complexity analysis based on the quantum circuit model.
Finally, we discuss the number of qubits required for encoding, gate
counts in the circuit model, and the practicality of applying this to a
small-scale device in the future.
Prabhas Chongstitvatana is a professor in the department of computer
engineering, Chulalongkorn University. He earned B.Eng. in Electrical
Engineering from Kasetsart University, Thailand in 1980 and Ph.D. from the
department of artificial intelligence, Edinburgh University, U.K. in 1992.
His research involves robotics, evolutionary computation, computer
architecture, bioinformatics and quantum computing. He is a lifetime
member of Thailand Engineering Institute, senior member of Thai Academy of
Science and Technology, senior adviser of Thai Robotics Society, founding
member of Thai Embedded System Association and IEEE Robotics and
Automation Society. He was the president of ECTI Association of Thailand
2012-2013. He has been awarded "National Distinguished Researcher" by
National Research Council of Thailand in 2009. His current interest is in
building Quantum computer.
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 had been employed in the
position of Head of Software & Information Technology by Yannix Co.,
Ltd. until 2020. Currently, she is post doctor in Computer Engineering at
Chulalongkorn University. Her research is heavily focused on quantum
computing and quantum algorithms for optimization problems.