Student or educator? Sign up with your school email and get 6 months of Pro free.
CoChat

The DOI matches its Crossref record; 71 of the 71 references it cites were found in a registry or an index.

Quantum optimization of maximum independent set using Rydberg atom arrays

Open access

Abstract

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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1126/science.abo6587

Cites

71 of 71 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 18

  1. E. Farhi J. Goldstone S. Gutmann M. Sipser Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106 (2000). · arXiv
  2. E. Farhi J. Goldstone S. Gutmann A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 [quant-ph] (2014). · arXiv
  3. T. M. Graham et al . Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer. arXiv:2112.14589 [quant-ph] (2022). · arXiv
  4. E. Farhi D. Gamarnik S. Gutmann The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. arXiv:2004.09002 [quant-ph] (2020). · arXiv
  5. J.-G. Liu X. Gao M. Cain M. D. Lukin S.-T. Wang Computing solution space properties of combinatorial optimization problems via generic tensor networks. arxiv:2205.03718 [cond-mat-stat-mech] (2022). · arXiv
  6. M. Szegedy in 45th Annual IEEE Symposium on Foundations of Computer Science (2004) pp. 32–41.
  7. E. Crosson E. Farhi C. Y.-Y. Lin H.-H. Lin P. Shor Different Strategies for Optimization Using the Quantum Adiabatic Algorithm. arXiv:1401.7320 [quant-ph] (2014). · arXiv
  8. D. Gamarnik I. Zadik The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property. arXiv:1904.07174 [math.ST] (2019). · arXiv
  9. D. Bluvstein H. Levine G. Semeghini T. T. Wang S. Ebadi M. Kalinowski A. Keesling N. Maskara H. Pichler M. Greiner V. Vuletić M. D. Lukin A quantum processor based on coherent transport of entangled atom arrays. Nature 604 451–456 (2022). 10.1038/s41586-022-04592-635444318 · DOI · Paper page
  10. M. Fishman S. R. White E. M. Stoudenmire The ITensor Software Library for Tensor Network Calculations. arXiv:2007.14822 [cs.MS] (2020). · arXiv
  11. M. Archimi et al . Measurements of blackbody radiation-induced transition rates between high-lying S P and D Rydberg leve l . arXiv:2111.15333 [physics.atom-ph] (2021). · arXiv
  12. D. P. Kingma J. Ba Adam: A Method for Stochastic Optimization. arXiv:1412.6980 [cs.LG] (2017). · arXiv
  13. J. Duchi, E. Hazan, Y. Singer, J. Mach. Learn. Res. 12, 2121–2159 (2011).
  14. L. Luo Y. Xiong Y. Liu X. Sun Adaptive Gradient Methods with Dynamic Bound of Learning Rate. arXiv:1902.09843 [cs.LG] (2019). · arXiv
  15. J. Biamonte V. Bergholm Tensor Networks in a Nutshell. arXiv:1708.00006 [quant-ph] (2017). · arXiv
  16. F. Pan P. Zhang Simulating the Sycamore quantum supremacy circuits. arXiv:2103.03074 [quant-ph] (2021). · arXiv
  17. G. Kalachev P. Panteleev M.-H. Yung Recursive Multi-Tensor Contraction for XEB Verification of Quantum Circuits. arXiv:2108.05665 [quant-ph] (2021). · arXiv
  18. 10.1103/PhysRevLett.69.2863 · DOI · Paper page

Cited by

See all 430

Metadata

Authors
Ebadi, S., Keesling, A., Cain, M., Wang, T. T., Levine, H., Bluvstein, D., Semeghini, G., Omran, A., Liu, J.-G., Samajdar, R., Luo, X.-Z., Nash, B., Gao, X., Barak, B., Farhi, E., Sachdev, S., Gemelke, N., Zhou, L., Choi, S., Pichler, H., Wang, S.-T., Greiner, M., Vuletić, V., & Lukin, M. D.
Affiliations
  • Harvard University (US)
  • University of Waterloo (CA)
  • Google (United States) (US)
  • Department of Physics, Harvard University, Cambridge, MA 02138, USA.
  • QuEra Computing (United States) (US)
  • California Institute of Technology (US)
  • Massachusetts Institute of Technology (US)
  • Austrian Academy of Sciences (AT)
Corresponding author
  • Ebadi, S.
  • Keesling, A.
  • Cain, M.
  • Greiner, M.
  • Vuletić, V.
  • Lukin, M. D.
Venue
Science
Published
2022-06-10
Volume
376
Issue
6598
Pages
1209-1215
ISSN
  • 0036-8075 (ISSN-L)
  • 1095-9203
OpenAlex
W2889426946
Cited by
430
References
71
Citations by year
2026: 71 · 2025: 119 · 2024: 101 · 2023: 91 · 2022: 28
FWCI
27.78
Type
journal article
Language
en
Open access
Locations
  • Science (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • CaltechAUTHORS (California Institute of Technology) (submittedVersion)
  • Zenodo (CERN European Organization for Nuclear Research) (submittedVersion, cc-by)
  • arXiv (Cornell University)
  • Zenodo (CERN European Organization for Nuclear Research) (cc-by)
Funders
U.S. Department of Energy (DESC0021013, DESC0020347, DESC0019030, DESC0022199)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Cold Atom Physics and Bose-Einstein Condensates
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
Keywords
maximum independent set, Rydberg atom arrays, Rydberg blockade, quantum optimization, variational quantum algorithms, quantum advantage, local minima

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.