Construction of model Hamiltonians for adiabatic quantum computation and its application to finding low-energy conformations of lattice protein models
Open accessAbstract
In this paper we explore the use of a quantum optimization algorithm for obtaining low-energy conformations of protein models. We discuss mappings between protein models and optimization variables, which are in turn mapped to a system of coupled quantum bits. General strategies are given for constructing Hamiltonians to be used to solve optimization problems of physical, chemical, or biological interest via quantum computation by adiabatic evolution. As an example, we implement the Hamiltonian corresponding to the hydrophobic-polar model for protein folding. Furthermore, we present an approach to reduce the resulting Hamiltonian to two-body terms gearing toward an experimental realization.
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.
Integrity signals
Registry
Cites
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.
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?
The protein-folding problem was attempted to be solved using quantum annealing.
“The problem was attempted to slove using quantum annealing [80].”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [80]
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
Messiah, A. (1961) · Cited by 16,012 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472 · see citing works
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056 · see citing works
Discrete Mathematics and Its Applications
(2010) · Discrete mathematics and its applications · doi:10.1201/chdismthapp · Cited by 1,591 · see citing works
Principles of protein folding — A perspective from simple exact models
Dill, K. A., Bromberg, S., Yue, K., Chan, H. S., Fiebig, K. M., Yee, D. P., & Thomas, P. D. (1995) · Protein Science · doi:10.1002/pro.5560040401 · Cited by 1,517 · see citing works
Simulated Quantum Computation of Molecular Energies
Aspuru-Guzik, A., Dutoi, A. D., Love, P. J., & Head-Gordon, M. (2005) · Science · doi:10.1126/science.1113479 · Cited by 1,418 · see citing works
Self-citationCold Spring Harbor Symposia on Quantitative Biology.
Berg, H. (1989) · Journal of Electroanalytical Chemistry · doi:10.1016/0022-0728(89)87283-3 · Cited by 1,152 · see citing works
A lattice statistical mechanics model of the conformational and sequence spaces of proteins
Lau, K. F., & Dill, K. A. (1989) · Macromolecules · doi:10.1021/ma00200a030 · Cited by 954 · see citing works
Boros, E., & Hammer, P. L. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00341-9 · Cited by 827 · see citing works
Genetic Algorithms for Protein Folding Simulations
Unger, R., & Moult, J. (1993) · Journal of Molecular Biology · doi:10.1006/jmbi.1993.1258 · Cited by 523 · see citing works
Protein Folding in the Hydrophobic-Hydrophilic ( HP ) Model is NP-Complete
Berger, B., & Leighton, T. (1998) · Journal of Computational Biology · doi:10.1089/cmb.1998.5.27 · Cited by 421 · see citing works
Protein Folding Thermodynamics and Dynamics: Where Physics, Chemistry, and Biology Meet
Shakhnovich, E. I. (2006) · Chemical Reviews · doi:10.1021/cr040425u · Cited by 372 · see citing works
On the Complexity of Protein Folding
Crescenzi, P., Goldman, D., Papadimitriou, C. H., Piccolboni, A., & Yannakakis, M. (1998) · Journal of Computational Biology · doi:10.1089/cmb.1998.5.423 · Cited by 363 · see citing works
Protein Folding Theory: From Lattice to All-Atom Models
Mirny, L., & Shakhnovich, E. (2001) · Annual Review of Biophysics and Biomolecular Structure · doi:10.1146/annurev.biophys.30.1.361 · Cited by 341 · see citing works
Chan, H. S., & Dill, K. A. (1993) · Physics Today · doi:10.1063/1.881371 · Cited by 308 · see citing works
The Genetic Control of Tertiary Protein Structure: Studies With Model SystemsPreprint
Epstein, C. J., Goldberger, R. F., & Anfinsen, C. B. (1963) · Cold Spring Harbor Symposia on Quantitative Biology · doi:10.1101/sqb.1963.028.01.060 · Cited by 304 · see citing works
A test of lattice protein folding algorithms.
Yue, K., Fiebig, K. M., Thomas, P. D., Chan, H. S., Shakhnovich, E. I., & Dill, K. A. (1995) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.92.1.325 · Cited by 286 · see citing works
An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem
Shmygelska, A., & Hoos, H. H. (2005) · BMC Bioinformatics · doi:10.1186/1471-2105-6-30 · Cited by 261 · see citing works
Kinetics versus Thermodynamics in Protein Folding
Baker, D. A., & Agard, D. A. (1994) · Biochemistry · doi:10.1021/bi00190a002 · Cited by 242 · see citing works
T HE F AST P ROTEIN F OLDING P ROBLEM
Gruebele, M. (1999) · Annual Review of Physical Chemistry · doi:10.1146/annurev.physchem.50.1.485 · Cited by 203 · see citing works
Understanding protein folding with energy landscape theory Part I: Basic concepts
Plotkin, S. S., & Onuchic, J. N. (2002) · Quarterly Reviews of Biophysics · doi:10.1017/s0033583502003761 · Cited by 199 · see citing works
The complexity of stoquastic local Hamiltonian problems
Bravyi, S. B., Divincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2008) · CERN Document Server (European Organization for Nuclear Research) · doi:10.5555/2011772.2011773 · Cited by 141 · see citing works
Sign- and Magnitude-Tunable Coupler for Superconducting Flux Qubits
Harris, R., Berkley, A. J., Johnson, M. W., Bunyk, P., Govorkov, S. A., Thom, M. C., Uchaikin, S. V., Wilson, A. B., Chung, J., Holtham, E., et al. (2007) · Physical Review Letters · doi:10.1103/physrevlett.98.177001 · Cited by 127 · see citing works
Thermodynamics of protein folding: a microscopic view
Lazaridis, T., & Karplus, M. (2002) · Biophysical Chemistry · doi:10.1016/s0301-4622(02)00293-4 · Cited by 125 · see citing works
Biamonte, J. (2008) · Physical Review A · doi:10.1103/physreva.77.052331 · Cited by 118 · see citing works
A fast conformational search strategy for finding low energy structures of model proteins
Beutler, T. C., & Dill, K. A. (1996) · Protein Science · doi:10.1002/pro.5560051010 · Cited by 97 · see citing works
Contact interactions method: A new algorithm for protein folding simulations
Toma, L., & Toma, S. (1996) · Protein Science · doi:10.1002/pro.5560050118 · Cited by 80 · see citing works
The complexity of stoquastic local Hamiltonian problems
Bravyi, S. B., Divincenzo, D. P., Oliveira, R. I., & Terhal, B. M. (2008) · Quantum Information and Computation · doi:10.26421/qic8.5-1 · Cited by 79 · see citing works
Discrete Mathematics and Its Applications
-, L. D. (2000) · Cited by 73 · see citing works
Growth-based optimization algorithm for lattice heteropolymers
Hsu, H., Mehra, V., Nadler, W., et al. (2003) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.68.021113 · Cited by 65 · see citing works
Designability of protein structures: A lattice‐model study using the Miyazawa‐Jernigan matrix
Li, H., Tang, C., & Wingreen, N. S. (2002) · Proteins Structure Function and Bioinformatics · doi:10.1002/prot.10239 · Cited by 65 · see citing works
Investigation of the three-dimensional lattice HP protein folding model using a genetic algorithm
Custódio, F. L., Barbosa, H. J. C., & Dardenne, L. E. (2004) · Genetics and Molecular Biology · doi:10.1590/s1415-47572004000400023 · Cited by 39 · see citing works
Scalable Superconducting Architecture for Adiabatic Quantum ComputationPreprint
Kaminsky, W. M., Lloyd, S., & Orlando, T. P. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0403090 · Cited by 35 · see citing works
Development and optimisation of a novel genetic algorithm for studying model protein folding
Cox, G. A., Mortimer-Jones, T. V., Taylor, R. P., et al. (2004) · Theoretical Chemistry Accounts · doi:10.1007/s00214-004-0601-4 · Cited by 34 · see citing works
Relating time complexity of protein folding simulation to approximations of folding time
Steinhöfel, K. K., Skaliotis, A., & Albrecht, A. A. (2007) · Computer Physics Communications · doi:10.1016/j.cpc.2006.12.002 · Cited by 13 · see citing works
Analyzing energy landscapes for folding model proteins
Cox, G. A., & Johnston, R. L. (2006) · The Journal of Chemical Physics · doi:10.1063/1.2198537 · Cited by 7 · see citing works
The Physical Implementation of Quantum Computation
DiVincenzo, D. P. (2000) · Fortschritte der Physik · doi:10.1002/1521-3978(200009)48:9/11
Flagged first, then by citations
Research works printed but not linked: 10
- [2]S. S. Plotkin and J. N. Onuchic , Quarterly Reviews of Biophysics 35 (2002).
- [4]L. Mirny and E. Shaknovich , Annual Review of Biophysics and Biomolecular Structure 30 (2001).
- [6]M. Gruebele , Annual Review of Physical Chemistry 50 , 485 (1999).
- [11]P. W. Shor , SIAM Journal on Computing 26 , 1484 (1997).
- [21]R. Backofen and S. Will , Proc. XIX Intl. Conf. on Logic Programming , 49 (2003).
- [23]H. P. Hsu , V. Mehra , W. Nadler , and P. Grassberger , Physical Review E 68 , 021113 (2003).
- [25]K. Yue , K. M. Fiebig , P. D. Thomas , H. S. Chan , E. I. Shaknovich , and K. A. Dill , Proc. Nat. Acad. Sci. USA 92 , 325 (1995).
- [26]P. Crescenzi , D. Goldman , C. Papadimitriou , A. Piccolboni , and M. Yannakakis , Journal of Computational Biology 5 , 423 (FAL 1998).
- [27]B. Berger and T. Leighton , Journal of Computational Biology 5 , 27 (SPR 1998).
- [29]R. Harris , A. Berkley , M. Johnson , P. Bunyk , S. Govorkov , M. Thom , S. Uchaikin , A. Wilson , J. Chung , E. Holtham , J. Biamonte , A. Yu , M. Amin , and A. van den Brink , Physical Review Letters 98 , 177001 (2007).
Cited by
Sorted by citations
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
Self-citationQuantum computational chemistry
McArdle, S., Endo, S., Aspuru-Guzik, A., Benjamin, S. C., & Yuan, X. (2020) · Reviews of Modern Physics · doi:10.1103/revmodphys.92.015003 · Cited by 1,621 · see citing works
Self-citationFinding low-energy conformations of lattice protein models by quantum annealing
Perdomo-Ortiz, A., Dickson, N., Drew-Brook, M., Rose, G., & Aspuru-Guzik, A. (2012) · Scientific Reports · doi:10.1038/srep00571 · Cited by 366 · see citing works
Self-citationSimulating Chemistry Using Quantum Computers
Kassal, I., Whitfield, J. D., Perdomo-Ortiz, A., Yung, M.-H., & Aspuru-Guzik, A. (2011) · Annual Review of Physical Chemistry · doi:10.1146/annurev-physchem-032210-103512 · Cited by 352 · see citing works
Self-citationPotential of quantum computing for drug discovery
Cao, Y., Romero, J., & Aspuru-Guzik, A. (2018) · IBM Journal of Research and Development · doi:10.1147/jrd.2018.2888987 · Cited by 357 · see citing works
Self-citationThe prospects of quantum computing in computational molecular biology
Outeiral, C., Strahm, M., Shi, J., Morris, G. M., Benjamin, S. C., & Deane, C. M. (2021) · WIREs Computational Molecular Science · doi:10.1002/wcms.1481 · Cited by 232 · see citing works
Resource-efficient quantum algorithm for protein folding
Robert, A., Barkoutsos, P. K., Woerner, S., & Tavernelli, I. (2021) · npj Quantum Information · doi:10.1038/s41534-021-00368-4 · Cited by 201 · see citing works
A study of heuristic guesses for adiabatic quantum computation
Perdomo-Ortiz, A., Venegas-Andraca, S. E., & Aspuru-Guzik, A. (2011) · Quantum Information Processing · doi:10.1007/s11128-010-0168-z · Cited by 111 · see citing works
Self-citationBiology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87 · see citing works
Pal, S., Bhattacharya, M., Lee, S.-S., & Chakraborty, C. (2024) · Molecular Biotechnology · doi:10.1007/s12033-023-00765-4 · Cited by 84 · see citing works
“The problem was attempted to slove using quantum annealing [80].”
Towards practical applications in quantum computational biology
Fedorov, A. K., & Gelfand, M. S. (2021) · Nature Computational Science · doi:10.1038/s43588-021-00024-z · Cited by 62 · see citing works
Insights from incorporating quantum computing into drug design workflows
Lau, B., Emani, P. S., Chapman, J., Yao, L., Lam, T., Merrill, P., Warrell, J., Gerstein, M. B., & Lam, H. Y. K. (2023) · Bioinformatics · doi:10.1093/bioinformatics/btac789 · Cited by 54 · see citing works
Singh, H., Majumder, S., & Mishra, S. (2023) · The Journal of Chemical Physics · doi:10.1063/5.0161057 · Cited by 51 · see citing works
Babbush, R., Perdomo‐Ortiz, A., O'Gorman, B., Macready, W., & Aspuru‐Guzik, A. (2014) · Advances in Chemical Physics · doi:10.1002/9781118755815.ch05 · Cited by 45 · see citing works
Self-citationThe prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer
Allcock, J., Vangone, A., Meyder, A., Adaszewski, S., Strahm, M., Hsieh, C.-Y., & Zhang, S. (2022) · Frontiers in Drug Discovery · doi:10.3389/fddsv.2022.908870 · Cited by 12 · see citing works
- Authors
- Perdomo, A., Truncik, C., Tubert-Brohman, I., Rose, G., & Aspuru-Guzik, A.
- Affiliations
- D-Wave Systems (Canada) (CA)
- Venue
- Physical Review A
- Publisher
- American Physical Society (APS)
- Published
- 2008-07-11
- Volume
- 78
- Issue
- 1
- ISSN
- 0556-2791 (ISSN-L)
- 1050-2947
- 1094-1622
- OpenAlex
- W2103095418
- Cited by
- 120
- References
- 37
- Citations by year
- 2026: 6 · 2025: 7 · 2024: 12 · 2023: 8 · 2022: 15 · 2021: 9 · 2020: 5 · 2019: 10 · 2018: 4 · 2017: 2 · 2016: 3 · 2015: 5 · 2014: 9 · 2013: 6 · 2012: 6
- FWCI
- 6.86
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Physical Review A (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- Digital Access to Scholarship at Harvard (DASH) (Harvard University) (submittedVersion, cc-by)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › DNA and Biological Computing
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Keywords
- adiabatic quantum computation, model Hamiltonian, quantum optimization, protein folding, protein conformational space, hydrophobic-polar model, lattice protein models, Hamiltonian construction
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
