3.3 Moving from Ising to QUBO and back
Consider the following problem. Let’s say that you are given a set of integers and a target integer value , and you are asked whether there is any subset of whose sum is . For instance, if and , then the answer is affirmative, because . However, if and , the answer is negative because all the numbers in the set are even and they cannot add up to an odd number.
This problem, called the Subset Sum problem, is known to be -complete (see, for instance, Section 7.5 in the book by Sipser [90] for a proof). It turns out that we can reduce the Subset Sum problem to finding a spin configuration of minimal energy for an Ising model, (which is an -hard problem – see Section 3.1.3). This means that we can rewrite any instance of Subset Sum as an Ising ground state problem (check Appendix C, Computational Complexity, for a refresher on reductions).
However, it may not be directly evident how to do so.
In fact, it is much simpler to pose the...
