PDF《Finding low-energy conformations of》

Finding low-energy conformations of lattice protein models by quantum annealing Alejandro Perdomo-Ortiz1 , Neil Dickson2 , Marshall Drew-Brook2 , Geordie Rose2 &

Ala ?n Aspuru-Guzik1

1 Department of Chemistry and Chemical Biology, Harvard University,

12 Oxford Street, Cambridge, MA 02138, USA,

2 D-Wave Systems, Inc.

, 100-4401 Still Creek Drive, Burnaby, British Columbia V5C 6G9, Canada. Lattice protein folding models are a cornerstone of computational biophysics. Although these models are a coarse grained representation, they provide useful insight into the energy landscape of natural proteins. Finding low-energy threedimensional structures is an intractable problem even in the simplest model, the Hydrophobic-Polar (HP) model. Description of protein-like properties are more accurately described by generalized models, such as the one proposed by Miyazawa and Jernigan (MJ), which explicitly take into account the unique interactions among all

20 amino acids. There is theoretical and experimental evidence of the advantage of solving classical optimization problems using quantum annealing over its classical analogue (simulated annealing). In this report, we present a benchmark implementation of quantum annealing for lattice protein folding problems (six different experiments up to

81 superconducting quantum bits). This first implementation of a biophysical problem paves the way towards studying optimization problems in biophysics and statistical mechanics using quantum devices. T he search for more efficient optimization algorithms is an important endeavor with prevalence on many disciplines ranging from the social sciences to the physical and natural sciences. Belonging to the latter, the protein folding problem1C7 consists of finding the lowest free-energy configuration or, equivalently, the native structure of a protein given its amino-acid sequence. Knowing how proteins fold elucidate their three-dimensional structure-function relationship which is crucial to the understanding of enzymes and for the treatment of misfolded-protein diseases such as Alzheimer'

s, Huntington'

s, and Parkinson'

s disease. Due to the high computa- tional cost of modeling proteins in atomistic detail8,9 , coarse-grained descriptions of the protein folding problem, such as those found in lattice models, provide valuable insight about the folding mechanisms2,4C6,10 . Harnessing quantum-mechanical effects to speed up the solving of classical optimization problems is at the heart of quantum annealing algorithms (QA)11C15 . There is theoretical11,12,16C18 and experimental19 evidence of the advantage of solving classical optimization problems using QA11C14 over its classical analogue (simulated anneal- ing20 ). In QA, quantum mechanical tunneling allows for more efficient exploration of difficult potential energy landscapes such as that of classical spin-glass problems. In our implementation of lattice folding, quantum fluctuations (tunneling) occurs between states representing different model protein conformations or folds. The theoretical challenge is to efficiently map the hard computational problem of interest (e.g., lattice folding) to a classical spin-glass Hamiltonian: such mapping requiring a polynomial number of quantum bits (qubits) with the size of the problem (protein length) is described elsewhere21 . Here we present a new mapping which, due to its exponential scaling with problem size, is not intended for large instances. The proposed mapping employs very few qubits for small problem instances, making it ideal for this first experimental demonstration and imple- mentation on current quantum devices22 . A combination of the existing polynomial mapping21 and more advanced quantum devices would allow for the simulation of much larger instances of lattice folding and other related optimization problems. Solving arbitrary problem instances requires a programmable quantum device to implement the correspond- ing classical Hamiltonian. We employ quantum annealing on the programmable device to obtain low-energy conformations of the protein model. We emphasize that nothing quantum mechanical is implied about the protein or its folding process;