Solving One-Dimensional Distance Geometry: a Comparison of GPU Annealing and Branch-and-Prune

Abstract

This paper explores the application of the Quantix GPU annealer for solving the Subset Sum Problem (SSP) and equivalent cycle instances of the one-dimensional Distance Geometry Problem (DGP). We present a comparative study against the exact Branch and Prune (BP) algorithm across various instance classes to evaluate their respective strengths and limitations. Our computational experiments reveal a significant divergence in performance, despite both solvers operating as 64-bit digital systems. While the BP algorithm efficiently solves standard, unstructured instances, it exhibits exponential complexity on highly structured instances where its pruning mechanisms fail. Conversely, the GPU annealer navigates deeply structured data with ease, but struggles with low-density instances. This difficulty arises because the necessary Quadratic Unconstrained Binary Optimization (QUBO) formulation quadratically increases the required bit precision, causing the annealer to hit representation limits faster than traditional methods. We empirically show that the GPU annealer’s efficacy seems to be dictated by the system’s capacity to represent the underlying QUBO model.