English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization

Schiffer, B., Wild, D., Maskara, N., Cain, M., Lukin, M. D., & Samajdar, R. (2024). Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization. Physical Review Research, 6: 013271. doi:10.1103/PhysRevResearch.6.013271.

Item is

Files

show Files
hide Files
:
2306.13131.pdf (Preprint), 3MB
Name:
2306.13131.pdf
Description:
-
OA-Status:
Green
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-
:
6507.pdf (Publisher version), 2MB
Name:
6507.pdf
Description:
-
OA-Status:
Gold
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Schiffer, Benjamin1, 2, Author           
Wild, Dominik1, 2, Author           
Maskara, Nishad, Author
Cain, Madelyn, Author
Lukin, Mikhail D., Author
Samajdar, Rhine, Author
Affiliations:
1Theory, Max Planck Institute of Quantum Optics, Max Planck Society, ou_1445571              
2MCQST - Munich Center for Quantum Science and Technology, External Organizations, Schellingstraße 4, 80799 München, DE, ou_3330166              

Content

show
hide
Free keywords: Condensed Matter, Strongly Correlated Electrons, cond-mat.str-el
 Abstract: Classical optimization problems can be solved by adiabatically preparing the
ground state of a quantum Hamiltonian that encodes the problem. The performance
of this approach is determined by the smallest gap encountered during the
evolution. Here, we consider the maximum independent set problem, which can be
efficiently encoded in the Hamiltonian describing a Rydberg atom array. We
present a general construction of instances of the problem for which the
minimum gap decays superexponentially with system size, implying a
superexponentially large time to solution via adiabatic evolution. The small
gap arises from locally independent choices, which cause the system to
initially evolve and localize into a configuration far from the solution in
terms of Hamming distance. We investigate remedies to this problem.
Specifically, we show that quantum quenches in these models can exhibit
signatures of quantum many-body scars, which in turn, can circumvent the
superexponential gaps. By quenching from a suboptimal configuration, states
with a larger ground state overlap can be prepared, illustrating the utility of
quantum quenches as an algorithmic tool.

Details

show
hide
Language(s): eng - English
 Dates: 2023-06-222024-01-182024-03-122024-03
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: arXiv: 2306.13131v1
DOI: 10.1103/PhysRevResearch.6.013271
Other: 6507
 Degree: -

Event

show

Legal Case

show

Project information

show hide
Project name : FET Open SuperQuLAN
Grant ID : 899354
Funding program : European Union’s Horizon 2020 research and innovation program
Funding organization : European Commission (EC)
Project name : Marie Sklodowska-Curie Grant
Grant ID : 101023276
Funding program : European Union’s Horizon 2020 research and innovation programme
Funding organization : European Commission (EC)
Project name : -
Grant ID : -
Funding program : Hightech Agenda Bayern Plus
Funding organization : Munich Quantum Valley, which is supported by the Bavarian state government

Source 1

show
hide
Title: Physical Review Research
  Abbreviation : Phys. Rev. Research
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: College Park, Maryland, United States : American Physical Society (APS)
Pages: - Volume / Issue: 6 Sequence Number: 013271 Start / End Page: - Identifier: ISSN: 2643-1564
CoNE: https://pure.mpg.de/cone/journals/resource/2643-1564