Protein folding, the determination of the lowest-energy configuration of a
protein, is an unsolved computational problem. If protein folding could be
solved, it would lead to significant advances in molecular biology, and
technological development in areas such as drug discovery and catalyst design.
As a hard combinatorial optimisation problem, protein folding has been studied
as a potential target problem for adiabatic quantum computing. Although several
experimental implementations have been discussed in the literature, the
computational scaling of these approaches has not been elucidated. In this
article, we present a numerical study of the (stoquastic) adiabatic quantum
algorithm applied to protein lattice folding. Using exact numerical modelling
of small systems, we find that the time-to-solution metric scales exponentially
with peptide length, even for small peptides. However, comparison with
classical heuristics for optimisation indicates a potential limited quantum
speedup. Overall, our results suggest that quantum algorithms may well offer
improvements for problems in the protein folding and structure prediction
realm.
q-bio.BM
,quant-ph
