# Problems rephrased as quadratic unconstrained binary optimization

I was impressed when i came across Quadratic unconstrained binary optimization (QUBO) recently, and saw how one can rephrase many combinatorial problems into questions about optima of binary functions. A very nice review with many examples can be found in Andrew Lucas' Ising formulations of many NP problems. He shows problems such as Graph Coloring or 3SAT as a minimisation problem.

My question is: In general, what type of problems can be mapped to QUBO? In particular, is it possible to map even more difficult problem (such as counting solutions of 3SAT or other #P problems) to QUBO?

Are there examples for that, or would that contradict some results or strongly believed conjectures about computation complexity?

• Is QUBO not in NP, and thus NP-Complete? If it is, your question is equivalent to some flavor of $\#P \subseteq NP$, which is famously still open. – Yonatan N Mar 17 '19 at 5:24