# Mapping NP-hard and NP-complete optimisation problems to Quadratic Unconstrained Binary Optimisation problems

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Nov 2019.

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

- [Black Box Optimization Using QUBO and the Cross Entropy Method](https://mlsanity.com/paper/2206.12510/) (2022)
- [QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing](https://mlsanity.com/paper/2309.12678/) (2023)
- [Optimizing Sensor Redundancy in Sequential Decision-Making Problems](https://mlsanity.com/paper/2412.07686/) (2024)

## Abstract (arXiv)

We discuss several mappings from well-known NP-hard problems to Quadratic Unconstrained Binary Optimisation problems which are treated incorrectly by Lucas. We provide counterexamples and correct the mappings. We also extend the body of QUBO formulations of NP-complete and NP-hard optimisation problems by discussing additional problems.