View in EDS HTML Full Text PDF Full Text

Quantum optimization of maximum independent set using Rydberg atom arrays.

Saved in:
Bibliographic Details
Title: Quantum optimization of maximum independent set using Rydberg atom arrays.
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.
Source: Science (pre-March 2025). 6/10/2022, Vol. 376 Issue 6598, p1209-1215. 7p. 5 Color Photographs.
Subjects: Rydberg states, Quantum information theory, Quantum information science, Algorithms, Independent sets
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. [ABSTRACT FROM AUTHOR]
Copyright of Science (pre-March 2025) is the property of American Association for the Advancement of Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Psychology and Behavioral Sciences Collection
Full text is not displayed to guests.
FullText Links:
  – Type: pdflink
Text:
  Availability: 1
Header DbId: pbh
DbLabel: Psychology and Behavioral Sciences Collection
An: 157349152
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Quantum optimization of maximum independent set using Rydberg atom arrays.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Ebadi%2C+S%2E%22">Ebadi, S.</searchLink><br /><searchLink fieldCode="AR" term="%22Keesling%2C+A%2E%22">Keesling, A.</searchLink><br /><searchLink fieldCode="AR" term="%22Cain%2C+M%2E%22">Cain, M.</searchLink><br /><searchLink fieldCode="AR" term="%22Wang%2C+T%2E+T%2E%22">Wang, T. T.</searchLink><br /><searchLink fieldCode="AR" term="%22Levine%2C+H%2E%22">Levine, H.</searchLink><br /><searchLink fieldCode="AR" term="%22Bluvstein%2C+D%2E%22">Bluvstein, D.</searchLink><br /><searchLink fieldCode="AR" term="%22Semeghini%2C+G%2E%22">Semeghini, G.</searchLink><br /><searchLink fieldCode="AR" term="%22Omran%2C+A%2E%22">Omran, A.</searchLink><br /><searchLink fieldCode="AR" term="%22Liu%2C+J%2E-G%2E%22">Liu, J.-G.</searchLink><br /><searchLink fieldCode="AR" term="%22Samajdar%2C+R%2E%22">Samajdar, R.</searchLink><br /><searchLink fieldCode="AR" term="%22Luo%2C+X%2E-Z%2E%22">Luo, X.-Z.</searchLink><br /><searchLink fieldCode="AR" term="%22Nash%2C+B%2E%22">Nash, B.</searchLink><br /><searchLink fieldCode="AR" term="%22Gao%2C+X%2E%22">Gao, X.</searchLink><br /><searchLink fieldCode="AR" term="%22Barak%2C+B%2E%22">Barak, B.</searchLink><br /><searchLink fieldCode="AR" term="%22Farhi%2C+E%2E%22">Farhi, E.</searchLink><br /><searchLink fieldCode="AR" term="%22Sachdev%2C+S%2E%22">Sachdev, S.</searchLink><br /><searchLink fieldCode="AR" term="%22Gemelke%2C+N%2E%22">Gemelke, N.</searchLink><br /><searchLink fieldCode="AR" term="%22Zhou%2C+L%2E%22">Zhou, L.</searchLink><br /><searchLink fieldCode="AR" term="%22Choi%2C+S%2E%22">Choi, S.</searchLink><br /><searchLink fieldCode="AR" term="%22Pichler%2C+H%2E%22">Pichler, H.</searchLink>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Science+%28pre-March+2025%29%22">Science (pre-March 2025)</searchLink>. 6/10/2022, Vol. 376 Issue 6598, p1209-1215. 7p. 5 Color Photographs.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Rydberg+states%22">Rydberg states</searchLink><br /><searchLink fieldCode="DE" term="%22Quantum+information+theory%22">Quantum information theory</searchLink><br /><searchLink fieldCode="DE" term="%22Quantum+information+science%22">Quantum information science</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Independent+sets%22">Independent sets</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Science (pre-March 2025) is the property of American Association for the Advancement of Science and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=pbh&AN=157349152
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1126/science.abo6587
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 7
        StartPage: 1209
    Subjects:
      – SubjectFull: Rydberg states
        Type: general
      – SubjectFull: Quantum information theory
        Type: general
      – SubjectFull: Quantum information science
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Independent sets
        Type: general
    Titles:
      – TitleFull: Quantum optimization of maximum independent set using Rydberg atom arrays.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Ebadi, S.
      – PersonEntity:
          Name:
            NameFull: Keesling, A.
      – PersonEntity:
          Name:
            NameFull: Cain, M.
      – PersonEntity:
          Name:
            NameFull: Wang, T. T.
      – PersonEntity:
          Name:
            NameFull: Levine, H.
      – PersonEntity:
          Name:
            NameFull: Bluvstein, D.
      – PersonEntity:
          Name:
            NameFull: Semeghini, G.
      – PersonEntity:
          Name:
            NameFull: Omran, A.
      – PersonEntity:
          Name:
            NameFull: Liu, J.-G.
      – PersonEntity:
          Name:
            NameFull: Samajdar, R.
      – PersonEntity:
          Name:
            NameFull: Luo, X.-Z.
      – PersonEntity:
          Name:
            NameFull: Nash, B.
      – PersonEntity:
          Name:
            NameFull: Gao, X.
      – PersonEntity:
          Name:
            NameFull: Barak, B.
      – PersonEntity:
          Name:
            NameFull: Farhi, E.
      – PersonEntity:
          Name:
            NameFull: Sachdev, S.
      – PersonEntity:
          Name:
            NameFull: Gemelke, N.
      – PersonEntity:
          Name:
            NameFull: Zhou, L.
      – PersonEntity:
          Name:
            NameFull: Choi, S.
      – PersonEntity:
          Name:
            NameFull: Pichler, H.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 10
              M: 06
              Text: 6/10/2022
              Type: published
              Y: 2022
          Identifiers:
            – Type: issn-print
              Value: 00368075
          Numbering:
            – Type: volume
              Value: 376
            – Type: issue
              Value: 6598
          Titles:
            – TitleFull: Science (pre-March 2025)
              Type: main
ResultId 1