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?

  • 2
    $\begingroup$ 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. $\endgroup$ – Yonatan N Mar 17 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.