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.
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.
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
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.
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.
Quantum computing has progressed from a theoretical concept to a practical experimental technology. By processing information according to quantum mechanics rather than classical rules, quantum computers may offer advantages for certain problems. Although a few algorithms have proven speedups, it remains unclear where quantum computers will be practically useful, especially since current devices are noisy, small, and not yet fault tolerant. This thesis explores quantum computing for biophysically motivated combinatorial problems, with a focus on lattice protein models. In these simplified models, a protein is represented as a chain on a discrete lattice. Despite their simplicity, lattice proteins retain important features of real proteins, such as such as the folding of a chain with exponentially many possible shapes to a unique minimum-energy structure and steric constraints.To run lattice protein problems on quantum hardware, they must first be formulated using binary variables and objective functions. The latter typically contain soft constraints needed to ensure physical solutions. In Papers~\I--\II, we developed and extended a coordinate-based mapping for lattice protein folding, enabling D-Wave's hybrid quantum-classical annealer to fold both 2D hydrophobic-polar and 3D Miyazawa-Jernigan lattice proteins. In Paper~\III, we adapted the approach to the gate-based paradigm and showed how quadratic soft constraints could be removed by a mixer developed for the maximum-independent-set problem. Papers~\IV--\V addressed lattice protein design using quantum annealing, quantum approximate optimization algorithm, quantum alternating operator ansatz and hardware-efficient ansatz, while Paper~\VI extended the framework to multi-chain thermodynamics and the reconstruction of densities of states and heat-capacity features.Together, these papers show how folding, design, and multi-chain thermodynamics can be formulated, implemented, and analyzed using present-day quantum and hybrid hardware. A recurring limitation is the treatment of soft constraints. In quantum annealing, their high connectivity leads to error accumulation. On gate-based hardware, they increase circuit depth and sensitivity to noise. At the same time, temporary constraint violations can provide useful freedom during optimization. Further progress will therefore require improved formulations, algorithms and hardware that reduce the cost of enforcing physical solutions while retaining this flexibility.
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.