Extended local error correction of the maximum independent set solutions obtained by Rydberg-atom experiments

In recent years, finding the solutions of the maximum independent set problem (MIS) by Rydberg-atom experiments has drawn keen interest [1,2], being expected to achieve a sub-exponential, efficient computation of the MIS problem in the NP class of computational complexity. However, experimental solution errors remain, being attributed to the current level of environmental noise and systematic errors, while they are partially corrected either by a greedy local error correction algorithm [1] or the most-likelihood estimation [2]. Here, we combine the above two correction methods to consider an extended local error correction which utilizes a small-scale lookup database of most-likelihood estimations. A preliminary result shows that, with the new method, MIS solutions are retrievable over 10% probability from possible experimental MIS solutions under the assumption of even up to 40% bitflip error probability, surpassing the under 4% retrieval probability of previous demonstrations. In conclusion, Rydberg atom experiments for the MIS problem could be improved by the presented extended local correction method to be of an accuracy mainly limited by the algorithmic efficiency and power of classical computation.

[1] S. Ebadi et al., "Quantum optimization of maximum independent set using Rydberg atom arrays," Science 376, 1209 (2022).

[2] M. Kim, K. Kim, J. Hwang, E.-G. Moon, and J. Ahn, “Rydberg quantum wires for maximum independent set problems,” Nature Phys., 18, 755-759 (2022).