DC 2 – Beyond Quadratic Unconstrained Binary Optimisation (QUBO)

Project Title: Beyond Quadratic Unconstrained Binary Optimisation (QUBO)
Doctoral Candidate: N.N.
Host Institution: CNR IASI Rome
Supervisors: Claudio Gentile, Frauke Liers

Objectives: QUBO is a powerful paradigm suitable for addressing many difficult real-world optimisation problems. The interest in QUBO has grown considerably in the last decade since computing systems based on quantum annealing came to the market. The development of methods for the exact solution of QUBO problems was one of the topics of the MINOA project where, for example, experimental evidence was provided that quantum supremacy over classical systems is still far from being obtained. Regardless of whether a fast and reliable QUBO solver is built with quantum or classical technologies, there is a growing demand for hybrid algorithms for Quadratic Constrained Binary Optimisation (QCBO) models that use that solver as an optimisation engine. QCBO problems abound, e.g., in logistics, in scheduling and more generally in operations research. Moreover, bilevel versions of QUBO problems with interdiction variables will also be addressed. A second possible extension of QUBO, rather than adding constraints to the problem, considers polynomials of degree greater than 2 (PUBO) or even arbitrary functions of binary variables (FUBO) in the objective function. Models of this type are very useful in many Dapplications, e.g., in machine learning. The reduction of PUBO to QUBO dates back to the work of Rosenthal but typically produces too large QUBO instances. Other approaches that boil down somewhat to the QUBO techniques have been proposed for PUBO and FUBO by members our consortium. Due to the wide spectrum of possible applications of PUBO and FUBO models, it is relevant to explore new methods to solve these difficult problems efficiently, at least for moderate sized cases, possibly exploiting a QUBO engine like one of those mentioned above.

Expected Results: Studying new methods for solving QUBO problems. New extensions of QUBO to PUBO and FUBO problems. New optimisation methods for Quantum Computing. Application in Machine Learning.

Planned secondment: 2 months at MAIOR (S. Carosi) at the end of the 1st year to gain experience on decomposition methods and their applications; 3 months during the 2nd year at FAU (F. Liers) to develop methods for Quantum Computing and study applications of QUBO to Physics.

Degree awarding institution: Sapienza Università di Roma