Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization

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. Finally, we show how to reduce the locality of couplings in these energy functions so they can be realized as Hamiltonians on existing quantum annealing machines. We intend that this review be used as a case study for encoding related combinatorial optimization problems in a form suitable for adiabatic quantum optimization.

44 pages, 21 figures

References in corpus (5)

• On the construction of model Hamiltonians for adiabatic quantum computation and its application to finding low energy conformations of lattice protein models
• Non-perturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins
• Exact enumeration of self-avoiding walks
• Resource Efficient Gadgets for Compiling Adiabatic Quantum Optimization Problems
• A simple theory of protein folding kinetics

Cited by in corpus (21)

• Ising formulations of many NP problems
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum computational chemistry
• Quantum Chemistry in the Age of Quantum Computing
• A case study in programming a quantum annealer for hard operational planning problems
• Adiabatic Quantum Simulation of Quantum Chemistry
• Exploiting locality in quantum computation for quantum chemistry
• A NASA Perspective on Quantum Computing: Opportunities and Challenges
• Quantum Computing for Molecular Biology
• Bayesian Network Structure Learning Using Quantum Annealing
• A Quantum Annealing Approach for Fault Detection and Diagnosis of Graph-Based Systems
• Digitized-Counterdiabatic Quantum Algorithm for Protein Folding
• QFold: Quantum Walks and Deep Learning to Solve Protein Folding
• Polymer Physics by Quantum Computing
• Degeneracy, degree, and heavy tails in quantum annealing
• Accelerated chemical space search using a quantum-inspired cluster expansion approach
• Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
• The prospects of Monte Carlo antibody loop modelling on a fault-tolerant quantum computer
• Resource analysis of quantum algorithms for coarse-grained protein folding models
• Sampling a rare protein transition with a hybrid classical-quantum computing algorithm
• Scalable almost-linear dynamical Ising machines