⚛️ quantum physics

Quantum Approximate Optimisation Algorithm for Protein Sidechain Packing

This paper presents a hybrid quantum-classical pipeline utilizing the Quantum Approximate Optimisation Algorithm (QAOA) with a constraint-preserving ansatz to efficiently solve the NP-hard protein sidechain packing problem on AlphaFold2 backbones, demonstrating improved conformational energy and scalable performance compared to classical exhaustive search.

Original authors: Sebastian O. M. Stewart, Nick Chancellor, Jonte R Hance, Ittoop Vergheese Puthoor

Published 2026-09-28

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Sebastian O. M. Stewart, Nick Chancellor, Jonte R Hance, Ittoop Vergheese Puthoor

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Proteins are the workhorses of life, tiny molecular machines that drive the chemical processes keeping us alive. To function, a protein must fold into a specific, stable three-dimensional shape, much like a long, flexible chain twisting into a precise knot. Scientists have become very good at predicting the main backbone of this chain, the central spine that holds the structure together. However, the final, crucial step involves arranging the smaller chemical branches, known as sidechains, that sprout from this backbone. These branches determine how the protein interacts with other molecules, such as drugs trying to bind to it. If these sidechains are placed even slightly incorrectly, the protein's function can fail, or a drug might miss its target entirely. While modern computer programs can predict the main shape with high reliability, they often struggle to position these side branches with the same accuracy, leaving a gap in our ability to design effective medicines.

Researchers at Newcastle University have developed a new method to bridge this gap, using a hybrid approach that combines classical computers with quantum computing techniques. Their goal was to take a protein structure predicted by a powerful tool called AlphaFold and refine the positions of its sidechains to find the most stable, low-energy arrangement. In the world of protein folding, finding this perfect arrangement is a notoriously difficult puzzle. The number of possible ways to arrange the side branches grows so rapidly that checking every single possibility becomes impossible for even the fastest supercomputers once the protein gets large enough. This is known as an NP-hard problem, a classification for tasks where the difficulty explodes as the size of the problem increases.

To tackle this, the team built a pipeline that first uses standard software to prepare the protein data, selecting a manageable set of possible shapes for each sidechain. They then handed this refined problem to a quantum algorithm known as the Quantum Approximate Optimisation Algorithm, or QAOA. This algorithm is designed to search through vast possibilities to find the best solution. A major hurdle in using quantum computers for this task is that they naturally explore all combinations, including many that are physically impossible, such as a single sidechain being in two places at once. The researchers solved this by designing a special starting point and a specific set of rules for how the quantum system evolves. They began with a state where every possible position was equally likely, and then used a circular mixing process that shuffled these possibilities without ever allowing the system to leave the realm of valid, single-position arrangements. This clever setup removed the need for complex penalty terms that usually slow down the calculation, allowing the system to focus entirely on finding the lowest energy state.

The team tested their method on a specific protein called bovine pancreatic trypsin inhibitor, using both high-confidence and moderate-confidence regions of the AlphaFold prediction. In the areas where the original prediction was already very strong, the quantum method mostly matched the existing result, occasionally finding slightly better arrangements. However, in regions where the original prediction was less certain, the new method showed significant promise. In these moderate-confidence zones, the quantum approach found arrangements that were substantially more stable, with energy improvements averaging over eight kilocalories per mole and reaching peaks of more than sixteen kilocalories per mole. These results suggest that the method is particularly effective at correcting errors in areas where the initial prediction was weaker.

Crucially, the researchers did not just claim these improvements; they developed a way to measure how many attempts, or "shots," a quantum computer would need to reliably find the best answer as the problem size grew. They found that while the number of required attempts does increase, it grows at a rate that remains manageable for high-performance computing, staying well below the exponential explosion seen in classical methods for certain types of proteins. The study confirms that this hybrid pipeline can successfully repack sidechains to lower the energy of a protein structure, offering a potential tool to improve the accuracy of drug discovery. The work remains a simulation, running on powerful graphics processors rather than physical quantum hardware, but it demonstrates that the mathematical framework is sound and ready for future testing on real quantum devices. By decoupling the optimization process from the initial prediction quality, the method provides a reliable way to search for the best possible structure within a given set of options, regardless of how good the starting point was.

Technical Summary: Quantum Approximate Optimisation Algorithm for Protein Sidechain Packing

Problem Statement
Protein sidechain packing is a critical sub-problem in protein folding, determining the three-dimensional arrangement of amino acid sidechains (rotamers) relative to a fixed backbone. This process is essential for structure-based drug discovery, as binding sites are defined by these sidechain conformations. While tools like AlphaFold2 reliably predict protein backbones, their sidechain positioning can deviate from experimental data by up to 20%. Recovering the lowest-energy rotamer assignment for a fixed backbone is an NP-hard combinatorial optimization problem. Classical heuristics, such as Rosetta's stochastic Monte Carlo search, do not guarantee global optimality. This paper proposes a hybrid quantum-classical pipeline to address this by reformulating sidechain energy minimization as a Quadratic Unconstrained Binary Optimization (QUBO) problem solvable via the Quantum Approximate Optimization Algorithm (QAOA).

Methodology
The proposed pipeline operates in three stages: preprocessing, QAOA optimization, and post-processing.

