Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on NanoBioscience

Quantum Speedup for Protein Structure Prediction

Renata Wong, Weng-Long Chang

Published Mar 10, 2021• 32 citations
Publisher

Abstract

Protein structure prediction (PSP) predicts the native conformation for a given protein sequence. Classically, the problem has been shown to belong to the NP-complete complexity class. Its applications range from physics, through bioinformatics to medicine and quantum biology. It is possible however to speed it up with quantum computational methods, as we show in this paper. Here we develop a fast quantum algorithm for PSP in three-dimensional hydrophobic-hydrophilic model on body-centered cubic lattice with quadratic speedup over its classical counterparts. Given a protein sequence of n amino acids, our algorithm reduces the temporal and spatial complexities to, respectively, O(2\frac n2) and O(n2logn). With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed algorithm we successfully solve the problem on IBM quantum simulator involving 21 and 25 qubits. We confirm the experimentally obtained high probability of success in finding the desired conformation by calculating the theoretical probability estimations.

DOI
10.1109/tnb.2021.3065051

Related papers

Protein Structure Prediction with High Degrees of Freedom in a Gate-Based Quantum Computer

Jaya Vasavi Pamidimukkala, Soham Bopardikar, Avinash Dakshinamoorthy +3 more

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.

arXiv:2311.14141•Journal of Chemical Theory and Computation•Nov 6, 2024•9 citations

Efficient Quantum Protein Structure Prediction with Problem-Agnostic Ansatzes

Hanna Linn, Ruihao Li, Holden, Alexander +6 more

Accurately predicting protein structures from amino acid sequences remains a fundamental challenge in computational biology, with profound implications for understanding biological functions and enabling structure-based drug discovery. Quantum computing approaches based on coarse-grained lattice models combined with variational algorithms have been proposed as an initial step towards predicting protein structures using quantum computers. In this work, we introduce a more efficient quantum protein structure prediction workflow that bypasses the need for explicit Hamiltonian construction by employing a problem-agnostic ansatz. The ansatz is trained to minimize an energy-based cost function that can be efficiently computed on classical computers, eliminating the need for ancillary qubits and reducing circuit depth compared to previous Hamiltonian-based methods. This enables a more scalable approach for larger proteins and facilitates the inclusion of higher-order interactions, previously hard to achieve in quantum approaches. We validate our method by benchmarking a hardware-efficient ansatz on a large set of proteins with up to 26 amino acids, modeled on the tetrahedral, body-centered cubic, and face-centered cubic lattices, incorporating up to second-nearest-neighbor interactions. We assess the performance on both a noise-free simulator and the ibm_kingston quantum computer using a set of distinct metrics to probe different aspects of the prediction quality. These experiments push the boundaries of quantum methods for protein structure prediction, targeting sequences that are longer than those typically addressed in prior studies. Overall, the results highlight the scalability and versatility of our approach, while also identifying key areas for improvement to inform future algorithm development and hardware advancements.

arXiv:2509.18263•Sep 22, 2025•0 citations

Resource-efficient quantum algorithm for protein folding

Anton Robert, Panagiotis Kl. Barkoutsos, Stefan Woerner +1 more

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 $${\mathcal{O}}({N}^{4})$$ 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.

arXiv:1908.02163•npj Quantum Information•Feb 17, 2021•202 citations

Quantum Bioinformatics: Protein Structure Prediction Based on Quantum Entanglement

Jincheng Zhang

This paper presents a novel approach to protein structure prediction leveraging the principles of quantum entanglement. Traditional protein structure prediction methods are often limited by the computational complexity of simulating large biomolecular systems. We propose a framework that utilizes quantum entanglement to model the complex correlations inherent in protein folding, potentially overcoming these limitations. The core idea involves translating the amino acid sequence of a protein into a quantum state and employing quantum computation, specifically entanglement-based algorithms, to predict the protein's three-dimensional structure. The theoretical framework outlines the transformation process, the quantum algorithm design, and the methods for interpreting the results. We explore the potential advantages of this approach, focusing on its ability to capture long-range interactions and conformational flexibility that are difficult to model accurately with classical methods. The ultimate goal is to establish a new paradigm for protein structure prediction, offering improved accuracy and efficiency.

•Aug 29, 2026•0 citations

Quantum Bioinformatics and Protein Structure Prediction

Jincheng Zhang

