Quantum programming of non-deterministic polynomial-time problems with Rydberg atom graphs

Currently there are growing interests in using Rydberg atom graphs for quantum computing of classically intractable problems, for example, the non-deterministic polynomial-time (NP) problems. It has been identified some NP problems are easily implementable with intrinsic Hamiltonians of interacting Rydberg atoms, of which atom arrangements define the problems in such a way that their solutions are compilable from the ground states of the Rydberg many-body Hamiltonians [1]. In the presentation, we first review our recent Rydberg-atom experiments performed for one of the NP-complete problems, the Maximum Independent Set (MIS) problem, in which we have investigated the MIS solutions of planar and nonplanar graphs implemented with atoms used as data qubits and quantum wires [2,3], and then we report new experimental efforts towards Rydberg-atom programming of other NP and NP-complete problems such as the 3-Satisfiability [4] and prime-number factorization problems.

[1] H. Pichler et al., "Quantum optimization for maximum independent set using Rydberg atom arrays," arXiv:1808.10816 (2018).

[2] M. Kim et al., "Rydberg Quantum Wires for Maximum Independent Set Problems," Nature Physics 18, 755 (2022).

[3] A. W. Byun et al., "Finding the maximum independent sets of Platonic graphs using Rydberg atoms," PRX Quantum 3, 030305 (2022).

[4] S. Jeong et al., "Quantum programming of the satisfiability problem using Rydberg atom graphs," preprint (2023).