Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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‐Guzik

Published Nov 14, 2012• 3 citations
OpenAlex

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.

Related papers

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 +2 more

This chapter presents a general construction of the free energy function for the two-dimensional lattice heteropolymer model widely used to study the dynamics of proteins. It demonstrates how to map the lattice heteropolymer problem into forms that can be solved by using different types of technology and algorithms. The embedding strategies presented here apply to many discrete optimization problems. Mapping these problems to a constraint programming problem is a three-step process. The chapter provides a brief description of the process and expands upon each step as it applies to lattice folding. It explains the “circuit” construction that provides optimal efficiency at the cost of introducing high-ordered many-body terms. Finally, the chapter demonstrates the final steps required to embed a small instance of a particular lattice protein problem into a quadratic unconstrained binary optimization (QUBO) Hamiltonian.

arXiv:1211.3422•Advances in chemical physics•Apr 4, 2014•49 citations

Quantum Annealing for Combinatorial Optimization: Foundations, Architectures, Benchmarks, and Emerging Directions

Rudraksh Sharma, Ravi Katukam, Arjun Nagulapally

Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.

quant-pharXiv:2602.03101•International Journal for Research in Applied Science and Engineering Technology•Feb 4, 2026•3 citations

Quantum algorithms for compact polymer thermodynamics

Davide Rattacaso, Daniel Jaschke, Antonio Trovato +2 more

Efficient sampling from ensembles of Hamiltonian cycles is critical for predicting the thermodynamic properties of compact polymers, with applications including modeling protein and RNA folding and designing soft materials. Although classical Monte Carlo methods are widely regarded as the standard approach, their efficiency is strongly limited when applied to compact polymers. In this work, we enable a quadratic speedup in the estimation of thermodynamic properties of maximally compact polymers and heteropolymers by quantum computation. To this end, we encode the target thermodynamic ensemble into the amplitudes of a quantum state, i.e., a quantum sample, which can be processed via amplitude amplification. Using quantum equational reasoning, we construct a local parent Hamiltonian whose unique ground state realizes a quantum sample of all Hamiltonian cycles. This state can be prepared on quantum hardware using ground-state preparation methods, such as quantum annealing, and subsequently manipulated to generate quantum samples of polymers and heteropolymers at a target temperature. Finally, we approximate the quantum sample as a tensor network, revealing an entanglement area law. For fixed-width rectangular lattices, we obtain a time-efficient and compact encoding of the full ensemble of Hamiltonian cycles, enabling the efficient evaluation of expectation values, partition functions, and configuration probabilities via tensor contractions, without resorting to sampling.

quant-pharXiv:2603.12334•Mar 16, 2026•1 citation

Solving lattice protein problems with quantum computing

Lucas Knuthson

Quantum computing has progressed from a theoretical concept to a practical experimental technology. By processing information according to quantum mechanics rather than classical rules, quantum computers may offer advantages for certain problems. Although a few algorithms have proven speedups, it remains unclear where quantum computers will be practically useful, especially since current devices are noisy, small, and not yet fault tolerant. This thesis explores quantum computing for biophysically motivated combinatorial problems, with a focus on lattice protein models. In these simplified models, a protein is represented as a chain on a discrete lattice. Despite their simplicity, lattice proteins retain important features of real proteins, such as such as the folding of a chain with exponentially many possible shapes to a unique minimum-energy structure and steric constraints.To run lattice protein problems on quantum hardware, they must first be formulated using binary variables and objective functions. The latter typically contain soft constraints needed to ensure physical solutions. In Papers~\I--\II, we developed and extended a coordinate-based mapping for lattice protein folding, enabling D-Wave's hybrid quantum-classical annealer to fold both $2$D hydrophobic-polar and $3$D Miyazawa-Jernigan lattice proteins. In Paper~\III, we adapted the approach to the gate-based paradigm and showed how quadratic soft constraints could be removed by a mixer developed for the maximum-independent-set problem. Papers~\IV--\V addressed lattice protein design using quantum annealing, quantum approximate optimization algorithm, quantum alternating operator ansatz and hardware-efficient ansatz, while Paper~\VI extended the framework to multi-chain thermodynamics and the reconstruction of densities of states and heat-capacity features.Together, these papers show how folding, design, and multi-chain thermodynamics can be formulated, implemented, and analyzed using present-day quantum and hybrid hardware. A recurring limitation is the treatment of soft constraints. In quantum annealing, their high connectivity leads to error accumulation. On gate-based hardware, they increase circuit depth and sensitivity to noise. At the same time, temporary constraint violations can provide useful freedom during optimization. Further progress will therefore require improved formulations, algorithms and hardware that reduce the cost of enforcing physical solutions while retaining this flexibility.

•Jan 1, 2026•0 citations

A Constraint Programming Approach for QUBO Solving and Quantum Annealing

Philippe Codognet

Quantum Annealing is an alternative type of computation in which problems are encoded in quantum Hamiltonians (energy functions) and quantum dynamics is used to find solutions (ground states of minimal energy). Quantum computers such as the D-Wave systems are indeed implementing those ideas in hardware, as well as "quantum-inspired" devices based on classical electronics such as Fujitsu’s Digital Annealing Unit. All those systems use the same modeling language: Quadratic Unconstrained Binary Optimization (QUBO). However, QUBO is a low-level language and for modeling combinatorial problems such as constraint satisfaction and constrained optimization problems, we need to introduce higher-level abstractions in order to define complex constraints.

International Conference on Art, Science, and Engineering of Programming (<Programming>)•Mar 11, 2024•2 citations

Encoding the At-Most-One Constraint for QUBO and Quantum Annealing: Experiments with the N-Queens problem

Philippe Codognet

