  Quantum annealing is a promising approach for obtaining good approximate
solutions to difficult optimization problems. Folding a protein sequence into
its minimum-energy structure represents such a problem. For testing new
algorithms and technologies for this task, the minimal lattice-based HP model
is well suited, as it represents a considerable challenge despite its
simplicity. The HP model has favorable interactions between adjacent, not
directly bound hydrophobic residues. Here, we develop a novel spin
representation for lattice protein folding tailored for quantum annealing. With
a distributed encoding onto the lattice, it differs from earlier attempts to
fold lattice proteins on quantum annealers, which were based upon chain growth
techniques. With our encoding, the Hamiltonian by design has the quadratic
structure required for calculations on an Ising-type annealer, without having
to introduce any auxiliary spin variables. This property greatly facilitates
the study of long chains. The approach is robust to changes in the parameters
required to constrain the spin system to chain-like configurations, and
performs very well in terms of solution quality. The results are evaluated
against existing exact results for HP chains with up to $N=30$ beads with 100%
hit rate, thereby also outperforming classical simulated annealing. In
addition, the method allows us to recover the lowest known energies for $N=48$
and $N=64$ HP chains, with similar hit rates. These results are obtained by the
commonly used hybrid quantum-classical approach. For pure quantum annealing,
our method successfully folds an $N=14$ HP chain. The calculations were
performed on a D-Wave Advantage quantum annealer.
