The computational problem PUBO, which we take to stand for Polynomial
Unconstrained Binary Optimization, is the problem of finding the minimizing
input to a given polynomial with binary variables. Similarly, the
computational problem QUBO (Quadratic Unconstrained Binary
Optimization) is the same as PUBO except that the polynomial has
at most degree 2. PUBO (and thus also QUBO) are NP-hard, as can be
seen from the fact that many NP-hard problems can be reduced to QUBO [1]}.
For the sake of brevity, we often use the term “QUBO” to refer
to a quadratic polynomial with binary variables rather than the computational
problem itself as in “\(f(x,y,z)=z+xy-x\)  is a QUBO and \(g(x,y,z)=xyz\) 
is a PUBO”.
