Let's calculate quickly what happens.
We have an extremely simple Number Partitioning problem consisting of the set of numbers . It has an optimal solution, which is splitting the set into two subsets and .
The Ising formulation for Number Partitioning is given as , where is the j-th number in the set. Thus, with , for the given set the result is . Now, the Hamiltonian for an Ising formulation is very simple: Replace by a Pauli Z Gate. We can now write the Hamiltonian using QuBits (with an exemplary QuBit state):
Thus, we can evaluate the cost of a possible set of subsets by using QuBits. For instance, a state means that the numbers 1 and 3 are in one subset and the number 2 is in another subset. It should be noted that and .
More specifically (where ), the Quantum formulation for our problem is:
Here, we have , and . Thus, the total cost is:
Note that one of the the optimal solutions is:
Another one would have been the state .
In summary, we can now adapt a bunch of QuBits to evaluate the goodness of a solution. This in turn opens interesting possibilities..
- Lucas, Andrew. "Ising formulations of many NP problems.", 2014