Assessing the potential of Rydberg atoms for adiabatic quantum computing of an NP-hard problem

When practically confronted with an NP-hard combinatorial optimization problem, the first question many computer scientists ask is whether a good approximation algorithm exists (i.e a tractable algorithm with provable guarantees on solution quality). We argue that the quality and potential of NISQ quantum annealers should therefore be assessed through the approximation ratio that they achieve on specific NP-hard problems. We put this methodology to practice for a platform consisting of neutral atoms trapped in optical arrays [1], which may be used to tackle an NP-hard problem called UD-MIS [2]. We present numerical estimates of the approximation ratio achieved by this approach under realistic noise conditions, on a class of experimentally-implementable random graphs. These results are then compared with the performances achieved by classical PTASs (Polynomial-Time Approximation Schemes) on the same problem.



[1] Barredo, D., De Léséleuc, S., Lienhard, V., Lahaye, T., & Browaeys, A. (2016). Science, 354(6315), 1021-1023.
[2] Pichler, H., Wang, S. T., Zhou, L., Choi, S., & Lukin, M. D. (2018). arXiv preprint arXiv:1808.10816.