The tutorial will be divided into 4 parts, starting from the theoretical
aspects of QC, QA and the QUBO problem formulation. There will
be a practical part where participants will be invited to code and
solve a few selected problems using quantum annealers.
Part 1: QC Foundations (40 min)
The first part consists of a
gentle introduction to QC, showing its potential benefits as well as
its limitations. We will also delve into the QA paradigm, trying to
explain the difference between classical and quantum computation
and dispelling some QC-related myths. It includes:
- an overview and basic understanding of QC and its potential benefits;
- a basic understanding of Quantum Circuit and Quantum Adiabatic models;
- relations between the classical optimizations meta-heuristics
Simulated Annealing and Quantum Annealing with
the Quantum Adiabatic model;
- the evolution of a quantum system to a state of minimal
energy;
- how to represent the energy configuration of a quantum
system (i.e., Hamiltonian) using the Ising model;
- the similarity between the Ising model and the QUBO representation for optimizing (NP-hard) problems.
Part 2: QUBO Formulation (50 min)
This part will show how
to represent classical binary optimization problems in QUBO formulation. In particular, it will explain how to write NP-complete
binary decision problems (e.g., number partitioning) and NP-hard
binary optimization problems (e.g., quadratic assignment) in QUBO
formulation, describing constraints and loss functions.
Part 3: QC for IR and RS and their Evaluation (30 min)
This part will introduce IR and RS problems which can be solved by using
QA , namely Feature Selection, Clustering and Model Boosting.
Moreover, we will discuss how to evaluate such QA algorithms
from both the efficiency and effectiveness point of view. Finally,
it will introduce the QuantumCLEF lab and present the lessons
learned from it.
Part 4: Hands-on (60 min)
This part discusses how to use
quantum annealers, which are available as a cloud service. It involves
- the architecture and topology of a quantum annealer;
- how to use the QUBO formulation of a problem to program
the quantum annealer via Minor Embedding;
- how the density of the QUBO problem impacts the number
of variables required on the quantum annealer;
- how to program a quantum annealer and read the result
(hands-on);
- Feature Selection and Clustering(hands-on);
- execution and evaluation of one of the above algorithms on
the QuantumCLEF infrastructure (hands-on).
The intended audience for this tutorial
are researchers and practitioners coming from Information
Retrieval (IR) and Recommender Systems (RS), as well as from
other fields, such as Natural Language Processing, Machine
Learning, Big Data, Operations Research, and Optimization.
In fact, QC and QA are powerful tools that can be applied
to tackle problems in many different domains. Furthermore,
while the practical part of the tutorial is focused on how to
use QA for IR and RS, the problems we consider are quite
general and have wide application to different research areas
- Targeted audience: Due to the topic's novelty, the target audience is of researchers and industry practitioners mainly belonging to IR and RS.
- Prerequisite knowledge: This tutorial will be self-contained
and has minimal prerequisite knowledge, mainly consisting
of being familiar with the basic concepts of IR and RS. For
those interested in the hands-on part, basic Python programming skills are required to interact with quantum annealers through the tools provided by D-Wave but no specific
knowledge of the D-Wave API is required ahead.
Here you can find the slides used during the tutorial:
