Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing
MetadataShow full item record
CitationBabbush, R., Perdomo-Ortiz, A., O'Gorman, B., Macready, W. and Aspuru-Guzik, A. (2014) Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing, in Advances in Chemical Physics: Volume 155 (eds S. A. Rice and A. R. Dinner), John Wiley & Sons, Inc., Hoboken, New Jersey. doi: 10.1002/9781118755815.ch05
AbstractOptimization problems associated with the interaction of linked particles are at the heart of polymer science, protein folding and other important problems in the physical sciences. In this review we explain how to recast these problems as constraint satisfaction problems such as linear programming, maximum satisfiability, and pseudo-boolean optimization. By encoding problems this way, one can leverage substantial insight and powerful solvers from the computer science community which studies constraint programming for diverse applications such as logistics, scheduling, artificial intelligence, and circuit design. We demonstrate how to constrain and embed lattice heteropolymer problems using several strategies. Each strikes a unique balance between number of constraints, complexity of constraints, and number of variables. In addition, each strategy has distinct advantages and disadvantages depending on problem size and available resources. Finally, we show how to reduce the locality of couplings in these energy functions so they can be realized as Hamiltonians on existing adiabatic quantum annealing machines.
Citable link to this pagehttp://nrs.harvard.edu/urn-3:HUL.InstRepos:10382938
- FAS Scholarly Articles