Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing

This chapter presents a general construction of the free energy function for the two-dimensional lattice heteropolymer model widely used to study the dynamics of proteins. It demonstrates how to map the lattice heteropolymer problem into forms that can be solved by using different types of technology and algorithms. The embedding strategies presented here apply to many discrete optimization problems. Mapping these problems to a constraint programming problem is a three-step process. The chapter provides a brief description of the process and expands upon each step as it applies to lattice folding. It explains the “circuit” construction that provides optimal efficiency at the cost of introducing high-ordered many-body terms. Finally, the chapter demonstrates the final steps required to embed a small instance of a particular lattice protein problem into a quadratic unconstrained binary optimization (QUBO) Hamiltonian.