Mixed-Binary Quadratic Programming via QUBO Sampling without Continuous-Variable Binarization

Abstract:Quantum annealing and related combinatorial optimization methods typically accept quadratic unconstrained binary optimization (QUBO) problems as input, whereas many practical models include constraints and continuous variables. Standard QUBO conversions discretize continuous variables, increasing the binary dimension and often making feasible low-energy states harder to sample. We develop a finite-temperature formulation for a separable class of mixed-binary quadratic programs (MBQPs) that avoids this discretization. At fixed Lagrange multipliers, the continuous sector is integrated out analytically and enters only the multiplier update, leaving a QUBO over the original binary variables. We evaluate the method on the continuous relaxation of the quadratic $p$-median problem. Compared with a penalty-based QUBO formulation, it generates feasible solutions more reliably. At an appropriate inverse temperature, its conditional relative error is comparable to that of local search for small instances and often lower for the larger tested instances. In the time-to-target experiment, it also reaches the target faster than a commercial mixed-integer optimization solver toward the upper end of the tested range.

arXiv:2607.21286 [quant-ph]

(or arXiv:2607.21286v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2607.21286 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.