Gate-based universal quantum computers form a rapidly evolving field of quantum computing hardware technology. In previous work, we presented a quantum algorithm for lattice protein folding on a cubic lattice, tailored for quantum annealers. In this paper, we introduce a novel approach for solving the lattice protein folding problem on universal gate-based quantum computing architectures. Lattice protein models are coarse-grained representations of proteins that have been used extensively over the past thirty years to examine the principles of protein folding and design.These models can be used to explore a vast number of possible protein conformations and to infer structural properties of more complex atomistic protein structures. We formulate the problem as a quantum alternating operator ansatz, a member of the wider class of variational quantum/classical hybrid algorithms. To increase the probability of sampling the ground state, we propose splitting the optimization problem into hard and soft constraints. This enables us to use a previously under-utilised component of the variational algorithm to constrain the search to the subspace of solutions that satisfy the hard constraints.
Gate-based universal quantum computers form a rapidly evolving field of quantum computing hardware technology. In previous work, we presented a quantum algorithm for lattice protein folding on a cubic lattice, tailored for quantum annealers. In this paper, we introduce a novel approach for solving the lattice protein folding problem on universal gate-based quantum computing architectures. Lattice protein models are coarse-grained representations of proteins that have been used extensively over the past thirty years to examine the principles of protein folding and design.These models can be used to explore a vast number of possible protein conformations and to infer structural properties of more complex atomistic protein structures. We formulate the problem as a quantum alternating operator ansatz, a member of the wider class of variational quantum/classical hybrid algorithms. To increase the probability of sampling the ground state, we propose splitting the optimization problem into hard and soft constraints. This enables us to use a previously under-utilised component of the variational algorithm to constrain the search to the subspace of solutions that satisfy the hard constraints.
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 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.
Lattice models have been used extensively over the past thirty years to examine the principles of protein folding and design. These models can be used to determine the conformation of the lowest energy fold out of a large number of possible conformations. However, due to the size of the conformational space, new algorithms are required for folding longer proteins sequences. Preliminary work was performed by Babbush et al. (2012) to fold a small peptide on a planar lattice using a quantum annealing device. We extend this work by providing improved Ising-type Hamiltonian encodings for the problem of finding the lowest energy conformation of a lattice protein. We demonstrate a decrease in quantum circuit complexity from quadratic to quasilinear in certain cases. Additionally, we generalize to three spatial dimensions in order to obtain results with higher correlation to the actual atomistic 3D structure of the protein and outline our heuristic approach for splitting large problem instances into smaller subproblems that can be directly solved with the current D-Wave 2000Q architecture. To the best of our knowledge, this work sets a new record for lattice protein folding on a quantum annealer by folding Chignolin (10 residues) on a planar lattice and Trp-Cage (8 residues) on a cubic lattice.
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 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.