Platforms of Rydberg atoms have been proposed as promising candidates to solve some combinatorial NP-hard optimization problems.
A team of scientists at Atos Quantum Lab has computed 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 the Atos Quantum Learning Machine to perform noisy simulations of Rydberg platforms of up to 26 atoms interacting through realistic van der Waals interactions, they computed 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, they extrapolated the results to large atom numbers and compare them to a simple classical approximation heuristic.
They found that approximation ratios of at least ≈0.84 are within reach for near-future noise levels. Not taking into account further classical and quantum algorithmic improvements, they estimated that quantum advantage could be reached by attaining a number of controlled atoms of ∼8000 for a time budget of 2 s, and ∼1000–1200 for a time budget of 0.2 s, provided the coherence levels of the system can be improved by a factor 10 while maintaining a constant repetition rate.