Faster QUBO Brute-Force Solving using Gray Code

2023/10/30 by Mücke, Sascha · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2310.19373

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 implementation is provided.

Cited by

• QUBOLite: A lightweigth Python toolkit for QUBO

Related

• Logical and Inequality Implications for Reducing the Size and Complexity of Quadratic Unconstrained Binary Optimization Problems
• Quadratic Unconstrained Binary Optimization Problem Preprocessing:\n Theory and Empirical Analysis
• Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions
• QUBOLite: A lightweigth Python toolkit for QUBO
• A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions