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\}$. It has an optimal solution, which is splitting the set into two subsets $\{1, 2\}$ and $\{3\}$.

The Ising formulation for Number Partitioning is given as $A(\sum_{j=1}^{m}n_{j}x_{j})^2$, where $n_j$ is the j-th number in the set. Thus, with $A=1$, for the given set the result is $(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 $x_i$ by a Pauli Z Gate. We can now write the Hamiltonian using QuBits (with an exemplary QuBit state):

$\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\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 $\langle{}1|Z_i|1\rangle{} = -1$ and $\langle{}0|Z_i|0\rangle{} = 1$.

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

$\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 $\langle{}0|x_1|0\rangle{} = 1$, $\langle{}1|x_2|1\rangle{} = -1$ and $\langle{}0|x_3|0\rangle{} = 1$. Thus, the total cost is:

$\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:

$\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\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