Dynamic Range Reduction via Branch-and-Bound
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
A key strategy to enhance specialized hardware accelerators, such as GPUs and FPGA, is to reduce the numerical precision in arithmetic operations, which increases processing speed and lowers latency-both crucial for real-time AI applications. In this work, we consider NP-hard Quadratic Unconstrained Binary Optimization (QUBO) problems, which arise in machine learning and beyond. We show that these problems often require high numerical precision, posing challenges for hardware solvers. We introduce a principled Branch-andBound algorithm for reducing the precision requirements of QUBO problems by utilizing the dynamic range as measure of complexity. Experiments demonstrate that our method reduces the dynamic range in subset sum, clustering, and vector quantization problems, thereby increasing their solvability on actual quantum annealers and FPGA-based digital annealers.