# Black Box Optimization Using QUBO and the Cross Entropy Method

arXiv: https://arxiv.org/abs/2206.12510 · HTML: https://mlsanity.com/paper/2206.12510/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 24 references that are in the map.
- First posted on arXiv 24 Jun 2022.

## Builds on (most cited first, 6 of 6)

- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Bayesian Optimization of Combinatorial Structures](https://mlsanity.com/paper/1806.08838/) (2018)
- [Quadratic Unconstrained Binary Optimization Problem Preprocessing: Theory and Empirical Analysis](https://mlsanity.com/paper/1705.09844/) (2017)
- [Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems](https://mlsanity.com/paper/1911.08043/) (2019)
- [QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates](https://mlsanity.com/paper/2103.10695/) (2021)
- [Algorithmic QUBO Formulations for k-SAT and Hamiltonian Cycles](https://mlsanity.com/paper/2204.13539/) (2022)

## Built on by (most cited first, 3 of 3)

- [QuAnt: Quantum Annealing with Learnt Couplings](https://mlsanity.com/paper/2210.08114/) (2022)
- [Efficient Bit Labeling in Factorization Machines with Annealing for Traveling Salesman Problem](https://mlsanity.com/paper/2407.02091/) (2024)
- [Optimizing Sensor Redundancy in Sequential Decision-Making Problems](https://mlsanity.com/paper/2412.07686/) (2024)

## Abstract (arXiv)

Black-box optimization (BBO) can be used to optimize functions whose analytic form is unknown. A common approach to realising BBO is to learn a surrogate model which approximates the target black-box function which can then be solved via white-box optimization methods. In this paper, we present our approach BOX-QUBO, where the surrogate model is a QUBO matrix. However, unlike in previous state-of-the-art approaches, this matrix is not trained entirely by regression, but mostly by classification between 'good' and 'bad' solutions. This better accounts for the low capacity of the QUBO matrix, resulting in significantly better solutions overall. We tested our approach against the state-of-the-art on four domains and in all of them BOX-QUBO showed better results. A second contribution of this paper is the idea to also solve white-box problems, i.e. problems which could be directly formulated as QUBO, by means of black-box optimization in order to reduce the size of the QUBOs to the information-theoretic minimum. Experiments show that this significantly improves the results for MAX-k-SAT.