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 three sub-classes: (1) When all coefficients are integers QUBO is FP^NP-complete. When every coefficient is an integer lower bounded by a constant k, QUBO is FP^NP[log]-complete. (3) When coefficients can only be in the set {1, 0, -1}, QUBO is again 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.

翻译：在本文中,我们研究了功能问题FPNP分类中的二次不受限制的二次优化(QUBO)问题的计算复杂性,我们侧重于三个子类:(1) 当所有系数均为整数时,QUBO是完整的;当每个系数为整数,但受常数 k 约束的整数较低时,QUBO是全数。(3) 当系数只能出现在设定的 {1,0, -1}中时,QUBO再次是全数。由于最近量子整排的结果能够有效解决QUBO问题,我们的结果提供了量子整排算法和PPNP复杂等级分类之间的明确联系。我们还研究了QUBO问题决定版本的计算复杂性与整数系数。我们证明这个问题是DP的完成。