Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions

2021/07/24 by Amit Verma, Mark Lewis, Verma, Amit +3 · 1 citation
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #FOS: Mathematics #Formal Methods in Verification #Numerical Methods and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2107.11695

openalex publication_date 2021/07/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Quadratic Unconstrained Binary Optimization (QUBO) is recognized as a unifying framework for modeling a wide range of problems. Problems can be solved with commercial solvers customized for solving QUBO and since QUBO have degree two, it is useful to have a method for transforming higher degree pseudo-Boolean problems to QUBO format. The standard transformation approach requires additional auxiliary variables supported by penalty terms for each higher degree term. This paper improves on the existing cubic-to-quadratic transformation approach by minimizing the number of additional variables as well as penalty coefficient. Extensive experimental testing on Max 3-SAT modeled as QUBO shows a near 100% reduction in the subproblem size used for minimization of the number of auxiliary variables.

Citations

• QUBO transformation using Eigenvalue Decomposition

Cited by

• Pattern or Not? QAOA Parameter Heuristics and Potentials of Parsimony

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
• Deriving Compact QUBO Models via Multilevel Constraint Transformation
• Faster QUBO Brute-Force Solving using Gray Code
• How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization