199
Part Five · Convergence

Quantum annealing for biological optimization problems

Designing a protein means choosing an amino acid for every position so that the chain folds into the desired shape and binds the desired target. The choices interact: whether a residue fits depends on its neighbours. Written down, that is an optimization over an enormous discrete space, and it can be phrased exactly in the Ising or QUBO form that quantum annealers accept (Chapter 125). Several groups have tried. This chapter builds a tiny design problem and solves it three ways.

On the plate: a six-position design problem.

Design as QUBO

Give each position ii a set of allowed residues aa, and a binary variable xiax_{ia} that is 1 if residue aa is placed at ii. The energy is a sum of single-residue terms Ei(a)E_i(a) (fit to the backbone) and pair terms Eij(a,b)E_{ij}(a,b) (interactions between neighbours), all quadratic in the xx’s; a penalty P(∑axia−1)2P(\sum_a x_{ia} - 1)^2 forces exactly one residue per position. That is a QUBO, mappable to an Ising Hamiltonian for an annealer or to QAOA. With 20 amino acids at nn positions there are 20n20^n sequences; real design also optimizes side-chain rotamers. Vikram Mulligan and colleagues mapped peptide design to an annealer in 2020; Tomáš Babej and colleagues mapped coarse-grained lattice folding to D-Wave hardware in 2018. Established as a formulation.

Solve it

Six positions, three residue types each, random but fixed energies: 36=7293^6 = 729 sequences, 18 binary variables. The plate finds the exact optimum by enumeration, then runs simulated annealing, the classical analogue of quantum annealing, from 50 random starts with 20 sweeps each, and . With 20 sweeps roughly a third of the runs land on the optimum and the rest in nearby local minima; with 200 sweeps most do, and taking the best of the 50 restarts finds it essentially always. That is how practical annealing is used: many cheap restarts. On real design problems with hundreds of positions, classical tools such as Rosetta’s packers, simulated annealing, integer programming and now deep-learning design methods are strong; published annealer studies match but do not beat them. Established for the classical results.

The critique

No demonstrated quantum advantage exists for biological optimization. Annealers face limited connectivity, which forces embeddings that consume many physical qubits per variable; analogue control errors; and small gaps on hard instances (Chapter 125). Classical heuristics are excellent on the structured instances that real design produces, and machine-learning design (RFdiffusion, ProteinMPNN, from David Baker’s group) has transformed the field without any quantum component. Optimization is the least promising of the quantum-biology applications in this part. Speculative

What you now have

Protein design as a QUBO with one-hot encoding and penalty terms, the size of sequence space, exact and simulated-annealing solutions of a small instance, published annealer studies, and why classical and machine-learning design dominate.

· · ·

Three questions to carry with you.

How is “one residue per position” enforced?tap
A quadratic penalty P(Σₐ x_ia − 1)².
Why does connectivity hurt annealers?tap
Dense interactions must be embedded with chains of physical qubits per variable.
What has transformed protein design recently?tap
Deep-learning methods such as RFdiffusion and ProteinMPNN.

And one to work out. With 20 amino acids at 10 positions, what is log⁡10\log_{10} of the number of sequences?

log₁₀ ≈

Sources: V. K. Mulligan et al., bioRxiv 752485 (2020). T. Babej, M. Fingerhuth and C. Ing, arXiv:1811.00713 (2018). T. Albash and D. A. Lidar, Rev. Mod. Phys. 90, 015002 (2018). J. L. Watson et al., Nature 620, 1089 (2023) (RFdiffusion). Checked by the plate: exhaustive enumeration of 729 sequences.

Next · Chapter 200
Quantum machine learning for genomics, imaging, and drug screening

A quantum-assisted model proposed cancer-drug candidates. How much did the quantum part contribute?

Turn the page