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

DSpace/Manakin Repository

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

Citable link to this page

 

 
Title: Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing
Author: Babbush, Ryan Joseph; Perdomo-Ortiz, Alejandro; O'Gorman, Bryan Andrew; Macready, William; Aspuru-Guzik, Alan

Note: Order does not necessarily reflect citation order of authors.

Citation: 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.ch05
Full Text & Related Files:
Abstract: 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.
Published Version: 10.1002/9781118755815.ch05
Other Sources: http://arxiv.org/abs/1211.3422
Terms 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#OAP
Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:10382938
Downloads of this work:

Show full Dublin Core record

This item appears in the following Collection(s)

 
 

Search DASH


Advanced Search
 
 

Submitters