Identifying minimum-energy structures of lattice proteins is a challenging discrete optimization problem. Quantum approaches such as analog quantum annealing and the gate-based quantum approximate optimization algorithm (QAOA) can address this problem after mapping it to a binary representation, which typically involves introducing penalty terms to enforce valid chain configurations. However, in this and many related problems, the use of quadratic penalty terms can be avoided by restricting the search space to independent sets in a conflict graph and using a QAOA mixer designed for the maximum independent set problem. In this work, we implement and explore this QAOA variant for lattice protein folding. Here, the objective function consists solely of the protein energy together with a simple linear bias term, without quadratic penalties. We validate this approach through classical simulations of the quantum circuits for lattice proteins of lengths $N=4$ and $N=6$. To explore larger systems, we further introduce a heuristic iterative local-search scheme, with which we successfully fold lattice proteins with lengths up to $N=14$ using local subgraphs with at most 26 qubits.
Identifying minimum-energy structures of lattice proteins is a challenging discrete optimization problem. Quantum approaches such as analog quantum annealing and the gate-based quantum approximate optimization algorithm (QAOA) can address this problem after mapping it to a binary representation, which typically involves introducing penalty terms to enforce valid chain configurations. However, in this and many related problems, the use of quadratic penalty terms can be avoided by restricting the search space to independent sets in a conflict graph and using a QAOA mixer designed for the maximum independent set problem. In this work, we implement and explore this QAOA variant for lattice protein folding. Here, the objective function consists solely of the protein energy together with a simple linear bias term, without quadratic penalties. We validate this approach through classical simulations of the quantum circuits for lattice proteins of lengths N=4 and N=6. To explore larger systems, we further introduce a heuristic iterative local-search scheme, with which we successfully fold lattice proteins with lengths up to N=14 using local subgraphs with at most 26 qubits.
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.
Quantum heuristics have shown promise in solving various optimization problems, including lattice protein folding. Equally relevant is the inverse problem, protein design, where one seeks sequences that fold to a given target structure. The latter problem is often split into two steps: (i) searching for sequences that minimize the energy in the target structure, and (ii) testing whether the generated sequences fold to the desired structure. Here, we investigate the utility of variational quantum algorithms for the first of these two steps on today’s noisy intermediate-scale quantum devices. We focus on the sequence optimization task, which is less resource-demanding than folding computations. We test the quantum approximate optimization algorithm and variants of it, with problem-informed quantum circuits, as well as the hardware-efficient ansatz, with problem-agnostic quantum circuits. While the former approach, with a careful choice of mixer, yields good results in noiseless simulations (success probability ≥ 0.95 in all instances), its performance drops drastically under noise. With the problem-agnostic circuits, which are more compatible with hardware constraints, improved performance is observed in noisy simulations, compared to their problem-informed counterparts. When running the problem-agnostic circuits on a real quantum device, with parameters taken from simulations, we obtain a significant success probability ( ≥ 0.2 ) in most instances.
Protein folding -- the problem of predicting the spatial structure of a protein given its sequence of amino-acids -- has attracted considerable research effort in biochemistry in recent decades. In this work, we explore the potential of quantum computing to solve a simplified version of protein folding. More precisely, we numerically investigate the performance of a variational quantum algorithm, the Quantum Approximate Optimization Algorithm (QAOA), in sampling low-energy conformations of short peptides. We start by benchmarking the algorithm on an even simpler problem: sampling self-avoiding walks, which is a necessary condition for a valid protein conformation. Motivated by promising results achieved by QAOA on this problem, we then apply the algorithm to a more complete version of protein folding, including a simplified physical potential. In this case, based on numerical simulations on 20 qubits, we find less promising results: deep quantum circuits are required to achieve accurate results, and the performance of QAOA can be matched by random sampling up to a small overhead. Overall, these results cast serious doubt on the ability of QAOA to address the protein folding problem in the near term, even in an extremely simplified setting. We believe that the approach and conclusions presented in this work could offer valuable methodological insights on how to systematically evaluate variational quantum optimization algorithms on real-world problems beyond protein folding.
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.
Protein folding has been one of the most difficult problems for over a half-century,The random thermal motions causing conformational changes that lead energetically downhill towards the native structure, a principle captured in funnel-shaped energy landscapes.Unfolded polypeptides have a wide range of possible conformations. The search problem becomes intractable for classical computers due to the exponential growth of potential conformations with chain length. So far, there is theoretical and experimental evidence that solving such optimization problems using Quantum Computing approaches such as Quantum Annealing, VQE, and QAOA has an advantage. Although Google's DeepMind-AlphaFold has accomplished much,But we can go even further with the quantum approach.Here we show how to predict structure of protein as well as RNA folding using the Variational Quantum Eigensolver with Conditional Value at Risk (CVaR) expectation values for the solution of the problem and for finding the minimum configuration energy and our task is to identify a protein's minimal energy structure. The protein's structure is optimized to reduce energy. Also making sure that all physical constraints are met and encoding the protein folding problem into a qubit operator.