# Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions

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

## 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 (most cited first, 5 of 5)

- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Quadratization in discrete optimization and quantum mechanics](https://mlsanity.com/paper/1901.04405/) (2019)
- [Constraint Programming to Discover One-Flip Local Optima of Quadratic Unconstrained Binary Optimization Problems](https://mlsanity.com/paper/2104.01709/) (2021)
- [Goal Seeking Quadratic Unconstrained Binary Optimization](https://mlsanity.com/paper/2103.12951/) (2021)
- [QUBO transformation using Eigenvalue Decomposition](https://mlsanity.com/paper/2106.10532/) (2021)

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

- [A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning](https://mlsanity.com/paper/2308.13978/) (2023)
- [A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning](https://mlsanity.com/paper/2311.16277/) (2023)

## 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.