Faster QUBO Brute-Force Solving using Gray Code
This article describes an improved brute-force solving strategy for Quadratic Unconstrained Binary Optimization (QUBO) problems that is faster than naive approaches and easily parallelizable. It exploits the Gray code ordering of natural numbers to allow for a more efficient evaluation of the QUBO objective function. The implementation in Python is discussed in detail, and an additional C implementation is provided.
- Published in:
arXiv - Type:
Article - Authors:
Mücke, Sascha - Year:
2023 - Source:
https://arxiv.org/abs/2310.19373
Citation information
Mücke, Sascha: Faster QUBO Brute-Force Solving using Gray Code, arXiv, 2023, https://arxiv.org/abs/2310.19373, Muecke.2023a,
@Article{Muecke.2023a,
author={Mücke, Sascha},
title={Faster QUBO Brute-Force Solving using Gray Code},
journal={arXiv},
url={https://arxiv.org/abs/2310.19373},
year={2023},
abstract={This article describes an improved brute-force solving strategy for Quadratic Unconstrained Binary Optimization (QUBO) problems that is faster than naive approaches and easily parallelizable. It exploits the Gray code ordering of natural numbers to allow for a more efficient evaluation of the QUBO objective function. The implementation in Python is discussed in detail, and an additional C...}}
