Researchers from the Department of Physics at KAIST, Daejeon, and Korea University, Seoul, have conducted experiments using Rydberg-atom quantum simulators to solve the Maximum Independent Set (MIS) problem. The MIS problem is a complex computational issue that cannot be efficiently solved using classical computations. The team used adiabatic quantum computation (AQC) to solve the MIS problem, preparing an 11-by-18 array of optical tweezers to trap rubidium atoms. The data from these experiments could be used to analyse adiabatic computing behaviour and explore quantum phase transitions.
Quantum Computing Dataset for Maximum Independent Set Problem
A team of researchers, Kangheun Kim, Minhyuk Kim, Juyoung Park, and Andrew Byun, under the guidance of Jaewook Ahn from the Department of Physics, KAIST, Daejeon, and the Department of Physics, Korea University, Seoul, have presented a set of quantum adiabatic computing data from Rydberg-atom experiments. These experiments were performed to solve the Maximum Independent Set (MIS) problem of up to 141 atoms randomly arranged on the king lattice.
The Maximum Independent Set Problem
The MIS problem is a nondeterministic polynomial (NP) complete problem, which is not efficiently solvable with classical computations. It belongs to the computational class of NP-complete problems, the hardest computational problems with no known classical algorithms that are efficient. The MIS problem aims to find the maximum independent set, the largest set among the independent sets, where the independent set is defined as a set of unedged vertices.
Rydberg Quantum Simulators
Rydberg quantum simulators are currently one of the biggest quantum computing physical platforms capable of utilizing up to a few hundred qubits. The constraint of the independent set is implementable intrinsically with the Rydberg blockade effect that forbids two atoms proximate within a certain distance from being simultaneously excited to the same Rydberg-atom state. Therefore, a set of atoms arranged to a graph and simultaneously pumped to Rydberg atoms results in a nonadjacent arrangement of Rydberg atoms fulfilling the independent set constraint.
Adiabatic Quantum Computation
Rydberg-atom systems could perform adiabatic quantum computation (AQC) for the MIS problem in such a way that a target manybody ground state is prepared adiabatically from an easily preparable initial ground state. There are several recent experiments computing the solution of the MIS problem on the Rydberg-atom system by AQC.
Experimental AQC Data
The team provided a set of experimental AQC data of the MIS problem performed on the Rydberg-atom system. They first prepared an 11-by-18 array of optical tweezers. This lattice is identical to the union-jack-like king graph recently experimented by Ebadi et al. On 198 optical tweezer traps, atoms are stochastically loaded with about a probability of about 50% and resulting random graphs are used.
Atom-array Preparation
Rubidium atoms (87Rb) are loaded onto an array of 18 by 11 optical tweezers with the nearest atom distance of d = 60 μm. To successfully trap the hundreds of atoms, all 198 tweezer traps are prepared as uniformly as possible. Tweezer traps are generated by Fourier transform of the phase displayed on the spatial light modulator (SLM). The initial trap phase was generated with the Gerchberg-Saxton weighted (GSW) algorithm with 100 iterations starting from the uniform trap phase guess.
Analysis of Adiabatic Computing Behavior
The data could be harnessed for the analysis of adiabatic computing behavior, the exploration of quantum phase transitions (QPT) in the transverse Ising model, and as a reference for conducting benchmark tests of the Rydberg atom approach to optimization problems.
The article titled “Quantum computing dataset of maximum independent set problem on king lattice of over hundred Rydberg atoms” was published in the Scientific Data journal on January 23, 2024. The authors of the study are Kangheun Kim, Minhyuk Kim, Ju‐Young Park, Andrew Byun, and Jaewook Ahn. The study can be accessed through its DOI: https://doi.org/10.1038/s41597-024-02926-9.
