  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.
