Linkedin-in

Optimized QUBO formulation methods for quantum computing

  • Nano Colloquia
Speaker
Dario De Santis
Affiliation
Scuola Normale Superiore
Date
2024-09-19
Time
11:00
Venue
ON-SITE NEST Meeting Room ONLINE https://tinyurl.com/NanoColloquia
Host
Fabio Taddei
Several combinatorial optimization problems can be solved with a quantum computer once that a corresponding quadratic unconstrained binary optimization (QUBO) form is derived, namely a quadratic form that has no constraint attached. The aim of this work is to drastically reduce the variables needed for these QUBO reformulations in order to unlock the possibility to efficiently obtain optimal solutions for a class of optimization problems with quantum devices already available today. This is achieved by introducing novel tools that allow an efficient use of slack variables, even for problems with non-linear constraints, without the need to approximate the starting problem. We divide our new techniques in two independent parts: the iterative quadratic polynomial and the master-satellite methods. Hence, we show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario called Max-Profit Balance Settlement. We follow by submitting several instances of this problem to two D-wave quantum annealers, namely quantum devices specifically designed to solve QUBO problems, comparing the performances of our novel approach with standard methods.

Istituto Nanoscienze 

Consiglio Nazionale delle Ricerche

 

PEC: protocollo.nano@pec.cnr.it

Partita IVA 02118311006

Facebook-f Instagram Twitter Linkedin
Pisa NEST

Piazza San Silvestro 12

56127 Pisa, Italy

phone +39 050 509418

fax +39 050 509550

segreteria.nest@nano.cnr.it

Modena S3
via Campi 213/A
41125 Modena, Italy
phone +39 059 2055629
fax +39 059 2055651
segreteria.s3@nano.cnr.it

Istituto Nanoscienze Consiglio Nazionale delle Ricerche

Facebook-f Instagram Twitter Linkedin
Pisa NEST

Piazza San Silvestro 12, I
56127 Pisa

phone +39 050 509525/418

fax +39 050 509550

Modena S3

via Campi 213/A, I 

41125 Modena 7

phone +39 059 2055629

fax +39 059 2055651″