Related Experiment Video
Updated: Nov 14, 2025

A Protocol for Computer-Based Protein Structure and Function Prediction
Published on: November 3, 2011
Quantum Speedup for Protein Structure Prediction
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, [Formula: see text] and O(n2 logn) . 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.
Related Concept Videos
Protein Organization
The primary structure of a protein is its amino acid sequence....
Protein and Protein Structure
A protein's shape is critical to its function. For example, an enzyme...
Protein and Protein Structures
Protein Folding
Protein Structure Is Critical to Its Biological Function
Proteins perform a wide range of biological functions such as catalyzing chemical reactions, providing...
Protein Folding
Conservation of Protein Domains Over Different Proteins
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to...

