Answered
Reference for note on problem mapping
When discussing Ising and QUBO models, there is a note in the docs that states, "This limited focus is not constraining: any problem in the NP complexity class may be translated into this form." (https://docs.dwavesys.com/docs/latest/c_qpu_intro.html)
Is there a reference for this note?
Comments
Trying to guess the answer here -- is the note referring to this?
F. Barahona. “On the computational complexity of Ising spin glass models”, Journal of Physics A15 3241 (1982).
Thomas, you beat me to it! Thanks for providing the answer to your own question. This is indeed the paper.
Note also that this claim is a consequence of a proof that QUBO is NP-complete. See Lucas, A., 2014. Ising formulations of many NP problems. Frontiers in Physics, 2, p.5. https://arxiv.org/abs/1302.5843
While this is not the original source of the proof, Lucas states that 1/ Ising is another name for QUBO, and 2/ Ising is NP-complete (which means, by definition of NP-complete, that all problems in NP can map to it). It gives many concrete examples of problems being mapped to Ising (plus the trivial mapping from Ising to QUBO).
Please sign in to leave a comment.