This paper explores the potential of integrating quantum computing with bioinformatics to revolutionize protein structure prediction. Traditional methods face significant computational challenges, particularly with complex proteins. We propose a novel approach leveraging quantum algorithms to accelerate molecular simulations and integrate biological data for enhanced prediction accuracy. The core claim centers on the ability to achieve more precise protein structure determination through this combined methodology. Specifically, we outline a mechanism utilizing quantum algorithms to drastically reduce simulation times and subsequently, incorporate biological information for optimization. This represents a new paradigm in protein structure prediction, offering a pathway to accurately model protein folding and dynamics. The work delves into the theoretical foundations and potential algorithmic implementations, laying the groundwork for future research and development in this exciting field. The focus is on the computational speedup offered by quantum approaches and the strategic integration with existing bioinformatics techniques.

•Sep 6, 2026•0 citations

Efficient quantum algorithm for lattice protein folding

Youle Wang, Xiangzhen Zhou

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 Science and Technology•Dec 17, 2024•8 citations
Protein structure prediction (PSP) predicts the native conformation for a given protein sequence. Classically, the problem has been shown to belong to the NP-complete complexity class. Its applications range from physics, through bioinformatics to medicine and quantum biology. It is possible however to speed it up with quantum computational methods, as we show in this paper. Here we develop a fast quantum algorithm for PSP in three-dimensional hydrophobic-hydrophilic model on body-centered cubic lattice with quadratic speedup over its classical counterparts. Given a protein sequence of n amino acids, our algorithm reduces the temporal and spatial complexities to, respectively, O(2\frac n2) and O(n2logn). With respect to oracle-related quantum algorithms for the NP-complete problems, we identify our algorithm as optimal. To justify the feasibility of the proposed algorithm we successfully solve the problem on IBM quantum simulator involving 21 and 25 qubits. We confirm the experimentally obtained high probability of success in finding the desired conformation by calculating the theoretical probability estimations.
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.
Accurately predicting protein structures from amino acid sequences remains a fundamental challenge in computational biology, with profound implications for understanding biological functions and enabling structure-based drug discovery. Quantum computing approaches based on coarse-grained lattice models combined with variational algorithms have been proposed as an initial step towards predicting protein structures using quantum computers. In this work, we introduce a more efficient quantum protein structure prediction workflow that bypasses the need for explicit Hamiltonian construction by employing a problem-agnostic ansatz. The ansatz is trained to minimize an energy-based cost function that can be efficiently computed on classical computers, eliminating the need for ancillary qubits and reducing circuit depth compared to previous Hamiltonian-based methods. This enables a more scalable approach for larger proteins and facilitates the inclusion of higher-order interactions, previously hard to achieve in quantum approaches. We validate our method by benchmarking a hardware-efficient ansatz on a large set of proteins with up to 26 amino acids, modeled on the tetrahedral, body-centered cubic, and face-centered cubic lattices, incorporating up to second-nearest-neighbor interactions. We assess the performance on both a noise-free simulator and the ibm_kingston quantum computer using a set of distinct metrics to probe different aspects of the prediction quality. These experiments push the boundaries of quantum methods for protein structure prediction, targeting sequences that are longer than those typically addressed in prior studies. Overall, the results highlight the scalability and versatility of our approach, while also identifying key areas for improvement to inform future algorithm development and hardware advancements.
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){\mathcal{O}}({N}^{4})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.
This paper presents a novel approach to protein structure prediction leveraging the principles of quantum entanglement. Traditional protein structure prediction methods are often limited by the computational complexity of simulating large biomolecular systems. We propose a framework that utilizes quantum entanglement to model the complex correlations inherent in protein folding, potentially overcoming these limitations. The core idea involves translating the amino acid sequence of a protein into a quantum state and employing quantum computation, specifically entanglement-based algorithms, to predict the protein's three-dimensional structure. The theoretical framework outlines the transformation process, the quantum algorithm design, and the methods for interpreting the results. We explore the potential advantages of this approach, focusing on its ability to capture long-range interactions and conformational flexibility that are difficult to model accurately with classical methods. The ultimate goal is to establish a new paradigm for protein structure prediction, offering improved accuracy and efficiency.
This paper explores the potential of integrating quantum computing with bioinformatics to revolutionize protein structure prediction. Traditional methods face significant computational challenges, particularly with complex proteins. We propose a novel approach leveraging quantum algorithms to accelerate molecular simulations and integrate biological data for enhanced prediction accuracy. The core claim centers on the ability to achieve more precise protein structure determination through this combined methodology. Specifically, we outline a mechanism utilizing quantum algorithms to drastically reduce simulation times and subsequently, incorporate biological information for optimization. This represents a new paradigm in protein structure prediction, offering a pathway to accurately model protein folding and dynamics. The work delves into the theoretical foundations and potential algorithmic implementations, laying the groundwork for future research and development in this exciting field. The focus is on the computational speedup offered by quantum approaches and the strategic integration with existing bioinformatics techniques.
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.