Introduction to Quantum Optimization
Description
Scope:
Quantum computers are rapidly becoming more powerful and increasingly applicable to solve problems in the real world. They have the potential to solve extremely hard computational problems, which are currently intractable by conventional computers. A major application domain of quantum computers is solving hard combinatorial optimization problems. This is the emerging field of quantum optimization. The algorithms that quantum computers use for optimization can be regarded as general types of stochastic heuristic optimization algorithms.
There are two main types of quantum computers, quantum annealers and quantum gate computers. These have very different architectures. To solve optimization problems on quantum computers, they need to be reformulated in a format suitable for the specific architecture. Quantum annealers are specially tailored to solve combinatorial optimization problems, once they are reformulated as a Quadratic Unconstrained Binary Optimisation (QUBO) problem. In quantum gates computers, Quantum Approximate Optimization Algorithm (QAOA) can be used to approximately solve optimization problems. In this case, a classical algorithm can be used on top of the quantum computer to guide the search of parameters.
The tutorial is aimed at researchers in optimization who have no previous knowledge of quantum computers and want to learn about how to solve optimization problems on quantum computers. The tutorial will demonstrate how to solve in practice a simple combinatorial optimization problem on the two main quantum computer architectures (quantum gate computers and quantum annealers) using Jupyter notebooks to experiment hands-on on solving simple optimization problems on quantum computer simulators.
Content:
Part 1 (Quantum Annealers):
- Quantum Annealers Background
- Optimisation on Quantum Annealers
- Solving the Max Cut problem on a Quantum Annealer
Part 2 (Quantum Gate Computers):
- Quantum Gate Computers Background
- Optimisation on Quantum Gate Computers
- Solving the Max Cut problem on a Quantum Gate Computer (via QAOA)
Organizers
University of Exeter, UK
Alberto Moraglio is a Senior Lecturer at the University of Exeter, UK. He holds a PhD in Computer Science from the University of Essex and Master and Bachelor degrees (Laurea) in Computer Engineering from the Polytechnic University of Turin, Italy. He is the founder of a Geometric Theory of Evolutionary Algorithms, which unifies Evolutionary Algorithms across representations and has been used for the principled design and rigorous theoretical analysis of new successful search algorithms. He gave several tutorials at GECCO, IEEE CEC and PPSN, and has an extensive publication record on this subject. He has served as co-chair for the GP track, the GA track and the Theory track at GECCO. He also co-chaired twice the European Conference on Genetic Programming, and is an associate editor of Genetic Programming and Evolvable Machines journal. He has applied his geometric theory to derive a new form of Genetic Programming based on semantics with appealing theoretical properties which is rapidly gaining popularity in the GP community. In the last three years, Alberto has been collaborating with Fujitsu Laboratories on Optimisation on Quantum Annealing machines. He has formulated dozens of Combinatorial Optimisation problems in a format suitable for the Quantum hardware. He is also the inventor of a software (a compiler) aimed at making these machines usable without specific expertise by automating the translation of high-level description of combinatorial optimisation problems to a low-level format suitable for the Quantum hardware (patented invention).
University of Malaga, Spain
Francisco Chicano holds a PhD in Computer Science from the University of Málaga and a Degree in Physics from the National Distance Education University. Since 2008 he is with the Department of Languages and Computing Sciences of the University of Málaga. His research interests include quantum computing, the application of search techniques to Software Engineering problems and the use of theoretical results to efficiently solve combinatorial optimization problems. He is in the editorial board of Evolutionary Computation Journal, Engineering Applications of Artificial Intelligence, Journal of Systems and Software and ACM Transactions on Evolutionary Learning and Optimization. He has also been programme chair and Editor-in-Chief in international events.