  Protein folding -- the problem of predicting the spatial structure of a
protein given its sequence of amino-acids -- has attracted considerable
research effort in biochemistry in recent decades. In this work, we explore the
potential of quantum computing to solve a simplified version of protein
folding. More precisely, we numerically investigate the performance of a
variational quantum algorithm, the Quantum Approximate Optimization Algorithm
(QAOA), in sampling low-energy conformations of short peptides. We start by
benchmarking the algorithm on an even simpler problem: sampling self-avoiding
walks, which is a necessary condition for a valid protein conformation.
Motivated by promising results achieved by QAOA on this problem, we then apply
the algorithm to a more complete version of protein folding, including a
simplified physical potential. In this case, based on numerical simulations on
20 qubits, we find less promising results: deep quantum circuits are required
to achieve accurate results, and the performance of QAOA can be matched by
random sampling up to a small overhead. Overall, these results cast serious
doubt on the ability of QAOA to address the protein folding problem in the near
term, even in an extremely simplified setting. We believe that the approach and
conclusions presented in this work could offer valuable methodological insights
on how to systematically evaluate variational quantum optimization algorithms
on real-world problems beyond protein folding.
