A Caltech Library Service

Quantum optimization of maximum independent set using Rydberg atom arrays

Ebadi, S. and Keesling, A. and Cain, M. and Wang, T. T. and Levine, H. and Bluvstein, D. and Semeghini, G. and Omran, A. and Liu, J.-G. and Samajdar, R. and Luo, X.-Z. and Nash, B. and Gao, X. and Barak, B. and Farhi, E. and Sachdev, S. and Gemelke, N. and Zhou, L. and Choi, S. and Pichler, H. and Wang, S.-T. and Greiner, M. and Vuletić, V. and Lukin, M. D. (2022) Quantum optimization of maximum independent set using Rydberg atom arrays. Science, 376 (6598). pp. 1209-1215. ISSN 0036-8075. doi:10.1126/science.abo6587.

[img] PDF - Submitted Version
See Usage Policy.

[img] PDF (Materials and Methods; Figs. S1 to S22; Table S1; References (57–87)) - Supplemental Material
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Ebadi, S.0000-0003-4146-3637
Keesling, A.0000-0003-3931-0949
Cain, M.0000-0002-5298-3112
Wang, T. T.0000-0003-3107-2579
Levine, H.0000-0001-8270-3233
Bluvstein, D.0000-0002-9934-9530
Semeghini, G.0000-0001-9071-2279
Omran, A.0000-0002-2253-0278
Liu, J.-G.0000-0003-1635-2679
Samajdar, R.0000-0001-5171-7798
Barak, B.0000-0002-4053-8927
Farhi, E.0000-0002-7309-8489
Sachdev, S.0000-0002-2432-7070
Gemelke, N.0000-0001-9911-4275
Zhou, L.0000-0001-7598-8621
Choi, S.0000-0002-1247-062X
Pichler, H.0000-0003-2144-536X
Wang, S.-T.0000-0003-1403-5901
Greiner, M.0000-0002-2935-2363
Vuletić, V.0000-0002-9786-0538
Lukin, M. D.0000-0002-8658-1007
Additional Information:© 2022 the authors, some rights reserved; exclusive licensee American Association for the Advancement of Science. No claim to original US government works. Submitted 17 February 2022; accepted 22 April 2022; Published online 5 May 2022. We thank I. Cirac, J. Cong, S. Evered, M. Kalinowski, M. Lin, T. Manovitz, M. Murphy, B. Schiffer, J. Singh, A. Sohrabizadeh, J. Tura, and D. Wild for illuminating discussions and feedback on the manuscript. We acknowledge financial support from the DARPA ONISQ program (grant no. W911NF2010021), the Center for Ultracold Atoms, the National Science Foundation, the Vannevar Bush Faculty Fellowship, the US Department of Energy [DE-SC0021013 and DOE Quantum Systems Accelerator Center (contract no. 7568717)], the Army Research Office MURI, QuEra Computing, and Amazon Web Services. M.C. acknowledges support from DOE CSG award fellowship (DE-SC0020347). H.L. acknowledges support from the National Defense Science and Engineering Graduate (NDSEG) fellowship. D.B. acknowledges support from the NSF Graduate Research Fellowship Program (grant DGE1745303) and The Fannie and John Hertz Foundation. G.S. acknowledges support from a fellowship from the Max Planck/Harvard Research Center for Quantum Optics. R.S. and S.S. were supported by the U.S. Department of Energy under grant DE-SC0019030. X.G. acknowledges support from a fellowship from the Max Planck/Harvard Research Center for Quantum Optics. B.B. acknowledges support from DARPA grant W911NF2010021, a Simons investigator fellowships, NSF grants CCF 1565264 and DMS-2134157, and DOE grant DE-SC0022199. H.P. acknowledges support by the Army Research Office (grant no. W911NF-21-1-0367). The DMRG calculations in this paper were performed using the ITensor package (54) and were run on the FASRC Odyssey cluster supported by the FAS Division of Science Research Computing Group at Harvard University. Author contributions: S.E., A.K., M.C., T.T.W., H.L., D.B., G.S., A.O., and J.-G. L. contributed to building the experimental setup, performing the measurements, and data analysis. M.C., J.-G. L., R. S., X.-Z. L., B. N., X. G., L. Z., S. C., H. P., and S.-T. W. contributed to theoretical analysis and interpretation. B. B., E. F., S. S., and N. G. contributed to interpretation of the observations and benchmarking studies. All authors discussed the results and contributed to the manuscript. All work was supervised by M.G., V.V., and M.D.L. Competing interests: N.G., M.G., V.V., and M.D.L. are cofounders and shareholders of QuEra Computing. A.K. is a shareholder and an executive at QuEra Computing. A.O. and S.-T.W. are shareholders of QuEra Computing. Some of the techniques and methods used in this work are included in pending patent applications filed by Harvard University (Patent application nos. PCT/US2018/042080 and PCT/US2019/049115). Data and materials availability: Code for classical tensor network algorithms for graph characterization is available at (35). Data and code are available on Zenodo (56).
Group:Walter Burke Institute for Theoretical Physics, AWS Center for Quantum Computing
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)W911NF2010021
Harvard-MIT Center for Ultracold AtomsUNSPECIFIED
Vannevar Bush FellowshipUNSPECIFIED
Department of Energy (DOE)DE-SC0021013
Quantum Systems Accelerator7568717
Army Research Office (ARO)UNSPECIFIED
Amazon Web ServicesUNSPECIFIED
Department of Energy (DOE)DE-SC0020347
National Defense Science and Engineering Graduate (NDSEG) FellowshipUNSPECIFIED
NSF Graduate Research FellowshipDGE-1745303
Fannie and John Hertz FoundationUNSPECIFIED
Max Planck/Harvard Research Center for Quantum OpticsUNSPECIFIED
Department of Energy (DOE)DE-SC0019030
Defense Advanced Research Projects Agency (DARPA)W911NF2010021
Simons FoundationUNSPECIFIED
Department of Energy (DOE)DE-SC0022199
Army Research Office (ARO)W911NF-21-1-0367
Issue or Number:6598
Record Number:CaltechAUTHORS:20220505-221358148
Persistent URL:
Official Citation:Quantum optimization of maximum independent set using Rydberg atom arrays. S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletic, M. D. Lukin. Science, 376 (6598); DOI: 10.1126/science.abo6587
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:114602
Deposited By: Tony Diaz
Deposited On:05 May 2022 22:48
Last Modified:28 Jun 2022 18:15

Repository Staff Only: item control page