# Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2020.

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

- [QuantumQUBO Agent: Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language](https://mlsanity.com/paper/2609.10629/) (2026)

## Abstract (arXiv)

Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on 16 instances, ranging from 37 to 223 variables, demonstrate that our approach requires notably fewer binary variables than quadratization. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.