Folding HP Proteins on a Quantum Annealer

Sammanfattning: Quantum annealing provides a promising avenue for obtaining good approximate solutions to difficult optimization problems. Protein folding represents one such problem. For testing novel algorithms and technologies, simplified lattice models are well suited, as they represent considerable computational challenges despite their simplicity. One such model is the HP model, where the protein is represented as a self-avoiding chain of hydrophobic (H) and polar (P) beads residing on a lattice. Previous attempts at folding lattice proteins on a quantum annealer used chain growth techniques, where self-avoidance is tricky to implement. In this project, we develop a novel spin representation of the HP model suited for quantum annealing. This approach naturally handles self-avoidance, and performs well in terms of scaling properties with chain length. The approach is implemented using classical simulated annealing, a hybrid quantum-classical approach and pure quantum annealing. In the pure quantum annealing case, we successfully fold the largest chain done on a quantum computer. However, we also notice that pure quantum annealing can not match simulated annealing yet. In contrast, the hybrid approach is able to solve the largest HP chains, $N=30$, where $N$ is the number of beads, for which exact solutions are known. Moreover, it outperforms classical simulated annealing using the same encoding, both in terms of success rate and solution time, and successfully compare with the best-known solutions for larger chains, $N=48$ and $N=64$. Further, we see that the encoding is robust in terms of changes in the parameters required to constrain the spin system to chain-like configurations. The calculations were performed on a D-Wave Advantage quantum annealer.