Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing
View/ Open
Author
Perdomo-Ortiz, Alejandro
Macready, William
Published Version
https://doi.org/10.1002/9781118755815.ch05Metadata
Show full item recordCitation
Babbush, 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.ch05Abstract
Optimization 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.Other Sources
http://arxiv.org/abs/1211.3422Terms of Use
This article is made available under the terms and conditions applicable to Open Access Policy Articles, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#OAPCitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:10382938
Collections
- FAS Scholarly Articles [18292]
Contact administrator regarding this item (to report mistakes or request changes)