Finding the Maximum Independent Sets of Platonic Graphs Using Rydberg Atoms

Abstract

We present Rydberg-atom-array experiments performed to find the maximum independent sets of Platonic graphs. Three Platonic graphs-the tetrahedron, cube, and octahedron of Platonic solids-are constructed with atoms and Rydberg interatomic interactions, representing, respectively, the vertices and edges of the graphs. In particular, the three-dimensional Platonic graph structures are transformed onto the two-dimensional plane by using Rydberg quantum wires that couple otherwise uncoupled long-distance atoms. The maximum independent sets of the graphs correspond to the antiferrolike many-body ground-state spin configurations of the as-constructed Rydberg-atom arrays, which are successfully probed by quasiadiabatic control of the Rydberg-atom arrays from the paramagnetic phase to their antiferrolike phases. Our small-scale quantum simulations using fewer than 18 atoms are limited by experimental imperfections, which can be easily improved upon by the state-of-the-art Rydberg-atom technologies for scales of more than 1000 atoms. Our quantum-wire approach is expected to pave a new route toward large-scale quantum simulations.