Folding HP Proteins on a Quantum Annealer

Abstract

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.

Popular Abstract (Swedish)

Kvantdatorer har fått mycket fokus i media de senaste åren på grund av sin potentiella förmåga att lösa problem som är för tidskrävande för att låta sig lösas på klassiska datorer. Kvantdatorer skiljer sig i grunden från dagens datorer, genom att bygga på gåtfulla kvantmekaniska egenskaper. En sådan är kvantsuperposition, som innebär att en partikel kan vara i flera kvanttillstånd samtidigt. Antag, till exempel, att uppgiften är att finna vägen ut ur en labyrint. En klassisk dator löser detta problem genom att testa alla möjliga vägar en efter en. En kvantdator skulle, genom kvantsuperposition, istället kunna testa alla vägar samtidigt, och därmed lösa problemet snabbare.


Att bygga en kvantdator är en utmaning eftersom processorn måste vara isolerad från världen runtomkring för att behålla sina kvantmekaniska egenskaper. De stora satsningarna som för närvarande görs fokuserar därför inte bara på generella kvantdatorer, utan även på mer specialicerade sådana för särskilda ändamål. Ett viktigt exempel är adiabatiska kvantdatorer för optimeringsproblem. En sådan dator består av ett kvantsystem där energifunktionen av systemet kan regleras. Initialt kan kvantsystemet antas befinna i ett tillstånd som i labyrintexemplet motsvarar en blandning av alla möjliga vägar. Det går att visa att tillståndet sedan kan ändras till ett som motsvarar vägen ut ur labyrinten, genom att ändra energifunktionen. Om denna ändring sker långsamt nog hittar vi vägen ut varje gång. Dessvärre kan förändringen i praktiken inte ske hur långsamt som helst, eftersom processorn måste hållas helt isolerad. Detta medför att den sökta vägen ut inte kommer hittas med 100\% sannolikhet.

I detta projekt försöker vi använda en adiabatisk kvantdator för att bestämma strukturen av förenklade proteiner. Proteinstrukturberäkningar är ett svårt men viktigt problem, eftersom kännedom om strukturen är avgörande för att förutspå hur exempelvis enzymproteiner fungerar. I vår förenklade modell kan proteinet ses som ett kapat pärlhalsband, där pärlorna representerar aminosyror. Dessutom tillåter vi bara pärlorna att vara på specifika platser, precis som schackpjäser bara får vara på en utav 64 rutor på schackbrädet. Trots denna restriktion kan pärlhalsbandet anta en mängd olika former. Bland dessa söker vi den struktur som har lägst energi. Försök att lösa detta optimeringsproblem på en kvantdator har gjorts förut. I denna uppsats utvecklar vi en ny formulering av strukturbestämmningsproblemet, väl lämpad för kvantdatorer. Vi testar med framgång metoden på en kvantdator utvecklad av D-Wave Systems, för adiabatiska kvantberäkningar.

• author: Knuthson, Lucas
• supervisor: Anders Irbäck
• organization: Computational Biology and Biological Physics - Undergoing reorganization
• course: FYTM04 20221
• year: 2022
• type: H2 - Master's Degree (Two Years)
• subject: Physics and Astronomy
• language: English
• id: 9083302
• date added to LUP: 2022-06-21 11:22:14
• date last changed: 2022-06-29 15:29:39