Investigating the potential for a limited quantum speedup on protein lattice problems
Benjamin, SC, Deane, CM, Jiye Shi, Outeiral, C, Morris, GM, Strahm, M
Abstract
Protein folding, the determination of the lowest-energy configuration of a\nprotein, is an unsolved computational problem. If protein folding could be\nsolved, it would lead to significant advances in molecular biology, and\ntechnological development in areas such as drug discovery and catalyst design.\nAs a hard combinatorial optimisation problem, protein folding has been studied\nas a potential target problem for adiabatic quantum computing. Although several\nexperimental implementations have been discussed in the literature, the\ncomputational scaling of these approaches has not been elucidated. In this\narticle, we present a numerical study of the (stoquastic) adiabatic quantum\nalgorithm applied to protein lattice folding. Using exact numerical modelling\nof small systems, we find that the time-to-solution metric scales exponentially\nwith peptide length, even for small peptides. However, comparison with\nclassical heuristics for optimisation indicates a potential limited quantum\nspeedup. Overall, our results suggest that quantum algorithms may well offer\nimprovements for problems in the protein folding and structure prediction\nrealm.