Generate Image

Solving Number Partitioning Problem on QAOA

Yuichiro Minato

2022/01/30 15:53

#qaoa

Number Partitioning Problem

Number Partitioning Problem is a problem to make two groups that sum of the each groups are the same.

Reference

Ising formulations of many NP problems
Andrew Lucas
https://arxiv.org/abs/1302.5843

Ising hamiltonian

$i$ th of N natural number we put as $n_i$ . And if this number belongs to any groups we show this using $Z_i$ . If $n_i$ belongs to group A, it is $Z_i=1$ . And if it belongs to group B it is $Z_i=0$ .

And then we create a hamiltonian of $H$ that take the minimum value when the sum of each groups are the same.

H = (\sum n_i*Z_i)^2

It will be $H=0$ when the sum of two groups are the same and takes $H>0$ if these are different.

Example

Let's try solve a simple example. Now we have a list of natural number

[3,6,5,6,5,2,6,8,5,8]

and we make two groups. The hamiltonian is very simple

H = 3*Z(0)+6*Z(1)+5*Z(2)+6*Z(3)+5*Z(4)+2*Z(5)+6*Z(6)+8*Z(7)+5*Z(8)+8*Z(9)


#sum 38
num = [3,6,5,6,5,2,6,5]

from blueqat import vqe
from blueqat.pauli import Z

hamiltonian = (num[0]*Z(0)+num[1]*Z(1)+num[2]*Z(2)+num[3]*Z(3)+num[4]*Z(4)+num[5]*Z(5)+num[6]*Z(6)+num[7]*Z(7))**2
step = 2

result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian.simplify(), step)).run()

b = sum([x*y for (x,y) in zip(num, list(result.most_common(1)[0][0]))])

#answer 19
print(b)

result.most_common(12)

(((0, 1, 1, 1, 0, 1, 0, 0), 0.008320427578059642),

 ((0, 1, 0, 0, 1, 1, 1, 0), 0.008320427578059642),

 ((1, 0, 1, 1, 0, 0, 0, 1), 0.008320427578059642),

 ((1, 0, 0, 0, 1, 0, 1, 1), 0.008320427578059642),

 ((1, 0, 1, 1, 1, 0, 0, 0), 0.008320427578059638),

 ((1, 0, 1, 0, 1, 0, 1, 0), 0.008320427578059638),

 ((0, 1, 0, 1, 0, 1, 0, 1), 0.008320427578059638),

 ((0, 1, 0, 0, 0, 1, 1, 1), 0.008320427578059638),

 ((1, 1, 1, 0, 1, 0, 0, 0), 0.008320427578059637),

 ((0, 0, 0, 1, 0, 1, 1, 1), 0.008320427578059637),

 ((0, 1, 0, 1, 1, 1, 0, 0), 0.008320427578059635),

 ((1, 0, 1, 0, 0, 0, 1, 1), 0.008320427578059635))

Finally we got two groups the sum is each 19.