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 accessAbstract
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.
Integrity signals
Registry
Cites
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.
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?
The cited source says what the claim attributes to it.
In the citing paper
“Lastly, there have been very large-scale demonstrations of QAOA on analog quantum simulators.”
From Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer (2022) · cites this paper as [15]
The cited source says what the claim attributes to it.
In the citing paper
“A specific class of problems that has been implemented in a hardware-efficient way is the Maximum independent set (MIS) problem on unit disc graphs, since the independent set constraint is natively fulfilled by the Rydberg blockade mechanism [95].”
From Neutral atom quantum computing hardware: performance and end-user perspective (2023) · cites this paper as [95]
The cited source says what the claim attributes to it.
In the citing paper
“There are several algorithmic classes which can be used to solve the MIS on a neutral atom platform, such as the Quantum Approximate Optimisation Algorithm (QAOA), quantum annealing algorithms (QAA) [96], or variational quantum simulation as described in [95,97].”
From Neutral atom quantum computing hardware: performance and end-user perspective (2023) · cites this paper as [95]
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
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
(1979) · Cited by 43,841
Equation of State Calculations by Fast Computing Machines
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953) · The Journal of Chemical Physics · doi:10.1063/1.1699114 · Cited by 37,192
A Simplex Method for Function Minimization
Nelder, J. A., & Mead, R. (1965) · The Computer Journal · doi:10.1093/comjnl/7.4.308 · Cited by 28,905
Monte Carlo sampling methods using Markov chains and their applications.
Hastings, W. K. (1970) · Biometrika · doi:10.1093/biomet/57.1.97 · Cited by 15,195
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Density matrix formulation for quantum renormalization groups
White, S. R. (1992) · Physical Review Letters · doi:10.1103/physrevlett.69.2863 · Cited by 7,702
Electromagnetically induced transparency: Optics in coherent media
Fleischhauer, M., Imamoglu, A., & Marangos, J. P. (2005) · Reviews of Modern Physics · doi:10.1103/revmodphys.77.633 · Cited by 5,189
The density-matrix renormalization group in the age of matrix product states
Schollwöck, U. (2011) · Annals of Physics · doi:10.1016/j.aop.2010.09.012 · Cited by 4,818
Density-matrix algorithms for quantum renormalization groups
White, S. R. (1993) · Physical Review B · doi:10.1103/physrevb.48.10345 · Cited by 3,244
Research works printed but not linked: 18
- E. Farhi J. Goldstone S. Gutmann M. Sipser Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106 (2000). · arXiv
- E. Farhi J. Goldstone S. Gutmann A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 [quant-ph] (2014). · arXiv
- 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
- 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
- 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
- M. Szegedy in 45th Annual IEEE Symposium on Foundations of Computer Science (2004) pp. 32–41.
- 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
- 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
- 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
- M. Fishman S. R. White E. M. Stoudenmire The ITensor Software Library for Tensor Network Calculations. arXiv:2007.14822 [cs.MS] (2020). · arXiv
- 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
- D. P. Kingma J. Ba Adam: A Method for Stochastic Optimization. arXiv:1412.6980 [cs.LG] (2017). · arXiv
- J. Duchi, E. Hazan, Y. Singer, J. Mach. Learn. Res. 12, 2121–2159 (2011).
- L. Luo Y. Xiong Y. Liu X. Sun Adaptive Gradient Methods with Dynamic Bound of Learning Rate. arXiv:1902.09843 [cs.LG] (2019). · arXiv
- J. Biamonte V. Bergholm Tensor Networks in a Nutshell. arXiv:1708.00006 [quant-ph] (2017). · arXiv
- F. Pan P. Zhang Simulating the Sycamore quantum supremacy circuits. arXiv:2103.03074 [quant-ph] (2021). · arXiv
- G. Kalachev P. Panteleev M.-H. Yung Recursive Multi-Tensor Contraction for XEB Verification of Quantum Circuits. arXiv:2108.05665 [quant-ph] (2021). · arXiv
- 10.1103/PhysRevLett.69.2863 · DOI · Paper page
Cited by
Quantum Kibble–Zurek mechanism and critical dynamics on a programmable Rydberg simulator
Keesling, A., Omran, A., Levine, H., Bernien, H., Pichler, H., Choi, S., Samajdar, R., Schwartz, S., Silvi, P., Sachdev, S., et al. (2019) · Nature · doi:10.1038/s41586-019-1070-1 · Cited by 534
Self-citationA review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 408
Koch, C. P., Boscain, U., Calarco, T., Dirr, G., Filipp, S., Glaser, S. J., Kosloff, R., Montangero, S., Schulte-Herbrüggen, T., Sugny, D., et al. (2022) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-022-00138-x · Cited by 405
Quantum science with optical tweezer arrays of ultracold atoms and molecules
Kaufman, A. M., & Ni, K.-K. (2021) · Nature Physics · doi:10.1038/s41567-021-01357-2 · Cited by 374
Quantum annealing for industry applications: introduction and review
Yarkoni, S., Raponi, E., Bäck, T., & Schmitt, S. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac8c54 · Cited by 341
Quantum critical dynamics in a 5,000-qubit programmable spin glass
King, A. D., Raymond, J., Lanting, T., Harris, R., Zucca, A., Altomare, F., Berkley, A. J., Boothby, K., Ejtemaee, S., Enderud, C., et al. (2023) · Nature · doi:10.1038/s41586-023-05867-2 · Cited by 242
Challenges and opportunities in quantum optimization
Abbas, A., Ambainis, A., Augustino, B., Bärtschi, A., Buhrman, H., Coffrin, C., Cortiana, G., Dunjko, V., Egger, D. J., Elmegreen, B. G., et al. (2024) · Nature Reviews Physics · doi:10.1038/s42254-024-00770-9 · Cited by 201
“The problems chosen should be sufficiently hard for state-of-the-art classical solvers to leave a margin for quantum methods, but”
Beyond-classical computation in quantum simulation
King, A. D., Nocera, A., Rams, M. M., Dziarmaga, J., Wiersema, R., Bernoudy, W., Raymond, J., Kaushal, N., Heinsdorf, N., Harris, R., et al. (2025) · Science · doi:10.1126/science.ado6285 · Cited by 138
Neutral atom quantum computing hardware: performance and end-user perspective
Wintersperger, K., Dommert, F., Ehmer, T., Hoursanov, A., Klepsch, J., Mauerer, W., Reuber, G., Strohm, T., Yin, M., & Luber, S. (2023) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-023-00190-1 · Cited by 117
Optimization Applications as Quantum Performance Benchmarks
Lubinski, T., Coffrin, C., McGeoch, C., Sathe, P., Apanavicius, J., & Neira, D. E. B. (2023) · arXiv · doi:10.48550/arxiv.2302.02278 · Cited by 62
Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer
Niroula, P., Shaydulin, R., Yalovetzky, R., Minssen, P., Herman, D., Hu, S., & Pistoia, M. (2022) · Scientific Reports · doi:10.1038/s41598-022-20853-w · Cited by 59
Towards large-scale quantum optimization solvers with few qubits
Sciorilli, M., Borges, L., Patti, T. L., García-Martín, D., Camilo, G., Anandkumar, A., & Aolita, L. (2025) · Nature Communications · doi:10.1038/s41467-024-55346-z · Cited by 47
Dalyac, C., Henriet, L., Jeandel, E., Lechner, W., Perdrix, S., Porcheron, M., & Veshchezerova, M. (2021) · EPJ Quantum Technology · doi:10.1140/epjqt/s40507-021-00100-3 · Cited by 46
“3 MIS In this Section we present how to solve a MIS problem using a QAOA procedure on a neutral atom processor working in an analog mode [13, 43].”
BackgroundMethodInfluentialBias-field digitized counterdiabatic quantum optimization
Cadavid, A. G., Dalal, A., Simen, A., Solano, E., & Hegade, N. N. (2025) · Physical Review Research · doi:10.1103/physrevresearch.7.l022010 · Cited by 10
Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
Maciejewski, F. B., Biamonte, J., Hadfield, S., & Venturelli, D. (2025) · Quantum · doi:10.22331/q-2025-11-06-1906 · Cited by 10
Industry applications of neutral-atom quantum computing solving independent set problems
Wurtz, J., Lopes, P. L. S., Gorgulla, C., Gemelke, N., Keesling, A., & Wang, S. (2022) · arXiv · doi:10.48550/arxiv.2205.08500 · Cited by 8
Self-citation
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.
- ORCID
- 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
- green
- arxiv.org
- 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.