Solving Optimisation Problems with a Quantum Computer

Prabhas Chongstitvatana and Kamonluk Suksen

Seminar at National University of Singapore

29 November 2023

Abstract :

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.