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?