# Computational Complexity of Quadratic Unconstrained Binary Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Sep 2021.

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

- [Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization](https://mlsanity.com/paper/2203.12633/) (2022)

## Abstract (arXiv)

In this paper, we study the computational complexity of the quadratic unconstrained binary optimization (QUBO) problem under the functional problem FP^NP categorization. We focus on four sub-classes: (1) When all coefficients are integers QUBO is FP^NP-complete. (2) When every coefficient is an integer lower bounded by a constant k, QUBO is FP^NP[log]-complete. (3) When every coefficient is an integer upper bounded by a constant k, QUBO is again FP^NP[log]-complete. (4) When coefficients can only be in the set {1, 0, -1}, QUBO is FP^NP[log]-complete. With recent results in quantum annealing able to solve QUBO problems efficiently, our results provide a clear connection between quantum annealing algorithms and the FP^NP complexity class categorization. We also study the computational complexity of the decision version of the QUBO problem with integer coefficients. We prove that this problem is DP-complete.