Seminar 1: Quantum Annealing for Constraint Satisfaction and Constrained Optimization Seminar 2: Solving Optimisation Problems with a Quantum Computer
Seminar 2: Prabhas Chongstitvatana and Kamonluk Suksen, Faculty of Engineering, Chulalongkorn University
COM1 Level 3
MR1, COM1-03-19
Seminar 1 (2pm to 3pm)
Abstract :
Quantum computing will have a profound impact on computer science in the next 10 to 20 years. In the domains of combinatorial optimization and problem solving, the use of quantum computers to solve concrete problems has started to raise tremendous interest, in both the gate-based paradigm with the Quantum Approximate Optimization Algorithm and in the adiabatic computing paradigm with Quantum Annealing (QA). QA is an alternative type of computation in which problems are encoded in quantum Hamiltonians (energy functions) and quantum dynamics is used to find solutions (ground states of minimal energy). QA can be seen as derived from simulated annealing, but taking advantage of the quantum tunneling effect to overcome energy barriers and therefore escape local minima during the computation. Quantum computers such as the D-Wave systems are implementing those ideas in hardware, as well as quantum-inspired devices based on classical electronics such as Fujitsu’s Digital Annealing Unit. From a programming point of view, the use of QA computers for solving combinatorial problems is getting easier by the general adoption of the Quadratic Unconstrained Binary Optimization (QUBO) formalism. QUBO has become a standard input language for all “Ising Machines” developed by D-Wave, NTT, Fujitsu, Hitachi, Toshiba, Fixstars Amplify and NEC.
We will describe in this talk how constraint problems can be encoded in QUBO and solved by QA. After introducing the basic concepts of QUBO and quantum annealing, we will detail the encoding of basic and complex constraints and present QUBO models for well-known constraint satisfaction and constrained optimization problems such as N-queens, Magic Square, Costas Arrays, and the Quadratic Assignment Problem (QAP), together with implementation results on quantum and quantum-inspired hardware.
Biodata:
Philippe Codognet received a Ph.D. in Computer Science from University of Bordeaux-I (France) in 1989. He worked at the central research laboratory of Thomson-CSF (now Thales) in Orsay (France) and then joined INRIA, the French National Research Center in Computer Science, with a sabbatical leave in 1997/8 at Sony Computer Science Laboratory in Paris. Since 1998, he has been professor of Computer Science at University Pierre & Marie Curie in Paris (now Sorbonne University). In 2003, he moved to Japan and worked as attaché for science and technology at the French Embassy in Japan (Tokyo). Then, on leave at CNRS (French National Center for Scientific Research), he created and directed a joint Japanese-French Laboratory in Computer Science regrouping CNRS, Sorbonne University, University of Tokyo, Keio University and the National Institute of Informatics (Japan). This laboratory became a CNRS International Research Laboratory (IRL) in January 2012. He then worked as Director of the CNRS Office in Tokyo and as attaché for science and university cooperation at the French Embassy in Singapore. He is back in Japan since September 2019 as director of the JFLI (Japanese-French Laboratory for Informatics), and an invited professor at University of Tokyo. His main research topics are in the domain of artificial intelligence and focus on combinatorial optimization and constraint programming, high-level programming languages, logic, parallel computing and computer-based music. His current interest lies in Quantum Computing, in particular in quantum annealing for constrained optimization problems. He has over 120 publications in international conferences and journals.
Seminar 2 (3pm to 4pm)
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.
Biodata:
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 pursuing a lecturer in Computer Engineering at Chulalongkorn University. Her research is heavily focused on quantum computing and quantum algorithms for optimization problems.