1
$\begingroup$

I am reading the paper from Andrew Lucas, Ising formulations of many NP problems, and I am stuck with the formulation of the following Ising Hamiltonian:

$$H = A \bigg( K - \sum_v x_v \bigg)^2 + B\bigg[ \frac{K(K-1)}{2}- \sum_{(uv)\in E} x_u x_v \bigg]$$ I have realized that I don't really understand why the expression corresponding to the constant $A$ is squared but not the one corresponding to the constant $B$.

$\endgroup$
1
  • $\begingroup$ Is $K$ also a constant and where does $x_v$ take values? $\endgroup$ Mar 3 at 20:25

1 Answer 1

2
$\begingroup$

The square comes from the definition of the Hamilton $H_A$ given in equation (8) of the referenced paper. This term is described by

"... is an energy which provides a penalty if the number of elements in the + set is not equal to the number in the − set"

By squaring the sum you basically do not distinguish if the + set or the - set was larger. You just get a positive number depending on the difference of the number of + and - elements.

$\endgroup$
1
  • $\begingroup$ I think you're mistaken, that expression and paragraph you're referring to are from the graph partitioning problem, not the clique, which is the next point. In the clique problem, it's essential to talk about size, so it doesn't make much sense... $\endgroup$
    – Laura
    Mar 7 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.