CoChat
Sign Up
Cited by 39Quantum Computing Algorithms and ArchitectureQuantum many-body systemsQuantum Information and Cryptography

Quantum adiabatic algorithm design using reinforcement learning

Open access
Lin, Jian, Lai, Zhong Yuan, Li, Xiaopeng·2020·Physical Review A
DOI 10.1103/physreva.101.052327
Open this paper in CoChat — free accountOpen PDF

Abstract

Quantum algorithm design plays a crucial role in exploiting the computational advantage of quantum devices. Here we develop a deep-reinforcement-learning based approach for quantum adiabatic algorithm design. Our approach is generically applicable to a class of problems with solution hard-to-find but easy-to-verify, e.g., searching and NP-complete problems. We benchmark this approach in Grover-search and 3-SAT problems, and find that the adiabatic algorithm obtained by our RL approach leads to significant improvement in the resultant success probability. In application to Grover search, our RL design automatically produces an adiabatic quantum algorithm that has the quadratic speedup. We find for all our studied cases that quantitatively the RL-designed algorithm has a better performance compared to the analytically constructed nonlinear Hamiltonian path when the encoding Hamiltonian is solvable, and that this RL-design approach remains applicable even when the nonlinear Hamiltonian path is not analytically available. In 3-SAT we find RL design has fascinating transferability---the adiabatic algorithm obtained by training on a specific choice of clause number leads to better performance consistently over the linear algorithm on different clause numbers. These findings suggest the applicability of reinforcement learning for automated quantum adiabatic algorithm design. Further considering the established complexity equivalence of circuit and adiabatic quantum algorithms, we expect the RL-designed adiabatic algorithm to inspire novel circuit algorithms as well. Our approach is potentially applicable to different quantum hardware from trapped ions and optical lattices to superconducting-qubit devices.

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

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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

Integrity signals

Registry

Crossref · 10.1103/physreva.101.052327

Cites

36 of 36 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

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

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

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?

  • Architecture search approaches that adapt the ansatz of a variational approach may take an existing ansatz as a starting point or be more generally created.

    “Likewise, architecture search approaches that adapt the ansatz of the variational approach may take an existing ansatz as a starting point [86, 89, 155] or be more generally created [88, 96, 97, 151, 152].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [88]

    The Introduction (p. 2) describes reinforcement learning that automatically designs a quantum adiabatic algorithm by finding a Hamiltonian path, supporting the general idea of automated design. But the cited work does not describe architecture search that creates or adapts the ansatz of a variational approach; its search object is an adiabatic path, as specified in §A (p. 2). (LLM, conf=0.82)

    Experimental — accuracy not yet measured

  • Highly problem-specific ansätze to VQAs, not based on standard methods such as QAOA or VQE, and their effect on performance and resulting energy landscapes have been studied.

    “Highly problem-specific ansÃďtze to VQAs, which are not based on standard methods such as QAOA or VQE, and their effect on performance and resulting energy landscapes have been studied [83, 88, 151, 152].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [88]

    The optimization-problem section (p. 2) describes a problem-dependent, parameterized Hamiltonian path, and the introduction (p. 2) reports its effect on algorithm performance. But the paper studies reinforcement-learned adiabatic algorithms, not VQA ansätze; its energy-spectrum analysis (p. 5) does not establish a claim about VQA energy landscapes. (LLM, conf=0.82)

    Experimental — accuracy not yet measured

  • Machine learning techniques have been applied for program generation and architecture search.

    “Besides finding reusable parameters and optimizing parameters, machine learning techniques have been applied for ansatz search purposes, e.g., for finding mixer Hamiltonians for the Quantum Alternating Operator Ansatz [114], and for program generation and architecture search [88, 97, 151, 152].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [88]

    The Introduction (pp. 1–2) describes using reinforcement learning to design a quantum adiabatic algorithm by searching for an optimal Hamiltonian path, supporting automated algorithm design as an example. The paper does not describe generating programs or searching program or circuit architectures; its search is over paths for fixed Hamiltonians (Section II.A, p. 2). (LLM, conf=0.84)

    Experimental — accuracy not yet measured

  • Adapted annealing schedules, reverse annealing, and spatially inhomogeneous driving represent possible adaptations to the annealing procedure in QA.

    “In this regard, adapted annealing schedules [27, 88], reverse annealing [62], as well as spatially inhomogeneous driving [136] represent according possible adaptations.”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [88]

  • Within QA, machine learning has been utilized to identify optimized annealing schedules with reinforcement learning.

    “Within QA, machine learning has been utilized to identify optimized annealing schedules with reinforcement learning [88] and a combination of Monte Carlo Tree Search with neural nets [27].”

    From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [88]

Self-check

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

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

Cites

Flagged first, then by citations

Research works printed but not linked: 4

  1. [15]M. Gong, M.-C. Chen, Y. Zheng, S. Wang, C. Zha, H. Deng, Z. Yan, H. Rong, Y. Wu, S. Li, et al., arXiv preprint arXiv:1811.02292 (2018). · arXiv
  2. [18]H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y.-M. He, X. Jiang, L. You, Z. Wang, et al., Physical review letters 123 , 250503 (2019).
  3. [38]M. Jarret, B. Lackey, A. Liu, and K. Wan, arXiv e-prints arXiv:1810.04686 (2018), 1810.04686. · arXiv
  4. [39]M. Slutskii, T. Albash, L. Barash, and I. Hen, arXiv eprints arXiv:1904.04420 (2019), 1904.04420. · arXiv

Cited by

Sorted by citations

  • Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study

    Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works

    “…[51], [75], [76, 99], [141], [143], [146] Measurement [122], [125] Grover-search [52], [118] Other gate-based approaches [15], [16], [24], [94] Hamiltonians [62, 111, 136], [136] Space [136] Time [27], [62, 88] Other approaches [19, 63] sensitivity of QAOA to initial parameter settings [137].”
    BackgroundMethodInfluential

Related

Authors
Lin, J., Lai, Z. Y., & Li, X.
Affiliations
Fudan University (CN)
ORCID
Venue
Physical Review A
Publisher
American Physical Society (APS)
Published
2020-05-18
Volume
101
Issue
5
ISSN
  • 0556-2791 (ISSN-L)
  • 2469-9926
  • 2469-9934
DOI
10.1103/physreva.101.052327
OpenAlex
W3022968469
Cited by
39
References
36
Citations by year
2026: 5 · 2025: 6 · 2024: 1 · 2023: 6 · 2022: 9 · 2021: 9 · 2020: 3
FWCI
2.65
Type
journal article
Language
en
Open access
Licence
link.aps.org/licenses/aps-default-license (vor)
Locations
  • Physical Review A (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Basic Research Program of China (2017YFA0304204)
  • National Natural Science Foundation of China (11774067, 11934002)
  • Natural Science Foundation of Shanghai (19ZR1471500)
  • Science and Technology Commission of Shanghai Municipality (2019SHZDZX04)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
deep reinforcement learning, Grover's algorithm, 3-SAT, nonlinear Hamiltonian, transferability, NP-complete problems, quadratic speedup

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