# Interpretation of the numerical partition problem using the Ising model

How to formulate the numerical partition problem using the Ising model?

Given a set with N numbers S = {n1, n2, …, nN}, is there a partition into two distinct sets R and S-R, so that the sum of the elements is the same?

This is the problem of the numerical partition, which is known to be NP-complete.

Example. I have two children, and I want to separate the toys in a box equally for both of them. Each toy has a different value, given by the set

S = {9, 6, 5, 1, 4, 9, 12, 5, 2, 15}

How can I do this division?

The formulation via Ising’s model, according to Lucas*:

Where xi is the decision variable, which in this case can take values between -1 and +1, representing spins, as if they were magnets. A is a constant for scaling the energy level (here it is useless, but it can be useful in case of translating this model to a real quantum computer), and, for simplicity, I will assume A = 1.

In the case of the numerical example, it is straightforward:

As the idea is to divide into two groups, this is achieved when H = 0. The square serves to make both positive and negative differences positive.

It is very simple to model and solve in the Excel solver, just taking care to transform the binary variable into -1 and +1, and also consider that the objective function is non-linear.

Download here .

There are several possible solutions, what the literature calls degenerations. An obvious one is the complement of the solution — just change the +1 for -1 in a solution.

One way the Lucas indicates to avoid degeneration is to set the first variable to +1 (or -1) — and this has the advantage of saving a qubit.

If the ground state is greater than zero, it means that there is no exact solution, but the solution found is the best possible.

There is an easy interpretation of the Ising model in this case.

Suppose a simpler example:

S = {1,4,3}

Thinking of magnets and forces interacting, the graph would be totally connected.

Imagine the solution, the x2 being -1. It would be like a magnet with the pole changed.

Values 8 and 24 become negative, while value 16 remains positive (because it squares). The sums of the numbers in black and red are the same.

This formulation of a NP problem in a Ising model has the goal of later using this in a quantum annealing computer.

Andrew Lucas’s paper is a spectacular reference on the topic:

- Reference: Ising formulations of many NP problems — Andrew Lucas

About the author:

Arnaldo Gunzi is Project Manager on Analytics and Innovation. Passionate about Combinatorial Optimization, Philosophy and Quantum Computing.

Technical ideas with a bit of philosophy:

See also: