Resource-efficient quantum algorithm for protein folding
Open accessAbstract
Abstract Predicting the three-dimensional structure of a protein from its primary sequence of amino acids is known as the protein folding problem. Due to the central role of proteins’ structures in chemistry, biology and medicine applications, this subject has been intensively studied for over half a century. Although classical algorithms provide practical solutions for the sampling of the conformation space of small proteins, they cannot tackle the intrinsic NP-hard complexity of the problem, even when reduced to the simplest Hydrophobic-Polar model. On the other hand, while fault-tolerant quantum computers are beyond reach for state-of-the-art quantum technologies, there is evidence that quantum algorithms can be successfully used in noisy state-of-the-art quantum computers to accelerate energy optimization in frustrated systems. In this work, we present a model Hamiltonian with $${\mathcal{O}}({N}^{4})$$ O ( N 4 ) scaling and a corresponding quantum variational algorithm for the folding of a polymer chain with N monomers on a lattice. The model reflects many physico-chemical properties of the protein, reducing the gap between coarse-grained representations and mere lattice models. In addition, we use a robust and versatile optimization scheme, bringing together variational quantum algorithms specifically adapted to classical cost functions and evolutionary strategies to simulate the folding of the 10 amino acid Angiotensin on 22 qubits. The same method is also successfully applied to the study of the folding of a 7 amino acid neuropeptide using 9 qubits on an IBM 20-qubit quantum computer. Bringing together recent advances in building gate-based quantum computers with noise-tolerant hybrid quantum-classical algorithms, this work paves the way towards accessible and relevant scientific experiments on real quantum processors.
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?
Quantum computing can contribute to biochemical systems, biology, biochemistry, computation of protein-ligand interplay, mRNA codon optimization, and protein folding with higher-order speeds compared with conventional computers.
“its contribution is possible in biochemical systems [7], biology [8], biochemistry [9], computation of protein-ligand interplay [10], mRNA codon optimization [11], and protein folding [12] to name a few with higherorder speeds compared with conventional computers.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [12]
The Abstract and Discussion describe a quantum algorithm used to simulate protein folding, so the protein-folding application is supported. The Discussion says the algorithm may speed up the search, but it does not establish the claimed higher-order speed advantage over conventional computers. The other applications in the sentence have separate citations and are not attributed to this paper. (LLM, conf=0.86)
Experimental — accuracy not yet measuredProtein folding is an optimization problem and a candidate for heuristic quantum optimization algorithms.
“A candidate in the biological context is the protein folding problem, which is an optimization problem, for which heuristic quantum optimization algorithms are being investigated.[109,110]”
From Quantum Computing for Molecular Biology** (2023) · cites this paper as [110]
The first attempts to solve protein folding with quantum annealing and later hybrid algorithms based on QAOA, VQE, and quantum random walks have been proposed.
“The first attempts to solve the protein folding optimization problem relied on quantum annealing [205,206] while, more recently, hybrid classical-variational algorithms based on QAOA, [109] VQE, [110] and on quantum random walks [207] have been proposed.”
From Quantum Computing for Molecular Biology** (2023) · cites this paper as [110]
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
Storn, R., & Price, K. (1997) · Journal of Global Optimization · doi:10.1023/a:1008202821328 · Cited by 29,569 · see citing works
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552 · see citing works
The theory of variational hybrid quantum-classical algorithms
McClean, J. R., Romero, J., Babbush, R., & Aspuru-Guzik, A. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/2/023023 · Cited by 2,227 · see citing works
How fast-folding proteins fold
Lindorff-Larsen, K., Piana, S., Dror, R. O., & Shaw, D. E. (2011) · Science · doi:10.1126/science.1208351 · Cited by 1,980 · see citing works
Recent advances in differential evolution – An updated survey
Das, S., Mullick, S. S., & Suganthan, P. N. (2016) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2016.01.004 · Cited by 1,596 · see citing works
Are there pathways for protein folding?
Levinthal, C. (1968) · Journal de Chimie Physique · doi:10.1051/jcp/1968650044 · Cited by 1,536 · see citing works
Duan, Y., & Kollman, P. A. (1998) · Science · doi:10.1126/science.282.5389.740 · Cited by 1,341 · see citing works
Qiskit: An Open-source Framework for Quantum Computing
Aleksandrowicz, G., Alexander, T., Barkoutsos, P. K., et al. (2019) · Zenodo (CERN European Organization for Nuclear Research) · doi:10.5281/zenodo.2562111 · Cited by 1,314 · see citing works
Self-citationOnuchic, J. N., & Wolynes, P. G. (2004) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2004.01.009 · Cited by 1,298 · see citing works
Miyazawa, S., & Jernigan, R. L. (1996) · Journal of Molecular Biology · doi:10.1006/jmbi.1996.0114 · Cited by 1,231 · see citing works
Computer simulation of protein folding
Levitt, M., & Warshel, A. (1975) · Nature · doi:10.1038/253694a0 · Cited by 1,051 · see citing works
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772 · see citing works
Zwanzig, R., Szabo, A., & Bagchi, B. (1992) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.89.1.20 · Cited by 527 · see citing works
Toward an outline of the topography of a realistic protein-folding funnel.
Onuchic, J. N., Wolynes, P. G., Luthey-Schulten, Z., & Socci, N. D. (1995) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.92.8.3626 · Cited by 523 · see citing works
Piana, S., Klepeis, J. L., & Shaw, D. E. (2014) · Current Opinion in Structural Biology · doi:10.1016/j.sbi.2013.12.006 · Cited by 513 · see citing works
Finding 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
Quantum Supremacy through the Quantum Approximate Optimization Algorithm
Farhi, E., & Harrow, A. W. (2016) · arXiv · doi:10.48550/arxiv.1602.07674 · Cited by 331 · see citing works
A practical heuristic for finding graph minorsPreprint
Cai, J. L., Macready, W. G., & Roy, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1406.2741 · Cited by 284 · see citing works
General Quantum Interference Principle and Duality Computer
Gui-Lu, L. (2006) · Communications in Theoretical Physics · doi:10.1088/0253-6102/45/5/013 · Cited by 269 · see citing works
Improving Variational Quantum Optimization using CVaR
Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., & Woerner, S. (2020) · Quantum · doi:10.22331/q-2020-04-20-256 · Cited by 263 · see citing works
Self-citationA lattice model for protein structure prediction at low resolution.
Hinds, D. A., & Levitt, M. (1992) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.89.7.2536 · Cited by 217 · see citing works
Perdomo, A., Truncik, C., Tubert-Brohman, I., Rose, G., & Aspuru-Guzik, A. (2008) · Physical Review A · doi:10.1103/physreva.78.012320 · Cited by 120 · see citing works
A Full Quantum Eigensolver for Quantum Chemistry Simulations
Wei, S., Li, H., & Long, G. (2020) · Research · doi:10.34133/2020/1486935 · Cited by 95 · see citing works
A quantum alternating operator ansatz with hard and soft constraints for lattice protein foldingPreprint
Fingerhuth, M., Babej, T., & Ing, C. E. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.13411 · Cited by 70 · see citing works
Coarse-grained lattice protein folding on a quantum annealerPreprint
Babej, T., Ing, C. E., & Fingerhuth, M. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.00713 · Cited by 47 · see citing works
Flagged first, then by citations
Research works printed but not linked: 1
- Babbush, R., Perdomo-Ortiz, A., O'Gorman, B., Macready, W. & Aspuru-Guzik, A. Construction of energy functions for lattice heteropolymer models: Efficient encodings for constraint satisfaction programming and quantum annealing. arXiv preprint arXiv:1211.3422 155, 201 -244 (2014). · arXiv
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
Quantum 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
Quantum computing for near-term applications in generative chemistry and drug discovery.
Pyrkov, A., Aliper, A., Bezrukov, D., Lin, Y.-C., Polykovskiy, D., Kamya, P., Ren, F., & Zhavoronkov, A. (2023) · Drug Discovery Today · doi:10.1016/j.drudis.2023.103675 · Cited by 100 · see citing works
Quantum Computing for Molecular Biology**
Baiardi, A., Christandl, M., & Reiher, M. (2023) · ChemBioChem · doi:10.1002/cbic.202300120 · Cited by 93 · see citing works
Quantum-optimal-control-inspired ansatz for variational quantum algorithms
Choquette, A., Di Paolo, A., Barkoutsos, P. K., Sénéchal, D., Tavernelli, I., & Blais, A. (2021) · Physical Review Research · doi:10.1103/physrevresearch.3.023092 · Cited by 86 · see citing works
Self-citationPal, S., Bhattacharya, M., Lee, S.-S., & Chakraborty, C. (2024) · Molecular Biotechnology · doi:10.1007/s12033-023-00765-4 · Cited by 84 · see citing works
A hybrid quantum computing pipeline for real world drug discovery
Li, W., Yin, Z., Li, X., Ma, D., Yi, S., Zhang, Z., Zou, C., Bu, K., Dai, M., Yue, J., et al. (2024) · Scientific Reports · doi:10.1038/s41598-024-67897-8 · Cited by 67 · see citing works
“DFT calculations were performed using Gaussian 16.”
MethodQuantum computing for chemical and biomolecular product design
Andersson, M. P., Jones, M. N., Mikkelsen, K. V., You, F., & Mansouri, S. S. (2022) · Current Opinion in Chemical Engineering · doi:10.1016/j.coche.2021.100754 · Cited by 66 · see citing works
Quantum computing algorithms: getting closer to critical problems in computational biology
Marchetti, L., Nifosì, R., Martelli, P. L., Da Pozzo, E., Cappello, V., Banterle, F., Trincavelli, M. L., Martini, C., & D’Elia, M. (2022) · Briefings in Bioinformatics · doi:10.1093/bib/bbac437 · Cited by 47 · see citing works
“[73] report a quantum gate-based approach to protein folding on a lattice, using a modified version of the VQE algorithm (discussed in the next section) and requiring a number of qubits that scales quadratically with the number of amino acids.”
MethodPolymer physics by quantum computing
Micheletti, C., Hauke, P., & Faccioli, P. (2021) · Physical Review Letters · doi:10.1103/physrevlett.127.080501 · Cited by 48 · see citing works
Peptide conformational sampling using the Quantum Approximate Optimization Algorithm
Boulebnane, S., Lucas, X., Meyder, A., Adaszewski, S., & Montanaro, A. (2023) · npj Quantum Information · doi:10.1038/s41534-023-00733-5 · Cited by 32 · see citing works
Gate-based quantum computing for protein design
Khatami, M. H., Mendes, U. C., Wiebe, N., & Kim, P. M. (2023) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1011033 · Cited by 26 · see citing works
Swan, M., dos Santos, R. P., & Witte, F. (2022) · Quantum Reports · doi:10.3390/quantum4010008 · Cited by 16 · see citing works
Bias-field digitized counterdiabatic quantum algorithm for higher-order binary optimization
Romero, S. V., Visuri, A.-M., Cadavid, A. G., Simen, A., Solano, E., & Hegade, N. N. (2025) · Communications Physics · doi:10.1038/s42005-025-02270-3 · Cited by 18 · see citing works
“Even though our work addresses problems with up to three-body terms, our method is equally applicable to higher-order optimization problems, including the LABS problem [17], MAX k -SAT [52], factorization [53] and protein folding [54, 55], among others.”
The 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
- Robert, A., Barkoutsos, P. K., Woerner, S., & Tavernelli, I.
- Affiliations
- Centre National de la Recherche Scientifique (FR)
- IBM Research - Zurich (CH)
- Corresponding author
- Tavernelli, Ivano
- Venue
- npj Quantum Information
- Published
- 2021-02-17
- Volume
- 7
- Issue
- 1
- ISSN
- 2056-6387 (ISSN-L)
- OpenAlex
- W2965027194
- Cited by
- 201
- References
- 25
- Citations by year
- 2026: 36 · 2025: 47 · 2024: 44 · 2023: 35 · 2022: 25 · 2021: 12 · 2020: 1
- FWCI
- 10.21
- Type
- journal article
- Language
- en
- Open access
- gold
- doi.org
- Locations
- npj Quantum Information (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
- arXiv (Cornell University)
- Funders
- Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (200021-179312)
- 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
- protein folding, Hamiltonian model, hydrophobic-polar model, angiotensin, noisy quantum computers, hybrid quantum-classical optimization, evolution strategies, conformational space, coarse-grained protein models
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
