  Recent progress in quantum computing and quantum simulation of many-body
systems with arrays of neutral atoms using Rydberg excitation brought
unforeseen opportunities towards computational advantage in solving various
optimization problems. The problem of maximum-weight independent set (MWIS) of
unit-disk graphs is an example of NP-hard optimization problems. It involves
finding the largest set of vertices with the maximum sum of their weights for a
graph which has edges connecting all pairs of vertices within a unit distance.
This problem can be solved using quantum annealing with an array of interacting
Rydberg atoms. For a particular graph, a spatial arrangement of atoms
represents vertices of the graph, while the detuning from the resonance at
Rydberg excitation defines weights of these vertices. The edges of the graph
can be drawn according to the unit disk criterion. MWIS can be obtained by
applying a variational quantum adiabatic algorithm (VQAA). We consider driving
the quantum system of interacting atoms to the many-body ground state using a
non-linear quasi-adiabatic profile for sweeping the Rydberg detuning. We also
propose using a quantum wire which is a set of auxiliary atoms of a different
chemical element to mediate strong coupling between the remote vertices of the
graph. We investigate this effect for different lengths of the quantum wire. We
also investigate the quantum phases of matter realizing commensurate and
incommensurate phases in 1D and 2D spatial arrangement of the atomic array.
