pith. sign in

arxiv: 2508.10660 · v2 · submitted 2025-08-14 · 🪐 quant-ph

Exploring Quantum Annealing for Coarse-Grained Protein Folding

Timon Scheiber , Matthias Heller , Andreas Giebel This is my paper

Pith reviewed 2026-05-18 23:00 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum annealingprotein foldingcoarse-grained modelstetrahedral latticeinterleaved gridsembeddingsimulated annealingab initio models
0
0 comments X

The pith

Current quantum annealing hardware faces embedding challenges that restrict protein folding applications to proof-of-concept sizes, while exhibiting a scaling advantage over simulated annealing on embedded instances.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper investigates applying quantum annealing to coarse-grained protein folding by comparing several ab initio models and introducing a novel encoding for coordinate-based models on the tetrahedral lattice using interleaved grids. A sympathetic reader would care because the work tests whether quantum hardware can eventually address a hard biological optimization task that remains difficult for classical computers. The authors find large differences in how well the models perform, including one that produces unphysical configurations inside the set of feasible solutions. They determine that present quantum annealing devices cannot yet handle anything beyond small demonstration cases because of the difficulty of mapping the logical problem onto the hardware's physical qubits. A scaling benefit over an in-house simulated annealing implementation appears only when the comparison is made on the already-embedded problem versions.

Core claim

We compare several proposed ab initio protein folding models for quantum computers and introduce a novel encoding of coordinate based models on the tetrahedral lattice based on interleaved grids. Our findings reveal significant variations in model performance, with one model yielding unphysical configurations within the feasible solution space. We conclude that current quantum annealing hardware is not yet suited for tackling problems beyond a proof-of-concept size, primarily due to challenges in the embedding. Nonetheless, we observe a scaling advantage over our in-house simulated annealing implementation, which, however, is only noticeable when comparing performance on the embeddedproblems

What carries the argument

The novel encoding of coordinate-based models on the tetrahedral lattice using interleaved grids, which maps the protein folding problem into a form solvable by quantum annealing hardware.

Load-bearing premise

The scaling advantage observed only on embedded versions of the problems will persist or appear on the original unembedded protein-folding instances once hardware embedding capabilities improve.

What would settle it

Direct performance comparisons of quantum annealing and simulated annealing on the original unembedded protein folding instances using future hardware with lower embedding overhead would test whether the scaling advantage carries over.

Figures

Figures reproduced from arXiv: 2508.10660 by Andreas Giebel, Matthias Heller, Timon Scheiber.

