Protein folding is a computationally challenging problem because the number of possible structures increases rapidly with sequence length. This paper presents a hybrid quantum-classical framework for protein folding using the Hydrophobic-Polar (HP) model in a three-dimensional lattice. Valid protein structures are generated using a self-avoiding walk, and their energy is evaluated based on hydrophobic interactions. Simulated annealing is used as the classical opti- mization method, while the Quantum Approximate Optimization Algorithm (QAOA) is used for quantum optimization. Experimental results show that simulated annealing achieves lower energy values (e.g., -5.0 eV) compared to QAOA (-4.45 eV). Although quantum optimization does not yet outperform classical methods, it produces close approximations and shows potential for future improvements.
Protein folding is a computationally challenging problem because the number of possible structures increases rapidly with sequence length. This paper presents a hybrid quantum-classical framework for protein folding using the Hydrophobic-Polar (HP) model in a three-dimensional lattice. Valid protein structures are generated using a self-avoiding walk, and their energy is evaluated based on hydrophobic interactions. Simulated annealing is used as the classical opti- mization method, while the Quantum Approximate Optimization Algorithm (QAOA) is used for quantum optimization. Experimental results show that simulated annealing achieves lower energy values (e.g., -5.0 eV) compared to QAOA (-4.45 eV). Although quantum optimization does not yet outperform classical methods, it produces close approximations and shows potential for future improvements.
Quantum annealing is a promising approach for obtaining good approximate solutions to difficult optimization problems.Folding a protein sequence into its minimum-energy structure represents such a problem.For testing new algorithms and technologies for this task, the minimal lattice-based [hydrophobic (H) or polar (P) beads] HP model is well suited, as it represents a considerable challenge despite its simplicity.The HP model has favorable interactions between adjacent, not directly bound hydrophobic residues.Here, we develop a novel spin representation for lattice protein folding tailored for quantum annealing.With a distributed encoding onto the lattice, it differs from earlier attempts to fold lattice proteins on quantum annealers, which were based upon chain growth techniques.With our encoding, the Hamiltonian by design has the quadratic structure required for calculations on an Ising-type annealer, without having to introduce any auxiliary spin variables.This property greatly facilitates the study of long chains.The approach is robust to changes in the parameters required to constrain the spin system to chainlike configurations, and performs very well in terms of solution quality.The results are evaluated against existing exact results for HP chains with up to N = 30 beads with 100% hit rate, thereby also outperforming classical simulated annealing.In addition, the method allows us to recover the lowest known energies for N = 48 and N = 64 HP chains, with similar hit rates.These results are obtained by the commonly used hybrid quantum-classical approach.For pure quantum annealing, our method successfully folds an N = 14 HP chain.The calculations were performed on a D-Wave Advantage quantum annealer.
Lattice protein folding models are a cornerstone of computational biophysics. Although these models are a coarse grained representation, they provide useful insight into the energy landscape of natural proteins. Finding low-energy threedimensional structures is an intractable problem even in the simplest model, the Hydrophobic-Polar (HP) model. Description of protein-like properties are more accurately described by generalized models, such as the one proposed by Miyazawa and Jernigan (MJ), which explicitly take into account the unique interactions among all 20 amino acids. There is theoretical and experimental evidence of the advantage of solving classical optimization problems using quantum annealing over its classical analogue (simulated annealing). In this report, we present a benchmark implementation of quantum annealing for lattice protein folding problems (six different experiments up to 81 superconducting quantum bits). This first implementation of a biophysical problem paves the way towards studying optimization problems in biophysics and statistical mechanics using quantum devices.
Quantum annealing has shown promise for finding solutions to difficult optimization problems, including protein folding. Recently, we used the D-Wave Advantage quantum annealer to explore the folding problem in a coarse-grained lattice model, the HP model, in which amino acids are classified into two broad groups: hydrophobic (H) and polar (P). Using a set of 22 HP sequences with up to 64 amino acids, we demonstrated the fast and consistent identification of the correct HP model ground states using the D-Wave hybrid quantum-classical solver. An equally relevant biophysical challenge, called the protein design problem, is the inverse of the above, where the task is to predict protein sequences that fold to a given structure. Here, we approach the design problem by a two-step procedure implemented and executed on a D-Wave machine. In the first step, we perform a pure sequence-space search by varying the type of amino acid at each sequence position, and seek sequences which minimize the HP-model energy of the target structure. After mapping this task onto an Ising spin-glass representation, we employ a hybrid quantum-classical solver to deliver energy-optimal sequences for structures with 30–64 amino acids, with a 100% success rate. In the second step, we filter the optimized sequences from the first step according to their ability to fold to the intended structure. In addition, we try solving the sequence optimization problem using only the quantum processing unit (QPU), which confines us to sizes ≤20 , due to exponentially decreasing success rates. To shed light on the pure QPU results, we investigate the effects of control errors caused by an imperfect implementation of the intended Hamiltonian on the QPU, by numerically analyzing the Schrödinger equation. We find that the simulated success rates in the presence of control noise semiquantitatively reproduce the modest pure QPU results for larger chains. Published by the American Physical Society 2024
Protein folding, which traces the protein three-dimensional (3D) structure from its amino acid sequence, is a half-a-century-old problem in biology. The function of the protein correlates with its structure, emphasizing the need to study protein folding to understand the cellular and molecular processes better. While recent AI-based methods have shown significant success in protein structure prediction, their accuracy diminishes with proteins of low sequence similarity. Classical simulations face challenges in generating extensive conformational samplings. In this work, we develop a novel turn-based encoding algorithm with more significant degrees of freedom that successfully runs on a gate-based quantum computer and predicts the structure of proteins of varied lengths utilizing up to 114 qubits (IBM hardware). To make the problem tractable in quantum computers, the protein sequences were described with the simplistic HP model (H = hydrophobic residues, P = polar residues). The proposed formulation successfully captures the so-called nucleation step in protein folding, the hydrophobic collapse, that brings the hydrophobic residues to the core of the protein.
Protein folding is one of the age-old biological problems that refers to the mechanism of understanding and predicting how a protein's linear sequence of amino acids folds into its specific three dimensional structure.This structure is critical, as a protein's functionality is inherently linked to its final folded form. Misfolding can lead to severe diseases such as Alzheimer's and cystic fibrosis, highlighting the biological and clinical importance of understanding protein folding mechanisms. This work presents a novel turn based encoding optimization algorithm for predicting the folded structures of peptides and small proteins. Our approach builds upon our previous research, where our objective function focused on hydrophobic collapse, a fundamental phenomenon underlying the protein folding process. In this work, we extend that framework by not only incorporating hydrophobic interactions but also including all non bonded interactions modeled using the Miyazawa Jernigan potential. We constructed a Hamiltonian from the defined objective function that encodes the folding process on a three dimensional face centered cubic lattice, offering superior packing efficiency and a realistic representation of protein conformations. This Hamiltonian is then solved using classical and quantum solvers to explore the vast conformational space of proteins. To identify the lowest-energy folded configurations, we utilize the Variational Quantum Eigensolver implemented on IBM 133 qubit hardware. The predicted structures are validated against experimental data using root mean square deviation as a metric and compared against classical simulated annealing and molecular dynamics simulation results. Our findings highlight the promise of hybrid classical and quantum approaches in advancing protein folding predictions, particularly for sequences with low homology.
Using a simple lattice model with a 2 letter amino acid alphabet (H: hydrophobic and P: polar), we have explored the important biophysical problems of protein folding and protein design. Our formulation of these problems features a simple algebraic form for the Hamiltonian irrespective of the system size and composition. Since exact results are available from for lattice HP chains up to a size of 30, we were able to thoroughly validate our approach. The D-Wave advantage quantum annealer successfully identifies the ground state of the HP model protein chain in 100% of cases. For a few longer protein chains with up to 64 amino acids, where exact enumerations were not available but extensive Monte Carlo studies exist, the D-Wave hybrid annealer found the correct ground states within minutes, once again with a 100% success rate. Applying the same technique to the protein design problem, we found novel HP protein sequences with the same ground state as the largest systems we studied for folding. In contrast to the sequences used for folding, some of our newly found sequences had unique rather than degenerate ground states.