Protein folding processes are a vital aspect of molecular biology that is hard to simulate with conventional computers. Quantum algorithms have been proven superior for certain problems and may help tackle this complex life science challenge. We analyze the resource requirements for simulating simplified yet computationally challenging protein folding models on a quantum computer, assessing the feasibility of these existing approaches in the current and near-future technological landscape. We calculate the minimum number of qubits, interactions, and two-qubit gates necessary to build a heuristic quantum algorithm with the specific information of a folding problem. Particularly, we focus on the resources needed to build quantum operations based on the Hamiltonian linked to the protein folding models for a given amino acid count. Such operations are a fundamental component of these quantum algorithms, guiding the evolution of the quantum state for efficient computations. Specifically, we study coarse-grained folding models on the lattice and the fixed backbone side-chain conformation model and assess their compatibility with the constraints of existing quantum hardware given different bit encodings. We conclude that the number of qubits required falls within current technological capabilities. However, the limiting factor is the high number of interactions in the Hamiltonian, resulting in a quantum gate count unavailable today.
Protein folding processes are a vital aspect of molecular biology that is hard to simulate with conventional computers. Quantum algorithms have been proven superior for certain problems and may help tackle this complex life science challenge. We analyze the resource requirements for simulating simplified yet computationally challenging protein folding models on a quantum computer, assessing the feasibility of these existing approaches in the current and near-future technological landscape. We calculate the minimum number of qubits, interactions, and two-qubit gates necessary to build a heuristic quantum algorithm with the specific information of a folding problem. Particularly, we focus on the resources needed to build quantum operations based on the Hamiltonian linked to the protein folding models for a given amino acid count. Such operations are a fundamental component of these quantum algorithms, guiding the evolution of the quantum state for efficient computations. Specifically, we study coarse-grained folding models on the lattice and the fixed backbone side-chain conformation model and assess their compatibility with the constraints of existing quantum hardware given different bit encodings. We conclude that the number of qubits required falls within current technological capabilities. However, the limiting factor is the high number of interactions in the Hamiltonian, resulting in a quantum gate count unavailable today.
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 O(N4) 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.
Abstract Predicting a protein’s three-dimensional structure from its primary amino acid sequence constitutes the protein folding problem, a pivotal challenge within computational biology. This task has been identified as a fitting domain for applying quantum annealing, an algorithmic technique posited to be faster than its classical counterparts. Nevertheless, the utility of quantum annealing is intrinsically contingent upon the spectral gap associated with the Hamiltonian of lattice proteins. This critical dependence introduces a limitation to the efficacy of these techniques, particularly in the context of simulating the intricate folding processes of proteins. In this paper, we address lattice protein folding as a polynomial unconstrained binary optimization problem, devising a hybrid quantum–classical algorithm to determine the minimum energy conformation effectively. Our method is distinguished by its logarithmic scaling with the spectral gap, conferring a significant edge over the conventional quantum annealing algorithms. The present findings indicate that the folding of lattice proteins can be achieved with a resource consumption that is polynomial in the lattice protein length, provided an ansatz state that encodes the target conformation is utilized. We also provide a simple and scalable method for preparing such states and further explore the adaptation of our method for extension to off-lattice protein models. This work paves a new avenue for surmounting complex computational biology problems via the utilization of quantum computers.
- A study published in the international journal npj Quantum Information (Nature Portfolio) presents a resource-efficient quantum algorithm framework based on the Variational Quantum Eigensolver (VQE) for peptide and protein folding. - By translating protein folding into a tetrahedral lattice model and combining Conditional Value-at-Risk (CVaR) VQE with a classical evolutionary algorithm, the number of required qubits was drastically reduced. - It successfully folded a 7-amino acid neuropeptide using only 9 qubits on actual IBM 20-qubit quantum hardware, demonstrating its practical potential for next-generation drug discovery in the NISQ (Noisy Intermediate-Scale Quantum) era. [Quantum Biology Society] The protein folding problem, which involves predicting the three-dimensional structure of proteins and peptides from their primary amino acid sequence, plays a central role in various applications such as chemistry, biology, and medicine. However, as the sequence lengthens, the number of possible structures to explore explodes exponentially, making it difficult for classical computers to handle its intrinsic NP-hard complexity. Recently, a new quantum algorithm that can efficiently solve this long-standing challenge even on noisy intermediate-scale quantum (NISQ) computers has been developed, drawing the attention of the academic community. The paper titled "Resource-efficient quantum algorithm for protein folding," published in the international journal npj Quantum Information, presents an innovative computing framework for the discovery of next-generation peptide drugs. The research team of Anton Robert and Ivano Tavernelli from IBM Quantum, IBM Research - Zurich in Switzerland successfully led this groundbreaking study. ■ The Meeting of Lattice Models and Qubit Optimization Until now, attempts to introduce quantum computing to protein folding have required an unattainably high number of qubits that current, near-term quantum hardware cannot handle. To solve this, the research team converted protein folding into a tetrahedral lattice model. This model can efficiently depict the growth of a polymer chain while maintaining chemically plausible bond angles. In particular, they adopted a method of adding penalty terms to the Hamiltonian to prevent unphysical amino acid overlaps (e.g., beads occupying the same lattice site). Through this, they succeeded in drastically reducing the number of qubits required for calculation while suppressing the complexity of the algorithm to the level of O(N⁴). ■ Demonstration of Folding on Actual Quantum Hardware This algorithm maximized efficiency by combining CVaR-VQE, a variation of the Variational Quantum Eigensolver (VQE), with a classical Differential Evolution optimizer. Applying this technique, the researchers simulated the folding of the 10-amino acid Angiotensin peptide using only 22 qubits, successfully finding the most stable energy state (native fold). Furthermore, they successfully demonstrated the folding of a 7-amino acid neuropeptide (APRLRFY) using only 9 qubits on IBM's 20-qubit quantum computer hardware. This study is a groundbreaking achievement proving that the protein folding problem, which previously required massive computing resources, can be successfully solved even in a noisy real quantum processor environment. It is expected to bring tremendous innovation to next-generation /de novo/ drug design and disease treatment research utilizing quantum computing in the future.
In the convergence of quantum computing and life science, we explore protein structure prediction and design on near-term intermediate-scale quantum devices. We investigate the algorithmic and resource constraints of today’s quantum computers, aiming to assess their potential in solving biologically relevant problems. We describe key variational quantum algorithms, including the problem-informed Quantum Approximate Optimization Algorithm and the problem-agnostic Hardware-Efficient Ansatz. Additionally, quantum walks are examined. The computationally complex coarse-grained lattice models in protein structure prediction and design are discussed. Quantum algorithms are then applied to these models to address the utility and limitations of today’s quantum computers. The thesis critically evaluates the limitations of quantum methods in comparison to classical approaches, highlighting the trade-offs between resource requirements in today’s quantum devices and the performance of quantum algorithms. Through this interdisciplinary investigation, the work contributes to understanding how quantum algorithms may advance computational biology in today’s quantum computing landscape.
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. Moreover, 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 possible scaling advantage over our in-house simulated annealing implementation, which, however, is only noticeable when comparing performance on the embedded problems.
In computational biology, protein folding continues to be a key challenge with important implications for drug design and biological function comprehension. Using both classical and quantum computing methods, this paper provides an in-depth analysis of various possible lattice configurations and how theyare used in protein folding. To assess the protein design, we investigate classic models including the more intricate Miyazawa-Jernigan (MJ) interaction matrix and the hydrophobic-hydrophilic (HP) lattice model. Furthermore, we use integer programming methods to protein folding problems on lattices, addressing their NP-hardness and proving their effectiveness in obtaining optimal solutions. Expanding upon these conventional techniques, we present sophisticated graph neural network (GNN) models, particularly the RG-MPNN, which integrate pharmacophore ideas to predict chemical properties by using task-related representations. In the latter section of our paper, we examine how protein folding simulations on lattice structures could be transformed using quantum algorithms. Compared to classical methods, quantum computational techniques promise to be more accurate and efficient at handling the enormous diversity and complexity of protein folding.