jrnl · home about list my companies

# Quantum Annealing Hamiltonian Example Calculation

Let's calculate quickly what happens.

We have an extremely simple Number Partitioning problem consisting of the set of numbers {1,2,3}\{1, 2, 3\}. It has an optimal solution, which is splitting the set into two subsets {1,2}\{1, 2\} and {3}\{3\}.

The Ising formulation for Number Partitioning is given as A(j=1mnjxj)2A(\sum_{j=1}^{m}n_{j}x_{j})^2, where njn_j is the j-th number in the set. Thus, with A=1A=1, for the given set the result is (x1+2x2+3x3)2=x1x1+4x1x2+6x1x3+4x2x2+12x2x3+9x3x3(x_1 + 2x_2 + 3x_3)^2 = x_1x_1 + 4x_1x_2 + 6x_1x_3 + 4x_2x_2 + 12x_2x_3 + 9x_3x_3. Now, the Hamiltonian for an Ising formulation is very simple: Replace xix_i by a Pauli Z Gate. We can now write the Hamiltonian using QuBits (with an exemplary QuBit state):

010Z1Z2Z3010\langle{}010|Z_1Z_2Z_3|010\rangle{}

Thus, we can evaluate the cost of a possible set of subsets by using QuBits. For instance, a state 010|010\rangle{} means that the numbers 1 and 3 are in one subset and the number 2 is in another subset. It should be noted that 1Zi1=1\langle{}1|Z_i|1\rangle{} = -1 and 0Zi0=1\langle{}0|Z_i|0\rangle{} = 1.

More specifically (where xi=Zix_i = Z_i), the Quantum formulation for our problem is:

010x1x1+4x1x2+6x1x3+4x2x2+12x2x3+9x3x3010\langle{}010|x_1x_1 + 4x_1x_2 + 6x_1x_3 + 4x_2x_2 + 12x_2x_3 + 9x_3x_3|010\rangle{}

Here, we have 0x10=1\langle{}0|x_1|0\rangle{} = 1, 1x21=1\langle{}1|x_2|1\rangle{} = -1 and 0x30=1\langle{}0|x_3|0\rangle{} = 1. Thus, the total cost is:

010x1x1+4x1x2+6x1x3+4x2x2+12x2x3+9x3x3010=14+6+412+9=4\langle{}010|x_1x_1 + 4x_1x_2 + 6x_1x_3 + 4x_2x_2 + 12x_2x_3 + 9x_3x_3|010\rangle{} = 1 - 4 + 6 + 4 - 12 + 9 = 4.

Note that one of the the optimal solutions is:

001x1x1+4x1x2+6x1x3+4x2x2+12x2x3+9x3x3001=1+46+412+9=0\langle{}001|x_1x_1 + 4x_1x_2 + 6x_1x_3 + 4x_2x_2 + 12x_2x_3 + 9x_3x_3|001\rangle{} = 1 + 4 - 6 + 4 - 12 + 9 = 0.

Another one would have been the state 110|110\rangle{}.

In summary, we can now adapt a bunch of QuBits to evaluate the goodness of a solution. This in turn opens interesting possibilities..

References:

  • Lucas, Andrew. "Ising formulations of many NP problems.", 2014
Published on