Challenging Alphafold, Shanghai University Solves Protein Folding Problem with Hybrid Quantum Algorithm

An international joint team of the University of the Basque Country (Spain), Kipu Quantum (Germany), Shanghai University and the Basque Science Foundation has solved the problem of protein folding on a tetrahedral lattice using a combination of classical and quantum computing techniques.

Protein folding problem = NP-hard optimization problem

The protein folding problem involves finding the lowest energy configuration for a given amino acid sequence, an NP-hard optimization problem often encountered in fields such as chemistry, biology and drug design, the researchers said.

Proteins are important for a variety of functions in living organisms, and their folding mechanisms are important for understanding diseases caused by misfolding and have the potential to open up new treatments for diseases associated with protein misfolding, such as Alzheimer's, Huntington's, and Parkinson's diseases.

Because of their computational complexity, classical computers struggle to deal with the folding of proteins with complex, subtly varying three-dimensional shapes. The researchers suggest that this particular type of complexity makes the problem a good candidate for quantum computing solutions.

Parametric quantum circuit (PQC) with high probability of experimental success

"In general, protein folding is modeled by a suitable two- or three-dimensional lattice, while allowing amino acids to be placed where the interaction energy is minimal. With an appropriate encoding scheme, this problem can be translated into a problematic Hamiltonian quantity whose ground state shows the configuration of the protein in question in a given lattice."

To solve this problem, the researchers' algorithm uses a parametric quantum circuit (PQC) quantum circuit, inspired by the anti-adiabatic (CD) protocol, in combination with a classical optimization procedure that optimizes the PQC parameters. The algorithm was tested on various quantum hardware platforms using up to 17 quantum bits on proteins with up to nine amino acids, including trapped ions, Google and IBM's superconducting circuits.

Output probability distribution of N = 9 quantum bits after implementing the optimal circuit on (a) IBM ibmq guadalupe and (b) Google's quantum virtual machine rainbow. Among them, experiment (a) was performed 8192 times and experiment (b) was performed 10,000 times.

Output probability distributions of N=13 AVDINNNA protein and N=17 CYIQNCPLG protein on trapped ion systems.

The results show that the algorithm has a high probability of success and is suitable for use in the NISQ (noise-containing intermediate-scale quantum) era: because quantum computers have a limited number of quantum bits and are prone to noise.

The team said, "This work paves the way for implementing question heuristic answers to industrial examples in the current NISQ era by using digitized inverse two-dimensional protocols. We believe this quantum algorithm can be extended to other relevant applications."

Challenges remain

Challenges remain, however, including sensitivity to initial parameters and selecting the appropriate CD term from the adiabatic metrology pool. Overcoming these challenges could lead to the introduction of quanta in real-world use, even beyond the impressive achievements of some of today's supercomputers in sorting out protein folding problems, the researchers added.

"We believe this work advances quantum computing and brings us one step closer to actual quantum advantages that would have to challenge the success of classical computing, including the recent AlphaFold achievement."

Link to paper：

https://arxiv.org/pdf/2212.13511.pdf

Reference link：

https://thequantuminsider.com/2022/12/30/hybrid-quantum-classical-algorithm-shows-promise-for-unraveling-the-protein-folding-problem/