QUBO Sampling for Mixed Binary Quadratic Programming 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 Lagrange-multiplier method for a separable class of mixed-binary quadratic programs (MBQPs) without discretizing continuous variables. The method is based on a finite-temperature free-energy formulation and uses QUBO sampling for the binary sector. 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 comparisons, the proposed method maintains high target-reached rates for stringent fixed-accuracy targets. For the larger instances within the tested range, it also reaches the prescribed targets faster than a commercial mixed-integer optimization solver.
Versions
Related
- Warm-IP: A Path-Following ADMM Warm Start for Interior-Point Quadratic Programming
- Exponential advantage in continuous-variable quantum state learning
- Complexity transition for continuous-variable cluster state
- Wavelength-shifting attack on a chip-based continuous-variable quantum key distribution system
- High-fidelity WDM/SDM fronthaul system based on state-continuous variable-bit coding and sparse residual enhancement
BibTeX
@misc{takabayashi2026qubo,
title = {{QUBO Sampling for Mixed Binary Quadratic Programming without Continuous Variable Binarization}},
author = {Taisei Takabayashi and Masayuki Ohzeki},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2607.21286},
eprint = {2607.21286},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.21286},
}
RIS
TY - UNPB
TI - QUBO Sampling for Mixed Binary Quadratic Programming without Continuous Variable Binarization
AU - Taisei Takabayashi
AU - Masayuki Ohzeki
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2607.21286
UR - https://arxiv.org/abs/2607.21286
AB - 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 Lagrange-multiplier method for a separable class of mixed-binary quadratic programs (MBQPs) without discretizing continuous variables. The method is based on a finite-temperature free-energy formulation and uses QUBO sampling for the binary sector. 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 comparisons, the proposed method maintains high target-reached rates for stringent fixed-accuracy targets. For the larger instances within the tested range, it also reaches the prescribed targets faster than a commercial mixed-integer optimization solver.
ER -