Help us make Indico better by taking this survey! Aidez-nous à améliorer Indico en répondant à ce sondage !

May 29, 2023 to June 1, 2023
Santiago de Compostela
Europe/Madrid timezone

Encodings of binary variables for efficient use in a quantum computer

Jun 1, 2023, 12:00 PM
20m
Aula Magna

Aula Magna

Facultad de Matemáticas, USC

Speaker

Márcio Taddei (ICFO - The Institute of Photonic Sciences)

Description

Quantum computers in the NISQ era (noisy, intermediate-scale, quantum) still offer a relatively small amount of qubits. The largest quantum computers so far, dedicated to binary optimization, do not surpass a few thousands qubits. We nevertheless are willing and able to probe such computers in real-life tasks with their high demand in number of variables to optimize over.
We tackle a binary optimization problem and discuss the problems around its conversion to a QUBO (quadratic unconstrained binary optimization), which is the kind of problem treated by quantum annealers such as the D-Wave quantum computers. Among these problems are the use of penalties and, importantly, quadratization (reduction of higher-order polynomials to binary ones) that typically requires (scarcely available) extra variables. Different encodings of the same problem are discussed, and, surprisingly, encoding the original problem's variables as densely as possible into fewer binary variables becomes counterproductive after a certain degree in the context of QUBO optimization. We show how this result comes about in the context of different forms of quadratization and discuss their advantages and disadvantages for use in a quantum computer.

Primary authors

Mr Giacomo Franceschetto (IQOQI VIenna, Università degli Studi di Padova) Márcio Taddei (ICFO - The Institute of Photonic Sciences)

Presentation materials