Planning & Scheduling and Quantum Computing: what can they do for each other?

An ICAPS'22 Tutorial

(half day)

June 13, 2022

Description

Quantum Computing represents the next big step towards speed boost in computation, which promises major breakthroughs in several disciplines including Artificial Intelligence for the resolution of important classes of problems. Quantum algorithms process information stored in qubits, the basic memory unit of quantum processors, and quantum operations (called gates) are the building blocks of quantum algorithms. In order to be run on quantum computing hardware, quantum algorithms must be compiled into a set of elementary machine instructions (i.e., quantum gates). Since currently available quantum circuits suffer a number of technological problems such as noise and decoherence, it is important that the process that carries out the quantum computation be somehow adapted to the physical limitations of the quantum hardware of interest, by means of a proper compilation. This is the point in which AI-based P&S techniques can be of help to produce efficient compilation plans. On the other side, the speed-up promised by quantum technology may be greatly beneficial to solve P&S problems of more and more realistic size.

Outline

  • We first provide an introductory part aimed at familiarizing the audience on the basics of quantum computing theory, focusing our attention on the so-called Quantum Alternate Operator Ansatz (QAOA) algorithms applied to the gate-model noisy intermediate-scale quantum (NISQ) processor units.
  • We then proceed by analyzing a set of compilation algorithms based on AI-based optimization metaheuristics that can be tested on one of the publicly available quantum computing software development kits (e.g., Qiskit - https://qiskit.org/), followed by a hands-on session in which the audience can run some exemplificatory code on the selected framework.
  • Finally, we will provide some examples of how quantum circuits can be exploited to solve some types of scheduling problems (e.g., the Satellite Scheduling), terminating in a hands-on session in which the audience will test the presented algorithms.

Bios

Marco Baioletti

Marco Baioletti [M.S. Mathematics 1990, Ph.D. Statistical and Mathematical Methods for Economical and Social Research 1996] is an assistant professor at the University of Perugia since 2004. His research interests are focused on some areas of Artificial Intelligence (AI), in particular automated planning, probabilistic modelling and reasoning, metaheuristics for combinatorial optimization, neuro-evolution, quantum circuit compilation. He has published more than 70 papers, both in journals, book and peer-reviewed international AI conferences. He has been in the program committee of several international conferences (PPSN, EVO*, GECCO). He has recently participated to the study funded by the Ariadna program of the ESA "Meta-Heuristic Algorithms for the Quantum Circuit Compilation Problem".

Angelo Oddi

Angelo Oddi [M.S. Electronic Engineering 1993, Ph.D. Medical Computer Science 1997] is a Senior Researcher of the Institute of Cognitive Sciences and Technologies of the Italian National Research Council (ISTC-CNR). His research work focuses on Artificial Intelligence (AI), in particular planning & scheduling, constraint-based reasoning, learning and the design of autonomous systems for real-world applications. He has published more than 70 papers, both in journals, book and peer-reviewed international AI conferences. Dr. Oddi has been in the program committee of several international conferences (ICAPS, ECAI, AAAI, IJCAI) and was Conference Chair of the International Conference on Automated Planning and Scheduling 2013 (ICAPS-2013), Rome, June 10-14, 2013. He participated in several national and international projects; in particular, he was national coordinator of the FIRB VISEL project (MIUR – Italian Ministry of Education University and Research – funds) aimed to develop a Deaf-centered E-Learning Environment (DELE). He has been involved in the realization of the MEXAR2 and RAXEM systems (2005-2012) dealing with the automatic generation of downlink/uplink plans for the European Space Agency (ESA) Mars-Express mission. Relatively to the MEXAR2 system, he acted as technical director and is still responsible for its maintenance (2014-2022). He has been the coordinator of the IMPACT project (Intrinsically Motivated Planning Architecture for Curiosity-driven roboTs) funded by ESA within the Innovation Triangle Initiative (ITI) 2017 program and recently held the position of head of the study funded by the Ariadna program of the ESA "Meta-Heuristic Algorithms for the Quantum Circuit Compilation Problem".

Riccardo Rasconi

Riccardo Rasconi [M.S. Electronic Engineering 2003, Ph.D. Information and Communication Sciences and Technologies 2007] is a Research Scientist at ISTC-CNR. Riccardo has a long-term participation experience in national and international research projects, both from a Planning & Scheduling perspective and, more recently, from a ML perspective. Here is a very partial list, limited to the Space-related research projects only: Riccardo has been an active member of the ESA Project “GOAC (Goal Oriented Autonomous Controller)” ESA Project, about the development of an autonomous controller to provide increasing levels of autonomy for robotic task achievement. He is recently participating to the MEXAR2 Maintenance activity (an AI-based Tool for Continuous Support to Mission Planning). Moreover, he has recently participated to the ESA Study IMPACT: Intrinsically Motivated Planning Architecture for Curiosity-driven roboTs, that leveraged ML and Reinforcement Learning techniques to extend the autonomy capabilities of a robotic agent that explores the Martian surface. He has recently participated to the study funded by the Ariadna program of the ESA "Meta-Heuristic Algorithms for the Quantum Circuit Compilation Problem". He has published over 48 research papers in Journals, Book Chapters and peer-reviewed Conference Proceedings in Computer Science, Planning & Scheduling, Constraint Reasoning.