Fast quantum algorithm for protein structure prediction in hydrophobic-hydrophilic model

In its unfolded form, a protein is a linear sequence of amino acids. Protein structure prediction attempts to find the native conformation for a given protein, which has potential applications in drug and vaccine development. Classically, protein structure prediction is an NP-complete, unsolved computational problem. Quantum computing however promises to improve upon the performance of classical algorithms. Here we develop a quantum algorithm in hydrophobic-hydrophilic model on two-dimensional square lattice to solve the problem for any sequence of length N amino acids with a quadratic speedup over its classical counterpart. This speedup is achieved using Grover's quantum search algorithm. The algorithm can be used for amino acid sequences of arbitrary length. It consists of three stages: (1) preparation of a superposition state that encodes all possible 2^2(N−1) conformations, (2) calculation of coordinates and energy for each possible conformation in parallel, and (3) finding the conformation with the minimal energy. The asymptotic complexity with regard to space is O(N³), while the obtained speedup is quadratic compared to the classical counterpart. We have successfully simulated the algorithm on the IBM Quantum's qasm simulator using Qiskit SDK. Also, we have further confirmed the correctness of the results by calculating theoretical probability of finding the right conformation.