Figure 1
Figure 1. Figure 1: Example of a 10 amino acid mini protein folded on two different lattices. (a) A two di [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Metrics for the model scaling. We show the required number of qubits when reducing [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Spin overlap distribution for sections of increasing sequence length of the 189 amino acid [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Embedding data of the considered sequence lengths for the different models. The data was [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Influence of the embedding on the spin overlap for the models on the tetrahedral grid for [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example of an unphysical ground state configuration obtained from the turn-based tetra [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: TTS scaling of the proposed models under simulated annealing. The data is taken over 100 [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: TTS scaling for the two tested quantum annealers: [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Left panel: Scaling comparison of Quantum annealing and simulated annealing. The blue [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Scaling difference for the sparse and dense encoding. While the dense encoding leads to [PITH_FULL_IMAGE:figures/full_fig_p021_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Scaling difference for the sparse and dense encoding. While the dense encoding leads to [PITH_FULL_IMAGE:figures/full_fig_p024_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Example image of the two lattices forming the tetrahedral grid. Even bead are placed on [PITH_FULL_IMAGE:figures/full_fig_p027_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Optimal cooling rate for the coordinate-based model on the tetrahedral grid for problem [PITH_FULL_IMAGE:figures/full_fig_p030_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: Optimal cooling rate for the coordinate-based models on the cartesian grid for problem [PITH_FULL_IMAGE:figures/full_fig_p030_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: Optimal cooling rate for the turn-based models for problem instances with varying amino [PITH_FULL_IMAGE:figures/full_fig_p030_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Embedding data for all models on the tetrahedral grid [PITH_FULL_IMAGE:figures/full_fig_p031_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Embedding data for all models on the Cartesian grid. The last data point for [PITH_FULL_IMAGE:figures/full_fig_p031_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Optimal anneal time to minimize the TTS for the D-Wave [PITH_FULL_IMAGE:figures/full_fig_p032_18.png] view at source ↗
read the original abstract

We explore the potential application of quantum annealing to address the protein structure problem. To this end, we compare several proposed ab initio protein folding models for quantum computers and analyze their scaling and performance for classical and quantum heuristics. Furthermore, we introduce a novel encoding of coordinate based models on the tetrahedral lattice, based on interleaved grids. Our findings reveal significant variations in model performance, with one model yielding unphysical configurations within the feasible solution space. Furthermore, we conclude that current quantum annealing hardware is not yet suited for tackling problems beyond a proof-of-concept size, primarily due to challenges in the embedding. Nonetheless, we observe a scaling advantage over our in-house simulated annealing implementation, which, however, is only noticeable when comparing performance on the embedded problems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript explores the application of quantum annealing to coarse-grained ab initio protein folding. It compares several proposed models, introduces a novel coordinate-based encoding on the tetrahedral lattice using interleaved grids, evaluates scaling and performance against classical heuristics including an in-house simulated annealing baseline, reports variations across models (including unphysical configurations in one case), and concludes that current QA hardware is limited to proof-of-concept sizes due to embedding overhead while observing a scaling advantage over SA that is noticeable only on the embedded problem instances.

Significance. If the comparative analysis and novel encoding hold up under scrutiny, the work usefully maps practical challenges of embedding protein-folding QUBOs onto current annealers and documents model-dependent solution quality. The explicit qualification that the scaling advantage appears only on embedded instances is a strength in transparency; extending this to falsifiable predictions about native instances would increase impact for the quantum optimization community.

major comments (2)
  1. [Abstract and Discussion] Abstract and Discussion: The headline observation of a scaling advantage is restricted to performance on embedded QUBO instances. Because embedding increases variable count and alters connectivity (and therefore changes the effective energy landscape relative to the original coordinate-based formulation), the manuscript should provide a direct comparison of solution quality or scaling between quantum runs on the embedded graph and a classical solver applied to the identical unembedded QUBO; without this, the claim that the advantage will persist or improve once embedding overhead decreases remains an untested extrapolation.
  2. [Model performance analysis] Model performance analysis: The attribution of unphysical configurations in one model to the encoding (rather than an artifact of the annealing schedule or hardware noise) is stated but not supported by an explicit control experiment, such as running the same unembedded formulation with the in-house SA baseline or a classical exact solver; this distinction is load-bearing for the conclusion that the issue is encoding-specific.
minor comments (2)
  1. [Methods] Clarify the precise definition and parameter settings of the in-house simulated annealing baseline so that the embedded-problem comparison can be reproduced.
  2. [Results] Add a short table or paragraph summarizing the variable count and embedding chain length growth for each model as a function of protein chain length.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed comments on our manuscript. We have revised the text to address the concerns raised while maintaining the integrity of our reported results and conclusions.

read point-by-point responses

  1. Referee: [Abstract and Discussion] Abstract and Discussion: The headline observation of a scaling advantage is restricted to performance on embedded QUBO instances. Because embedding increases variable count and alters connectivity (and therefore changes the effective energy landscape relative to the original coordinate-based formulation), the manuscript should provide a direct comparison of solution quality or scaling between quantum runs on the embedded graph and a classical solver applied to the identical unembedded QUBO; without this, the claim that the advantage will persist or improve once embedding overhead decreases remains an untested extrapolation.

    Authors: We agree that the reported scaling advantage is observed specifically when comparing quantum annealing results on the embedded instances against our in-house simulated annealing baseline applied to the same embedded QUBOs. This comparison is the relevant one for current hardware, as the annealer must solve the embedded problem. In the revised manuscript we have updated the Abstract and Discussion to remove any implication that the advantage will necessarily persist or improve with reduced embedding overhead. We now explicitly frame the observation as holding under present embedding constraints and note that testing persistence on native instances would require future hardware improvements. A full direct comparison with classical solvers on unembedded QUBOs for the larger instances studied here is computationally prohibitive, but we have added a brief remark on small-instance trends where such checks are feasible. revision: partial

  2. Referee: [Model performance analysis] Model performance analysis: The attribution of unphysical configurations in one model to the encoding (rather than an artifact of the annealing schedule or hardware noise) is stated but not supported by an explicit control experiment, such as running the same unembedded formulation with the in-house SA baseline or a classical exact solver; this distinction is load-bearing for the conclusion that the issue is encoding-specific.

    Authors: We thank the referee for pointing out the need for clearer support. The unphysical configurations satisfy the penalty terms of the QUBO (i.e., lie inside the feasible space defined by the encoding) yet fail basic geometric checks for valid protein folds; this is therefore a property of the model formulation itself. In the revised manuscript we have added an explicit statement clarifying that these configurations were identified via post-processing against physical validity criteria, independent of the optimization method used to obtain them. We have also noted that the same feasible-space definition applies to any solver operating on that QUBO, thereby reinforcing that the presence of such solutions is encoding-specific rather than an artifact of the quantum annealing schedule or hardware noise. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected; claims rest on empirical observations with external baseline

full rationale

The paper introduces a novel interleaved-grid encoding for tetrahedral-lattice protein models, runs quantum annealing and an in-house simulated annealing baseline on embedded QUBO instances, and reports observed scaling differences plus hardware limitations. No derivation chain reduces a claimed result to a self-definition, a fitted parameter renamed as a prediction, or a self-citation that renders the central empirical findings tautological. The comparison to the classical heuristic supplies an independent reference point, and all performance statements are explicitly scoped to the embedded instances with stated caveats about embedding overhead.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The work relies on standard assumptions of ab initio folding models and quantum annealing embeddings.

pith-pipeline@v0.9.0 · 5648 in / 1278 out tokens · 43211 ms · 2026-05-18T23:00:51.610012+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages · 4 internal anchors

  1. [1]

    A folding-docking-affinity framework for protein-ligand binding affinity prediction,

    M.-H. Wu, Z. Xie, and D. Zhi, “A folding-docking-affinity framework for protein-ligand binding affinity prediction,” Communications Chemistry, vol. 8, no. 1, pp. 1–9, 2025

    work page 2025

  2. [2]

    Principles of protein- protein interactions: what are the preferred ways for proteins to interact?,

    O. Keskin, A. Gursoy, B. Ma, and R. Nussinov, “Principles of protein- protein interactions: what are the preferred ways for proteins to interact?,” Chemical reviews, vol. 108, no. 4, pp. 1225–1244, 2008

    work page 2008

  3. [3]

    Highly accurate protein structure prediction with alphafold,

    J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tunyasuvunakool, R. Bates, A. ˇZ´ ıdek, A. Potapenko, et al. , “Highly accurate protein structure prediction with alphafold,” nature, vol. 596, no. 7873, pp. 583–589, 2021

    work page 2021

  4. [4]

    Accurate prediction of protein structures and interactions using a three-track neural network,

    M. Baek, F. DiMaio, I. Anishchenko, J. Dauparas, S. Ovchinnikov, G. R. Lee, J. Wang, Q. Cong, L. N. Kinch, R. D. Schaeffer, et al. , “Accurate prediction of protein structures and interactions using a three-track neural network,” Science, vol. 373, no. 6557, pp. 871–876, 2021

    work page 2021

  5. [5]

    Accurate structure prediction of biomolecular interactions with alphafold 3,

    J. Abramson, J. Adler, J. Dunger, R. Evans, T. Green, A. Pritzel, O. Ronneberger, L. Willmore, A. J. Ballard, J. Bambrick, et al. , “Accurate structure prediction of biomolecular interactions with alphafold 3,” Nature, pp. 1–3, 2024

    work page 2024

  6. [6]

    A perspective on protein structure prediction using quantum computers,

    H. Doga, B. Raubenolt, F. Cumbo, J. Joshi, F. P. DiFilippo, J. Qin, D. Blankenberg, and O. She- hab, “A perspective on protein structure prediction using quantum computers,” Journal of Chem- ical Theory and Computation , vol. 20, no. 9, pp. 3359–3378, 2024

    work page 2024

  7. [7]

    Current structure predictors are not learning the physics of protein folding,

    C. Outeiral, D. A. Nissley, and C. M. Deane, “Current structure predictors are not learning the physics of protein folding,” Bioinformatics, vol. 38, no. 7, pp. 1881–1887, 2022

    work page 2022

  8. [8]

    Noncanonical amino acids in biocatalysis,

    Z. Birch-Price, F. J. Hardy, T. M. Lister, A. R. Kohn, and A. P. Green, “Noncanonical amino acids in biocatalysis,” Chemical Reviews, vol. 124, no. 14, pp. 8740–8786, 2024

    work page 2024

  9. [9]

    Protein functional landscapes, dynamics, allostery: a tortuous path towards a universal theoretical framework,

    P. I. Zhuravlev and G. A. Papoian, “Protein functional landscapes, dynamics, allostery: a tortuous path towards a universal theoretical framework,” Quarterly reviews of biophysics , vol. 43, no. 3, pp. 295–332, 2010

    work page 2010

  10. [10]

    Optimized parallel tempering simulations of pro- teins,

    S. Trebst, M. Troyer, and U. H. Hansmann, “Optimized parallel tempering simulations of pro- teins,” The Journal of chemical physics , vol. 124, no. 17, 2006

    work page 2006

  11. [11]

    Optimization by simulated annealing,

    S. Kirkpatrick, C. D. Gelatt Jr, and M. P. Vecchi, “Optimization by simulated annealing,”science, vol. 220, no. 4598, pp. 671–680, 1983

    work page 1983

  12. [12]

    Replica monte carlo simulation of spin-glasses,

    R. H. Swendsen and J.-S. Wang, “Replica monte carlo simulation of spin-glasses,” Physical review letters, vol. 57, no. 21, p. 2607, 1986

    work page 1986

  13. [13]

    General- ized simulated annealing applied to protein folding studies,

    F. P. Agostini, D. D. O. Soares-Pinto, M. A. Moret, C. Osthoff, and P. G. Pascutti, “General- ized simulated annealing applied to protein folding studies,” Journal of computational chemistry , vol. 27, no. 11, pp. 1142–1155, 2006

    work page 2006

  14. [14]

    The rosetta all-atom energy function for macromolecular modeling and design,

    R. F. Alford, A. Leaver-Fay, J. R. Jeliazkov, M. J. O’Meara, F. P. DiMaio, H. Park, M. V. Shapovalov, P. D. Renfrew, V. K. Mulligan, K. Kappel, et al. , “The rosetta all-atom energy function for macromolecular modeling and design,” Journal of chemical theory and computation , vol. 13, no. 6, pp. 3031–3048, 2017

    work page 2017

  15. [15]

    A numerical implementation of quantum anneal- ing,

    D. de Falco, B. Apolloni, and N. Cesa-Bianchi, “A numerical implementation of quantum anneal- ing,” Stochastic Processes, Physics and Geometry , vol. 324, 1988

    work page 1988

  16. [16]

    Quantum annealing for combinatorial optimization: a benchmarking study,

    S. Kim, S.-W. Ahn, I.-S. Suh, A. W. Dowling, E. Lee, and T. Luo, “Quantum annealing for combinatorial optimization: a benchmarking study,” npj Quantum Information , vol. 11, no. 1, pp. 1–8, 2025

    work page 2025

  17. [17]

    What is the computational value of finite-range tunneling?,

    V. S. Denchev, S. Boixo, S. V. Isakov, N. Ding, R. Babbush, V. Smelyanskiy, J. Martinis, and H. Neven, “What is the computational value of finite-range tunneling?,”Physical Review X, vol. 6, no. 3, p. 031015, 2016. 17

    work page 2016

  18. [18]

    Construction of model hamiltonians for adiabatic quantum computation and its application to finding low-energy conformations of lattice protein models,

    A. Perdomo, C. Truncik, I. Tubert-Brohman, G. Rose, and A. Aspuru-Guzik, “Construction of model hamiltonians for adiabatic quantum computation and its application to finding low-energy conformations of lattice protein models,” Physical Review A—Atomic, Molecular, and Optical Physics, vol. 78, no. 1, p. 012320, 2008

    work page 2008

  19. [19]

    Finding low- energy conformations of lattice protein models by quantum annealing,

    A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik, “Finding low- energy conformations of lattice protein models by quantum annealing,” Scientific reports, vol. 2, no. 1, pp. 1–7, 2012

    work page 2012

  20. [20]

    Resource-efficient quantum algorithm for protein folding,

    A. Robert, P. K. Barkoutsos, S. Woerner, and I. Tavernelli, “Resource-efficient quantum algorithm for protein folding,” npj Quantum Information , vol. 7, no. 1, p. 38, 2021

    work page 2021

  21. [21]

    Construc- tion of energy functions for lattice heteropolymer models: Efficient encodings for constraint sat- isfaction programming and quantum annealing,

    R. Babbush, A. Perdomo-Ortiz, B. O’Gorman, W. Macready, and A. Aspuru-Guzik, “Construc- tion of energy functions for lattice heteropolymer models: Efficient encodings for constraint sat- isfaction programming and quantum annealing,” Advances in Chemical Physics: Volume 155 , pp. 201–244, 2014

    work page 2014

  22. [22]

    Coarse-grained lattice protein folding on a quantum annealer

    T. Babej, M. Fingerhuth, et al., “Coarse-grained lattice protein folding on a quantum annealer,” arXiv preprint arXiv:1811.00713 , 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  23. [23]

    Folding lattice proteins with quantum annealing,

    A. Irb¨ ack, L. Knuthson, S. Mohanty, and C. Peterson, “Folding lattice proteins with quantum annealing,” Physical Review Research, vol. 4, no. 4, p. 043013, 2022

    work page 2022

  24. [24]

    Protein structure prediction with high degrees of freedom in a gate-based quantum com- puter,

    J. V. Pamidimukkala, S. Bopardikar, A. Dakshinamoorthy, A. Kannan, K. Dasgupta, and S. Sena- pati, “Protein structure prediction with high degrees of freedom in a gate-based quantum com- puter,” Journal of Chemical Theory and Computation , vol. 20, no. 22, pp. 10223–10234, 2024

    work page 2024

  25. [25]

    Using quantum annealing to design lattice proteins,

    A. Irb¨ ack, L. Knuthson, S. Mohanty, and C. Peterson, “Using quantum annealing to design lattice proteins,” Physical Review Research, vol. 6, no. 1, p. 013162, 2024

    work page 2024

  26. [26]

    Quadratic unconstrained binary optimization and constraint programming approaches for lattice- based cyclic peptide docking,

    J. K. Brubaker, K. E. Booth, A. Arakawa, F. Furrer, J. Ghosh, T. Sato, and H. G. Katzgraber, “Quadratic unconstrained binary optimization and constraint programming approaches for lattice- based cyclic peptide docking,” arXiv preprint arXiv:2412.10260 , 2024

    work page arXiv 2024

  27. [27]

    Peptide conformational sampling using the quantum approximate optimization algorithm,

    S. Boulebnane, X. Lucas, A. Meyder, S. Adaszewski, and A. Montanaro, “Peptide conformational sampling using the quantum approximate optimization algorithm,” npj Quantum Information , vol. 9, no. 1, p. 70, 2023

    work page 2023

  28. [28]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” arXiv preprint arXiv:1411.4028 , 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  29. [29]

    Investigating the potential for a limited quantum speedup on protein lattice problems,

    C. Outeiral, G. M. Morris, J. Shi, M. Strahm, S. C. Benjamin, and C. M. Deane, “Investigating the potential for a limited quantum speedup on protein lattice problems,”New Journal of Physics, vol. 23, no. 10, p. 103030, 2021

    work page 2021

  30. [30]

    Resource analysis of quantum al- gorithms for coarse-grained protein folding models,

    H. Linn, I. Brundin, L. Garc´ ıa- ´Alvarez, and G. Johansson, “Resource analysis of quantum al- gorithms for coarse-grained protein folding models,” Physical Review Research , vol. 6, no. 3, p. 033112, 2024

    work page 2024

  31. [31]

    On the computational complexity of ising spin glass models,

    F. Barahona, “On the computational complexity of ising spin glass models,” Journal of Physics A: Mathematical and General , vol. 15, no. 10, p. 3241, 1982

    work page 1982

  32. [32]

    Reduction of bivalent maximization to the quadratic case.,

    I. G. Rosenberg, “Reduction of bivalent maximization to the quadratic case.,” 1975

    work page 1975

  33. [33]

    Estimation of effective interresidue contact energies from protein crystal structures: quasi-chemical approximation,

    S. Miyazawa and R. L. Jernigan, “Estimation of effective interresidue contact energies from protein crystal structures: quasi-chemical approximation,” Macromolecules, vol. 18, no. 3, pp. 534–552, 1985

    work page 1985

  34. [34]

    Protein folding in the hydrophobic-hydrophilic (hp) is np-complete,

    B. Berger and T. Leighton, “Protein folding in the hydrophobic-hydrophilic (hp) is np-complete,” in Proceedings of the second annual international conference on Computational molecular biology , pp. 30–39, 1998. 18

    work page 1998

  35. [35]

    Equation of state calculations by fast computing machines,

    N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, “Equation of state calculations by fast computing machines,” The journal of chemical physics , vol. 21, no. 6, pp. 1087–1092, 1953

    work page 1953

  36. [36]

    An efficient simple cooling schedule for simulated annealing,

    M. M. Atiqullah, “An efficient simple cooling schedule for simulated annealing,” in Computa- tional Science and Its Applications - ICCSA 2004 (T. Kanade, ed.), vol. 3045 of Lecture Notes in Computer Science, pp. 396–404, Berlin/Heidelberg: Springer Berlin Heidelberg, 2004

    work page 2004

  37. [37]

    Solving the sparse qubo on multiple gpus for simulating a quantum annealer,

    T. Imanaga, K. Nakano, R. Yasudo, Y. Ito, Y. Kawamata, R. Katsuki, S. Ozaki, T. Yazane, and K. Hamano, “Solving the sparse qubo on multiple gpus for simulating a quantum annealer,” in 2021 Ninth International Symposium on Computing and Networking (CANDAR) , pp. 19–28, 2021

    work page 2021

  38. [38]

    Parallel graph coloring for manycore architectures,

    M. Deveci, E. G. Boman, K. D. Devine, and S. Rajamanickam, “Parallel graph coloring for manycore architectures,” 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 892–901, 2016

    work page 2016

  39. [39]

    Quantum annealing in the transverse ising model,

    T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse ising model,” Physical Review E, vol. 58, no. 5, p. 5355, 1998

    work page 1998

  40. [40]

    Theory of quantum annealing of an ising spin glass,

    G. E. Santoro, R. Martoˇ n´ ak, E. Tosatti, and R. Car, “Theory of quantum annealing of an ising spin glass,” Science, vol. 295, no. 5564, pp. 2427–2430, 2002

    work page 2002

  41. [41]

    The Complexity of Stoquastic Local Hamiltonian Problems

    S. Bravyi, D. P. Divincenzo, R. I. Oliveira, and B. M. Terhal, “The complexity of stoquastic local hamiltonian problems,” arXiv preprint quant-ph/0606140 , 2006

    work page internal anchor Pith review Pith/arXiv arXiv 2006

  42. [42]

    Correlations between the dynamics of parallel tem- pering and the free-energy landscape in spin glasses,

    B. Yucesoy, J. Machta, and H. G. Katzgraber, “Correlations between the dynamics of parallel tem- pering and the free-energy landscape in spin glasses,” Physical Review E—Statistical, Nonlinear, and Soft Matter Physics , vol. 87, no. 1, p. 012104, 2013

    work page 2013

  43. [43]

    Seeking quantum speedup through spin glasses: The good, the bad, and the ugly,

    H. G. Katzgraber, F. Hamze, Z. Zhu, A. J. Ochoa, and H. Munoz-Bauza, “Seeking quantum speedup through spin glasses: The good, the bad, and the ugly,” Physical Review X, vol. 5, no. 3, p. 031026, 2015

    work page 2015

  44. [44]

    Pyqubo: Python library for mapping combinatorial optimization problems to qubo form,

    M. Zaman, K. Tanahashi, and S. Tanaka, “Pyqubo: Python library for mapping combinatorial optimization problems to qubo form,” IEEE Transactions on Computers , vol. 71, no. 4, pp. 838– 850, 2021

    work page 2021

  45. [45]

    Resource efficient gadgets for compiling adi- abatic quantum optimization problems,

    R. Babbush, B. O’Gorman, and A. Aspuru-Guzik, “Resource efficient gadgets for compiling adi- abatic quantum optimization problems,” Annalen der Physik , vol. 525, no. 10-11, pp. 877–888, 2013

    work page 2013

  46. [46]

    Minor-embedding in adiabatic quantum computation: I. the parameter setting prob- lem,

    V. Choi, “Minor-embedding in adiabatic quantum computation: I. the parameter setting prob- lem,” Quantum Information Processing, vol. 7, pp. 193–209, 2008

    work page 2008

  47. [47]

    Addressing the minor-embedding problem in quantum annealing and evaluating state-of-the-art algorithm performance,

    A. Gomez-Tejedor, E. Osaba, and E. Villar-Rodriguez, “Addressing the minor-embedding problem in quantum annealing and evaluating state-of-the-art algorithm performance,” arXiv preprint arXiv:2504.13376, 2025

    work page arXiv 2025

  48. [48]

    A practical heuristic for finding graph minors

    J. Cai, W. G. Macready, and A. Roy, “A practical heuristic for finding graph minors,” arXiv preprint arXiv:1406.2741, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  49. [49]

    The D-Wave Advantage2 Prototype

    C. McGeoch, P. Farre, and K. Boothby, “The D-Wave Advantage2 Prototype.” https://www.dwavequantum.com/media/eixhdtpa/14-1063a-a_the_d-wave_advantage2_ prototype-4.pdf

    work page

  50. [50]

    Zephyr: A next-generation topology for large-scale quantum annealing,

    A. D. King, J. Carrasquilla, and et al., “Zephyr: A next-generation topology for large-scale quantum annealing,” arXiv preprint arXiv:2207.14786 , 2022

    work page arXiv 2022

  51. [51]

    Analog errors in quantum annealing: doom and hope,

    A. Pearson, A. Mishra, I. Hen, and D. A. Lidar, “Analog errors in quantum annealing: doom and hope,” npj Quantum Information , vol. 5, no. 1, p. 107, 2019. 19

    work page 2019

  52. [52]

    Defining and detecting quantum speedup,

    T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer, “Defining and detecting quantum speedup,” science, vol. 345, no. 6195, pp. 420–424, 2014

    work page 2014

  53. [53]

    Efficient partition of integer optimization problems with one-hot encoding,

    S. Okada, M. Ohzeki, and S. Taguchi, “Efficient partition of integer optimization problems with one-hot encoding,” Scientific reports, vol. 9, no. 1, p. 13036, 2019

    work page 2019

  54. [54]

    Error-corrected quantum annealing with hundreds of qubits,

    K. L. Pudenz, T. Albash, and D. A. Lidar, “Error-corrected quantum annealing with hundreds of qubits,” Nature communications, vol. 5, no. 1, p. 3243, 2014

    work page 2014

  55. [55]

    Modernizing quantum annealing using local searches,

    N. Chancellor, “Modernizing quantum annealing using local searches,” New Journal of Physics , vol. 19, no. 2, p. 023024, 2017

    work page 2017

  56. [56]

    Scaling advantage in approximate optimization with quantum annealing,

    H. M. Bauza and D. A. Lidar, “Scaling advantage in approximate optimization with quantum annealing,” arXiv preprint arXiv:2401.07184 , 2024

    work page arXiv 2024

  57. [57]

    quantum-protein-folding (GitHub repository)

    K. J. Sung and L. Bello, “quantum-protein-folding (GitHub repository).” https://github.com/ qiskit-community/quantum-protein-folding?tab=coc-ov-file , 2024. Accessed: 2025-08-14. 20 A Models In this appendix, we give a brief review of the PSP models considered in this work. The review here is by no means meant to be exhaustive. Additional details on the m...

    work page 2024

  58. [58]

    (20) which is only applied to ensure that qubits are not in one of the two states which do not encode a turn. To prohibit the peptide chain from folding back onto itself, an additional energy penalty is implemented utilizing the turn indicators as follows: Hback = NX j=1 (tj +x ∧ tj+1 −x ) + (tj −x ∧ tj+1 +x ) +(tj +y ∧ tj+1 −y ) + (tj −y ∧ tj+1 +y ) +(tj...

    work page