QUBO and Quantum Annealing

Prof. Michele Marchesi
University of Cagliari and NetService spa

Abstract

The seminar, lasting about an hour, presents the problems of unconstrained binary quadratic optimization, where the variables assume binary values (0/1 or -1/1), and the function to be optimized is a quadratic form with real coefficients. It will discuss various real problems that can be represented as QUBO and how to incorporate constraints using penalty coefficients. Exact classical solvers, which can only be used for small problems due to the NP-complete complexity of QUBO problems, and the main heuristic solvers: Tabu Search and Simulated Annealing, will then be presented. Finally, the Quantum Annealing approach for solving this type of problem on specialized quantum computers will be presented.

Schedule

July 25th, 9:30-10:30 (Palazzo delle Scienze, Aula B)