  We discuss the computational complexity of finding the ground state of the
two-dimensional array of quantum bits that interact via strong van der Waals
interactions. Specifically, we focus on systems where the interaction strength
between two spins depends only on their relative distance $x$ and decays as
$1/x^6$ that have been realized with individually trapped homogeneously excited
neutral atoms interacting via the so-called Rydberg blockade mechanism. We show
that the solution to NP-complete problems can be encoded in ground state of
such a many-body system by a proper geometrical arrangement of the atoms. We
present a reduction from the NP-complete maximum independent set problem on
planar graphs with maximum degree three. Our results demonstrate that
computationally hard optimization problems can be naturally addressed with
coherent quantum optimizers accessible in near term experiments.
