CoChat
Sign Up
PreprintCited by 35Quantum Computing Algorithms and ArchitectureCold Atom Physics and Bose-Einstein CondensatesQuantum Information and Cryptography

Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays

Open access
Pichler, Hannes, Wang, Sheng-Tao, Zhou, Leo, Choi, Soonwon, Lukin, Mikhail D.·2018·arXiv
DOI 10.48550/arxiv.1808.10816arXiv 1808.10816
Open this paper in CoChat — free accountOpen PDF

Abstract

We describe and analyze an architecture for quantum optimization to solve maximum independent set (MIS) problems using neutral atom arrays trapped in optical tweezers. Optimizing independent sets is one of the paradigmatic, NP-hard problems in computer science. Our approach is based on coherent manipulation of atom arrays via the excitation into Rydberg atomic states. Specifically, we show that solutions of MIS problems can be efficiently encoded in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg blockade mechanism. By studying the performance of leading classical algorithms, we identify parameter regimes, where computationally hard instances can be tested using near-term experimental systems. Practical implementations of both quantum annealing and variational quantum optimization algorithms beyond the adiabatic principle are discussed.

Integrity signals

Registry

DataCite · 10.48550/arxiv.1808.10816

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

  • Several approaches exist to overcome these challenges, such as the stroboscopic scheme or optimising the locations of the atoms.

    “several approaches exist to overcome this challenges such as the stroboscopic scheme proposed in [96] or optimising the locations of the atoms which also influences the strength of the interaction.”

    From Neutral atom quantum computing hardware: performance and end-user perspective (2023) · cites this paper as [96]

  • Several algorithmic classes can be used to solve the MIS on a neutral atom platform, such as QAOA, QAA, or variational quantum simulation.

    “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 [96]

Cited by

Sorted by citations

Authors
Pichler, H., Wang, S.-T., Zhou, L., Choi, S., & Lukin, M. D.
Affiliations
Harvard University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2018
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1808.10816
arXiv
1808.10816
OpenAlex
W4299393113
Cited by
35
References
0
Citations by year
2026: 1 · 2025: 3 · 2024: 4 · 2023: 4 · 2022: 5 · 2021: 7 · 2020: 5 · 2019: 6
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation
  • Smithsonian Institution
  • U.S. Department of Energy
  • Harvard University
  • Adolph C. and Mary Sprague Miller Institute for Basic Research in Science, University of California Berkeley
  • Smithsonian Astrophysical Observatory
  • Multidisciplinary University Research Initiative
  • Center for Ultracold Atoms, Massachusetts Institute of Technology
  • FAS Division of Science, Harvard University
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 › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
maximum independent set, Rydberg atom arrays, optical tweezers, Rydberg blockade, quantum optimization, quantum annealing, variational quantum algorithms, NP-hard problems, neutral atom quantum computing

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