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

Ryan Babbush, Alejandro Perdomo‐Ortiz, Bryan O’Gorman, William G. Macready, Alán Aspuru‐GuzikarXiv 2012 · arXiv

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.

Introduction

Predicting the native state of a protein—its lowest-energy configuration—remains a fundamental challenge in computational biology. Even simplified lattice heteropolymer models, where amino acids are represented as beads on a grid, are NP-hard. The difficulty lies not just in the computational complexity but in the translation between physical energy landscapes and the discrete logic required by modern solvers. This paper bridges this gap by recasting protein folding as a Constraint Satisfaction Problem (CSP), enabling the use of powerful tools from computer science like linear programming, maximum satisfiability (SAT), and pseudo-boolean optimization (PBO).

Encoding Strategies for Lattice Models

The authors propose three primary strategies for encoding self-avoiding walks (SAWs) on a lattice, each offering different advantages in terms of bit efficiency and interaction complexity.

  1. Turn Ancilla Encoding: This method tracks relative turns (e.g., left, right, straight) between consecutive amino acids rather than absolute coordinates. It utilizes "ancilla" or helper bits to enforce the constraint that the walk must be self-avoiding (no overlaps).
  2. Turn Circuit Encoding: This is the most bit-efficient approach. It uses logic circuits, such as half-adders, to calculate the net displacement in each direction. If the displacement returns to zero, an overlap is detected. While compact, it results in high-locality terms that can be challenging for certain hardware.
  3. Diamond Encoding: This spatial approach maps bits to specific lattice sites. By fixing the first bead, the possible locations for subsequent beads are restricted to a "diamond" shape, significantly reducing the search space compared to a naive grid. Its primary advantage is being natively 2-local (QUBO), requiring only pairwise interactions.
Visual representation of the turn-based encoding for a self-avoiding walk on a 2D lattice.

Selecting the optimal encoding requires balancing three competing factors: bit efficiency (qubit count), locality (interaction complexity), and coefficient resolution (precision of coupling strengths). For instance, while Turn Circuit encoding uses fewer bits, it requires complex many-body terms. Conversely, Diamond encoding is hardware-friendly for quantum annealers but consumes more bits.

Decision flowchart for selecting an encoding strategy based on hardware constraints and problem size.

The paper also introduces "Locality Reduction," a technique to decompose high-order interactions (like 3-local or 4-local terms) into 2-local terms suitable for current quantum hardware. This is achieved by adding auxiliary variables, a process the authors optimized using greedy algorithms.

Key Results and Implementation

The methodology was validated using the Hydrophobic-Polar (HP) model and the more complex Miyazawa-Jernigan (MJ) model. As a proof of concept, the authors successfully mapped a 6-unit protein sequence (PSVKMA) onto a 2D lattice. This resulted in a 28x28 QUBO matrix, which was then implemented on a D-Wave quantum annealing system using up to 81 qubits. This work represents one of the first experimental demonstrations of lattice protein folding on quantum hardware.

Limitations and Future Outlook

Despite these advancements, scaling remains a hurdle as the underlying problem is NP-hard. Hardware limitations, particularly coupler resolution and the precision of penalty values, can affect the solver's ability to find the true global minimum. Future work will focus on extending these techniques to 3D lattices and generalizing these encoding "tricks" to other combinatorial optimization problems in the physical sciences.

Summary updated

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.
BibTeX
@misc{babbush2012construction,
  author = {Ryan Babbush and Alejandro Perdomo‐Ortiz and Bryan O’Gorman and William G. Macready and Alán Aspuru‐Guzik},
  title = {{Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing}},
  year = {2012},
  eprint = {1211.3422},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1211.3422},
}
Figure