  With the advances in customized hardware for quantum annealing and
digital/CMOS Annealing, Quadratic Unconstrained Binary Optimization (QUBO)
models have received growing attention in the optimization literature.
Motivated by an existing general-purpose approach that derives QUBO models from
binary linear programs (BLP), we propose a novel Multilevel Constraint
Transformation Scheme (MLCTS) that derives QUBO models with fewer ancillary
binary variables. We formulate sufficient conditions for the existence of a
compact QUBO formulation (i.e., in the original BLP decision space) in terms of
constraint levelness and demonstrate the flexibility and applicability of MLCTS
on synthetic examples and several well-known combinatorial optimization
problems, i.e., the Maximum 2-Satisfiability Problem, the Linear Ordering
Problem, the Community Detection Problem, and the Maximum Independence Set
Problem. For a proof-of-concept, we compare the performance of two QUBO models
for the latter problem on both a general-purpose software-based solver and a
hardware-based QUBO solver. The MLCTS-derived models demonstrate significantly
better performance for both solvers, in particular, solving up to seven times
more instances with the hardware-based approach.
