I remember having heard once that generic spin-graphs e.g. Ising, or at least 2-local ones, can always be mapped to one another one (which will typically be larger), where every spin has at most $n$ neighbours. I'm not completely sure about the value of $n$, but seem to remember $n=3$ works. This also implies that finding ground states of 2-local Hamiltonians with max $n$ neighbours is an NP-hard problem.

Could someone confirm this and point me to a reference?



Your Answer

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

Browse other questions tagged or ask your own question.