Rydberg-atom quantum computing of NP-complete problems

Currently there are growing interests in using Rydberg atom graphs for quantum computing of classically intractable problems, for example, the non-deterministic polynomial-time complete (NP-complete) problems. It has been identified some NP-complete 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 we report our experimental efforts for Rydberg-atom implementation of 3-SAT problems [4], along with further possibilities to other NP-complete problems such as Set Packing, Graph Coloring, and Clique problems, and Binary Integer Linear Programming.



[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 computing of 3-SAT problems using Rydberg atom graphs," in preparation (2022).