Source-linked AI summary
Resource-Efficient Quantum Algorithm for Protein Folding
Anton Robert, Panagiotis Kl. Barkoutsos, Stefan Woerner, Ivano Tavernelli
TL;DR
The paper addresses how lattice-based interaction models can distinguish protein folds while enforcing valid polymer conformations. It constructs local Hamiltonian terms for tetrahedral-lattice contacts and reports simulations reproducing correct minimal-energy α-helix and β-sheet structures.
Problem
The model must distinguish protein folds using interaction terms while excluding contacts that cannot discriminate among conformations.
Method
The approach constructs a tetrahedral-lattice Hamiltonian with qubit constraints and penalty terms that enforce valid turns and prevent bead overlaps.
Results
Simulations reproduced the correct minimal-energy structures for both β-sheet and α-helix contact maps.
Takeaways & Limitations
The simulations support using contact-map Hamiltonians to stabilize and recover these two secondary-structure motifs.
Abstract
from arXiv · showhide
Predicting the three-dimensional (3D) structure of a protein from its primary sequence of amino acids is known as the protein folding (PF) problem. Due to the central role of proteins' 3D structures in chemistry, biology and medicine applications (e.g., in drug discovery) this subject has been intensively studied for over half a century. Although classical algorithms provide practical solutions, sampling the conformation space of small proteins, they cannot tackle the intrinsic NP-hard complexity of the problem, even reduced to its simplest Hydrophobic-Polar model. While fault-tolerant quantum computers are still beyond reach for state-of-the-art quantum technologies, there is evidence that quantum algorithms can be successfully used on Noisy Intermediate-Scale Quantum (NISQ) computers to accelerate energy optimization in frustrated systems. In this work, we present a model Hamiltonian with $\mathcal{O}(N^4)$ scaling and a corresponding quantum variational algorithm for the folding of a polymer chain with $N$ monomers on a tetrahedral lattice. The model reflects many physico-chemical properties of the protein, reducing the gap between coarse-grained representations and mere lattice models. We use a robust and versatile optimisation scheme, bringing together variational quantum algorithms specifically adapted to classical cost functions and evolutionary strategies (genetic algorithms), to simulate the folding of the 10 amino acid Angiotensin peptide on 22 qubits. The same method is also successfully applied to the study of the folding of a 7 amino acid neuropeptide using 9 qubits on an IBM Q 20-qubit quantum computer. Bringing together recent advances in building gate-based quantum computers with noise-tolerant hybrid quantum-classical algorithms, this work paves the way towards accessible and relevant scientific experiments on real quantum processors.
MATERIALS AND METHODS
The methods use VQE circuits with fixed depth m = 2 and an evolutionary population sized as P = 5mn, while noisy Qiskit simulations vary error rates with shot count.
- Noisy simulation settings: α = 1% applied to 128-shot noisy simulations, whereas α = 0.1% applied to 1024-shot simulations.Both used an all-to-all entangling scheme on Qiskit.
- Quantum circuit construction: VQE circuits were constructed at fixed depth m = 2.This depth was used for all circuits.
- Evolutionary optimization: P = 5mn set the evolutionary-algorithm population size for runs with n qubits.The choice was described as typical according to the literature.
- Evolutionary optimization: The differential-evolution selection strategy was practically identical to “current-to-best/1/bin”.This strategy follows the original formulation.
SUPPORTING INFORMATION FOR “RESOURCE-EFFICIENT QUANTUM ALGORITHM FOR PROTEIN FOLDING” · I. LATTICE MODEL
The lattice model defines backbone beads by their primary-sequence indices and represents each bead’s side chain as a set of constituent beads. Discussions of Hamiltonian locality use the sparser encoding unless additional information is available.
- I. LATTICE MODEL: Backbone beads are indexed i ∈ {1, ..., N} along the polymer’s primary sequence.The notation identifies bead i as the backbone bead at index i.
- I. LATTICE MODEL: Each backbone bead’s side chain is denoted by constituent beads i(1), i(2), ..., i(s).The passage introduces side-chain bead notation for each backbone bead.
- I. LATTICE MODEL: Hamiltonian locality is discussed with respect to the sparser encoding when no additional information is available.The encoding choice is an assumption for locality discussions.
A. Conformation encoding
The conformation is encoded by lattice turns represented either sparsely with four qubits per turn or more densely with two qubits per turn. Turn-axis indicators and distance functions then translate these bit strings into lattice geometry and Euclidean bead separations.
- Sparser Encoding: Sparse encoding assigns four qubits to each turn, with exactly one qubit set to one to represent a tetrahedral-lattice direction.The four qubits are q4i−3, q4i−2, q4i−1, and q4i.
- Denser Encoding: Dense encoding represents each turn with two qubits and requires 2(N −3) qubits for the complete conformation.If main-chain bead 2 has no side chain, one additional qubit can be saved by fixing q6 = 1.
- Turn indicator: The axis-indicator functions fa(i) return one for the axis selected at turn ti, using either the dense two-qubit expressions or the sparse one-qubit mapping.For sparse encoding, f0(i), f1(i), f2(i), and f3(i) equal q4i−3, q4i−2, q4i−1, and q4i, respectively.
- Distances: Distances between main-chain and side-chain beads are computed from turn occurrences, with side-chain contributions added or removed according to bead positions and parity.For side-chain beads i(s) and j(p), the distance between main-chain positions i and j is adjusted by the corresponding side-chain qubits.
- Distances: A bijection on the tetrahedral lattice maps the encoded distance d(i, j) to Euclidean through-space distance rij in lattice bond units.The supplied examples include d(i, j) = 0 ⇒ rij = 0 and d(i, j) = 1 ⇒ rij = 1.
B. Construction of local Hamiltonians
Local Hamiltonians enforce valid turn encodings, prevent unphysical chain growth and backfolding, and impose the correct polymer chirality. These constraints use conserved-qubit initialization or penalty terms with positive coefficients.
- Sparser encoding Hamiltonian: The sparse encoding requires exactly one of four turn qubits to equal one, enforced through valid initialization and number-preserving gates or a large positive λ penalty.This constraint is applied independently to each set of four qubits representing a turn.
- Growth constraint: Growth constraints prevent unphysical geometries by detecting turn pairs aligned along the same axis through the 2-local function T(i, j).T(i, j) returns 1 if and only if turns ti and tj lie along the same axis, a and ¯a.
- Growth constraint: A large positive λback penalizes consecutive turns selecting the same axis, while the resulting sum contains a linear number of 2-local terms.For branching degree s > 1, analogous penalties prevent overlap between consecutive side-chain bonds.
- Chirality constraints: Chirality is imposed because the side-chain insertion position is determined by consecutive main-chain turns, ti−1 and ti.The model encodes the expected side-chain chirality using a truth table over turn values and a parity indicator gi.
- Chirality constraints: The chirality penalty Hch penalizes structures whose actual side-chain chirality differs from the expected value for large positive λchirality.Hch contains a linear number of 3-local terms for the denser encoding and 5-local terms for the sparser encoding.
C. Construction of Hin
The interaction Hamiltonian Hin is constructed by exploiting tetrahedral-lattice properties, excluding sequence-neighbor interactions that cannot distinguish conformations and encoding relevant contacts with interaction qubits. Separate penalty and stabilization terms enforce lattice distances and prevent bead overlaps for first- and second-nearest-neighbor interactions, while higher-order interactions follow the same configuration-enumeration strategy.
- Interaction selection: Hin considers only bead pairs with j > i + 2 because nearest and second-nearest sequence neighbors occur in every conformation and cannot discriminate folds.Beads separated by fewer than 5 bonds also cannot be nearest neighbors on the tetrahedral lattice.
- Interaction encoding: The construction defines N(i) for first-neighbor beads and q(l)_ij quantities that encode lth-nearest-neighbor interactions between bead pairs.These interaction qubits remain independent from the configuration qubit registers.
- First nearest neighbour interactions: H(1): First-nearest-neighbor terms assign stabilization energy when d(i, j) = 1 and apply λ1-weighted distance penalties otherwise.A λ2-weighted penalty additionally suppresses local overlaps involving neighboring polymer beads.
- Second nearest neighbour interactions: H(2): Second-nearest-neighbor interactions require multiple interaction qubits because several configurations can produce a 2-NN contact.The Hamiltonian separates these cases into H(2)[1], H(2)[3, 3], H(2)[3, 5], and H(2)[5, 3].
- Second nearest neighbour interactions: H(2): For second-nearest-neighbor cases, distance checks and λ2, λ3, and λ5 penalties ensure the relevant distances hold and the energy expression remains positive when d(i, j) ≠ 2.Side chains require additional qubits, and interactions with l > 2 are constructed by enumerating configurations that generate each interaction.
II. CONTACT MAP
The contact-map design stabilizes α-helices and anti-parallel β-sheets, with simulations reproducing their correct minimal-energy structures. Helices use contacts parallel to the main diagonal, whereas β-sheets use counter-diagonal contacts.
- Secondary-structure stabilization: Simulations using the contact maps reproduce the correct minimal-energy structures for both β-sheets and α-helices.The maps stabilize two distinct secondary-structure elements: β-sheet on the left and α-helix on the right.
- Contact-map geometry: α-helices are stabilized by a second contact line parallel to the main diagonal, while anti-parallel β-sheets form contacts along the counter-diagonal.The upper-triangle contacts produce an α-helix turn, whereas lower-triangle contacts produce an anti-parallel β-sheet turn.
III. CONVERGENCE OF CVAR VQE FOR NOISY SIMULATION
This section examines noisy CVaR VQE simulation of Angiotensin folding, tracking low-energy conformation probabilities during minimization under finite-shot sampling.
- The Angiotensin folding simulation uses a realistic hardware noise model.
- 1024 shots track the evolution of P0(p) > 0 and maxp P0(p) for several low-energy conformations during minimization, with maxp P0(p) also evaluated at ns = 128.The corresponding conformations are identified in the main text.