Construction of model Hamiltonians for adiabatic quantum computation and its application to finding low-energy conformations of lattice protein models

In this paper we explore the use of a quantum optimization algorithm for obtaining low-energy conformations of protein models. We discuss mappings between protein models and optimization variables, which are in turn mapped to a system of coupled quantum bits. General strategies are given for constructing Hamiltonians to be used to solve optimization problems of physical, chemical, or biological interest via quantum computation by adiabatic evolution. As an example, we implement the Hamiltonian corresponding to the hydrophobic-polar model for protein folding. Furthermore, we present an approach to reduce the resulting Hamiltonian to two-body terms gearing toward an experimental realization.

Figure 1

(Color online) The lattice protein hydrophobic-polar (HP) model, showing the global energy minimum conformation for a sequence of 24 amino acids, HHPHPPPHHHHPPHHHHPPPHPHH $\left(E=-12\right)$. Dark gray (blue) beads represent hydrophobic residues (H) and light gray (orange) beads represent polar residues (P). The model consists of a self-avoiding chain with favorable $\left(E=-1\right)$ energetic interactions among hydrophobic residues in contact. Contact between nearest neighbors in the primary sequence are unavoidable, and their contribution is not added to the calculated energy. Black dots represent lattice sites. Dotted lines represent favorable energetic interactions, solid lines represent the self-avoiding chain.

Figure 2

(Color online) Grid-labeling conventions for a sequence of 4 amino acids, HPPH. (a) Amino acids 2 and 3 are fixed in the center of the grid to eliminate translational degeneracy. (b) One of the possible invalid configurations that might arise in the search and that would need to be discarded by the optimization algorithm. (c) Lowest-energy conformation for this example. The dotted line between amino acids 1 and 4 represents the hydrophobic interaction favored by the HP model. The configurations to optimize assume the form $q=q_{16}{q}_{15}{q}_{14}{q}_{13}01100101q_4{q}_3{q}_2{q}_1$, where the set of variables $q_{16}{q}_{15}{q}_{14}{q}_{13}$ and $q_4{q}_3{q}_2{q}_1$ determine the position of amino acids 4 and 1, respectively. For the particular case in (b), $q=1100011001011011$.

Figure 3

(Color online) Illustrative example of one of the uses of the XNOR Boolean function in our scheme for the construction of Hamiltonians. Consider two particles 1 and 2 that are restricted to occupy either position 0 or 1 in the dimension shown, and let $x_1$ and $x_2$ encode the position particle 1 and particle 2, respectively. The Boolean function $f_{\text{EQ}}$ can be interpreted as an onsite repulsion Hamiltonian which penalizes configurations where $x_1=x_2$. The possible configurations are encoded in the bit string $x=x_1{x}_2$.

Figure 4

Half-adder and full-adder components for the addition circuit implemented in the pairwise interaction Hamiltonian. We show the implementation of these two components for the addition of two 4-bit numbers yielding $z=z_5{z}_4{z}_3{z}_2{z}_1$. The addition of $n$-bit numbers can be generalized trivially.

Figure 5

(Color online) Spectrum of the instantaneous energy eigenvalues for the 8-local time-dependent Hamiltonian used in the algorithm for the peptide HPPH (left-hand side). The plot to the right examines the lowest 15 states of the 256 states from the left.

Figure 6

(Color online) Snapshots of the instantaneous ground state for $H\left(t\right)$. The brightness of the box is proportional to ${\left|c_n\right|}^2$. Axis labels and state vectors for each particular box correspond to $|\psi ⟩={\sum }_{n=0}^{255}{c}_n|n⟩$ with $|n⟩$ the $n\text{th}$ state vector out of the 256 possibilities given by $|q_{16}⟩|q_{15}⟩|q_{14}⟩|q_{13}⟩|q_4⟩|q_3⟩|q_2⟩|q_1⟩$. Notice that the $x$ axis is given by $|q_4⟩|q_3⟩|q_2⟩|q_1⟩$ and the $y$ axis given by $|q_{16}⟩|q_{15}⟩|q_{14}⟩|q_{13}⟩$. The final state corresponds to the two degenerate minima shown at the end

Figure 7

(Color online) Spectrum comparison of the instantaneous energy eigenvalues for the 4-local toy Hamiltonian ${\widehat{H}}_{\text{toy}}$ (left-hand side) and its corresponding 2-local version ${\widehat{H}}_{\text{toy,reduced}}$ (right-hand side). (Left-hand side) Full spectrum of the $2^4$ instantaneous eigenvalues for ${\widehat{H}}_{\text{toy}}\left({\tilde{q}}_{,}{\tilde{q}}_2,{\tilde{q}}_3,{\tilde{q}}_4\right)$. (Right-hand side) First 19 instantaneous eigenvalues for the 2-local version of ${\widehat{H}}_{\text{toy}}$, denoted as ${\widehat{H}}_{\text{toy,reduced}}$ in the text. The value used for $\delta$ is 5. The first $2^4$ levels, $0\le$ eigenvalues $\le 4$, are associated to the original levels from ${\widehat{H}}_{\text{toy}}$. The three remaining states with eigenvalues greater than 4 are penalized states which violate the conditions ${\tilde{q}}_n={\tilde{q}}_i\wedge {\tilde{q}}_j$ (see Table for details).