Chordal branch and bound algortihms for spin glasses
García Hernández, Álvaro · UPCommons institutional repository (Universitat Politècnica de Catalunya) · 2022
In the era of quantum technology, benchmarking classical algorithms is necessary for certifying the results given by the quantum device to the optimization problem that is wanted to solve. Here we analyse a new algorithm that gives an upper and a lower bound to the ground state solution of Ising type optimization problems. We test its performance in solution planted problems and compare it with simulated annealing, a common algorithm to solve optimization problems, getting in general more reliable results in the same amount of time. Additionally, we verify the tunable hardness of the planting schemes used to generate the optimization problems.