Quantum optimization of maximum independent set using Rydberg atom arrays

By S. Ebadi, A. Keesling, M. Cain, Tout T. Wang, H. Levine, D. Bluvstein, G. Semeghini, Ahmed Omran, Jin-Guo Liu, R. Samajdar and 14 more. Science, 2022

558 citations recorded by the source corpus.

Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the maximum independent set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find that the problem hardness is controlled by the solution degeneracy and number of local minima, and we experimentally benchmark the quantum algorithm’s performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins. Description Solving hard graph problems Realizing quantum speedup for solving practical, computationally hard problems is the central challenge in quantum information science. Ebadi et al. used Rydberg atom arrays composed of up to 289 coupled qubits in two spatial dimensions to investigate quantum optimization algorithms for solving the maximum independent set, a paradigmatic nondeterministic polynomial time–hard combinatorial optimization problem (see the Perspective by Schleier-Smith). A hardware-efficient encoding protocol associated with Rydberg blockade was used to realize a closed-loop optimization method to test several variational algorithms and subsequently apply them to systematically explore a class of nonplanar graphs with programmable connectivity. The results demonstrate the potential of quantum machines as a tool for the discovery of new promising algorithm classes. —ISO Rydberg atom arrays provide quantum speed-up for solving computationally hard optimization problems.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/2cbde52707a9ea66428d13f238fa18241254744e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe (2022, background): “, the case in the variational quantum eigensolver (VQE) [462] for theoretical chemistry [354], high energy physics [343] or computationally hard problems in graph theory [211].”
Quantum computing with neutral atoms (2020, background): “Interestingly, the physical interactions encoded in the Hamiltonian constrain the dynamics to only explore independent sets of the graph under study, then leading to an efficient search in the set of possible solutions [72, 54], as illustrated in Fig.”
Challenges and opportunities in quantum optimization (2023, unknown): “The problems chosen should be sufficiently hard for state-of-the-art classical solvers to leave a margin for quantum methods, but”
Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices (2018, methodology): “[45] for an implementation scheme of MIS with a platform of neutral atoms interacting via Rydberg excitations.”