mlsanityData to 14 Oct 2026

Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions

arXiv 2107.11695 ↗First posted 24 Jul 2021math.OC cs.AIcited by 2

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 5 of its 24 references that are in the map. First posted on arXiv 24 Jul 2021.

Builds on

5 of 24 references.

References · 5

  1. 2013Ising formulations of many NP problemscited by 207
  2. 2019Quadratization in discrete optimization and quantum mechanicscited by 5
  3. 2021Constraint Programming to Discover One-Flip Local Optima of Quadratic Unconstrained Binary Optimization Problemscited by 3
  4. 2021Goal Seeking Quadratic Unconstrained Binary Optimizationcited by 1
  5. 2021QUBO transformation using Eigenvalue Decompositioncited by 1

Built on by

Cited by year

Citing papers per year: 2023: 2.

2 papers.

  1. 2023A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learningcited by 1
  2. 2023A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learningcited by 0