Solving mixed-integer problems as QUBO: encodings, reformulations, and rolling-precision algorithm

Abstract

Many real-world optimization problems are constrained mixed-integer programs. This is problematic for quantum annealers and quadratic unconstrained binary optimization (QUBO)-based quantum optimization platforms, that operate natively on binary quadratic models. We present a unified framework for solving mixed-integer problems through QUBO. We present new encoding schemes that represent bounded continuous variables and selected nonlinear terms using structured collections of binary variables with controllable decimal precision. We review how a broad class of mixed-integer and geometric programs can be reformulated as QUBO. We further introduce a rolling-precision algorithm that avoids a monolithic high-resolution QUBO by solving a sequence of smaller QUBOs on successively refined discretization grids. Two strategies are proposed: (i) sequential bit-growth that progressively increases discretization depth, and (ii) constant-size zoom-in scheme that fixes the number of bits and refines precision by tightening variable bounds around incumbents. Illustrative tests demonstrate solutions with controllable accuracy while keeping individual QUBO sizes moderate.