CoChat
Sign Up
Cited by 32Quantum Computing Algorithms and ArchitectureProtein Structure and DynamicsQuantum many-body systems

Peptide conformational sampling using the Quantum Approximate Optimization Algorithm

Open access
Boulebnane, Sami, Lucas, Xavier, Meyder, Agnes, Adaszewski, Stanislaw, Montanaro, Ashley·2023·npj Quantum Information
DOI 10.1038/s41534-023-00733-5
Open this paper in CoChat — free accountOpen PDF

Abstract

Protein folding has attracted considerable research effort in biochemistry in recent decades. In this work, we explore the potential of quantum computing to solve a simplified version of protein folding. More precisely, we numerically investigate the performance of the Quantum Approximate Optimization Algorithm (QAOA) in sampling low-energy conformations of short peptides. We start by benchmarking the algorithm on an even simpler problem: sampling self-avoiding walks. Motivated by promising results, we then apply the algorithm to a more complete version of protein folding, including a simplified physical potential. In this case, we find less promising results: deep quantum circuits are required to achieve accurate results, and the performance of QAOA can be matched by random sampling up to a small overhead. Overall, these results cast serious doubt on the ability of QAOA to address the protein folding problem in the near term, even in an extremely simplified setting.

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.1038/s41534-023-00733-5

Cites

55 of 55 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?

  • Little is known about QAOA's potential to provide a scaling advantage over classical solvers.

    “While QAOA has been studied extensively (11–14), little is known about its potential to provide a scaling advantage over classical solvers.”

    From Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem (2024) · cites this paper as [13]

  • In a recent numerical study of random 8-SAT with N ≤ 20 variables, the TTS of QAOA with fixed parameters and constant depth grows as 1.23^N.

    “A recent numerical study (13) of random 8-SAT with N ≤ 20 variables has shown that the time to solution (TTS) of QAOA with fixed parameters and constant depth grows as 1.23N.”

    From Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem (2024) · cites this paper as [13]

    The quantum approximate optimization algorithm section reports fixed-depth QAOA results for self-avoiding walks, not random 8-SAT. Searches for 8-SAT, time to solution, and the 1.23^N scaling found no passage addressing the attributed result; the paper gives no page numbers in our copy. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

  • When QAOA is combined with amplitude amplification, the quantum TTS for random 8-SAT grows as 1.11^N.

    “When QAOA is combined with amplitude amplification, the quantum TTS grows as 1.11N (13), whereas the best classical heuristic has TTS that grows as 1.25N (13).”

    From Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem (2024) · cites this paper as [13]

    In “The quantum approximate optimization algorithm” (page unavailable), the paper compares QAOA with amplitude amplification for self-avoiding walks; it does not report their combined time to solution. Searches for random 8-SAT and the 1.11^N and 1.25^N scaling figures found no passage addressing those claims. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

  • The best classical heuristic for random 8-SAT has TTS that grows as 1.25^N.

    “When QAOA is combined with amplitude amplification, the quantum TTS grows as 1.11N (13), whereas the best classical heuristic has TTS that grows as 1.25N (13).”

    From Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem (2024) · cites this paper as [13]

    The Introduction and the section ‘The quantum approximate optimization algorithm’ discuss peptide conformations, self-avoiding walks, and comparisons with random sampling and amplitude amplification; the indexed passages provide no page numbers. Searches for random 8-SAT, classical-heuristic time to solution, and 1.25^N found no passage addressing the claimed scaling. (LLM, conf=0.76)

    Experimental — accuracy not yet measured

  • Boulebnane and Montanaro rigorously show that, for random k-SAT, the runtime of constant-depth QAOA grows exponentially with N at any fixed p, with the scaling exponent depending on p.

    “Boulebnane and Montanaro (13) rigorously show that, for random k-SAT, the runtime of constant-depth QAOA grows exponentially with N at any fixed p, with the scaling exponent depending on p.”

    From Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem (2024) · cites this paper as [13]

    The Introduction reports numerical results for QAOA sampling self-avoiding walks, and the Fig. 3 caption gives exponential fits for that sampling probability at several depths. Neither passage addresses random k-SAT or rigorously establishes its QAOA runtime scaling (searched: random k-SAT, satisfiability, rigorous runtime proof). (LLM, conf=0.77)

    Experimental — accuracy not yet measured

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

1 retracted

Flagged first, then by citations

Research works printed but not linked: 3

  1. Reiher, W. E. Theoretical Studies of Hydrogen Bonding. Ph.D. thesis, Harvard Uni- versity (1985).
  2. Brandao, F. G. S. L., Broughton, M., Farhi, E., Gutmann, S. & Neven, H. For fixed control parameters the quantum approximate optimization algorithm's objective function value concentrates for typical instances. Preprint at https://arxiv.org/abs/ 1812.04170 (2018).
  3. Yao, J., Bukov, M. & Lin, L. Policy gradient based quantum approximate optimi- zation algorithm. In Proceedings of The First Mathematical and Scientific Machine Learning Conference (eds Lu, J. & Ward, R.) Vol. 107 of Proceedings of Machine Learning Research, 605-634 (PMLR, Princeton University, 2020).

Cited by

Sorted by citations

Related

Authors
Boulebnane, S., Lucas, X., Meyder, A., Adaszewski, S., & Montanaro, A.
Affiliations
  • Phasecraft Ltd. (United Kingdom) (GB)
  • F. Hoffmann-La Roche AG (CH)
  • University of Bristol (GB)
Corresponding author
Montanaro, Ashley
ORCID
Venue
npj Quantum Information
Publisher
Springer Science and Business Media LLC
Published
2023-07-17
Volume
9
Issue
1
ISSN
2056-6387 (ISSN-L)
DOI
10.1038/s41534-023-00733-5
OpenAlex
W4384499003
Cited by
32
References
55
Citations by year
2026: 8 · 2025: 11 · 2024: 7 · 2023: 6
FWCI
3.02
Type
journal article
Language
en
Open access
Licence
Locations
  • npj Quantum Information (publishedVersion, cc-by)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • Bristol Research (University of Bristol) (submittedVersion, cc-by)
Funders
  • European Commission (HORIZON2020, 817581)
  • Engineering and Physical Sciences Research Council (EP/S021582/1, EP/S005021/1)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Protein Structure and Dynamics
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
quantum approximate optimization algorithm, protein folding, peptide conformational sampling, self-avoiding walks, quantum computing, low-energy conformations, quantum circuit depth, random sampling comparison

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