We present experiments in solving constrained optimization and constraint satisfaction problems by means of Quantum Annealing in terms of QUBO (Quadratic Unconstrained Binary Optimization). We investigate different QUBO formulations for the encoding of integers into Booleans and for the encoding of the At-Most-One constraint, which is used in combinatorial problems requiring capacity constraints. We compare four different QUBO models and report experiments done on the D-Wave annealing computer and the "quantum-inspired" Fixstars Amplify Annealing Engine. For this, we consider a simple example taken from the domain of Constraint Satisfaction Problems (CSP), the N-queens problem, as its formulation involves multiple instances of the At-Most-One constraints.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•11 citations
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.
This chapter presents a general construction of the free energy function for the two-dimensional lattice heteropolymer model widely used to study the dynamics of proteins. It demonstrates how to map the lattice heteropolymer problem into forms that can be solved by using different types of technology and algorithms. The embedding strategies presented here apply to many discrete optimization problems. Mapping these problems to a constraint programming problem is a three-step process. The chapter provides a brief description of the process and expands upon each step as it applies to lattice folding. It explains the “circuit” construction that provides optimal efficiency at the cost of introducing high-ordered many-body terms. Finally, the chapter demonstrates the final steps required to embed a small instance of a particular lattice protein problem into a quadratic unconstrained binary optimization (QUBO) Hamiltonian.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
Efficient sampling from ensembles of Hamiltonian cycles is critical for predicting the thermodynamic properties of compact polymers, with applications including modeling protein and RNA folding and designing soft materials. Although classical Monte Carlo methods are widely regarded as the standard approach, their efficiency is strongly limited when applied to compact polymers. In this work, we enable a quadratic speedup in the estimation of thermodynamic properties of maximally compact polymers and heteropolymers by quantum computation. To this end, we encode the target thermodynamic ensemble into the amplitudes of a quantum state, i.e., a quantum sample, which can be processed via amplitude amplification. Using quantum equational reasoning, we construct a local parent Hamiltonian whose unique ground state realizes a quantum sample of all Hamiltonian cycles. This state can be prepared on quantum hardware using ground-state preparation methods, such as quantum annealing, and subsequently manipulated to generate quantum samples of polymers and heteropolymers at a target temperature. Finally, we approximate the quantum sample as a tensor network, revealing an entanglement area law. For fixed-width rectangular lattices, we obtain a time-efficient and compact encoding of the full ensemble of Hamiltonian cycles, enabling the efficient evaluation of expectation values, partition functions, and configuration probabilities via tensor contractions, without resorting to sampling.
Quantum computing has progressed from a theoretical concept to a practical experimental technology. By processing information according to quantum mechanics rather than classical rules, quantum computers may offer advantages for certain problems. Although a few algorithms have proven speedups, it remains unclear where quantum computers will be practically useful, especially since current devices are noisy, small, and not yet fault tolerant. This thesis explores quantum computing for biophysically motivated combinatorial problems, with a focus on lattice protein models. In these simplified models, a protein is represented as a chain on a discrete lattice. Despite their simplicity, lattice proteins retain important features of real proteins, such as such as the folding of a chain with exponentially many possible shapes to a unique minimum-energy structure and steric constraints.To run lattice protein problems on quantum hardware, they must first be formulated using binary variables and objective functions. The latter typically contain soft constraints needed to ensure physical solutions. In Papers~\I--\II, we developed and extended a coordinate-based mapping for lattice protein folding, enabling D-Wave's hybrid quantum-classical annealer to fold both 222D hydrophobic-polar and 333D Miyazawa-Jernigan lattice proteins. In Paper~\III, we adapted the approach to the gate-based paradigm and showed how quadratic soft constraints could be removed by a mixer developed for the maximum-independent-set problem. Papers~\IV--\V addressed lattice protein design using quantum annealing, quantum approximate optimization algorithm, quantum alternating operator ansatz and hardware-efficient ansatz, while Paper~\VI extended the framework to multi-chain thermodynamics and the reconstruction of densities of states and heat-capacity features.Together, these papers show how folding, design, and multi-chain thermodynamics can be formulated, implemented, and analyzed using present-day quantum and hybrid hardware. A recurring limitation is the treatment of soft constraints. In quantum annealing, their high connectivity leads to error accumulation. On gate-based hardware, they increase circuit depth and sensitivity to noise. At the same time, temporary constraint violations can provide useful freedom during optimization. Further progress will therefore require improved formulations, algorithms and hardware that reduce the cost of enforcing physical solutions while retaining this flexibility.
Quantum Annealing is an alternative type of computation in which problems are encoded in quantum Hamiltonians (energy functions) and quantum dynamics is used to find solutions (ground states of minimal energy). Quantum computers such as the D-Wave systems are indeed implementing those ideas in hardware, as well as "quantum-inspired" devices based on classical electronics such as Fujitsu’s Digital Annealing Unit. All those systems use the same modeling language: Quadratic Unconstrained Binary Optimization (QUBO). However, QUBO is a low-level language and for modeling combinatorial problems such as constraint satisfaction and constrained optimization problems, we need to introduce higher-level abstractions in order to define complex constraints.
We present experiments in solving constrained optimization and constraint satisfaction problems by means of Quantum Annealing in terms of QUBO (Quadratic Unconstrained Binary Optimization). We investigate different QUBO formulations for the encoding of integers into Booleans and for the encoding of the At-Most-One constraint, which is used in combinatorial problems requiring capacity constraints. We compare four different QUBO models and report experiments done on the D-Wave annealing computer and the "quantum-inspired" Fixstars Amplify Annealing Engine. For this, we consider a simple example taken from the domain of Constraint Satisfaction Problems (CSP), the N-queens problem, as its formulation involves multiple instances of the At-Most-One constraints.