  Realizing quantum speedup for practically relevant, computationally hard
problems is a central challenge in quantum information science. Using Rydberg
atom arrays with up to 289 qubits in two spatial dimensions, we experimentally
investigate quantum algorithms for solving the Maximum Independent Set problem.
We use a hardware-efficient encoding associated with Rydberg blockade, realize
closed-loop optimization to test several variational algorithms, and
subsequently apply them to systematically explore a class of graphs with
programmable connectivity. We find the problem hardness is controlled by the
solution degeneracy and number of local minima, and experimentally benchmark
the quantum algorithm's performance against classical simulated annealing. On
the hardest graphs, we observe a superlinear quantum speedup in finding exact
solutions in the deep circuit regime and analyze its origins.
