Protein folding, going from sequence to structure by minimizing an energy function, represents a difficult optimization problem.
Simplified lattice-based models for this problem can often provide qualitatively relevant results, but remain computationally challenging and
are therefore ideal testbeds for novel algorithms. A pioneering QUBO formulation of the folding problem for lattice proteins was given by
Perdomo and coworkers [1]}. They considered the HP model [2]}, where proteins are represented by linear
chains of \(N\)  hydrophobic (H) or polar (P) beads, residing on a lattice. Their binary variables encoded bead coordinates on the lattice,
which led to a relatively large number of required qubits even for short chains but a polynomial rather than exponential scaling with \(N\) .