Preprocessing and Fixed-Backbone Reduction:
Using PyRosetta, the pipeline analyzes a protein subsection (e.g., Bovine Pancreatic Trypsin Inhibitor, 5PTI) to fix the backbone coordinates derived from AlphaFold2. It generates a discrete library of valid rotamers based on Dunbrack libraries. To manage computational complexity, the rotamer set is pruned via round-robin selection based on one-body energies, capping the number of candidates ( $R$ ) per residue. This reduces the task to selecting exactly one rotamer per residue from the pruned set to minimize total conformational energy.
QUBO Formulation:
The pairwise energy function (comprising one-body and two-body interaction terms) is encoded into a cost Hamiltonian ( $H_C$ ) using Pauli-Z operators. A one-hot encoding scheme is employed, allocating one qubit per valid rotamer. This results in a linear growth of qubit count ( $MN$ for $M$ residues and $N$ average rotamers) but a quadratic scaling of the cost Hamiltonian terms in the worst case, though practical sparsity reduces this to $O(MN \cdot d)$ .
Constraint-Preserving Ansatz:
To enforce the "one-hot" constraint (exactly one rotamer selected per residue) without relying on penalty terms in the cost function, the authors introduce a specific ansatz:
- Initial State: The system is initialized in a W-state, an equal superposition of all single-excitation basis states for each residue sub-register. This ensures the system starts within the valid Hamming-weight-1 subspace.
- Mixer Hamiltonian: Instead of a fully connected graph mixer (which scales as $O(MN^2)$ in two-qubit gates), a cyclic XY ring mixer is used. This restricts interactions to adjacent rotamers in a closed loop. This topology preserves the Hamming weight (ensuring validity is maintained throughout evolution) and reduces the two-qubit gate scaling to $O(MN)$ .
- Optimization Strategy: A warm-starting approach is utilized, where parameters for deeper circuits ( $p$ ) are initialized using the optimized parameters from shallower circuits, with new layers zero-padded and perturbed with Gaussian noise to escape saddle points.
Evaluation Metrics:
- $\Delta E$ : The energy difference between the QAOA result and the AlphaFold baseline ( $E_{QAOA} - E_{AF}$ ). Results are classified as Wins ( $\Delta E < -1.5$ kcal/mol), Ties ( $|\Delta E| \le 1.5$ kcal/mol), or Losses ( $\Delta E > 1.5$ kcal/mol).
- $S(N)$ (Asymptotic Shot-Scaling Metric): A metric defined to estimate the number of shots required to recover the Global Minimum-Energy Conformation (GMEC) with 99.99% probability. This is calculated against an experimentally resolved ground truth (exhaustively searched for small subsystems) to decouple optimizer quality from the quality of the AlphaFold baseline.

Key Results
The pipeline was evaluated on the 5PTI protein using classical state-vector simulations on GPUs.

High-Confidence Regions (pLDDT > 90): In regions where AlphaFold's backbone and sidechain predictions are highly reliable, the QAOA pipeline showed limited improvement over the baseline. Wins occurred in 15.6% of runs for 5–14 qubits, concentrated in specific residue windows (e.g., 60–63). As qubit counts increased to 18 and 22, the win rate dropped to zero, with results predominantly becoming ties. The authors attribute this to the "discretisation penalty": forcing already near-optimal continuous AlphaFold conformations into a finite discrete library often results in higher energy states, not because the quantum solver failed, but because the discrete search space is more restrictive than the continuous baseline.
Moderate-Confidence Regions (pLDDT $\approx$ 80): In regions where AlphaFold's sidechain placement is less reliable, the pipeline achieved significant improvements. Across 1,500 runs (5–14 qubits), 54% were wins, with a mean improvement of -8.114 kcal/mol and a peak of -16.265 kcal/mol. The authors clarify that these gains reflect the weakness of the AlphaFold baseline in these regions rather than an inherent superiority of the quantum solver, as $S(N)$ confirms the optimizer's ability to find the best option within the candidate set regardless of the baseline.
Shot Scaling ( $S(N)$ ): The fitted growth of the required shot count ( $e^{0.31N}$ ) remained below the classical exhaustive-search rate for moderate rotamer flexibility. The metric demonstrated that the required sampling overhead is sensitive to the specific local energy landscape and residue selection, not just the total qubit count.

Significance and Claims
The paper claims to present a viable hybrid quantum-classical pipeline that successfully addresses the NP-hard sidechain packing problem. Its primary contributions are:

Constraint-Preserving Ansatz: A novel combination of W-state initialization and a cyclic XY ring mixer that enforces one-hot validity structurally, eliminating the need for penalty terms and reducing two-qubit gate scaling from $O(MN^2)$ to $O(MN)$ .
Baseline-Independent Evaluation: The introduction of the $S(N)$ metric allows for the assessment of QAOA performance against the theoretical optimum (GMEC) independent of the quality of the starting AlphaFold structure. This distinguishes between solver failure and the inherent limitations of discretizing a continuous problem.
Proof of Concept: The work demonstrates that quantum optimization can lower conformational energy compared to AlphaFold baselines, particularly in regions where the classical baseline is weaker.

The authors remain modest regarding broader implications, noting that the observed energy improvements in moderate-confidence regions may be artifacts of the weak baseline rather than a demonstration of quantum advantage in solving the problem itself. They emphasize that downstream validation against binding affinity and structural stability is required to establish the method's utility for drug discovery. Furthermore, the generalizability of the $S(N)$ budget to proteins other than 5PTI and the impact of hardware noise on real quantum devices remain open questions.

More like this