  Platforms of Rydberg atoms have been proposed as promising candidates to
solve some combinatorial optimization problems. Here, we compute quantitative
requirements on the system sizes and noise levels that these platforms must
fulfill to reach quantum advantage in approximately solving the Unit-Disk
Maximum Independent Set problem. Using noisy simulations of Rydberg platforms
of up to 26 atoms interacting through realistic van der Waals interactions, we
compute the average approximation ratio that can be attained with a simple
quantum annealing-based heuristic within a fixed temporal computational budget.
Based on estimates of the correlation lengths measured in the engineered
quantum state, we extrapolate the results to large atom numbers and compare
them to a simple classical approximation heuristic. We find that approximation
ratios of at least $\approx 0.84$ are within reach for near-future noise
levels. Not taking into account further classical and quantum algorithmic
improvements, we estimate that quantum advantage could be reached by attaining
a number of controlled atoms of $\sim8,000$ for a time budget of 2 seconds, and
$\sim 1,000-1,200$ for a time budget of 0.2 seconds, provided the coherence
levels of the system can be improved by a factor 10 while maintaining a
constant repetition rate.
