  In this paper, we present a new method to solve a certain type of
Semidefinite Programming (SDP) problems. These types of SDPs naturally arise in
the Quadratic Convex Reformulation (QCR) method and can be used to obtain dual
bounds of Quadratic Unconstrained Binary Optimization (QUBO) problems. QUBO
problems have recently become the focus of attention in the quantum computing
and optimization communities as they are well suited to both gate-based and
annealing-based quantum computers on one side, and can encompass an exceptional
variety of combinatorial optimization problems on the other. Our new method can
be easily warm-started, making it very effective when embedded into a
branch-and-bound scheme and used to solve the QUBO problem to global
optimality. We test our method in this setting and present computational
results showing the effectiveness of our approach.
