Mátyás Koniorcyzk [1], Péter Naszvadi [1], Milkós Pintér [2] (2023.04.18 - 07.18)

[1] Wigner Reseach Centre for Physics
[2] Corvinus University of Budapest

Abstract: We investigate quadratic binary unconstrained optimization problems (QUBOs) in the framework of the project. These are hard computational tasks equivalent to the Ising model, and can also be solved with quantum annelaers. They can be rewritten into a mixed integer linear problem by the introduction of auxiliary variables; this is the standard (Fortet) linearization. In our research we investigate the extent to which the Fortet linearization can be used to improve on a solution obtained from heuristics (like, e.g. quantum annealing or simulated bifurcation), or the verification of their optimality with duality conditions. Meanwhile we solve small but hard QUBO instances, which contributes also to the better understanding of their structural properties.